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 epsilon. 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/epsilon))), 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 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.
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.