The Solovay-Kitaev Theorem

Derivation

The Solovay-Kitaev Theorem

D-410 Home PU-404 Threads symmetry Depends on Universality of CNOT with Single-Qubit Gates

Statement

Let \(\mathcal{G}\) be a finite set of gates in \(SU(2)\) that is universal (generates a dense subgroup) and closed under inverse. Then there exists a constant \(c\) such that for every \(U \in SU(2)\) and every \(\varepsilon > 0\) one can find a word \(W\) of length \(\ell = O\!\left(\log^{c}(1/\varepsilon)\right)\) in the letters of \(\mathcal{G}\) with operator-norm distance \(\lVert U - W \rVert < \varepsilon\), and this word is constructible by a classical algorithm running in time \(O\!\left(\log^{c}(1/\varepsilon)\right)\). The recursive construction achieves \(c \approx \log_{5/3}(3) \approx 3.97\), so the gate cost is polylogarithmic in \(1/\varepsilon\).

Why it matters

Universality tells you that a fixed gate set can reach every unitary arbitrarily closely, but it says nothing about cost. A priori the number of gates needed to hit accuracy \(\varepsilon\) could scale as \(1/\varepsilon\) or worse, which would make fault-tolerant quantum computation hopeless: the whole point of a discrete fault-tolerant set (Clifford + \(T\)) is that the continuous rotations demanded by an algorithm must be compiled into it, and every logical gate spawns such a compilation.

Solovay-Kitaev turns "dense" into "efficiently dense." The exponential improvement from \(1/\varepsilon\) to \(\log^{c}(1/\varepsilon)\) is what makes gate synthesis a solved-in-principle problem, and it is a purely group-theoretic fact about compact Lie groups, independent of the physical implementation.

Assumptions

The gate set \(\mathcal{G}\) is universal.If \(\langle\mathcal{G}\rangle\) is not dense in \(SU(2)\) (e.g. Clifford gates alone, which generate a finite group), there are unitaries no word can approach; the target \(\varepsilon\)-ball may contain no reachable point at all.

\(\mathcal{G}\) is closed under inverses: \(g \in \mathcal{G} \Rightarrow g^{-1}\in\mathcal{G}\).The construction uses group commutators \(V W V^{-1} W^{-1}\); without inverses the "net" of words is not closed under the operations the recursion needs, and the base case cannot be assembled. (In practice one appends inverses, at most doubling \(|\mathcal{G}|\).)

The group is \(SU(2)\) (or a compact semisimple Lie group), so its Lie algebra is generated by commutators.The efficiency hinges on \([\mathfrak{su}(2),\mathfrak{su}(2)]=\mathfrak{su}(2)\): a first-order error \(\Delta\) can be reproduced by a commutator of two elements each of size \(\sqrt{\Delta}\). For an abelian group all commutators are trivial and the shrinking mechanism fails entirely.

Base case: for some \(\varepsilon_0\) the set of words up to a fixed length forms an \(\varepsilon_0\)-net of \(SU(2)\).Density guarantees such an \(\varepsilon_0\) exists, but the recursion's contraction only holds once \(\varepsilon_0\) is small enough that the quadratic term dominates; if the base net is too coarse the iteration diverges instead of converging.

Derivation

\[ d(A,B) \equiv \lVert A - B \rVert, \qquad d(AC,BC)=d(A,B),\ d(CA,CB)=d(A,B) \]

Define the metric as the operator norm of the difference. Bi-invariance holds because the operator norm is unitarily invariant: \(\lVert AC-BC\rVert=\lVert(A-B)C\rVert=\lVert A-B\rVert\). This lets us translate errors around a word freely. A

\[ d(U_1 U_2,\, V_1 V_2) \le d(U_1,V_1) + d(U_2,V_2) \]

Errors compose sub-additively: \(\lVert U_1U_2-V_1V_2\rVert \le \lVert U_1U_2-V_1U_2\rVert + \lVert V_1U_2-V_1V_2\rVert = d(U_1,V_1)+d(U_2,V_2)\), using bi-invariance from Step 1. A length-\(\ell\) word accumulates error at most linearly in \(\ell\). A

\[ \text{Suppose } \mathcal{G}_{n-1}\ \text{is an } \varepsilon_{n-1}\text{-net: } \forall U\ \exists U_{n-1}\in\mathcal{G}_{n-1},\ d(U,U_{n-1})<\varepsilon_{n-1} \]

Inductive hypothesis. \(\mathcal{G}_{n-1}\) is the set of all words reachable at recursion depth \(n-1\). The base case \(n=0\) is the assumed \(\varepsilon_0\)-net. We must show depth \(n\) gives a much finer \(\varepsilon_n\)-net. B

\[ \Delta \equiv U\,U_{n-1}^{-1}, \qquad d(\Delta,\mathbf{1}) = d(U,U_{n-1}) < \varepsilon_{n-1} \]

Form the residual error \(\Delta\), the "gap" between the target and the best depth-\((n-1)\) approximation. By bi-invariance \(d(\Delta,\mathbf 1)=\lVert UU_{n-1}^{-1}-\mathbf 1\rVert=\lVert U-U_{n-1}\rVert\). The task reduces to approximating a unitary \(\Delta\) that is within \(\varepsilon_{n-1}\) of the identity. B

\[ \Delta=\exp(-i\,\vec{n}\cdot\vec{\sigma}\,\theta),\quad \theta=O(\varepsilon_{n-1}),\qquad \Delta=\mathbf 1 - i\theta\,\vec n\cdot\vec\sigma + O(\theta^2) \]

Because \(d(\Delta,\mathbf 1)<\varepsilon_{n-1}\), the rotation angle \(\theta\) of \(\Delta\) satisfies \(\theta = O(\varepsilon_{n-1})\); expanding the exponential, \(\Delta\) is a first-order (Lie-algebra) perturbation of the identity. This is where we leave the group and work in \(\mathfrak{su}(2)\). C

\[ [\,e^{A},e^{B}\,]\equiv e^{A}e^{B}e^{-A}e^{-B} = \exp\!\big([A,B] + O(|A|^3,|B|^3)\big) \]

The group-commutator identity (BCH expansion): the leading term of \(e^Ae^Be^{-A}e^{-B}\) is the Lie bracket \([A,B]\), with corrections cubic in the generators. This is the engine of the theorem — a second-order quantity \([A,B]\) is produced from first-order inputs \(A,B\). C

\[ \Delta = \exp([A,B]) \ \text{with}\ |A|,|B| = O(\sqrt{\theta}) = O\!\big(\varepsilon_{n-1}^{1/2}\big) \]

Since \(\mathfrak{su}(2)\) is spanned by brackets (\([\sigma_i,\sigma_j]=2i\epsilon_{ijk}\sigma_k\)), any algebra element \(-i\theta\,\vec n\cdot\vec\sigma\) of size \(\theta\) can be written as a single commutator \([A,B]\) where each of \(A,B\) has size of order \(\sqrt{\theta}\). Balancing the magnitudes is the crucial rescaling: the "square-root" is what makes the error shrink super-linearly. A constructive choice: pick \(A,B\) as rotations of angle \(\sim\sqrt{\theta}\) about orthogonal axes. C

\[ V,W\in\mathcal{G}_{n-1}:\quad d(V,e^{A})<c_{\mathrm{approx}}\,\varepsilon_{n-1}^{3/2},\qquad d(W,e^{B})<c_{\mathrm{approx}}\,\varepsilon_{n-1}^{3/2} \]

Apply the inductive hypothesis (Step 3) to the two group elements \(e^A,e^B\) of size \(O(\varepsilon_{n-1}^{1/2})\). Each is approximated to accuracy \(\varepsilon_{n-1}\) — but note we need them accurate relative to their size; the net at depth \(n-1\) gives absolute accuracy \(\varepsilon_{n-1}\), and a sharper packing argument yields error \(O(\varepsilon_{n-1}^{3/2})\) for these specifically small targets. \(V,W\) are honest words in \(\mathcal{G}\). B

\[ \tilde\Delta \equiv V\,W\,V^{-1}\,W^{-1}, \qquad d(\tilde\Delta,\Delta)\ \le\ c_{\mathrm{gc}}\,\varepsilon_{n-1}^{3/2} \]

Build the group commutator of the two words. Two error sources add (Step 2): (i) the BCH cubic correction of Step 6, of size \((\varepsilon_{n-1}^{1/2})^3=\varepsilon_{n-1}^{3/2}\); (ii) four factors each carrying the \(O(\varepsilon_{n-1}^{3/2})\) word-error of Step 8. Both are \(O(\varepsilon_{n-1}^{3/2})\), so \(\tilde\Delta\) reproduces the residual \(\Delta\) to that order. C

\[ U_n \equiv \tilde\Delta\,U_{n-1}, \qquad d(U,U_n) = d(\Delta,\tilde\Delta) \le c_{\mathrm{gc}}\,\varepsilon_{n-1}^{3/2} \]

Correct the previous approximation by prepending the commutator that mimics the residual. Using \(U=\Delta U_{n-1}\) (Step 4) and bi-invariance, \(d(U,U_n)=d(\Delta U_{n-1},\tilde\Delta U_{n-1})=d(\Delta,\tilde\Delta)\). \(U_n\) is a word in \(\mathcal{G}\), being a product of \(U_{n-1}\) and the four words \(V,W,V^{-1},W^{-1}\). B

\[ \boxed{\ \varepsilon_n = c_{\mathrm{gc}}\,\varepsilon_{n-1}^{3/2}\ } \quad\Longleftrightarrow\quad (c_{\mathrm{gc}}^{2}\,\varepsilon_n) = (c_{\mathrm{gc}}^{2}\,\varepsilon_{n-1})^{3/2} \]

The recursion relation for the net fineness. Writing \(\eta_n = c_{\mathrm{gc}}^{2}\varepsilon_n\) linearises it to \(\eta_n=\eta_{n-1}^{3/2}\), i.e. \(\log(1/\eta_n)=\tfrac32\log(1/\eta_{n-1})\). Convergence requires \(\eta_0<1\), i.e. \(\varepsilon_0 < 1/c_{\mathrm{gc}}^2\) — the base-net condition. B

\[ \varepsilon_n = \frac{1}{c_{\mathrm{gc}}^{2}}\big(c_{\mathrm{gc}}^{2}\varepsilon_0\big)^{(3/2)^{n}} \;\Longrightarrow\; n \approx \log_{3/2}\!\frac{\log(1/\varepsilon)}{\log(1/\varepsilon_0)} \]

Solving the recursion: to reach accuracy \(\varepsilon_n=\varepsilon\) the depth grows only doubly-logarithmically in \(1/\varepsilon\), because each level takes the accuracy exponent from \(k\) to \(\tfrac32 k\). Invert \(\varepsilon = \tfrac1{c^2}(c^2\varepsilon_0)^{(3/2)^n}\) to get \(n\). C

\[ \ell_n = 5\,\ell_{n-1} + \ell_{n-1} \;\Rightarrow\; \ell_n = c_1\,5^{\,n},\qquad \ell = O\!\big(5^{\,n}\big) \]

Length recursion: \(U_n=\tilde\Delta U_{n-1}\) uses \(U_{n-1}\) once and \(V,W,V^{-1},W^{-1}\) (each a depth-\((n-1)\) word) — five sub-words plus the correction, so length multiplies by \(5\) per level. With \(n\) levels the word length is \(O(5^n)\). B

\[ \ell = O(5^{\,n}),\ \ n=\log_{3/2}\!\log_{\varepsilon_0}\!\varepsilon \;\Rightarrow\; \ell = O\!\Big(\log^{\,\log_{3/2}5}(1/\varepsilon)\Big),\quad \log_{3/2}5 = \frac{\ln 5}{\ln(3/2)}\approx 3.97 \]

Eliminate \(n\): substituting \(5^n=(3/2)^{n\log_{3/2}5}\) and \((3/2)^n \sim \log(1/\varepsilon)\) gives \(\ell = O\big(\log^{c}(1/\varepsilon)\big)\) with \(c=\ln5/\ln(3/2)\approx3.97\). This is the promised polylogarithmic scaling. B

Result

\[ \lVert U - W \rVert < \varepsilon \quad\text{with}\quad \operatorname{length}(W)=O\!\left(\log^{c}\frac1\varepsilon\right),\ \ c=\frac{\ln 5}{\ln(3/2)}\approx 3.97 \]

Reading. Any single-qubit unitary can be compiled into an inverse-closed universal gate set with a number of gates that grows only as a fixed power of \(\log(1/\varepsilon)\), not as \(1/\varepsilon\). Each recursion level replaces the current error \(\varepsilon_{n-1}\) with \(c_{\mathrm{gc}}\varepsilon_{n-1}^{3/2}\) — a super-linear contraction — at the cost of multiplying the word length by \(5\). Because accuracy improves as a power tower while length grows geometrically, the trade-off is exponentially favourable. The exponent \(c\) is not fundamental: better commutator constructions and balanced generators lower it toward \(1\) (state-of-the-art numeric synthesis for specific sets reaches essentially \(c\to1\)).

Units check. Everything is dimensionless. \(U,W\in SU(2)\) are unitary matrices (dimensionless), \(\varepsilon\) is a pure number (operator-norm distance, \(0\le\varepsilon\le2\)), the length is a count of gates (dimensionless), and \(\log(1/\varepsilon)\) is dimensionless. The exponent \(c=\ln5/\ln(3/2)\) is a ratio of logarithms of pure numbers, hence dimensionless. Consistent.

Limiting cases

\(\varepsilon\to\varepsilon_0\) (one level, \(n=0\)): \(W\) is just the base-net word, length \(O(1)\); no recursion needed and the bound is trivially satisfied.
\(\varepsilon\to 0\): depth \(n\sim\log_{3/2}\log(1/\varepsilon)\to\infty\) but length \(\sim\log^{3.97}(1/\varepsilon)\) — still polynomially small in \(\log(1/\varepsilon)\); contrast the naive covering bound \(\sim(1/\varepsilon)^3\).
Idealised commutator (\(c_{\mathrm{gc}}\to0\), exact BCH): the contraction exponent stays \(3/2\); the constant only sets the base-net threshold \(\varepsilon_0<c_{\mathrm{gc}}^{-2}\), not the asymptotic power \(c\).
Balanced/optimal generators: if the residual can be written as a commutator with each factor of size exactly \(\sqrt\theta\) and the word-error scales as \(\varepsilon^{3/2}\), the exponent is as derived; improved schemes (fifth-order nets) push \(c\) below \(2\).

Breaks when

The group is abelian or the gate set generates a discrete subgroup. If \(\langle\mathcal{G}\rangle\) is finite (Clifford group) or the commutator \([A,B]\) vanishes to leading order (abelian directions), Step 6-7 produce nothing: there is no square-root shrinking, the recursion \(\varepsilon_n=c\varepsilon_{n-1}^{3/2}\) does not hold, and most targets are simply unreachable.
The base net is too coarse: \(\varepsilon_0 > 1/c_{\mathrm{gc}}^{2}\). Then \(\eta_0>1\) and the "contraction" \(\eta_n=\eta_{n-1}^{3/2}\) diverges — each level makes the error larger, not smaller. The theorem needs a sufficiently fine starting net, which for a poor gate set can itself require exponentially many gates before the recursion even engages.
Scaling to many qubits at fixed depth. The theorem is about \(SU(2)\) (and \(SU(d)\) with \(d\) fixed); the constants and the base-net size grow with \(\dim SU(d)=d^2-1\). For an \(n\)-qubit unitary in \(SU(2^n)\) a generic target needs \(\Omega(4^n\log(1/\varepsilon))\) gates — SK controls the \(\varepsilon\)-dependence, not the exponential dimension dependence.

Failure modes

Confusing "dense" with "efficient." Assuming universality alone bounds the gate count — it only guarantees existence of some word, a priori of length \(\sim1/\varepsilon^3\).
Getting the exponent balance wrong in Step 7. Writing \(\Delta=[A,B]\) with \(|A|,|B|\sim\theta\) instead of \(\sqrt\theta\); then the commutator is \(O(\theta^2)\), far too small, and cannot reproduce the \(O(\theta)\) residual.
Forgetting the base case must be fine enough. Proving the recursion contracts but never checking \(\varepsilon_0<c_{\mathrm{gc}}^{-2}\); the induction is then vacuous or divergent.
Using \(V W\) instead of \(V W V^{-1} W^{-1}\). A plain product gives error \(O(\theta)\) (first order), not the commutator's \(O(\theta^{3/2})\); the whole speed-up is lost.
Claiming \(c=1\) from this construction. The basic five-word recursion gives \(c=\ln5/\ln(3/2)\approx3.97\); the near-optimal exponent requires different (non-commutator) synthesis, not this proof.
Applying it verbatim to CNOT/two-qubit compilation. The single-qubit SK does not by itself entangle; entangling structure comes from the assumed universal set (prior result), SK refines the single-qubit rotations inside it.

Discussion

The Solovay-Kitaev theorem is fundamentally a statement about the geometry of compact Lie groups, not about quantum mechanics per se. Its engine is the identity \([\mathfrak g,\mathfrak g]=\mathfrak g\) for a semisimple Lie algebra: an error lying at first order in the algebra can be rebuilt as a commutator of two larger first-order elements. Because a commutator of things of size \(\delta\) has size \(\delta^2\), one inverts this to say an error of size \(\theta\) is a commutator of things of size \(\sqrt\theta\) — and those larger things are themselves easier to approximate. Iterating this "square-root descent" is what turns a linear error budget into a super-linear one and yields the doubly-logarithmic depth.

Physically, this is the compiler at the heart of fault tolerance. A fault-tolerant architecture offers a discrete gate set (Clifford + \(T\)), but quantum algorithms demand continuous rotations \(R_z(\phi)\) for arbitrary \(\phi\) — phase estimation, Hamiltonian simulation, and the QFT are full of them. SK guarantees each such rotation costs only \(\mathrm{polylog}(1/\varepsilon)\) discrete gates, so a circuit of \(m\) rotations each to accuracy \(\varepsilon/m\) inflates by only a polylogarithmic factor. Without SK, the discreteness forced by error correction would be catastrophic.

The connection to the symmetry thread is direct: universality is the statement that the words fill out the whole group \(SU(2)\) with no residual invariant subspace or conserved quantity obstructing them. The proof exploits the group's own symmetry — bi-invariance of the metric (Steps 1-2) means an error can be conjugated to sit next to the identity, where the Lie-algebra linearisation and the commutator identity apply. The exponent \(c=\ln5/\ln(3/2)\) reflects two competing symmetric rates: the multiplicative growth of word length (\(\times5\) per level, from the four commutator letters plus the carried approximation) against the super-linear \(3/2\) improvement in accuracy. Sharper analyses replace the group commutator with balanced/higher-order nets and drive \(c\) below \(2\); Kitaev-Shen-Vyalyi give \(c\approx3.97\), and Harrow-Recht-Chuang and later number-theoretic synthesis (for specific sets like Clifford\(+T\)) reach essentially optimal \(O(\log(1/\varepsilon))\).

Common misconceptions. (i) SK does not find the shortest word — it finds a provably short one; optimal synthesis for special sets uses number theory (exact synthesis over \(\mathbb Z[\tfrac1{\sqrt2},i]\)) and beats SK's constant. (ii) The polylog is in \(1/\varepsilon\), not in the number of qubits — SK does not tame the exponential cost of a generic multi-qubit unitary. (iii) The theorem needs inverse-closure; it is not a statement about arbitrary semigroups of gates.

Worked examples

\[ \textbf{Example A: gate count to compile one } R_z(\phi)\text{ to } \varepsilon=10^{-9}. \]

Estimate the word length from \(\ell = A\,\log^{c}(1/\varepsilon)\) with \(c=\ln5/\ln(3/2)\approx3.9750\) and a typical constant \(A\approx1\)-\(4\). Set the symbolic form before numbers. B

\[ \log_{10}(1/\varepsilon)=9 \ \Rightarrow\ \ln(1/\varepsilon)=9\ln10=20.72,\qquad \log^{c}(1/\varepsilon)=(20.72)^{3.975} \]

Convert the accuracy to a natural log (SK constants are stated with \(\ln\)). Compute the power. A

\[ (20.72)^{3.975}=\exp(3.975\times\ln 20.72)=\exp(3.975\times3.031)=\exp(12.05)\approx 1.7\times10^{5} \]

Evaluate. With \(A\approx1\) this is the order of magnitude; the raw SK constant \(A\) is a few, so a few\(\times10^{5}\) gates. A

\[ \ell \sim 10^{5}\text{-}10^{6}\ \text{gates} \]

Reading. Compiling a single arbitrary \(z\)-rotation to nine digits with basic SK costs of order \(10^5\)-\(10^6\) discrete gates. This large constant is exactly why SK is a proof of principle: number-theoretic synthesis for Clifford\(+T\) reduces this to \(\approx 3\log_2(1/\varepsilon)+O(\log\log)\approx 90\) \(T\)-gates for the same \(\varepsilon\). Units: gates are dimensionless counts, \(\varepsilon\) dimensionless.

\[ \textbf{Example B: recursion depth to go from } \varepsilon_0=0.1 \text{ to } \varepsilon=10^{-12}. \]

Use \(\varepsilon_n=\tfrac1{c_{\mathrm{gc}}^2}(c_{\mathrm{gc}}^2\varepsilon_0)^{(3/2)^n}\). Take the standard bound \(c_{\mathrm{gc}}\) such that \(c_{\mathrm{gc}}^2\varepsilon_0=\tfrac12\) for a clean estimate (i.e. \(\eta_0=1/2\)). Symbols first. B

\[ \eta_n=\eta_0^{(3/2)^n},\quad \eta_0=\tfrac12 \ \Rightarrow\ \log_2(1/\eta_n)=(3/2)^n \]

Linearise: with \(\eta_0=1/2\), \(1/\eta_n=2^{(3/2)^n}\). We need \(\eta_n\approx c_{\mathrm{gc}}^2\varepsilon=\tfrac12\cdot(\varepsilon/\varepsilon_0)=\tfrac12\times10^{-11}\), so \(\log_2(1/\eta_n)\approx\log_2(2\times10^{11})=37.5\). B

\[ (3/2)^n = 37.5 \ \Rightarrow\ n=\frac{\ln 37.5}{\ln 1.5}=\frac{3.624}{0.405}=8.9\ \Rightarrow\ n=9 \]

Solve for the integer depth (round up). Then the word length is \(\ell\sim5^{9}\). A

\[ \ell \sim 5^{9}=1.95\times10^{6} \]

Evaluate the length from the \(\times5\)-per-level recursion (Step 13). Consistent with the polylog estimate of Example A at comparable \(\varepsilon\). A

\[ n = 9\ \text{levels},\qquad \ell \sim 2\times10^{6}\ \text{gates} \]

Reading. Only nine levels of recursion take you from a coarse \(10\%\) net to twelve-digit accuracy — that is the doubly-logarithmic depth in action: each level roughly raises the accuracy exponent by \(3/2\). The price is \(5^9\approx2\times10^6\) gates. Units: \(n\) and \(\ell\) are dimensionless counts; \(\varepsilon,\eta\) are dimensionless.

Problems

(Level A) Verify the commutator exponent. If \(A,B\in\mathfrak{su}(2)\) with \(\lVert A\rVert,\lVert B\rVert=\delta\), show \(\lVert[A,B]\rVert=O(\delta^2)\) and hence that reproducing a residual of size \(\theta\) requires \(\delta=O(\sqrt\theta)\).
Solution
For \(2\times2\) matrices \(\lVert[A,B]\rVert=\lVert AB-BA\rVert\le\lVert AB\rVert+\lVert BA\rVert\le2\lVert A\rVert\lVert B\rVert=2\delta^2\), so \([A,B]=O(\delta^2)\). To match a residual \(\Delta=\exp([A,B])\) with rotation-angle \(\theta\), we need \(\lVert[A,B]\rVert\sim\theta\); setting \(2\delta^2=\theta\) gives \(\delta=\sqrt{\theta/2}=O(\sqrt\theta)\). This is precisely the square-root descent of Step 7.
(Level A) Solve the accuracy recursion. Given \(\varepsilon_n=c\,\varepsilon_{n-1}^{3/2}\) with \(c=2\) and \(\varepsilon_0=0.05\), compute \(\varepsilon_1,\varepsilon_2,\varepsilon_3\) and confirm it is contracting.
Solution
\(\varepsilon_1=2(0.05)^{1.5}=2\times0.01118=0.02236\). \(\varepsilon_2=2(0.02236)^{1.5}=2\times0.003344=0.006688\). \(\varepsilon_3=2(0.006688)^{1.5}=2\times5.47\times10^{-4}=1.094\times10^{-3}\). Each term is smaller than the last (0.05 → 0.0224 → 0.0067 → 0.0011), confirming contraction. Check the threshold: \(\eta_0=c^2\varepsilon_0=4\times0.05=0.2<1\), so convergence is guaranteed.
(Level B) Depth for target accuracy. Using \(\eta_n=\eta_0^{(3/2)^n}\) with \(\eta_0=0.2\), find the smallest \(n\) giving \(\eta_n<10^{-6}\).
Solution
Need \(\eta_0^{(3/2)^n}<10^{-6}\Rightarrow(3/2)^n\ln(0.2)<\ln(10^{-6})\Rightarrow(3/2)^n(-1.609)<-13.816\Rightarrow(3/2)^n>8.585\). Then \(n>\ln8.585/\ln1.5=2.150/0.405=5.31\), so \(n=6\). Check: \((1.5)^6=11.39\), \(\eta_6=0.2^{11.39}=\exp(11.39\times(-1.609))=\exp(-18.33)=1.1\times10^{-8}<10^{-6}\). Thus \(\boxed{n=6}\).
(Level B) Word-length vs accuracy exponent. Using \(\ell=O(5^n)\) and \((3/2)^n\propto\log(1/\varepsilon)\), derive the exponent \(c\) in \(\ell=O(\log^{c}(1/\varepsilon))\) and evaluate it numerically.
Solution
From \((3/2)^n\propto\log(1/\varepsilon)\), take logs: \(n\ln(3/2)=\ln\log(1/\varepsilon)+\text{const}\), so \(n=\log_{3/2}\log(1/\varepsilon)+O(1)\). Then \(5^n=5^{\log_{3/2}\log(1/\varepsilon)}=(\log(1/\varepsilon))^{\log_{3/2}5}\). Hence \(c=\log_{3/2}5=\ln5/\ln1.5=1.6094/0.4055=3.969\approx3.97\). So \(\ell=O(\log^{3.97}(1/\varepsilon))\).
(Level C) Total cost of a QFT-heavy circuit. A circuit uses \(m=10^{3}\) arbitrary single-qubit rotations, each to be compiled so the total error is \(<10^{-3}\). Using \(\ell=A\log^{3.97}(1/\varepsilon)\) with \(A=1\), estimate the total gate count and comment on the scaling.
Solution
Distribute error equally: each rotation to \(\varepsilon=10^{-3}/m=10^{-6}\) (sub-additivity, Step 2, guarantees total \(<m\varepsilon=10^{-3}\)). Per rotation: \(\ln(1/\varepsilon)=6\ln10=13.82\), \(\ell=(13.82)^{3.97}=\exp(3.97\times\ln13.82)=\exp(3.97\times2.626)=\exp(10.43)=3.4\times10^{4}\) gates. Total: \(m\times\ell=10^3\times3.4\times10^4=3.4\times10^{7}\) gates. Scaling comment: the per-gate cost grew only from the extra \(\log m\) inside \(\log(1/\varepsilon)\) — refining accuracy from \(10^{-3}\) to \(10^{-6}\) multiplied the length by just \((13.82/6.9)^{3.97}\approx15\), not by \(10^3\). This polylogarithmic inflation is the practical payoff of SK: the overhead of discretisation is a small polylog factor, not a polynomial blow-up.