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 $ε$ using $\widetilde{O}(n)$ T gates, where the tilde-$O$ notation suppresses polylogarithmic factors in $n$, $d$, and $1/ε$. Conversely, using stabilizer nullity, we prove that any Clifford+T implementation of such a block encoding with error $ε<\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.
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 ε using O(n) T gates, where the tilde-O notation suppresses polylogarithmic factors in n, d, and 1/ε. Conversely, using stabilizer nullity, we prove that any Clifford+T implementation of such a block encoding with error ε<211−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.
We determine the non-Clifford T-gate cost of constructing block encodings of structured fermionic and spin Hamiltonians in a unitary Clifford+T model, when arbitrarily many clean ancillas and unrestricted block-encoding subnormalization are allowed, but without mid-circuit measurements or classical feed-forward. Our main technical tool is an ancilla-compression theorem: any block encoding of an n-qubit operator with a clean ancillas and at most sT gates can be compressed to use at most min{a,n+2s} ancillas, without increasing the absolute error or T-count. For general second-quantized Hamiltonians with bounded one- and two-body coefficients, at operator-norm block-encoding error ε, a volume-covering argument combined with circuit counting gives the worst-case lower bound Ω(n2log(n4/ε)), matching the existing upper bound at fixed precision. For the bond-dependent Kitaev honeycomb family on n spins, we obtain independent lower bounds Ω(n) from stabilizer nullity and Ω(log(1/ε)) from one-qubit state preparation, established using different Hamiltonian instances. Together with an explicit LCU construction, they give the tight worst-case scaling Θ(n+log(1/ε)). As an application, we evaluate the T-count of a Hamiltonian simulation circuit based on quantum singular value transformation, with each block-encoding query compiled separately. When phase synthesis and controlled queries add at most constant-factor overhead, the simulation T-count scales as the query count times the optimal T-count per query.
Quantum state purification is the functionality that, given multiple copies of an unknown state, outputs a state with increased purity. This will be an essential building block for near- and middle-term quantum ecosystems before the availability of full fault tolerance, where one may want to suppress errors not only in expectation values but also in quantum states. We propose an effective state purification gadget with a moderate quantum overhead by projecting M noisy quantum inputs to their symmetric subspace defined by a set of projectors forming a symmetric subgroup with order M. Our method, applied in every short evolution over M redundant copies of noisy states, can suppress both coherent and stochastic errors by a factor of 1/M, respectively. This reduces the circuit implementation cost M times smaller than the state projection to the full symmetric subspace proposed by Barenco et al. more than two decades ago. We also show that our gadget purifies the depolarised inputs with probability p to asymptotically O(p2) with an optimal choice of M when p is small. The sampling cost scales O(p−1) for small p, which is also shown to be asymptotically optimal. Our method provides flexible choices of state purification depending on the hardware restrictions before fully fault-tolerant computation is available.
We study the Clifford+T synthesis of quantum multiplexers U=⨁i=12nUi: an n-qubit control register selects which single-qubit gate Ui∈SU(2) acts on the target qubit. For each block Ui, consider the minimum even T-count needed to approximate it within diamond distance ε without ancillae, and let m be the largest of these costs. For an arbitrary multiplexer U, we construct an approximation of U within the same distance using at most m+O(2n(m+1))T gates. With one control qubit, the cost is m+O(1) and no ancillae are required. We also prove a lower bound that allows the Clifford+T circuit to use any number of clean ancillae initialized to zero and returned exactly to zero. For fixed n and independent Haar-random blocks, the minimum T-count among these circuits lies between (3−δ)log2(1/ε) and (3+δ)log2(1/ε) for every fixed δ>0, except with probability O(εcn,δ) as ε→0. The optimal leading coefficient is therefore the same as for a single Haar-random SU(2) gate. In the lower-bound proof, unitarity forces pairs of off-diagonal blocks describing transitions in opposite directions to satisfy cancellation relations with residuals of order ε2. We combine these relations with the arithmetic of Clifford+T circuits to bound the Haar measure of targets compatible with each pair of off-diagonal blocks. As an application, we obtain ancilla-free approximations of Haar-random SU(4) gates within diamond distance ε, using at most (9+δ)log2(1/ε)T gates for every fixed δ>0, except with probability O(εcδ) with cδ>0.
T-efficient unitary synthesis via block-sparse Hamiltonian simulation
We construct Clifford+T circuits implementing arbitrary n-qubit unitaries with worst-case T-count O(N8/7) at constant operator-norm error, where N=2n, improving the previous exponent 5/4. The construction uses O(N6/7) clean ancillas. The main idea is to reduce the data addressed by each query to the block-encoding circuit for a sparse piece while controlling the additional simulation work needed to combine the pieces. We simulate a Hermitian logarithm of the target by flattening its traceless part with a two-layer random similarity transformation, randomly partitioning the transformed generator into block-sparse Hermitian pieces, and combining their evolutions using qDRIFT. For a target operator-norm error ε∈(0,1/2), let L=log2(N/ε), the qubit count plus the requested bits of accuracy. By successively correcting the approximation error, we obtain a circuit using O(N8/7L3/7+NL)T gates and O(N) clean ancillas whenever L≤N. We also prove that, at constant precision, the exponent 8/7 is optimal within a sequential block-SELECT model.
Abstract Quantum state purification is crucial in quantum communication and computation, aiming to recover a purified state from multiple copies of an unknown noisy state. This work introduces a general state purification framework designed to achieve the highest fidelity with a specified probability and characterize the associated trade-offs. For i.i.d. quantum states under depolarizing noise, our framework can replicate the purification protocol proposed by Barenco et al (1997 SIAM J. Comput. 26 1541–57) and further provide exact formulas for the purification fidelity and probability with explicit trade-offs. We prove the protocols’ optimality for two copies of noisy states with any dimension and confirm its optimality for higher numbers of copies and dimensions through numerical analysis. Our methodological approach paves the way for proving the protocol’s optimality in more general scenarios and leads to optimal protocols for other noise models. Furthermore, we present a systematic implementation method via block encoding and parameterized quantum circuits, providing explicit circuits for purifying three-copy and four-copy states under depolarizing noise. Finally, we estimate the sample complexity and generalize the protocol to a recursive form, demonstrating its practicality for quantum computers with limited memory.
Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T count of sparse QROM, in which only s of the 2n addresses store nonzero data. We prove that the optimal T count is Θ(n+min{s,s(m+log(2n+1/s))}). Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T-count bounds Θ(min{s,slog(2n+1/s)}+slog(1/ε)+log(1/ε)) for s-sparse state preparation and Θ(2ns(n+log(1/εBE))+log(1/εBE)) for block encoding of s-sparse matrices, where ε and εBE are the precision of state preparation and block encoding, respectively.