Finite-Precision Bit Complexity of the SU(2) Solovay–Kitaev Compiler

Set $q_0=4096{\eta }_0<1$. The exact error recurrence is ${\eta }_{j+1}=64{\eta }_j^{3\mathrm{/}2}$, so for $q_j=4096{\eta }_j$ we have $q_{j+1}=q_j^{3\mathrm{/}2}$ and ${\eta }_j=2^{-12}{q}_0^{(3\mathrm{/}2{)}^j}$. Choose fixed integers $K,A$ with $q_0^{(3\mathrm{/}2{)}^K}<1\mathrm{/}2$ and $2^A{q}_0\ge 1$. Let $j_N$ be the least integer with $(3\mathrm{/}2{)}^{j_N}\ge N$ and set $J=K+j_N$. Then $q_J\le 2^{-N}\le \epsilon \mathrm{/}2$, hence ${\eta }_J\le \epsilon$. Write the encoded rational tolerance as $\epsilon =p\mathrm{/}q$ with positive integers $p,q$. Since $q<2^{s_{\epsilon }}$ and $p\ge 1$, we have $N\le s_{\epsilon }+1$; binary search over integers $0,\dots ,s_{\epsilon }+1$ using exact comparisons $2^{N}p\ge 2q$ computes $N$ in time polynomial in $s_{\epsilon }$. The integer $j_N$ is found by repeated rational multiplication by $3\mathrm{/}2$; $J=O(\log N)$. Put $B=12+A\lceil (3\mathrm{/}2{)}^J\rceil$, $L_J=L_0{5}^J$, and $P=64(B+\lceil {\log }_2(L_J+1)\rceil +32)$. For every $j\le J$, ${\eta }_j\ge 2^{-B}$; also $B=O(N)$, ${\log }_2(L_J+1)=O(\log N)$, and $P=O(N)$. Each routine is requested at precision $P$ or higher, so word-product errors and interval widths are below $2^{-B-20}$; in particular, an interval for ${\tau }_j:={\eta }_j\mathrm{/}128$ has width at most ${\tau }_j\mathrm{/}4$. Compute these recurrence intervals from the rational ${\eta }_0$ using certified square-root and multiplication calls at precision $P$; since $2^{-P}\le 2^{-B-9}$, each resulting interval is narrower than ${\eta }_j\mathrm{/}512$.

At level zero, compute certified Frobenius-distance intervals from the target to each word in the fixed base net, and return the first word whose upper endpoint is at most ${\eta }_0$. By the base-net certificate in [F6], some word is at operator-norm distance at most ${\eta }_0\mathrm{/}4$; its Frobenius distance is at most $\sqrt{2}{\eta }_0\mathrm{/}4$. Since the fixed dimension is two, the chosen precision $P$ makes the Frobenius-distance interval error less than ${\eta }_0\mathrm{/}8$, so this word's upper endpoint is below ${\eta }_0$. For the selected word, operator norm is bounded by Frobenius norm, giving actual error at most ${\eta }_0$.

At a nonbase node of level $j$, recursively obtain the exact gate word $A$ for the lower-level call and set $D=U{A}^{\ast }$. Inductively, by [F9], for any unitary $Q$ one has $\mathrm{\parallel }XQ\mathrm{\parallel }={\max }_{\mathrm{\parallel }v\mathrm{\parallel }=1}\mathrm{\parallel }XQv\mathrm{\parallel }={\max }_{\mathrm{\parallel }w\mathrm{\parallel }=1}\mathrm{\parallel }Xw\mathrm{\parallel }=\mathrm{\parallel }X\mathrm{\parallel }$ because $Q$ maps the unit sphere bijectively to itself; thus $\mathrm{\parallel }D-I\mathrm{\parallel }=\mathrm{\parallel }(U-A)A^{\ast }\mathrm{\parallel }=\mathrm{\parallel }U-A\mathrm{\parallel }\le {\eta }_{j-1}<1\mathrm{/}2$. Use interval routines to enclose $X=\log D$ and $r=\mathrm{\parallel }X\mathrm{\parallel }$ by rational intervals $[r_{-},r_{+}]$ of width at most ${\tau }_j\mathrm{/}4$, and compute a rational interval $[{\tau }_j^{-},{\tau }_j^{+}]$ for ${\tau }_j={\eta }_j\mathrm{/}128$ of width at most ${\tau }_j\mathrm{/}4$. These intervals are certified; branch by comparing rational endpoints: if $r_{+}\le 2{\tau }_j^{-}$, return $A$ with no correction. Then $r\le r_{+}\le 2{\tau }_j^{-}\le 2{\tau }_j$. Since the eigenvalues of the traceless skew-Hermitian $X$ are $ir,-ir$ and $D=e^X$, $\mathrm{\parallel }D-I\mathrm{\parallel }=2\mathrm{\mid }\sin (r\mathrm{/}2)\mathrm{\mid }\le r\le 2{\tau }_j<{\eta }_j$; here $\mathrm{\mid }\sin t\mathrm{\mid }\le \mathrm{\mid }t\mathrm{\mid }$ follows from [F8], the mean value theorem, and [F7]. Otherwise, $r_{+}>2{\tau }_j^{-}$. The interval widths imply ${\tau }_j^{-}\ge 3{\tau }_j\mathrm{/}4$ and $r_{-}\ge r_{+}-{\tau }_j\mathrm{/}4$, hence $r\ge r_{-}>2{\tau }_j^{-}-{\tau }_j\mathrm{/}4\ge 5{\tau }_j\mathrm{/}4>{\tau }_j$. Thus the balanced branch has the certified denominator lower bound it needs. The branch comparison uses only rational interval endpoints, not an exact-real comparison with ${\tau }_j$ or an exact-zero test.

In the balanced branch write $X=iv\cdot \sigma$, so $\mathrm{\mid }v\mathrm{\mid }=r$ by [F5], and set $u=v\mathrm{/}r$. At least one coordinate satisfies $\mathrm{\mid }{u}_k\mathrm{\mid }\le 1\mathrm{/}\sqrt{3}$. Compute intervals for $\mathrm{\mid }{u}_1\mathrm{\mid },\mathrm{\mid }{u}_2\mathrm{\mid },\mathrm{\mid }{u}_3\mathrm{\mid }$ of width at most $1\mathrm{/}16$, and choose the first whose certified upper endpoint is at most $3\mathrm{/}4$; one exists since $1\mathrm{/}\sqrt{3}+1\mathrm{/}16<3\mathrm{/}4$. For its coordinate vector $e_k$, set $e=(u\times e_k)\mathrm{/}\mathrm{\mid }u\times e_k\mathrm{\mid }$, $a=\sqrt{r\mathrm{/}2}e$, and $b=-\sqrt{r\mathrm{/}2}(u\times e)$. The denominator is at least $\sqrt{7}\mathrm{/}4>1\mathrm{/}2$, so interval normalization is conditioned; also $e\perp u$, $\mathrm{\mid }u\times e\mathrm{\mid }=1$, and $a\times b=-(r\mathrm{/}2)u=-v\mathrm{/}2$. Thus, for $A_0=ia\cdot \sigma$ and $B_0=ib\cdot \sigma$, the Pauli commutator identity gives $[A_0,B_0]=X$. The near-identity bound gives $r\le 2{\eta }_{j-1}$, hence $\mathrm{\parallel }a\mathrm{\parallel }=\mathrm{\parallel }b\mathrm{\parallel }=\sqrt{r\mathrm{/}2}\le \sqrt{{\eta }_{j-1}}$. Exponentiating defines exact $V=e^{A_0},W=e^{B_0}$; interval routines provide Cauchy names for these exact child targets. The lower bound $r>{\tau }_j\ge 2^{-B-7}$ from step 2.1 and the cross-product bound show every denominator has at most $B+O(1)$ conditioning bits. For example, with $Q_a=(a\cdot \sigma )\mathrm{/}\mathrm{\mid }a\mathrm{\mid }$, [F5] gives $Q_a^{\ast }=Q_a$, $Q_a^2=I$, and $\mathrm{tr}(Q_a)=0$. Grouping the even and odd terms of the exponential series gives $V=\cos \mathrm{\mid }a\mathrm{\mid }I+i\sin \mathrm{\mid }a\mathrm{\mid }{Q}_a$ by [F7]. This formula implies $V^{\ast }V=I$; writing $Q_a=\left(\begin{array}{cc}x& z\\ \bar{z}& -x\end{array}\right)$, the identity $Q_a^2=I$ gives $x^2+\mathrm{\mid }z{\mathrm{\mid }}^2=1$, and direct determinant calculation then gives $\det V={\cos }^2\mathrm{\mid }a\mathrm{\mid }+{\sin }^2\mathrm{\mid }a\mathrm{\mid }=1$. The same calculation gives $W\in SU(2)$.

Put $s=\mathrm{\parallel }{A}_0\mathrm{\parallel }=\mathrm{\parallel }{B}_0\mathrm{\parallel }=\sqrt{r\mathrm{/}2}\le \sqrt{{\eta }_{j-1}}<1\mathrm{/}64$. The Hermitian involution $Q_a$ in step 3.1 has eigenvalues $1,-1$, so its displayed exponential formula gives $\mathrm{\parallel }V-I\mathrm{\parallel }=\mathrm{\mid }{e}^{is}-1\mathrm{\mid }=2\mathrm{\mid }\sin (s\mathrm{/}2)\mathrm{\mid }\le s$, and likewise $\mathrm{\parallel }W-I\mathrm{\parallel }\le s$. Here the scalar exponential product identity follows by multiplying its absolutely convergent series; together with [F7] it gives the sine expression, and [F8] gives the last inequality as in step 2.1. From [F9], applying the vector triangle inequality to unit inputs gives the operator-norm triangle inequality, and $\mathrm{\parallel }YZv\mathrm{\parallel }\le \mathrm{\parallel }Y\mathrm{\parallel }\mathrm{\parallel }Zv\mathrm{\parallel }\le \mathrm{\parallel }Y\mathrm{\parallel }\mathrm{\parallel }Z\mathrm{\parallel }$ gives submultiplicativity. Expand $e^{A_0}{e}^{B_0}{e}^{-A_0}{e}^{-B_0}$ in homogeneous degrees: degrees zero, one and two sum to $I+[A_0,B_0]=I+X$, and the sum of norms in degree $n$ is at most $(4s{)}^n\mathrm{/}n!$ by the multinomial identity. Its remaining tail is therefore at most $(4s{)}^3{e}^{4s}\mathrm{/}6<32s^3$, since $4s<1$ and $e={\sum }_{n\ge 0}1\mathrm{/}n!<3$. Also $\mathrm{\parallel }X\mathrm{\parallel }=\mathrm{\parallel }[A_0,B_0]\mathrm{\parallel }\le 2s^2$, so $\mathrm{\parallel }{e}^X-I-X\mathrm{\parallel }\le 2s^4{e}^{2s^2}\le s^3$; indeed $e^{2s^2}\le (1-2s^2{)}^{-1}$ and $2s\mathrm{/}(1-2s^2)<1$. Since $D=e^X$ and $V^{\ast }=e^{-A_0},W^{\ast }=e^{-B_0}$, these estimates give $\mathrm{\parallel }D-VW{V}^{\ast }{W}^{\ast }\mathrm{\parallel }\le 33s^3\le 40{\eta }_{j-1}^{3\mathrm{/}2}$ for these exact factors, independently of the existential clause of [F3].

Recursively compile these exact $V,W$ at level $j-1$, obtaining words $\tilde{V},\tilde{W}$ within ${\eta }_{j-1}$ of them. Step 4.1 approximates $D$ by $VW{V}^{\ast }{W}^{\ast }$ within $40{\eta }_{j-1}^{3\mathrm{/}2}$ and verifies both factor distances required by the cancellation bound in [F3], which adds at most $5{\eta }_{j-1}^{3\mathrm{/}2}$ when $V,W$ are replaced by $\tilde{V},\tilde{W}$. Since $U-(\tilde{V}\tilde{W}{\tilde{V}}^{\ast }{\tilde{W}}^{\ast }A)=(D-\tilde{V}\tilde{W}{\tilde{V}}^{\ast }{\tilde{W}}^{\ast })A$ and $A$ is unitary, [F9] right-multiplication invariance gives the same error norm. Thus the returned word $\tilde{V}\tilde{W}{\tilde{V}}^{\ast }{\tilde{W}}^{\ast }A$ approximates $U$ within $45{\eta }_{j-1}^{3\mathrm{/}2}\le {\eta }_j$. Together with the small-residual branch and step 1.2, induction proves the claimed error. The recursion has at most three calls per node and each output length satisfies $L_j\le 5L_{j-1}$, so its expanded length is at most $L_0{5}^J$.

Every exact target in a recursive call is represented by a Cauchy name obtained from its parent using matrix products, logarithms, Pauli coordinates, division by $r\ge {\tau }_j$, normalization, square roots and exponentials. In the balanced branch the only small square-root radicand is $x=r\mathrm{/}2>{\tau }_j\mathrm{/}2$. Request an enclosing interval of width at most $2^{-b}\sqrt{{\tau }_j}\mathrm{/}16$ and at most ${\tau }_j\mathrm{/}4$; its endpoints are then at least ${\tau }_j\mathrm{/}4$. The identity $\mathrm{\mid }\sqrt{x}-\sqrt{y}\mathrm{\mid }=\mathrm{\mid }x-y\mathrm{\mid }\mathrm{/}(\sqrt{x}+\sqrt{y})$ bounds the spread of their square roots by $2^{-b}\mathrm{/}16$. Both width requirements follow from $b+O(1+{\log }_2(1\mathrm{/}{\tau }_j))$ input bits, using the levelwise dyadic lower bound ${\tau }_j\ge 2^{-19-A\lceil (3\mathrm{/}2{)}^j\rceil }$ from step 1.1; no exact square-root comparison is needed to select the precision. Bisect the rational endpoints to $b+O(1)$ output bits as in [F4], costing cubic bit time in the working precision. Use this conditioned routine for $\sqrt{r\mathrm{/}2}$. For norms used in normalization, the Lipschitz estimate $\mathrm{\mid }\mathrm{\parallel }v\mathrm{\parallel }-\mathrm{\parallel }{v}^{\mathrm{\prime }}\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }v-v^{\mathrm{\prime }}\mathrm{\parallel }$ in [F4] likewise permits additive input precision; computing the norm of the rational midpoint by square-root bisection needs no further parent query. Each such query uses one parent matrix query at the required guard precision; the query returns all entries together, which the routines reuse. The interval routines have conditioning-bit bound $O(1+{\log }_2(1\mathrm{/}{\eta }_j))$. The sum of these bounds along a branch is $O(B)$, because ${\log }_2(1\mathrm{/}{\eta }_j)\le 12+A(3\mathrm{/}2{)}^j$ is geometric. Put $r_0=\max (c,3)$. Induction through the at most $J$ derived-name layers therefore bounds a query at precision $b$ by $O(J(b+B+\log L_J+1{)}^{r_0})$. At requested precision $P=O(N)$, this is polynomial in $N$ for every node. The finitely many algebraic gate entries are enclosed once by the minimal-polynomial bisection in [F4], in $O(P^3)$ time. The recursion tree has at most $3^J$ nodes. After this precomputation, direct evaluation of all word matrices costs at most $O(3^{J}J{L}_J{P}^2)$ bit operations; the remaining fixed-dimensional interval routines and derived target-name evaluations cost at most $O(3^{J}J(P+B+\log L_J+1{)}^{r_0})$. Since $J=O(\log N)$, $5^J=O(N^{{\log }_{3\mathrm{/}2}5})$ and $3^J=O(N^{{\log }_{3\mathrm{/}2}3})$, each of these costs, together with reading $\epsilon$ and printing the expanded output, is bounded by $O((N+s_{\epsilon }{)}^{c+10})$.