Solovay-Kitaev algorithm

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

Requires the generating set to be finite, inverse-closed and dense, and gives no optimality guarantee. Kuperberg's result improves the algorithm for a general finite, inverse-closed generating set acting on a qudit, and holds more generally for any finite set densely generating a connected semisimple real Lie group; in the noncompact case an extra length term is needed to reach group elements far from the identity.

Requires

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

Example

given  a target unitary U, a finite inverse-closed generating set that
       densely generates the group, and a recursion depth n

function approximate(U, n):
    if n == 0:
        return the nearest element of the precomputed net over the base set
    V = approximate(U, n - 1)
    D = U V^-1                       # what the previous level left to correct
    write D as a group commutator    D = A B A^-1 B^-1
    A' = approximate(A, n - 1)
    B' = approximate(B, n - 1)
    return A' B' A'^-1 B'^-1 V

return approximate(U, n)

# the general-purpose fallback: it works on gate sets with no exploitable
# algebraic structure, and it gives no optimality guarantee

Cost, as the source states it

Dawson and Nielsen: the algorithm runs in $O(\log^2.71(1/\varepsilon))$ classical time and produces a sequence of $O(\log^3.97(1/\varepsilon))$ gates guaranteed to approximate the target to accuracy $\varepsilon$. Kuperberg: word length $O(n^(1.44042+\delta))$ to approximate an arbitrary target to $n$ bits of precision, improving on the prior $O(n^(3+\delta))$.

Implementations

• sk, Dawson's C++ Solovay-Kitaev library

  • The Solovay-Kitaev algorithm

  The paper this method is recorded from is explicitly a teaching document: Dawson and Nielsen "stress that the paper is a review paper, as all the essential ideas appear in previous work", and close by saying the discussion "has been pedagogical, aimed at a formulation that brings out the key ideas, rather than being optimized for accuracy and efficiency". The paper releases nothing and carries no URL; the link to this artefact runs the other way, from the code to the paper, whose README calls itself "a C++ implementation of the Solovay-Kitaev algorithm, a review of which can be found at [quant-ph/0505030]". The code is of the paper's period rather than demonstrably contemporaneous with it: it targets g++ 3.3.5 and MS Visual C++ 7.1, its documentation points at a University of Queensland download under the first author's own page, and its LICENSE reads "Copyright (c) 2005 Chris Dawson" — but that LICENSE was added to the GitHub copy on 2019-08-14, to a repository created on 2017-09-01. The problem it solves is the one the paper poses: given an instruction set $G$ for $SU(2)$ — a finite, inverse-closed, dense set of single-qubit gates — find a sequence drawn from $G$ that approximates an arbitrary $U$ to accuracy $\varepsilon$.

  The library implements the preprocessing stage the paper specifies but does not build, and adds an index to it. The paper states the construction and leaves it there: "we assume that a preprocessing stage has been completed which allows us to find a basic $\varepsilon_0$-approximation to arbitrary $U \in SU(2)$", accomplished "by enumerating and storing a large number of instruction sequences from $G$, say up to some sufficiently large (but fixed) length $l_0$, and then providing a lookup routine which, given $U$, returns the closest sequence". The code's `Net` class does exactly that and adds an index: it divides the $SU(2)$ parameter space into tiles, associates each enumerated sequence with nearby tiles, and answers a lookup for $U$ by searching only the sequences in $U$'s own tile. Nets can be generated once, saved to a file and reloaded. `Net::solovay_kitaev(U, n)` then runs the paper's nine-line recursion to depth $n$, returning a `knot` — the instruction word, its length, and the matrix it evaluates to. The documentation is candid about two weaknesses: $SU(2)$ is parameterised by a 4D unit vector so the tiles are hypercubes in $\mathbb{R}^4$, which the author calls "stupid because the intersection of the unit sphere with these hypercubes varies enormously", making a good tile width hard to choose; and every net point is stored, with no reduction beyond refusing to follow a gate by its inverse or exceed a gate's order, so "the size of the Net's that are generated is enormous".

  There is no benchmark corpus. The inputs are a gate set, supplied by the caller as a label-to-matrix dictionary — "a Python dictionary whose keys are the uppercase characters used to label each gate, and the values being a Scipy matrix for the gate" — and, separately, a single target matrix passed to `solovay_kitaev` as its first argument. Two instruction sets ship in `python/sk/common.py`: `ht_net`, the "Hadamard and PI/8 gate set" the paper works with throughout, and `lps_net`, "The very efficient Lubotsky, Phillips and Sarnak set" — the same LPS construction the paper's Section 6 credits for the non-constructive $O(\log(1/\varepsilon))$ result of Harrow, Recht and Chuang. Inverses need not be listed: "It's not necessary to explicitly include inverses, they will be added for you if necessary. Inverses are labelled with lower case letters." Targets in the shipped examples are drawn at random from $SU(2)$.

  `sk`, C++, MIT licence, "Copyright (c) 2005 Chris Dawson", at https://github.com/cmdawson/sk — `src/Net.cpp`, `src/su2.cpp` and headers, with `src/example.cpp` as the worked example. A Boost.Python wrapper (`python/wrapper.cpp`, `python/PyNet.h`) exposes a Python package `sk` with modules `net`, `utils` and `common`, whose "wrapper functions around the C++ library allow you to use the scipy matrix type". One Makefile ships, and it invokes g++; the README still describes the 2005 distribution as carrying "Two Makefiles ... one for Linux/g++ the other for Windows/VC++", which the GitHub tree does not contain. A Doxygen configuration (`sk.dox`) does ship. The original distribution was `sk-0.1.tar.gz` with a `sk-0.1_w32.zip` Win32 binary from the author's University of Queensland page; the GitHub copy was created in 2017 and the README frames it as "for historical and pedagogical purposes", pointing readers at later work.

  No quantum hardware is involved; the artefact is a classical compiler, and the platforms named are compilers: "The sources have been successfully compiled with g++ 3.3.5 and with MS Visual C++ 7.1." The paper supplies the number that sizes the preprocessing stage, and states it as a measurement: "Numerically we have found that for the single-qubit instruction set consisting of the Hadamard gate, the $\pi/8$ gate, and its inverse, $\varepsilon_0 \approx 0.14$ and $l_0 = 16$ is sufficient for practical purposes" — against the analytic requirement $\varepsilon_0 < 1/32$ that the proof's $c_{approx} \approx 8c_{gc} \approx 4\sqrt{2}$ forces. The library's own documentation puts the same gate set lower, and the two figures do not agree: "A rough number for the HT set is about 14. For the LPS set is it around 6." The paper's criterion is an $\varepsilon_0$; the library's is "getting a decent covering of $SU(2)$". The shipped examples follow the library's figures rather than the paper's — an H/T net at tile width 0.18 to sequence length 14 (C++) and at tile width 0.15 to length 15 (Python) — then call the recursion at depth 5 and depth 3 respectively on a random $SU(2)$ target and print the accuracy achieved: the C++ example via `su2::proj_trace_dist`, the Python one via `utils.proj_dist`, both sign-minimised distances computed on the matrix entries rather than the operator norm in which the paper defines its $\varepsilon$. Neither example's output value is recorded anywhere in the repository. On memory, the author reports the nets are large enough that "on my aged laptop de-allocating the memory actually takes a few seconds".

• Qiskit's SolovayKitaev transpiler pass

  • The Solovay-Kitaev algorithm

  Qiskit needed a way to turn a circuit of continuous single-qubit rotations into one over a discrete, fault-tolerantly implementable gate set. The pass was contributed as Qiskit pull request 5657, "Add the Solovay-Kitaev algorithm to the transpiler passes", whose summary reads "Add the Solovay-Kitaev algorithm from https://arxiv.org/abs/quant-ph/0505030 by C. Dawson and M. Nielsen to the transpiler passes"; it was opened 2021-01-20 by GitHub user LNoorl and merged 2022-12-09, shipping in the 0.23 release. Both layers of the current code name this method's citation as their source: the Python class docstring says "This implementation of the Solovay-Kitaev algorithm is based on [2]", where [2] is Dawson and Nielsen 2005, and the Rust core's doc comment says "The code is based mainly on https://arxiv.org/pdf/quant-ph/0505030".

  `SolovayKitaevDecomposition` builds the basic-approximation net once and reuses it — "This generates the basic approximation set once as R-tree and re-uses it for each queried decomposition" — by enumerating combinations of the supplied discrete standard gates up to `depth` (default 12), storing each as an $SO(3)$ matrix paired with its gate word. The `SolovayKitaev` transformation pass then walks the DAG and replaces every single-qubit node that is non-parameterised and exposes a `to_matrix`; a node failing any of those three tests passes through untouched, under the loop's own comment "ignore operations on which the algorithm cannot run". Each surviving node is replaced by running the recursion to `recursion_degree`, default 5, documented as "The recursion depth for the Solovay-Kitaev algorithm. A larger recursion depth increases the accuracy and length of the decomposition." The same decomposition is also exposed as a unitary-synthesis plugin, `SolovayKitaevSynthesis`, which "is invoked by transpile() when the `unitary_synthesis_method` parameter is set to `"sk"`". Generated nets can be written out with `save_basic_approximations` and loaded back, so the preprocessing is paid once across sessions.

  Inputs are circuits handed to the transpiler, not a fixed benchmark suite. The discrete basis is the parameter that matters: it "Defaults to `["h", "t", "tdg"]`", and the class docstring's second worked basis is `["s", "sdg", "t", "tdg", "z", "h"]`. The release note's plugin example passes `["h", "s"]`, which is a different kind of input: $H$ and $S$ generate the finite single-qubit Clifford group, so they do not densely generate $SU(2)$ and no recursion depth makes that example converge — it demonstrates how the plugin is wired rather than a convergent decomposition, and it does not satisfy this method's own stated condition that the generating set be dense. All basis gates must be single-qubit and non-parameterised; a multi-qubit entry now "raises a clear ValueError", where previously "such gates could cause an internal Rust panic during synthesis".

  Apache-2.0, in the Qiskit repository at https://github.com/Qiskit/qiskit. The transpiler pass and the synthesis plugin are in `qiskit/transpiler/passes/synthesis/solovay_kitaev_synthesis.py`; the decomposition class is in `qiskit/synthesis/discrete_basis/solovay_kitaev.py`. The numerical core is Rust — `crates/synthesis/src/discrete_basis/solovay_kitaev.rs`, with `basic_approximations.rs` and `math.rs` alongside — built on nalgebra and bound through PyO3, so the Python `SolovayKitaevDecomposition` is a wrapper that delegates to `qiskit._accelerate.synthesis.discrete_basis.SolovayKitaevSynthesis`.

  No device run: this is a classical transpiler pass, and the runtime named is Qiskit itself, with the recursion executing in the compiled Rust `qiskit._accelerate` extension rather than in Python. The documented worked example takes `RX(0.8)` at `recursion_degree=2` and returns the three-gate sequence `H T H`. Two error figures for it are in circulation, attached to two different global phases. Pull request 5657 as opened showed the word carrying "global phase: -π/8" and "an L2-error of approximately 0.01". The current docstring shows the same word carrying "global phase: 7π/8" — the two labels differ by $\pi$, not by a multiple of $2\pi$ — and its runnable form prints `Error: 2.828408279166474`, computed by the example itself as `np.linalg.norm(Operator(circuit).data - Operator(discretized).data)`, the Frobenius norm of the raw operator difference with no minimisation over the global phase. The docstring retains the pull request's "approximately 0.01" sentence above that output; the 0.01 figure is the pull request's, and this entry does not attach it to the phase the current docstring prints. The release note's larger example transpiles a 3-qubit QFT to `["u", "cx"]` at optimization level 1 and then discretises it with the default H/T/T-dagger basis, printing the resulting gate counts.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

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

  Reduce approximation of a z-rotation to a grid problem over the ring $Z[1/sqrt(2), i]$ plus a relative norm equation, then exactly synthesize the resulting ring element. This is the production method for z-rotations under Clifford+T.

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

• The Solovay-Kitaev algorithm↗Christopher M. Dawson, Michael A. Nielsen · 2005theory yes · simulation ? · hardware no
• Breaking the cubic barrier in the Solovay-Kitaev algorithm↗Greg Kuperberg · 2023theory yes · simulation ? · hardware no