Solovay–Kitaev theorem explained

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.^[3]

A consequence of this theorem is that a quantum circuit of

constant-qubit gates can be approximated to

\varepsilon

error (in operator norm) by a quantum circuit of

O(mlog^{c(m/\varepsilon))}

gates from a desired finite universal gate set (where c is a constant).^[4] By comparison, just knowing that a gate set is universal only implies that constant-qubit gates can be approximated by a finite circuit from the gate set, with no bound on its length. 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.

Statement

Let

l{G}

be a finite set of elements in SU(2) containing its own inverses (so

g\inl{G}

implies

g^-1\inl{G}

) and such that the group

\langlel{G}\rangle

they generate is dense in SU(2). Consider some

\varepsilon>0

. Then there is a constant

such that for any

U\inSU(2)

, there is a sequence

of gates from

l{G}

of length

O(log^{c(1/\varepsilon))}

such that

\|S-U\|\leq\varepsilon

. That is,

approximates

to operator norm error. Furthermore, there is an efficient algorithm to find such a sequence. More generally, the theorem also holds in SU(d) for any fixed d.

This theorem also holds without the assumption that

l{G}

contains its own inverses, although presently with a larger value of

that also increases with the dimension

Quantitative bounds

The constant

can be made to be

log_(1+\sqrt{5)/2}2+\delta=1.44042\ldots+\delta

for any fixed

\delta>0

.^[5] However, there exist particular gate sets for which we can take

c=1

, which makes the length of the gate sequence optimal up to a constant factor.^[6]

Proof idea

Every known proof of the fully general Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to

U\in\operatorname{SU}(2)

. Suppose we have an approximation

U_n-1\in\operatorname{SU}(2)

such that

\|U-U_n-1\|\leq\varepsilon_n-1

. Our goal is to find a sequence of gates approximating

	-1
U
	n-1

\varepsilon_n

error, for

\varepsilon_n<\varepsilon_n-1

. By concatenating this sequence of gates with

U_n-1

, we get a sequence of gates

U_n

such that

\|U-U_n\|\leq\varepsilon_n

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". Specifically, for

V,W\in\operatorname{SU}(2)

satisfying

\|V-I\|\leq\delta₁

and

\|W-I\|\leq\delta₁

and approximations

\tilde{V},\tilde{W}\in\operatorname{SU}(2)

satisfying

\|V-\tilde{V}\|\leq\delta₂

and

\|W-\tilde{W}\|\leq\delta₂

, then

\|VWV^-1W^-1-\tilde{V}\tilde{W}\tilde{V}^-1\tilde{W}^-1\|\leqO(\delta_1\delta_2),

where the big O notation hides higher-order terms. One can naively bound the above expression to be

O(\delta₂₎

, but the group commutator structure creates substantial error cancellation.

We can use this observation to approximate

	-1
U
	n-1

as a group commutator

V_n-1W_n-1

	-1
V
	n-1

	-1
W
	n-1

. This can be done such that both

V_n-1

and

W_n-1

are close to the identity (since

\|U

	-1
U
	n-1

-I\|\leq\varepsilon_n-1

). So, if we recursively compute gate sequences approximating

V_n-1

and

W_n-1

\varepsilon_n-1

error, we get a gate sequence approximating

	-1
U
	n-1

to the desired better precision

\varepsilon_n

with

\varepsilon_n

. We can get a base case approximation with constant

\varepsilon₀

with an exhaustive search of bounded-length gate sequences.

Proof of Solovay-Kitaev Theorem

Let us choose the initial value

\varepsilon₀

so that

\varepsilon₀<\varepsilon'

to be able to apply the iterated “shrinking” lemma. In addition we want

s\varepsilon₀<1

to make sure that

\varepsilon_k

decreases as we increase

. Moreover, we also make sure that

\varepsilon₀

is small enough so that

	2
\varepsilon
	k

<\varepsilon_k+1

Since

\langleG\rangle

is dense in

\operatorname{SU}(2)

, we can choose

l₀

large enough^[7] so that

	l₀
G

is an

	2
\varepsilon
	0

-net for

\operatorname{SU}(2)

(and hence for

\operatorname{S}
	\varepsilon₀

, as well), no matter how small

\varepsilon₀

is. Thus, given any

U\in\operatorname{SU}(2)

, we can choose

U₀\in

	l₀
G

such that

||U-U_0||<

	2
\varepsilon
	0

. Let

\Delta:=

	+
UU
	0

be the “difference” of

and

U₀

. Then

\|\Delta₁-I\|=\|(U-U_0)U

	+\\|

	0

=\|U-U_0\|<

	2<\varepsilon
\varepsilon
	1.

Hence,

\Delta_1\in

\operatorname{S
	\varepsilon₁

}. By invoking the iterated "shrinking" lemma with

k=1

, thereexists

U₁\in

	l₁
G

such that

\|\Delta₁-U_1\|=\|U

	+
U
	0

-U_1\|=\|U-U₁U_0\|<

	2.
\varepsilon
	1

Similarly let

\Delta_2:=\Delta₁

	+
U
	1

	+
U
	0

	+
U
	1

. Then

\|\Delta₂-I\|=\|(U-U₁U_0)U

	+

	0

	+\\|
U
	1

=\|U-U₁U_0\|<

	2<\varepsilon
\varepsilon
	2.

Thus,

\Delta_2\in

\operatorname{S
	\varepsilon₂

} and we can invoke the iterated "shrinking" lemma (with

k=2

this time) to get

U₂\in

	l₂
G

such that

\|\Delta₂-U_2\|=\|U

	+
U
	0

	+
U
	1

-U_2\|=\|U-U₂U₁U_0\|<

	2.
\varepsilon
	2

If we continue in this way, after k steps we get

U_k\in

	l_k
\operatorname{G}

such that

\|U-U_kU_k-1...U_0\|<

	2.
\varepsilon
	k

Thus, we have obtained a sequence of

	kl
L=\sum
	m=\sum

	k5

	m=0

0=	5^k+1-1
	4

l₀<

	5
	4

	kl
5
	0

gates that approximates

to accuracy

	2
\varepsilon
	k

. To determine the value of

, we set

	2
\varepsilon
	k

=\left((s\varepsilon₀

	(3/2)^k
)

/s\right)^{2=\varepsilon}

and solve for k:

\left(	3
	2

\right)^k=

	log(1/s²\varepsilon)
	2log(1/s\varepsilon₀₎

Now we can always choose

\varepsilon₀

slightly smaller so that the obtained valueof

is an integer.^[8]

Notes and References

Kitaev. A Yu. 1997-12-31. Quantum computations: algorithms and error correction. Russian Mathematical Surveys. 52. 6. 1191–1249. 10.1070/rm1997v052n06abeh002155. 1997RuMaS..52.1191K . 250816585 . 0036-0279.
Book: Kitaev. Alexei Yu.. Classical and quantum computation. Shen. Alexander. Vyalyi. Mikhail N.. American Mathematical Society. 2002. 0-8218-2161-X. Providence, Rhode Island. 48965167.
Dawson. Christopher M.. Nielsen. Michael. 2006-01-01. The Solovay-Kitaev algorithm. Quantum Information & Computation. 6. 81–95. 10.26421/QIC6.1-6. EN. quant-ph/0505030.
Book: The Solovay–Kitaev theorem. Quantum Computation and Quantum Information: 10th Anniversary Edition. Nielsen. Michael A.. Chuang. Isaac L.. 2010. 617–624. en. 10.1017/cbo9780511976667.019. 9780511976667. 2020-05-20.
cs2 . Kuperberg . Greg . Breaking the cubic barrier in the Solovay-Kitaev algorithm . 2023-06-22 . quant-ph . 2306.13158.
Ross. Neil J.. Selinger. Peter. Optimal ancilla-free Clifford+T approximation of z-rotations. Quantum Information & Computation. 16. 11-12. 901–953. 10.26421/QIC16.11-12-1. 1403.2975.
Web site: Kitaev . Yu . Quantum computations: algorithms and error correction .
Web site: Nielsen, Chuang . M.A., I.L. . Quantum Computation and Quantum Information (Cambridge University Press, 2000), Appendix 3, pp. 617.