How many T gates are needed to approximate an arbitrary n -qubit quantum state to within error ε ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ ( 2 n log ( 1 / ε ) + log ( 1 / ε ) ) if we allow ancilla qubits. We also show that this is the optimal T -count for implementing an arbitrary diagonal n -qubit unitary to within error ε . We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.
How many T gates are needed to approximate an arbitrary n -qubit quantum state to within error ε ? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ ( 2 n log ( 1 / ε ) + log ( 1 / ε ) ) if we allow ancilla qubits. We also show that this is the optimal T -count for implementing an arbitrary diagonal n -qubit unitary to within error ε . We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.
How many T gates are needed to approximate an arbitrary n-qubit quantum state to within error ε? Improving prior work of Low, Kliuchnikov, and Schaeffer, we show that the optimal asymptotic scaling is Θ(2nlog(1/ε)+log(1/ε)) if we allow ancilla qubits. We also show that this is the optimal T-count for implementing an arbitrary diagonal n-qubit unitary to within error ε. We describe applications in which a tensor product of many single-qubit unitaries can be synthesized in parallel for the price of one.
Efficient synthesis of arbitrary quantum states and unitaries from a universal fault-tolerant gate-set e.g. Clifford+T is a key subroutine in quantum computation. As large quantum algorithms feature many qubits that encode coherent quantum information but remain idle for parts of the computation, these should be used if it minimizes overall gate counts, especially that of the expensive T-gates. We present a quantum algorithm for preparing any dimension- N pure quantum state specified by a list of N classical numbers, that realizes a trade-off between space and T-gates. Our scheme uses O ( log ( N / ϵ ) ) clean qubits and a tunable number of ∼ ( λ log ( log N ϵ ) ) dirty qubits, to reduce the T-gate cost to O ( N λ + λ log N ϵ log log N ϵ ) . This trade-off is optimal up to logarithmic factors, proven through an unconditional gate counting lower bound, and is, in the best case, a quadratic improvement in T-count over prior ancillary-free approaches. We prove similar statements for unitary synthesis by reduction to state preparation. Underlying our constructions is a T-efficient circuit implementation of a quantum oracle for arbitrary classical data.
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.
Abstract The ability to implement the Quantum Fourier Transform (QFT) efficiently on a quantum computer facilitates the advantages offered by a variety of fundamental quantum algorithms, such as those for integer factoring, computing discrete logarithm over Abelian groups, solving systems of linear equations, and phase estimation, to name a few. The standard fault-tolerant implementation of an n-qubit unitary QFT approximates the desired transformation by removing small-angle controlled rotations and synthesizing the remaining ones into Clifford+T gates, incurring the T-count complexity of O(nlog2(n)) O ( n log 2 ( n ) ) . In this paper, we show how to obtain approximate QFT with the T-count of O(nlog(n)) O ( n log ( n ) ) . For brevity, the above figures omit the dependence on the approximation error ε, assuming the error is fixed. Our approach relies on quantum circuits with measurements and feedforward, and on reusing a special quantum state that induces the phase gradient transformation. We report asymptotic analysis as well as concrete circuits, demonstrating significant advantages in both theory and practice.
Approximate synthesis of general single-qubit unitaries over the Clifford+T gate set
For the standard Clifford+T gate set, deterministic, ancilla-free synthesis now attains the minimal T-count for general single-qubit unitaries (Morisaki et al., arXiv:2510.05816). The T gate rotates by half the angle of T, generating a finer lattice of implementable operations. Access to this magic state is expected to lower the cost of deterministic and ancilla-free synthesis of general single-qubit unitaries (Kliuchnikov et al., arXiv:2203.10064), but no direct Clifford+T algorithm existed for this case. We provide one by extending the integer lattice-point enumeration method of Morisaki et al. We adopt a resource state cost model based on the magic-state catalysis approach of Gidney and Fowler (arXiv:1812.01238). On Haar-random targets synthesized to precisions ranging from ε=10−3 to 10−8, the cost of Clifford+T circuits scales as 2.4log2(1/ε) compared to 3.0log2(1/ε) for T-count-optimal Clifford+T circuits. Once a one-time catalyst state is amortized, the Clifford+T circuits are never costlier than their Clifford+T counterparts.
We present a simple algorithm that implements an arbitrary n -qubit unitary operator using a Clifford + T circuit with T-count O ( 2 4 n / 3 n 2 / 3 ) and ancilla-count O ( 2 2 n / 3 n 1 / 3 ) . The previous best T-count for unitary synthesis was O ( 2 3 n / 2 n ) with O ( 2 n / 2 ) ancillae by [Low , ]. There is a fundamental tradeoff between T gates and ancillae, and our algorithm extends the achievable regime of this tradeoff, reducing the exponent in T-count from 3 n / 2 to 4 n / 3 . The best known lower bound remains Ω ( 2 n ) , so the optimal T-count for general unitary synthesis is still open. Our construction is based on a recursive application of the cosine-sine decomposition, together with a generalization of the optimal diagonal unitary synthesis method by [D. Gosset , ] to multi-controlled k -qubit unitaries.