In quantum information and computation, the Solovay–Kitaev theorem says that if a set of single-qubit quantum gates generates a dense subgroup of SU(2), then that set can be used to approximate any desired quantum gate with a short sequence of gates that can also be found efficiently.
This theorem is considered one of the most significant results in the field of quantum computation and was first announced by Robert M. Solovay in 1995 and independently proven by Alexei Kitaev in 1997.
[1][2] Michael Nielsen and Christopher M. Dawson have noted its importance in the field.
error (in operator norm) by a quantum circuit of
So, the Solovay–Kitaev theorem shows that this approximation can be made surprisingly efficient, thereby justifying that quantum computers need only implement a finite number of gates to gain the full power of quantum computation.
be a finite set of elements in SU(2) containing its own inverses (so
[3] Furthermore, there is an efficient algorithm to find such a sequence.
, which makes the length of the gate sequence optimal up to a constant factor.
[7] Every known proof of the fully general Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to
Our goal is to find a sequence of gates approximating
The main idea in the original argument of Solovay and Kitaev is that commutators of elements close to the identity can be approximated "better-than-expected".
, then where the big O notation hides higher-order terms.
, but the group commutator structure creates substantial error cancellation.
So, if we recursively compute gate sequences approximating
error, we get a gate sequence approximating
with an exhaustive search of bounded-length gate sequences.
Here the main ideas that are used in the SK algorithm have been presented.
The SK algorithm may be expressed in nine lines of pseudocode.
Each of these lines are explained in detail below, but present it here in its entirety both for the reader's reference, and to stress the conceptual simplicity of the algorithm: Let us examine each of these lines in detail.
The first line: indicates that the algorithm is a function with two inputs: an arbitrary single-qubit quantum gate,
The function returns a sequence of instructions which approximates
, beyond which no further recursive calls are made: In order to implement this step it is assumed that a preprocessing stage has been completed which allows one to find a basic
is a constant, in principle this preprocessing stage may be accomplished simply by enumerating and storing a large number of instruction sequences from
Finding such an approximation also enables us to obtain an
, simply by concatenating exact sequence of instructions for
it turns out that this is not obvious and that there is always an infinite set of choices for
We call such a decomposition a balanced group commutator.
The algorithm concludes by returning the sequences approximating the group commutator, as well as
: Summing up, the function Solovay-Kitaev(U, n) returns a sequence which provides an
The five constituents in this sequence are all obtained by calling the function at the