We provide a non-deterministic quantum protocol that approximates the single qubit rotations R x (2 ϕ 2 1 ϕ 2 2 ) using R x (2 ϕ 1 ) and R x (2 ϕ 2 ) and a constant number of Clifford and T operations. We then use this method to construct a 'floating point' implementation of a small rotation wherein we use the aforementioned method to construct the exponent part of the rotation and also to combine it with a mantissa. This causes the cost of the synthesis to depend more strongly on the relative (rather than absolute) precision required. We analyze the mean and variance of the T -count required to use our techniques and provide new lower bounds for the T -count for ancilla free synthesis of small single-qubit axial rotations. We further show that our techniques can use ancillas to beat these lower bounds with high probability. We also discuss the T -depth of our method and see that the vast majority of the cost of the resultant circuits can be shifted to parallel computation paths.
We provide a non-deterministic quantum protocol that approximates the single qubit rotations R x (2 ϕ 2 1 ϕ 2 2 ) using R x (2 ϕ 1 ) and R x (2 ϕ 2 ) and a constant number of Clifford and T operations. We then use this method to construct a 'floating point' implementation of a small rotation wherein we use the aforementioned method to construct the exponent part of the rotation and also to combine it with a mantissa. This causes the cost of the synthesis to depend more strongly on the relative (rather than absolute) precision required. We analyze the mean and variance of the T -count required to use our techniques and provide new lower bounds for the T -count for ancilla free synthesis of small single-qubit axial rotations. We further show that our techniques can use ancillas to beat these lower bounds with high probability. We also discuss the T -depth of our method and see that the vast majority of the cost of the resultant circuits can be shifted to parallel computation paths.
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 develop a method for approximate synthesis of single-qubit rotations of the form e−if(φ1,...,φk)X that is based on the Repeat-Until-Success (RUS) framework for quantum circuit synthesis. We demonstrate how smooth computable functions f can be synthesized from two basic primitives. This synthesis approach constitutes a manifestly quantum form of arithmetic that differs greatly from the approaches commonly used in quantum algorithms. The key advantage of our approach is that it requires far fewer qubits than existing approaches: as a case in point, we show that using as few as 3 ancilla qubits, one can obtain RUS circuits for approximate multiplication and reciprocals. We also analyze the costs of performing multiplication and inversion on a quantum computer using conventional approaches and find that they can require too many qubits to execute on a small quantum computer, unlike our approach.
Quantum circuit synthesis is the process in which an arbitrary unitary operation is decomposed into a sequence of gates from a universal set, typically one which a quantum computer can implement both efficiently and fault-tolerantly. As physical implementations of quantum computers improve, the need is growing for tools that can effectively synthesize components of the circuits and algorithms they will run. Existing algorithms for exact, multi-qubit circuit synthesis scale exponentially in the number of qubits and circuit depth, leaving synthesis intractable for circuits on more than a handful of qubits. Even modest improvements in circuit synthesis procedures may lead to significant advances, pushing forward the boundaries of not only the size of solvable circuit synthesis problems, but also in what can be realized physically as a result of having more efficient circuits. We present a method for quantum circuit synthesis using deterministic walks. Also termed pseudorandom walks, these are walks in which once a starting point is chosen, its path is completely determined. We apply our method to construct a parallel framework for circuit synthesis, and implement one such version performing optimal T -count synthesis over the Clifford+ T gate set. We use our software to present examples where parallelization offers a significant speedup on the runtime, as well as directly confirm that the 4-qubit 1-bit full adder has optimal T -count 7 and T -depth 3.
We address the problem of optimal representation of single-qubit rotations in a certain unitary basis consisting of the so-called V gates and Pauli matrices. The V matrices were proposed by Lubotsky, Philips, and Sarnak [Commun. Pure Appl. Math. 40, 401–420 (1987)] as a purely geometric construct in 1987 and recently found applications in quantum computation. They allow for exceptionally simple quantum circuit synthesis algorithms based on quaternionic factorization. We adapt the deterministic-search technique initially proposed by Ross and Selinger to synthesize approximating Pauli+V circuits of optimal depth for single-qubit axial rotations. Our synthesis procedure based on simple SL2(ℤ) geometry is almost elementary.
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.
Recently it was shown that the resources required to implement unitary operations on a quantum computer can be reduced by using probabilistic quantum circuits called repeat-until-success (RUS) circuits. However, the previously best-known algorithm to synthesize a RUS circuit for a given target unitary requires exponential classical runtime. We present a probabilistically polynomial-time algorithm to synthesize a RUS circuit to approximate any given single-qubit unitary to precision ϵ over the Clifford+T basis. Surprisingly, the T count of the synthesized RUS circuit surpasses the theoretical lower bound of 3 log_{2}(1/ϵ) that holds for purely unitary single-qubit circuit decomposition. By taking advantage of measurement and an ancilla qubit, RUS circuits achieve an expected T count of 1.15 log_{2}(1/ϵ) for single-qubit z rotations. Our method leverages the fact that the set of unitaries implementable by RUS protocols has a higher density in the space of all unitaries compared to the density of purely unitary implementations.