Fixed-Arity Unitary Error Budget

For each one-qubit factor $G_j\in U(2)$, determinant multiplicativity and $G_j^{\ast }{G}_j=I$ give $\mathrm{\mid }\det G_j{\mathrm{\mid }}^2=1$. Thus [F7] gives $\det G_j=e^{i{\theta }_j}$ for a real ${\theta }_j$. Put ${\varphi }_j={\theta }_j\mathrm{/}2$ and $S_j=e^{-i{\varphi }_j}{G}_j$. Then $\det S_j=e^{-2i{\varphi }_j}\det G_j=1$ and $S_j$ is unitary, so $S_j\in SU(2)$ and $G_j=e^{i{\varphi }_j}{S}_j$.

Put $h=\min ({\eta }_0,\epsilon \mathrm{/}m)>0$. Let $r$ be the least nonnegative integer with $2^{-r}\le h$ and put $\delta =2^{-r}$. Such an $r$ exists since $2^{-r}\to 0$; since $h<1$, minimality gives $h\mathrm{/}2<\delta \le h$. Thus $\delta$ is rational, satisfies $0<\delta \le {\eta }_0$ and $\delta \le \epsilon \mathrm{/}m$, and is a permitted input to the compiler in [F1]. Apply it to each $S_j$. It gives a gate word $W_j$ with $\mathrm{\parallel }{S}_j-W_j\mathrm{\parallel }\le \delta$. The phase factors $e^{i{\varphi }_j}$ commute with all factors and multiply to one scalar for the entire circuit; after factoring it out, the exact and compiled products have the same CNOT slots and respectively $S_j$ and $W_j$ in each one-qubit slot.

First justify the full-register error at each local slot. Group its one-qubit support first and unused wires second, using the unitary wire permutation of [F10]. For a finite orthonormal basis $(e_{\mathrm{\ell }})$ of the unused register, every vector is uniquely $v={\sum }_{\mathrm{\ell }}{v}_{\mathrm{\ell }}\otimes e_{\mathrm{\ell }}$, and the product inner product gives $\mathrm{\parallel }v{\mathrm{\parallel }}^2={\sum }_{\mathrm{\ell }}\mathrm{\parallel }{v}_{\mathrm{\ell }}{\mathrm{\parallel }}^2$. For a local difference $A$, it also gives $\mathrm{\parallel }(A\otimes I)v{\mathrm{\parallel }}^2={\sum }_{\mathrm{\ell }}\mathrm{\parallel }A{v}_{\mathrm{\ell }}{\mathrm{\parallel }}^2\le \mathrm{\parallel }A{\mathrm{\parallel }}^2{\sum }_{\mathrm{\ell }}\mathrm{\parallel }{v}_{\mathrm{\ell }}{\mathrm{\parallel }}^2=\mathrm{\parallel }A{\mathrm{\parallel }}^2\mathrm{\parallel }v{\mathrm{\parallel }}^2$ by [F8]. Thus $\mathrm{\parallel }A\otimes I\mathrm{\parallel }\le \mathrm{\parallel }A\mathrm{\parallel }$. Conjugation by the wire permutation preserves norm, since a unitary preserves vector norms and maps the unit sphere onto itself. This includes the empty unused register. Apply this to each $S_j-W_j$ from step 2.1, giving full-register slot error at most $\delta$. Index the full ordered circuit product by $q=m+c$ slots, so the two products are $A_q\cdots A_1$ and $B_q\cdots B_1$. At a CNOT slot set $A_r=B_r$ to that exact gate; at a one-qubit slot use the exact $S_j$ and its compiled word $W_j$. Insert one factor at a time to obtain $A_q\cdots A_1-B_q\cdots B_1={\sum }_{r=1}^q{A}_q\cdots A_{r+1}(A_r-B_r)B_{r-1}\cdots B_1$. Every surrounding factor is unitary: exact factors, compiled words, and CNOTs are all unitary. For a unitary $Q$, $\mathrm{\parallel }Qv\mathrm{\parallel }=\mathrm{\parallel }v\mathrm{\parallel }$ for every unit vector $v$, so [F8] gives $\mathrm{\parallel }Q\mathrm{\parallel }=1$. The operator-norm triangle inequality follows from [F8] by applying [F9] to each unit input and taking the maximum. Then [F2] bounds the product difference by the sum of the $q$ factor errors. The CNOT slots contribute zero, and the $m$ one-qubit slots each contribute at most $\delta$, giving $m\delta \le \epsilon$. The scalar from step 2.1 is a single whole-circuit phase, proving the projective operator bound.

The unit circle is a closed subset of the closed unit ball in $\mathbb{C}$, so it is compact by [F6]. The continuous function $\lambda \mapsto \mathrm{\parallel }U-\lambda C\mathrm{\parallel }$ therefore attains its minimum at some $\mathrm{\mid }\lambda \mathrm{\mid }=1$. The phase from step 3.1 gives one value at most $\epsilon$, so this minimum is also at most $\epsilon$. By [F4], diagonalize $E$ in an orthonormal basis with eigenvalues ${\lambda }_1,\dots ,{\lambda }_{2^k}$. Nonnegativity [F3] makes each ${\lambda }_i\ge 0$, and $\mathrm{\parallel }E\mathrm{\parallel }\le 1$ gives ${\lambda }_i\le 1$ by applying the norm to a corresponding unit eigenvector. Define $E^{1\mathrm{/}2}$ in this basis by diagonal entries $\sqrt{{\lambda }_i}$, which exist by [F5]. Its square is $E$, it is self-adjoint, and direct calculation on coordinates gives $\mathrm{\parallel }{E}^{1\mathrm{/}2}\mathrm{\parallel }={\max }_i\sqrt{{\lambda }_i}\le 1$. The factors $U,C$ are unitary, so [F8] gives $\mathrm{\parallel }U\psi \mathrm{\parallel }=\mathrm{\parallel }C\psi \mathrm{\parallel }=1$. The two vectors $E^{1\mathrm{/}2}U\psi$ and $E^{1\mathrm{/}2}\lambda C\psi$ have norms at most $1$, and their distance is at most $\epsilon$ by step 3.1 and [F2]. The reverse triangle inequality from [F9] gives $\mathrm{\mid }\mathrm{\parallel }x\mathrm{\parallel }-\mathrm{\parallel }y\mathrm{\parallel }\mathrm{\mid }\le \mathrm{\parallel }x-y\mathrm{\parallel }$ for these vectors; factoring the difference of their squared norms therefore bounds it by $(1+1)\epsilon =2\epsilon$. Since the scalar phase does not change a norm, this proves the event bound.

Each one-qubit word uses $O({\log }^{{\log }_{3\mathrm{/}2}5}(1\mathrm{/}\delta ))$ gates by [F1]. Since $1\mathrm{/}\delta <2\max (1\mathrm{/}{\eta }_0,m\mathrm{/}\epsilon )$ and $m\mathrm{/}\epsilon >2$, this is $O({\log }^{{\log }_{3\mathrm{/}2}5}(m\mathrm{/}\epsilon ))$, with constants depending on the fixed base-net radius. Summing over $m$ factors and adding the $c$ exact CNOTs gives the stated count. The factorization and all replacements use the same wires, so no ancillas are introduced.