We consider the problem of approximating arbitrary single-qubit z-rotations by ancillafree Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/ε))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of Tcount 3 log2 (1/ε) + O(log(log(1/ε))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/ε)).
We consider the problem of approximating arbitrary single-qubit z-rotations by ancillafree Clifford+T circuits, up to given epsilon. We present a fast new probabilistic algorithm for solving this problem optimally, i.e., for finding the shortest possible circuit whatsoever for the given problem instance. The algorithm requires a factoring oracle (such as a quantum computer). Even in the absence of a factoring oracle, the algorithm is still near-optimal under a mild number-theoretic hypothesis. In this case, the algorithm finds a solution of T-count m + O(log(log(1/ε))), where m is the T-count of the second-to-optimal solution. In the typical case, this yields circuit approximations of Tcount 3 log2 (1/ε) + O(log(log(1/ε))). Our algorithm is efficient in practice, and provably efficient under the above-mentioned number-theoretic hypothesis, in the sense that its expected runtime is O(polylog(1/ε)).
We describe a new efficient algorithm to approximate z-rotations by ancilla-free Clifford+V circuits, up to a given precision ϵ. Our algorithm is optimal in the presence of an oracle for integer factoring: it outputs the shortest Clifford+V circuit solving the given problem instance. In the absence of such an oracle, our algorithm is still near-optimal, producing circuits of V\!-count m+O(log(log(1/ϵ))), where m is the V\!-count of the third-to-optimal solution. A restricted version of the algorithm approximates z-rotations in the Pauli+V gate set. Our method is based on previous work by the author and Selinger on the optimal ancilla-free approximation of z-rotations using Clifford+T gates and on previous work by Bocharov, Gurevich, and Svore on the asymptotically optimal ancilla-free approximation of z-rotations using Clifford+V gates.
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.
We present pygridsynth, an open-source Python library for ancilla-free approximate Clifford+T synthesis that runs in O(log(1/ε)) for precision ε. For n=1,2 qubits, the library builds upon established efficient and high-precision synthesis routines, such as nearly optimal Z-rotation synthesis and magnitude approximation. For n≥3 qubits, we introduce a partial-decomposition technique that generalizes the magnitude approximation, reducing constant factors in the T-count as (821⋅4n−29⋅2n+9)log2(1/ε)+o(log(1/ε)). The package also exposes a mixed-synthesis workflow that approximates target unitary channels by probabilistic mixtures of Clifford+T circuits, for which we empirically find that the synthesis error is reduced from ε to ε2/(2n). Taken together, these features make pygridsynth a Python-native platform for high-precision Clifford+T synthesis and for benchmarking unitary and mixed synthesis strategies on multi-qubit instances.
We give an efficient randomized algorithm for approximating an arbitrary element of $\SU(2)$ by a product of Clifford+T operators, up to any given error threshold ϵ>0. Under a mild hypothesis on the distribution of primes, the algorithm's expected runtime is polynomial in log(1/ϵ). If the operator to be approximated is a z-rotation, the resulting gate sequence has T-count K+4log2(1/ϵ), where K is approximately equal to 10. We also prove a worst-case lower bound of K+4log2(1/ϵ), where K=−9, so that our algorithm is within an additive constant of optimal for certain z-rotations. For an arbitrary member of $\SU(2)$, we achieve approximations with T-count K+12log2(1/ϵ). By contrast, the Solovay-Kitaev algorithm achieves T-count O(logc(1/ϵ)), where c is approximately 3.97.
Building generic gates from a restricted gate set is a difficult but important problem, especially in the noisy regime where only a limited set of noise-resistant gates are available, e.g., fault-tolerant Clifford gates (generated by Hadamard, phase, and gates) and fault-tolerant Toffoli gates. The Toffoli is also often used as a building block of many algorithms and will need to be constructed if not directly available. This makes Clifford + Toffoli an attractive gate set for building generic gates. In this Letter we give a simple and efficient algorithm for building an approximate single-qubit rotation using only Clifford + Toffoli , which in turn enables any generic single-qubit unitary. An important difference compared to earlier attempts is that the use of the Toffoli allows us to use simple rounding as opposed to a complicated approximation algorithm. The resulting gate array does not rely on repeatedly applying a fixed rotation, but immediately applies a rotation R θ * that is ε -close to the desired rotation R θ , with a success probability strictly greater than 1 / 2 . It can be rerun upon failure, giving an expected number of repetitions strictly less than 2, an expected Toffoli count strictly less than 4 ⌈ log 1 ε ⌉ , an expected gate depth strictly less than 4 ⌈ log 1 ε ⌉ + 6 , and uses 2 ⌈ log 1 ε ⌉ ancillas. The small circuit depth of our construction enables low-noise gates on existing quantum computational devices, and allows for arbitrary precision using a very modest number of ancillas. Published by the American Physical Society 2024
Fault-tolerant quantum computing typically requires the transpilation of arbitrary quantum circuits into a finite, universal gate set, such as Clifford+T. As a baseline, Diagonal approximation can be used for synthesizing single-qubit Pauli rotations, yielding an approximating sequence with T-count that equals 3log2(1/ε) for a target precision ε. Magnitude Approximation can reduce the T-count to only 1log2(1/ε) by allowing large residual errors, which are rotations about orthogonal axes. Within a complete quantum circuit, these residual errors can then be absorbed into neighboring gates before they are approximated themselves. Determining the optimal allocation of approximation strategies within a large, multi-qubit circuit presents a significant combinatorial challenge. In this work, we present a linear-time algorithm that guarantees an optimal solution to this problem. We demonstrate that the issue of delegating Magnitude versus Diagonal approximation across a circuit maps formally to a classical 1D Ising model with a spatially varying field. By minimizing the energy of this Hamiltonian, we identify the optimal approximation configuration for each rotation without exponential overhead. Benchmarking our method against standard diagonal approximation on random quantum circuits, we observe an average reduction of 26\% in the total approximating circuit gate count, offering a significant efficiency gain for the implementation of quantum algorithms on near-term and fault-tolerant architectures.