We present an approach to unitary synthesis that implements an arbitrary $n$-qubit unitary operator $U$ by a Clifford+T circuit with T-count $\widetilde{O}(2^n d_F^{\mathcal{C}}(U))$, where $d_F^{\mathcal{C}}(U)$ is the Frobenius norm distance of $U$ to the Clifford group. The T-count is shown to be near-optimal when $d_F^{\mathcal{C}}(U)$ is a constant. Our approach improves the previous best upper bound $\widetilde{O}(2^{4n/3})$ due to Tan (2025) for a large class of unitary operators $U$ as long as $d_F^{\mathcal{C}}(U) \ll 2^{n/3}$.
We present an approach to unitary synthesis that implements an arbitrary n-qubit unitary operator U by a Clifford+T circuit with T-count O(2ndFC(U)), where dFC(U) is the Frobenius norm distance of U to the Clifford group. The T-count is shown to be near-optimal when dFC(U) is a constant. Our approach improves the previous best upper bound O(24n/3) due to Tan (2025) for a large class of unitary operators U as long as dFC(U)≪2n/3.
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.
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.
Synthesizing arbitrary n-qubit unitaries using as few non-Clifford gates as possible is a central problem in fault-tolerant quantum compilation. We present a Clifford+T quantum circuit construction that approximately implements any classically specified unitary to within error ε and achieves a worst-case T-count with leading exponential scaling of 25n/4 whenever log(1/ε)=poly(n). This improves upon the best previous 24n/3 scaling. The key innovation lies in treating the target unitary as a single block-encoded object rather than a long product of simpler operations. A technique of block flattening controls the normalization while preserving an efficient implementation of the block encoding; subsequently, quantum singular value transformation maps its common singular value to one, thereby recovering the target unitary.
Abstract In quantum computing there are quite a few universal gate sets, each having their own characteristics. In this paper we study the Clifford+CS universal fault-tolerant gate set. The CS gate is used is many applications and this gate set is an important alternative to Clifford+T. We introduce a generating set in order to represent any unitary implementable by this gate set and with this we derive a bound on the CS-count of arbitrary multi-qubit unitaries. Analysing the channel representation of the generating set elements, we infer JnCS⊂JnT J n CS ⊂ J n T , where JnCS J n CS and JnT J n T are the set of unitaries exactly implementable by the Clifford+CS and Clifford+T gate sets, respectively. We develop CS-count optimal synthesis algorithms for both approximately and exactly implementable multi-qubit unitaries. With the help of these we derive a CS-count-optimal circuit for Toffoli, implying JnTof=JnCS J n Tof = J n CS , where JnTof J n Tof is the set of unitaries exactly implementable by the Clifford+Toffoli gate set. Such conclusions can have an important impact on resource estimates of quantum algorithms.
We construct n-qubit approximate unitary k-designs in 1D systems, achieving circuit depth O(log(n/ε)+klogk) with relative error ε and requiring O(nklogk) magic gates. This matches existing lower bounds Ω(log(n/ε)+k) for circuit depth, and Ω(nk) for the required number of T gates, up to a logk factor, achieving simultaneous near-optimality in all parameters. Our construction is based on a combination and refinement of two existing results. We reduce the required magic block size for breaking Clifford symmetries in the magic-augmented circuit construction of Zhang et al. from O(klogk) to O(logk). We also improve the breakthrough construction of Chen et al. to construct a generating set of 1D local constant-depth circuits for the unitary group with a constant spectral gap, making O(logk)-local random unitaries realizable in depth O(klogk). As a by-product, we provide a constant-size 1D-local generating set for the Clifford group, which we expect to be of independent interest. Combining the two results with the gluing lemma, we prove the final result.
We propose two Clifford+T synthesis algorithms that are optimal with respect to T-count. The first algorithm, called deterministic synthesis, approximates any single-qubit unitary by a single-qubit Clifford+T circuit with the minimum T-count. The second algorithm, called probabilistic synthesis, approximates any single-qubit unitary by a probabilistic mixture of single-qubit Clifford+T circuits with the minimum T-count. For most of single-qubit unitaries, the runtimes of deterministic synthesis and probabilistic synthesis are ε−1/2−o(1) and ε−1/4−o(1), respectively, for an approximation error ε. Although this complexity is exponential in the input size, we demonstrate that our algorithms run in practical time at ε≈10−15 and ε≈10−22, respectively. Furthermore, we show that, for most single-qubit unitaries, the deterministic synthesis algorithm requires at most 3log2(1/ε)+o(log2(1/ε))T-gates, and the probabilistic synthesis algorithm requires at most 1.5log2(1/ε)+o(log2(1/ε))T-gates. Remarkably, complexity analyses in this work do not rely on any numerical or number-theoretic conjectures.