CoChat
Sign Up
Cited by 288Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum many-body systems

The Solovay-Kitaev algorithm

Dawson, C.M., Nielsen, M.A.·2006·Quantum Information and Computation
DOI 10.26421/qic6.1-6
Open this paper in CoChat — free account

Abstract

This pedagogical review presents the proof of the Solovay-Kitaev theorem in the form of an efficient classical algorithm for compiling an arbitrary single-qubit gate into a sequence of gates from a fixed and finite set. The algorithm can be used, for example, to compile Shor's algorithm, which uses rotations of $\pi / 2^k$, into an efficient fault-tolerant form using only Hadamard, controlled-{\sc not}, and $\pi / 8$ gates. The algorithm runs in $O(\log^{2.71}(1/\epsilon))$ time, and produces as output a sequence of $O(\log^{3.97}(1/\epsilon))$ quantum gates which is guaranteed to approximate the desired quantum gate to an accuracy within $\epsilon > 0$. We also explain how the algorithm can be generalized to apply to multi-qubit gates and to gates from SU(d).

Integrity signals

Registry

Crossref · 10.26421/qic6.1-6

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • For d = 2^n, the Solovay-Kitaev theorem guarantees that qubit quantum circuits can be decomposed using a finite gate sequence.

    “For d = 2 n this theorem guarantees that qubit quantum circuits can be decomposed using a finite gate sequence.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Dawson and Nielsen, 2006

  • With a universal gate set G in SU(d), any unitary operation can be constructed efficiently.

    “With a universal gate set G ∈ SU ( d ) (also called instruction gate set ), any unitary operation can be constructed efficiently.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Dawson and Nielsen, 2006

  • The Solovay-Kitaev theorem requires that the gate set contains the inverse of all gates.

    “It also requires that the gate set contains the inverse of all gates.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Dawson and Nielsen, 2006

  • The Solovay-Kitaev theorem is an existence theorem and does not provide the decomposition it predicts.

    “Although this is one of the most important theorems in quantum computation, it is an existence theorem, i.e. it does not provide the decomposition that it predicts.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Dawson and Nielsen, 2006

  • The sequence in the Solovay-Kitaev theorem scales logarithmically as O(log^c(1/epsilon)), where c is a constant depending on the theorem proof.

    “This sequence scales logarithmically as O( log c ( 1 / ϵ )) , where c is a constant that depends on the theorem-proof.”

    From Noisy intermediate-scale quantum algorithms (2022) · cites this paper as Dawson and Nielsen, 2006

Cites

Flagged first, then by citations

Cited by

Sorted by citations

Authors
Dawson, C. M., & Nielsen, M. A.
Affiliations
The University of Queensland (AU)
ORCID
Nielsen, M.A.
Venue
Quantum Information and Computation
Publisher
Rinton Press
Published
2006-01
Volume
6
Issue
1
Pages
81-95
ISSN
1533-7146 (ISSN-L)
DOI
10.26421/qic6.1-6
OpenAlex
W2950843936
Cited by
288
References
3
Citations by year
2026: 17 · 2025: 26 · 2024: 35 · 2023: 70 · 2022: 13 · 2021: 28 · 2020: 13 · 2019: 14 · 2018: 9 · 2017: 7 · 2016: 1 · 2015: 4 · 2014: 7 · 2013: 14 · 2012: 8
FWCI
4.94
Type
journal article
Language
en
Open access
closed
Locations
Quantum Information and Computation (publishedVersion)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum many-body systems
Keywords
single-qubit gates, fault-tolerant quantum computing, Shor's algorithm, multi-qubit gates, quantum circuit synthesis

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review