Number-theoretic Clifford+T synthesis of z-rotations (Ross-Selinger)

What it fills

• Approximate a continuous rotation in a discrete gate set

  Given a target single-qubit unitary — typically a z-rotation by an arbitrary angle — and a precision $\varepsilon$, produce a finite word over a fixed discrete gate set such as Clifford+T whose product is within $\varepsilon$ of the target in a stated metric. The cost is charged in non-Clifford gates.

When it applies

Specific to $z$-rotations over Clifford+T (general $SU(2)$ at higher cost), and ancilla-free. The optimality claim carries a real condition: it requires a factoring oracle, such as a quantum computer. Without one the algorithm is near-optimal only under a mild number-theoretic hypothesis, and its provable efficiency rests on that same hypothesis. Exact synthesis of the resulting ring element is unconditional (Kliuchnikov, Maslov, Mosca).

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

given  a z-rotation and a target approximation error epsilon

# specific to z-rotations over Clifford+T -- general SU(2) at higher cost
# -- and ancilla-free

reduce the approximation of the z-rotation to
    a grid problem over the ring  Z[1/sqrt(2), i]
    plus a relative norm equation
# the record states the reduction, not how either the grid problem or the
# norm equation is solved, and this listing states neither

exactly synthesize the resulting ring element
    # this stage is unconditional (Kliuchnikov, Maslov, Mosca): it needs
    # neither the oracle nor the hypothesis below

return the ancilla-free Clifford+T approximation of the rotation

# T-count  3 log2(1/epsilon) + O(log log(1/epsilon))  in the typical case,
# with expected runtime  O(polylog(1/epsilon)).  the record names no value
# for the O(log log) term and none is supplied here

# the optimality claim carries a real condition: it requires a factoring
# oracle, such as a quantum computer. without one the algorithm is
# near-optimal only under a mild number-theoretic hypothesis, its provable
# efficiency rests on that same hypothesis, and the T-count it finds is
#     m + O(log log(1/epsilon)),  m the T-count of the second-to-optimal
#     solution

# do not build this -- Selinger's earlier algorithm. the record calls
# Ross-Selinger the production method for z-rotations under Clifford+T; the
# earlier form is kept here only for the contrast in its stated counts:
#     T-count  K + 4 log2(1/epsilon),  K approximately 10 for z-rotations,
#     against a proved worst-case lower bound of the same form with K = -9,
#     and  K + 12 log2(1/epsilon)  for an arbitrary SU(2) element

Cost, as the source states it

Ross and Selinger: T-count $3\log2(1/\varepsilon) + O(\log \log(1/\varepsilon))$ in the typical case, with expected runtime $O(\mathrm{polylog}(1/\varepsilon))$; without a factoring oracle it finds T-count $m + O(\log \log(1/\varepsilon))$, where $m$ is the T-count of the second-to-optimal solution. Selinger's earlier algorithm gives T-count $K + 4\log2(1/\varepsilon)$ with $K$ approximately 10 for $z$-rotations, against a proved worst-case lower bound of the same form with $K = -9$, and $K + 12\log2(1/\varepsilon)$ for an arbitrary $SU(2)$ element.

Implementations

• gridsynth, the reference Haskell implementation in the newsynth package

  • Optimal ancilla-free Clifford+T approximation of z-rotations

  Ross and Selinger built this to answer their own paper's question in practice: given a $z$-rotation $R_z(\theta)$ and a target $\varepsilon$, produce the ancilla-free Clifford+T circuit approximating it, and produce it fast enough to be used. Section 10 of the paper is the run: "We implemented Algorithm 7.6 in the programming language Haskell; the implementation is available from [13]." Algorithm 7.6 is the paper's main algorithm, and Section 7.2 names the reduction it rests on "Reduction to a grid problem and a Diophantine equation": enumerate the solutions $u$ of the scaled two-dimensional grid problem in order of increasing least denominator exponent; for each, "attempt to find a prime factorization" of an integer $n$ derived from $\xi = 1 - u^\dagger u \in D[\sqrt{2}]$, skipping that candidate if none is found; solve $t^\dagger t = \xi$ by the algorithm of Theorem 6.2; then "use the exact synthesis algorithm of [10] to find a Clifford+T circuit implementing either $U$ or $U'$" — with $U' = TUT^\dagger$ — "whichever has smaller T-count". That factoring attempt is step 2(b), and it is the step this record's optimality condition hangs on: "The optimality of the algorithm hinges on step 2(b)."

  The first of two sweeps ran on a single core of a 3.4GHz Intel i5-3570 CPU, approximating $R_z(\pi/128)$ at $\varepsilon$ from $10^{-10}$ down to $10^{-2000}$ and reporting for each the T-count of the computed operator, the actual error in the operator norm, and a lower bound on the T-count computed by the method of Remark 8.9. Because the enumeration of grid-problem solutions is deterministic, the algorithm tends to find the same one or two solutions whenever it is re-run on the same parameters, so the runtime column was instead averaged over 50 independent runs at random angles $\theta$ for each $\varepsilon$, and further broken down into average candidates tried per run and time spent per candidate. The second sweep fixed six angles of the form $\theta = 2\tan^{-1}(r)$ — three with $r \in \mathbb{Q}(\sqrt{2})$ and three without — and ran each at $\varepsilon = 10^{-100}$ through $10^{-500}$, to test Conjecture 8.10 on when the worst-case $4\log_2(1/\varepsilon)$ rather than the typical $3\log_2(1/\varepsilon)$ is reached; the paper states no machine for that second sweep, and Table 2 reports T-counts only, no runtimes.

  The inputs are analytic, not a corpus: the single operator $R_z(\pi/128)$ for Table 1; 50 random angles $\theta$ per $\varepsilon$ for the runtime averages, the paper stating no distribution for them; and for Table 2 the six explicit angles $2\tan^{-1}(2+3\sqrt{2})$, $2\tan^{-1}(5/3)$, $2\tan^{-1}((2+7\sqrt{2})/5)$, $2\tan^{-1}(2+3\sqrt{3})$, $2\tan^{-1}(\sqrt{5})$ and $2\tan^{-1}(1+11\sqrt{7})$. The released program takes the angle symbolically — `gridsynth pi/128` — and, in the page's own words, "will then automatically calculate π/128 to the required number of digits"; it also carries a `-t`/`--table` flag documented as "generate the table of results for the article", with `--count` defaulting to 50.

  The Haskell package `newsynth`, whose executable is `gridsynth`, by Peter Selinger and Neil J. Ross, distributed under GNU GPL version 3 or later — "either version 3 of the License, or (at your option) any later version", copyright 2012–2018 — from https://www.mathstat.dal.ca/~selinger/newsynth/ and from Hackage as `cabal install newsynth`. The paper cites version 0.3.0.1 (2015); the project page currently lists 0.3.0.4, released 2018/11/05. The Ross–Selinger algorithm lives in the module `Quantum.Synthesis.GridSynth` and is described there as "the algorithm used by the gridsynth program"; the package also carries `Quantum.Synthesis.CliffordT` for Matsumoto–Amano normal forms, `Quantum.Synthesis.MultiQubitSynthesis` for Giles–Selinger multi-qubit exact synthesis, and modules for cyclotomic and quadratic integer rings, a Diophantine solver and a one- and two-dimensional grid-problem solver. The package's own changelog dates the split: release 0.2 on 2014/03/12 "Added the new \"gridsynth\" algorithm, and removed the old \"newsynth\" algorithm", the old one being Selinger's earlier 2012 method. First public release was inside Quipper 0.4 on 2013/06/19. Precompiled 64-bit binaries are offered for Linux, Windows and macOS.

  On one core of a 3.4GHz Intel i5-3570 (Table 1): at $\varepsilon = 10^{-10}$, T-count 102 against a computed lower bound of $\geqslant 102$, actual error $0.91180 \cdot 10^{-10}$, runtime 0.0190s over 3.0 candidates; at $\varepsilon = 10^{-100}$, T-count 1000 against $\geqslant 998$, 0.3443s; at $\varepsilon = 10^{-1000}$, T-count 9974 against $\geqslant 9966$, 47.9300s; at $\varepsilon = 10^{-2000}$, T-count 19942 against $\geqslant 19934$, 383.1024s. Of that Table 1 lower-bound column the paper writes that the achieved T-count "exceeds this lower bound by at most a very small amount, which is consistent with $O(\log(\log(1/\varepsilon)))$ as predicted by Proposition 8.8(b)", and that the excess "will become zero in the presence of a factoring oracle". The headline is stated as "we were able to achieve approximations up to $\varepsilon = 10^{-1000}$ with a T-count of under 10000 in less than 50 seconds on average", and set against its predecessor on the same machine: "This compares to a T-count of 13300 and an average runtime of 504.8 seconds reported in [14] on the same hardware", [14] being Selinger's 2012 algorithm. The measured runtimes "appear to be $O(\log^3(1/\varepsilon))$". Table 2, which has no lower-bound column, separates the two regimes instead: at $\varepsilon = 10^{-500}$ the T-counts were 6636, 6636 and 6630 for the three angles with $r \in \mathbb{Q}(\sqrt{2})$, against $4\log_2(1/\varepsilon) = 6644$, and 4990, 4990 and 4990 for the other three, against $3\log_2(1/\varepsilon) = 4983$; the paper reads these as "close to" the two reference values, "[a]s predicted by Conjecture 8.10".

• SQCT, the Single Qubit Circuit Toolkit

  • Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates

  This is the exact-synthesis stage the Ross–Selinger pipeline hands its ring element to — the step the record calls unconditional. Ross and Selinger call it by name in Algorithm 7.6 step 3, "use the exact synthesis algorithm of [10]", their reference [10] being this paper. Kliuchnikov, Maslov and Mosca proved that in the single-qubit case the unitaries over $Z[1/\sqrt{2}, i]$ are exactly those computable by Clifford+T circuits, and gave Algorithm 1, which turns such a unitary into a circuit with a proved optimality guarantee: "We formally show H- and T-optimality of the circuits synthesized by Algorithm 1 in Appendix B." Section 6 of the paper is titled Implementation and consists of one sentence naming the artefact.

  Algorithm 1 was implemented and run as the back end of a two-stage pipeline. The front end was not the Ross–Selinger grid method, which did not yet exist: it was the authors' own implementation of the Solovay–Kitaev algorithm, used to find an approximating unitary over the ring, which Algorithm 1 then decomposed exactly. Rotations $R_z(\varphi)$ were approximated with 0 to 4 Solovay–Kitaev iterations for the published table and with 5 to 7 iterations for the longer runs. One deliberate engineering choice is recorded: of the four small circuits Algorithm 1 selects from at each step — H, HT, HT$^2$ and HT$^3$ — the last was written in the equivalent cheaper form HZT$^\dagger$, which "significantly reduces the number of Phase gates required to implement a unitary". Separately, the completely bounded trace norm between the exact and approximated controlled-rotation channels was computed by semidefinite programming, since 64-bit machine precision was insufficient, using SDPA-GMP with the GNU Multiple Precision Arithmetic Library and Mathematica to generate the problem files.

  The targets are seven analytically specified rotations, $R_z(\varphi)$ for $\varphi = \pi/16$, $\pi/32$, $\pi/64$, $\pi/128$, $\pi/256$, $\pi/512$ and $\pi/1024$, each at Solovay–Kitaev iteration counts $N_I = 0,\dots,4$ in Table 2. The angle convention is not the one used elsewhere on this record: the Table 2 caption defines $R_z(\varphi) = \mathrm{diag}(e^{-i\varphi}, e^{i\varphi})$, twice the rotation angle of the $R_z(\theta) = e^{-i\theta Z/2} = \mathrm{diag}(e^{-i\theta/2}, e^{i\theta/2})$ that Ross–Selinger and the pygridsynth paper write, so this paper's $R_z(\pi/128)$ is the $R_z(\pi/64)$ of the other two entries. The comparison baseline is Dawson's Solovay–Kitaev code, which the paper gives as "available at http://gitorious.org/quantum-compiler/", run over the $\{H, T\}$ library with maximal sequence length 22 and tile width 0.14. The paper states that it publishes the circuits themselves, not only their counts: "Actual specifications of all circuits reported, as well as those synthesized but not explicitly included in the Table 2, due to space constraints, may be obtained from http://qcirc.iqc.uwaterloo.ca/."

  SQCT — Single Qubit Circuit Toolkit — written in C++ and requiring a C++11 compiler, built with CMake, depending on Boost 1.48 (`program_options`, `chrono`, `timer`, `system`), the GNU Multiple Precision Arithmetic Library (gmp and gmpxx), the GNU MPFR Library, and Christian Schneider's `mpfr::real` for high-precision floating point. The paper gives the address as http://code.google.com/p/sqct/; that URL now redirects to https://github.com/vadym-kl/sqct, which carries both a GPL-3.0 and an LGPL-3.0 licence file. Its README states the provenance directly — "The program code based on results of http://arxiv.org/abs/1206.5236. It also implements the version of Solovay Kitaev algorithm described in http://arxiv.org/abs/quant-ph/0505030" — and its directory layout separates the two stages: `sk` for Solovay–Kitaev, `es` for exact synthesis, plus `theory` for a numerical proof of the paper's result and tests of the exact synthesis algorithm, and `appr` for optimal round-off of unitaries.

  These are figures for the whole two-stage pipeline, not for Algorithm 1 alone: the gate counts below are set by the Solovay–Kitaev front end, and the only column measuring the exact-synthesis stage this entry documents is $t_{decomp}$. Runs used a single core of an Intel Core i7-2600 (3.40GHz), with 2.1GB of RAM required during the unitary approximation stage. In Table 2, $R_z(\pi/128)$ — in this paper's doubled-angle convention, so a $\pi/64$ rotation elsewhere on this record — at $N_I = 4$ gave 34388 total gates: 13722 T and T$^\dagger$, 13722 Hadamard, 2 Phase, 6942 Pauli, at trace distance $1.32046 \times 10^{-14}$, with 2.86740s spent on the Solovay–Kitaev approximation and 0.11832s on the exact decomposition; $R_z(\pi/1024)$ at $N_I = 4$ gave 32983 gates, 13188 of them T, at $5.54995 \times 10^{-16}$. The paper's own reading of the split is that "the implementation of our synthesis Algorithm 1 (runtimes found in the column $t_{decomp}$) is significantly faster than the implementation of the Solovay-Kitaev algorithm used to approximate the unitary". Over the full set: "The total runtime to approximate and decompose unitaries ranged from approximately 11 to 600 seconds, correspondingly, featuring best approximating errors on the order of $10^{-50}$, and circuits with up to millions of gates." Against Dawson's code, arbitrary-precision arithmetic "allowed us to achieve precision up to $10^{-50}$ while Dawson's code encounters convergence problem when precision reaches $10^{-8}$", the latter using around 6GB of memory; resynthesizing Dawson's $\{H,T\}$ output with Algorithm 1 cut gate counts "by about 10-20%" "[i]n most cases", and in $\{H, T, P, Z\}$, where Dawson's code could be run "with the sequences of length 9 only", by "about 40-60%".

• pygridsynth, a native Python reimplementation

  • pygridsynth: A fast numerical tool for ancilla-free Clifford+T synthesis

  A second implementation of the same algorithm, built because the reference one is Haskell and the surrounding tooling is not: "A Python-native implementation is particularly valuable in this regard, as it enables seamless integration with the existing ecosystem of quantum programming frameworks and facilitates rapid prototyping, benchmarking, and deployment within standard scientific workflows." Its provenance is stated in the paper — "The implementation used in this work is based on the reference implementation by Selinger and Ross [26]", reference [26] being the newsynth page — and acknowledged from the other side: Selinger's own newsynth page lists it under Related work as "PyGridsynth, by Shuntaro Yamamoto and Nobuyuki Yoshioka. A native Python implementation of the Gridsynth algorithm. (Added December 25, 2024)."

  The Ross–Selinger algorithm is reimplemented as the single-qubit $z$-rotation kernel, with the exact-synthesis step rewriting the resulting $D[\omega]$ unitary into a Clifford+T word "with no additional approximation error beyond global-phase bookkeeping". Around that kernel the library adds layers the original does not have: single-qubit unitaries via Euler decomposition plus magnitude approximation; two-qubit unitaries via a three-CNOT template whose residual rotations are absorbed into the surrounding blocks; and $n \geqslant 3$ via recursive block ZXZ decomposition with a partial-decomposition strategy that leaves diagonal phase matrices undecomposed so they can be absorbed downstream, cutting the constant factor in the T-count. A separate mixed-synthesis workflow approximates a target channel by a probabilistic mixture of Clifford+T circuits, choosing the mixing weights by a linear program over the Pauli transfer matrix rather than the semidefinite program the construction would otherwise need. All arithmetic runs through `mpmath` at arbitrary precision, "handling error tolerances as small as $\varepsilon = 10^{-100}$ while maintaining numerical stability".

  The paper states no provenance for the targets of the unitary-synthesis benchmark: Section 6.1 says only that the synthesis error tolerance $\varepsilon$ was swept, and the Figure 6 caption that "each point corresponds to one synthesis run at a chosen tolerance $\varepsilon$". For the mixed-synthesis runs the inputs are generated inside the library: for an $n$-qubit target, $M = 2 \cdot 4^n$ perturbations $U_i = \hat{U}\exp(i\varepsilon H_i)$ built from randomly generated Hermitian operators — sampled uniformly from the unit sphere and then "relaxed using a repulsive force algorithm to ensure better distribution" (Appendix A) — with the unitary-synthesis tolerance set to $\varepsilon/10$ for numerical stability, and the perturbations "redraw[n] independently" as $\varepsilon$ is swept.

  `pygridsynth`, Python, MIT licence, by Shuntaro Yamamoto and Nobuyuki Yoshioka, at https://github.com/quantum-programming/pygridsynth and on PyPI at https://pypi.org/project/pygridsynth/ (`pip install pygridsynth`). It installs both a command-line executable, invoked as `pygridsynth <theta> <epsilon>`, and a library entry point `pygridsynth.gridsynth.gridsynth_gates(theta, epsilon)`; `mpmath` supplies the arbitrary-precision arithmetic.

  The paper benchmarks the library, not the Ross–Selinger $z$-rotation kernel in isolation: it carries no rotation-only sweep, and the kernel's contribution appears only inside the analytic T-count accounting below. Section 6.1 sweeps error tolerance and records, per run, the diamond-norm distance between target and synthesized channel and the total T-count. At $n = 1$ the curve is consistent with $7\log_2(1/\varepsilon)$, which the paper decomposes as magnitude approximation contributing $\log_2(1/\varepsilon)$ T gates and the two GridSynth $z$-rotations contributing $3\log_2(1/\varepsilon)$ each; at $n = 2$ the data align with $33\log_2(1/\varepsilon)$; at $n = 3$ and $n = 4$ they match the analytic bound $(21/8 \cdot 4^n - 9/2 \cdot 2^n + 9)\log_2(1/\varepsilon)$. Table 2 gives mean wall time for one full unitary-synthesis call as 0.061, 0.308, 1.574 and 7.991 seconds for $n = 1,2,3,4$ at $\varepsilon = 10^{-3}$, and 0.0873, 0.47, 2.283 and 11.322 seconds at $\varepsilon = 10^{-6}$; the paper names no processor or machine for these timings. For mixed synthesis the measured post-mix error tracks the quadratic law of Lemma 1; the further factor of order $1/(2n)$ that separates the curves for different $n$ is empirical only — the paper says it "can be empirically understood as mixture error picking up an additional factor of order $1/(2n)$" and that "[w]e leave the mathematical proof for such an improvement as a future work", its abstract likewise reading "we empirically find that the synthesis error is reduced from $\epsilon$ to $\epsilon^2/(2n)$".

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Solovay-Kitaev algorithm

  Recursively refine an approximation using group commutators, for any finite inverse-closed set that densely generates the group. It is the general-purpose fallback: it works on gate sets with no exploitable algebraic structure.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Optimal ancilla-free Clifford+T approximation of z-rotations↗Neil J. Ross, Peter Selinger · 2014theory yes · simulation ? · hardware no
• Efficient Clifford+T approximation of single-qubit operators↗Peter Selinger · 2012theory yes · simulation ? · hardware no
• Fast and efficient exact synthesis of single qubit unitaries generated by Clifford and T gates↗Vadym Kliuchnikov, Dmitri Maslov, Michele Mosca · 2012theory yes · simulation ? · hardware no