The nearly optimal scaling of non-Clifford cost with the number of copies is established and the fundamental resource requirements for coherent symmetry projection in quantum state purification are uncovered.
Abstract
Protecting quantum information from noise is essential for reliable quantum computation and quantum memories. Quantum state purification addresses this challenge by processing multiple noisy copies of an unknown quantum state to produce an output state of higher fidelity. Here we establish nearly tight upper and lower bounds on the non-Clifford resources required to implement the symmetric-projection purification protocol. For $n$ copies of a $d$-dimensional system, we construct a Clifford+T circuit that block-encodes the symmetric projector with operator-norm error at most $\epsilon$ using $\widetilde{O}(n)$ T gates, where the tilde-$O$ notation suppresses polylogarithmic factors in $n$, $d$, and $1/\epsilon$. Conversely, using stabilizer nullity, we prove that any Clifford+T implementation of such a block encoding with error $\epsilon<\frac{1}{2}\sqrt{1-1/n}$ requires at least $2n-2$ T gates, even allowing arbitrary positive normalization and clean stabilizer ancillas. Taken together, these results establish the nearly optimal scaling of non-Clifford cost with the number of copies and uncover the fundamental resource requirements for coherent symmetry projection in quantum state purification.
This work presents two quantum algorithms with complementary guarantees on circuit depth and sample complexity and proves a matching sample complexity lower bound of $\Omega(\log(n/\delta))$ for any quantum algorithm with failure probability at most $\delta\le 1/2-c$.
Quantum state preparation is a basic primitive of quantum computation and control, but its resource cost is usually analyzed for one target state or under an independent-copy construction. Here we study the many-copy problem under weighted Pauli control, where a Pauli-product rotation $e^{i\phi P}$ is charged by its ro...
Lin Zhu, Ranyiliu Chen, Xin Wang et al.· 0 citations
Quantum circuit optimization is an indispensable component of the quantum software stack, used to reduce noise, maximize performance, alleviate costs of quantum error correction, or target specific hardware. A related problem is approximate membership: for a fixed set of unitaries $S$, decide whether a given circuit $C...
Adam Husted Kjelstrøm, Jaco van de Pol, Andreas Pavlogiannis· 0 citations
Random quantum circuits aim to efficiently reproduce the statistical properties of ideal random quantum evolution. One approach is to construct approximate unitary designs, which match the moments of Haar-random unitaries up to a prescribed order with controlled error. We establish quantitative guarantees for how accur...
Quantum low-density parity-check (qLDPC) codes can substantially reduce the qubit overhead of fault-tolerant quantum computation, but any useful architecture based on such codes also requires an efficient mechanism to implement non-Clifford gates in a fault-tolerant manner. We introduce a space-time-efficient magic sta...
Varun Menon, Rohan Mehta, An-Di Gu et al.· 2 citations
We study the persistent quantum and classical memory required for exact heralded storage and retrieval of quantum measurements. Given only black-box access to the measurement channel, we construct an exact compression of the port-based program into an outcome-type record and a quantum register, with total dimension pol...
Filip Turobos, Ludmiła Marcinkowska, Z. Puchała· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.