The Solovay-Kitaev algorithm

Dawson, C. M. and Nielsen, M. A. (2006) The Solovay-Kitaev algorithm. Quantum Information and Computation, 6 1: 81-95.

Author Dawson, C. M.
Nielsen, M. A.
Title The Solovay-Kitaev algorithm
Journal name Quantum Information and Computation
ISSN 1533-7146
Publication date 2006-01-01
Sub-type Article (original research)
Open Access Status Not Open Access
Volume 6
Issue 1
Start page 81
End page 95
Total pages 15
Editor Dr Wei Chen
Place of publication Paramus, NJ, United States
Publisher Rinton Press
Language eng
Formatted 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/2k, into an efficient fault-tolerant form using only Hadamard, controlled-NOT, and pi/8 gates. The algorithm runs in O(log2.71(1/epsilon)) time, and produces as output a sequence of O(log3.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).
Keyword Solovay-Kitaev algorithm
Q-Index Code C1
Q-Index Status Provisional Code
Institutional Status UQ

Document type: Journal Article
Sub-type: Article (original research)
Collections: 2007 Higher Education Research Data Collection
School of Agriculture and Food Sciences
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 92 times in Thomson Reuters Web of Science Article | Citations
Scopus Citation Count Cited 100 times in Scopus Article | Citations
Google Scholar Search Google Scholar
Created: Wed, 15 Aug 2007, 19:23:53 EST