Solovay–Kitaev theorem

Let $\backslash mathcal\{G\}$ be a finite set of elements in SU(2) containing its own inverses (so $g\; \backslash in\; \backslash mathcal\{G\}$ implies $g^\{-1\}\; \backslash in\; \backslash mathcal\{G\}$) and such that the group $\backslash langle\; \backslash mathcal\{G\}\; \backslash rangle$ they generate is dense in SU(2). Consider some $\backslash varepsilon\; >\; 0$. Then there is a constant $c$ such that for any $U\; \backslash in\; \backslash mathrm\{SU\}(2)$, there is a sequence $S$ of gates from $\backslash mathcal\{G\}$ of length $O(\backslash log^c(1/\backslash varepsilon))$ such that $\backslash |S\; -\; U\backslash |\; \backslash leq\; \backslash varepsilon$. That is, $S$ approximates $U$ 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 $\backslash mathcal\{G\}$ contains its own inverses, although presently with a larger value of $c$ that also increases with the dimension $d$.{{Citation |last1=Bouland |first1=Adam |title=Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm |date=2021-12-03 |arxiv=2112.02040 |last2=Giurgica-Tiron |first2=Tudor}}

The constant $c$ can be made to be $\backslash log\_\{(1+\backslash sqrt\{5\})/2\}\; 2\; +\; \backslash delta\; =\; 1.44042\backslash ldots\; +\; \backslash delta$ for any fixed $\backslash delta\; >\; 0$.{{Cite arXiv |mode=cs2 |last=Kuperberg |first=Greg |title=Breaking the cubic barrier in the Solovay-Kitaev algorithm |date=2023-06-22 |class=quant-ph |eprint=2306.13158}} 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.{{Cite journal|last1=Ross|first1=Neil J.|last2=Selinger|first2=Peter|title=Optimal ancilla-free Clifford+T approximation of z-rotations|url=https://www.rintonpress.com/journals/doi/QIC16.11-12-1.html|journal=Quantum Information & Computation|volume=16|issue=11-12|pages=901–953|doi=10.26421/QIC16.11-12-1|arxiv=1403.2975

}}

Every known proof of the fully general Solovay–Kitaev theorem proceeds by recursively constructing a gate sequence giving increasingly good approximations to $U\; \backslash in\; \backslash operatorname\{SU\}(2)$. Suppose we have an approximation $U\_\{n-1\}\; \backslash in\; \backslash operatorname\{SU\}(2)$ such that $\backslash |\; U\; -\; U\_\{n-1\}\; \backslash |\; \backslash leq\; \backslash varepsilon\_\{n-1\}$. Our goal is to find a sequence of gates approximating $U\; U\_\{n-1\}^\{-1\}$ to $\backslash varepsilon\_n$ error, for . By concatenating this sequence of gates with $U\_\{n-1\}$, we get a sequence of gates $U\_n$ such that $\backslash |U\; -\; U\_n\backslash |\; \backslash leq\; \backslash 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\; \backslash in\; \backslash operatorname\{SU\}(2)$ satisfying $\backslash |V\; -\; I\backslash |\; \backslash leq\; \backslash delta\_1$ and $\backslash |W\; -\; I\backslash |\; \backslash leq\; \backslash delta\_1$ and approximations $\backslash tilde\{V\},\; \backslash tilde\{W\}\; \backslash in\; \backslash operatorname\{SU\}(2)$ satisfying $\backslash |V\; -\; \backslash tilde\{V\}\backslash |\; \backslash leq\; \backslash delta\_2$ and $\backslash |W\; -\; \backslash tilde\{W\}\backslash |\; \backslash leq\; \backslash delta\_2$, then

:$\backslash |VWV^\{-1\}W^\{-1\}\; -\; \backslash tilde\{V\}\backslash tilde\{W\}\backslash tilde\{V\}^\{-1\}\backslash tilde\{W\}^\{-1\}\backslash |\; \backslash leq\; O(\backslash delta\_1\backslash delta\_2),$

where the big O notation hides higher-order terms. One can naively bound the above expression to be $O(\backslash delta\_2)$, but the group commutator structure creates substantial error cancellation.

We can use this observation to approximate $U\; U\_\{n-1\}^\{-1\}$ as a group commutator $V\_\{n-1\}W\_\{n-1\}V\_\{n-1\}^\{-1\}W\_\{n-1\}^\{-1\}$. This can be done such that both $V\_\{n-1\}$ and $W\_\{n-1\}$ are close to the identity (since $\backslash |U\; U\_\{n-1\}^\{-1\}\; -\; I\backslash |\; \backslash leq\; \backslash varepsilon\_\{n-1\}$). So, if we recursively compute gate sequences approximating $V\_\{n-1\}$ and $W\_\{n-1\}$ to $\backslash varepsilon\_\{n-1\}$ error, we get a gate sequence approximating $U\; U\_\{n-1\}^\{-1\}$ to the desired better precision $\backslash varepsilon\_n$ with $\backslash varepsilon\_n$. We can get a base case approximation with constant $\backslash varepsilon\_0$ with an exhaustive search of bounded-length gate sequences.

Let us choose the initial value $\backslash varepsilon\_0$ so that to be able to apply the iterated “shrinking” lemma. In addition we want to make sure that $\backslash varepsilon\_k$ decreases as we increase $k$. Moreover, we also make sure that $\backslash varepsilon\_0$ is small enough so that .

Since $\backslash langle\; G\; \backslash rangle$ is dense in $\backslash operatorname\{SU\}(2)$, we can choose $l\_0$ large enough{{cite web |last1=Kitaev |first1=Yu |title=Quantum computations: algorithms and error correction |url=http://mi.mathnet.ru/eng/umn/v52/i6/p53}} so that $G^\{l\_0\}$ is an $\backslash varepsilon\_0^2$-net for $\backslash operatorname\{SU\}(2)$ (and hence for $\backslash operatorname\{S\}\_\{\backslash varepsilon\_0\}$, as well), no matter how small $\backslash varepsilon\_0$ is. Thus, given any $U\; \backslash in\; \backslash operatorname\{SU\}(2)$, we can choose $U\_0\; \backslash in\; G^\{l\_0\}$ such that . Let $\backslash Delta\; :=\; UU\_0^\{+\}$ be the “difference” of $U$ and $U\_0$. Then

:

Hence, $\backslash Delta\_1\backslash in\; \backslash operatorname\{S\_\{\backslash varepsilon\_1\}\}$. By invoking the iterated "shrinking" lemma with $k\; =\; 1$, there

exists $U\_1\; \backslash in\; G^\{l\_1\}$ such that

:

Similarly let $\backslash Delta\_2:=\backslash Delta\_1\; U\_1^+\; =\; U\; U\_0^+\; U\_1^+$. Then

:

Thus, $\backslash Delta\_2\backslash in\; \backslash operatorname\{S\_\{\backslash varepsilon\_2\}\}$ and we can invoke the iterated "shrinking" lemma (with

$k\; =\; 2$ this time) to get $U\_2\; \backslash in\; G^\{l\_2\}$ such that

If we continue in this way, after k steps we get $U\_k\; \backslash in\; \backslash operatorname\{G\}^\{l\_k\}$ such that

:

Thus, we have obtained a sequence of

:

gates that approximates $U$ to accuracy $\backslash varepsilon\_k^2$. To determine the value of $k$, we set $\backslash varepsilon\_k^2\; =\; \backslash left((s\backslash varepsilon\_0\; )^\{(3/2)^k\}/s\backslash right)^2=\backslash varepsilon$

and solve for k:

:$\backslash left(\backslash frac\{3\}\{2\}\backslash right)^k\; =\backslash frac\{\backslash text\{log\}(1/s^2\; \backslash varepsilon)\}\{2\backslash text\{log\}(1/s\backslash varepsilon\_0)\}$

.

Now we can always choose $\backslash varepsilon\_0$ slightly smaller so that the obtained value

of $k$ is an integer.{{cite web |last1=Nielsen, Chuang |first1=M.A., I.L. |title=Quantum Computation and Quantum Information (Cambridge University Press, 2000), Appendix 3, pp. 617{624.}} Let $c=\backslash text\{log\}5/\backslash text\{log\}(3/2)\; \backslash approx\; 3.97$ so that$5^k\; =\; \backslash left(\backslash frac\{3\}\{2\}\backslash right)^\{kc\}$. Then

:

Hence for any $U\; \backslash in\; \backslash operatorname\{SU\}(2)$ there is a sequence of $L=O(\backslash text\{log\}^c(1/\backslash varepsilon))$ gates that

approximates $U$ to accuracy $\backslash varepsilon$.

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:

function Solovay-Kitaev(Gate $U$, depth $n$) is

if ($n$ == 0)

return Basic Approximation to $U$

else

set $U\_\{n-1\}$ = Solovay-Kitaev($U$,$n-1$)

set $V,W$ = GC-Decompose($UU\_\{n-1\}^+$)

set $V\_\{n-1\}$ = Solovay-Kitaev($V,n-1$)

set $W\_\{n-1\}$ = Solovay-Kitaev($W,n-1$)

return $U\_n=V\_\{n-1\}W\_\{n-1\}V\_\{n-1\}^+W\_\{n-1\}^+U\_\{n-1\}$;

end function

Let us examine each of these lines in detail. The first line:

function Solovay-Kitaev(Gate $U$, depth $n$) is

indicates that the algorithm is a function with two inputs: an arbitrary single-qubit quantum

gate, $U$, which we desire to approximate, and a non-negative integer, $n$, which controls

the accuracy of the approximation. The function returns a sequence of instructions which

approximates $U$ to an accuracy $\backslash varepsilon\_n$, where $\backslash varepsilon\_n$ is a decreasing function of $n$, so that as $n$ gets

larger, the accuracy gets better, with $\backslash varepsilon\_n\backslash to\; 0$ as $n\backslash to\; \backslash infty$. $\backslash varepsilon\_n$ is described in detail below.

The Solovay-Kitaev function is recursive, so that to obtain an $\backslash varepsilon\_n$-approximation to $U$,

it will call itself to obtain $\backslash varepsilon\_\{n-1\}$-approximations to certain unitaries. The recursion terminates

at $n=0$, beyond which no further recursive calls are made:

if ($n$ == 0)

return Basic Approximation to $U$

In order to implement this step it is assumed that a preprocessing stage has been completed

which allows one to find a basic $\backslash varepsilon\_0$-approximation to arbitrary $U\; \backslash in\; \backslash operatorname\{SU\}(2)$. Since $\backslash varepsilon\_0$ is a constant, in principle this preprocessing stage may be accomplished simply 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.

At higher levels of recursion, to find an $\backslash varepsilon\_n$-approximation to $U$, one begins by finding an

$\backslash varepsilon\_\{n-1\}$-approximation to $U$:

else

set $U\_\{n-1\}$ = Solovay-Kitaev($U$,$n-1$)

$U\_\{n-1\}$ is used as a step towards finding an improved approximation to $U$. Defining $\backslash Delta$≡ $UU^+\_\{n-1\}$, the next three steps of the algorithm aim to find an $\backslash varepsilon\_\{n\}$-approximation to $\backslash Delta$, where $\backslash varepsilon\_\{n\}$ is some improved level of accuracy, i.e., . Finding such an approximation

also enables us to obtain an $\backslash varepsilon\_\{n\}$-approximation to $U$, simply by concatenating exact

sequence of instructions for $U\_\{n-1\}$ with $\backslash varepsilon\_\{n\}$-approximating sequence for $\backslash Delta$.

How do we find such an approximation to? First, observe that $\backslash Delta$ is within a distance $\backslash varepsilon\_\{n-1\}$ of the identity. This follows from the definition of $\backslash Delta$ and the fact that $U\_\{n-1\}$ is within a distance $\backslash varepsilon\_\{n-1\}$ of $U$.

Second, decompose $\backslash Delta$ as a group commutator $\backslash Delta\; =\; VWV^+W^+$ of unitary gates $V$ and $W$. For any $\backslash Delta$ it turns out that this is not obvious and that there is always an infinite set of

choices for $V$ and $W$ such that $\backslash Delta\; =\; VWV^+W^+$. For our purposes it is important that we

find $V$ and $W$ such that for some constant $c\_\{gc\}$. We call such a decomposition a balanced group commutator.

set $V,W$ = GC-Decompose($UU\_\{n-1\}^+$)

For practical implementations we will see below that it is useful to have $c\_\{gc\}$ as small as

possible.

The next step is to find instruction sequences which are $\backslash varepsilon\_\{n-1\}$-approximations to $V$ and $W$:

set $V\_\{n-1\}$ = Solovay-Kitaev($V,n-1$)

set $W\_\{n-1\}$ = Solovay-Kitaev($W,n-1$)

The group commutator of $V\_\{n-1\}$ and $W\_\{n\}$ turns out to be an $\backslash varepsilon\_\{n-1\}$ ≡ $c\_\{\backslash text\{approx\}\}\backslash varepsilon\_\{n-1\}^\{3/2\}$-approximation to $\backslash Delta$, for some small constant $c\_\{\backslash text\{approx\}\}$. Provided , we see that , and this procedure therefore provides an improved

approximation to $\backslash Delta$, and thus to $U$.

The constant $c\_\{\backslash text\{approx\}\}$ is important as it determines the precision $\backslash varepsilon\_0$ required of the initial approximations. In particular, we see that for this construction to guarantee that $\backslash varepsilon\_0>\backslash varepsilon\_1>...$ we must have .

The algorithm concludes by returning the sequences approximating the group commutator, as well as $U\_\{n-1\}$:

return $U\_n=V\_\{n-1\}W\_\{n-1\}V\_\{n-1\}^+W\_\{n-1\}^+U\_\{n-1\}$'';

Summing up, the function Solovay-Kitaev(U, n) returns a sequence which provides an $\backslash varepsilon\_n=c\_\{\backslash text\{approx\}\}\backslash varepsilon\_\{n-1\}^\{3/2\}$-approximation to the desired unitary $U$ . The five constituents in this sequence

are all obtained by calling the function at the $n-1$th level of recursion.{{cite web |last1=CHRISTOPHER M. DAWSON |first1=MICHAEL A. NIELSEN |title=THE SOLOVAY-KITAEV ALGORITHM |url=https://arxiv.org/pdf/quant-ph/0505030}}

{{Reflist}}

{{Quantum computing}}

{{DEFAULTSORT:Solovay-Kitaev theorem}}

Category:Mathematical theorems

Category:Quantum computing

Category:Quantum information theory