Effective synthesis of fixed-dimensional unitaries

If $D=1$, output the empty circuit: the scalar $1\times 1$ unitary is immaterial up to the allowed whole-circuit phase. Assume $D\ge 2$. Every Pauli-$X$ requested anywhere in this construction is emitted as the QC14 word $H{T}^{4}H$: the exact matrices in [F9] give $T^4=Z$ and $HZH=X$. First construct exact computational-basis transpositions for row pivoting. For bit strings $x,y$, flip their differing positions in order to form a Gray path $g_0=x,\dots ,g_d=y$. The adjacent swap $g_j\leftrightarrow g_{j+1}$ is an $X$ on their differing bit, controlled on the other $q-1$ fixed bits; for each control required to be $0$, apply the same exact $H{T}^{4}H$ word to that control wire before computing the control conjunction (or before the one-control gate), then undo it after the controlled operation and any conjunction uncomputation. A conjunction of at least two controls is computed into clean bits by a chain of Toffoli gates, the target $X$ is applied under the last conjunction bit, and the chain is reversed; with no controls use the same $H{T}^{4}H$ word, and with one positive control use CNOT. Toffoli is exact over the gate alphabet: for bits $a,b,c$, $4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c)+(a\oplus b\oplus c)\mathrm{.}$ Compute each parity into a clean bit by CNOTs, apply $T$ for positive terms and $T^{†}$ for negative terms, and uncompute; the resulting phase is $(-1{)}^{abc}$. Conjugating the third bit by $H$ gives Toffoli. The product of swaps along the path except its last edge, followed by the last swap and the reversed prefix, is exactly the transposition of $x,y$. In column $j$, earlier columns have already been made zero below row $j$, so the remaining tail has norm one by unitarity. Approximate its entry magnitudes to error at most $1\mathrm{/}(8D)$ and choose the least row among those with largest approximate magnitude as pivot; the selected exact magnitude is at least $1\mathrm{/}\sqrt{D}-1\mathrm{/}(4D)\ge 1\mathrm{/}(2\sqrt{D})$. Move that row to $j$ by the exact transposition just constructed, which preserves earlier zeros. For each lower entry $b$ and pivot $a$, use the determinant-one Givens block $r^{-1}\left(\begin{array}{cc}\bar{a}& \bar{b}\\ -b& a\end{array}\right)$, $r=(\mathrm{\mid }a{\mathrm{\mid }}^2+\mathrm{\mid }b{\mathrm{\mid }}^2{)}^{1\mathrm{/}2}$; direct multiplication sends $(a,b{)}^T$ to $(r,0{)}^T$. The pivot remains bounded below, so every division is conditioned and no exact zero test is needed. Fixed dimension, [F7], and the pivot lower bound give polynomial-time Cauchy names for the Givens factors and a diagonal unitary remainder. If the recorded left multipliers are $Q_1,\dots ,Q_s$, the terminal upper-triangular unitary is $\mathrm{\Delta }=Q_s\cdots Q_{1}U$; its first column has only a unit-modulus first entry, orthogonality forces the rest of the first row to vanish, and induction on the trailing principal block shows $\mathrm{\Delta }$ is diagonal. Hence $U=Q_1^{-1}\cdots Q_s^{-1}\mathrm{\Delta }$, an exact factorization in reverse chronological application order.

Each Givens factor from step 1.1 is an $SU(2)$ block on two basis strings $x,y$, in the two-level sense of [F8]. Flip their differing bit positions in order to form a Gray path $g_0=x,\dots ,g_d=y$. Controlled-$X$ gates on the other fixed bits swap $g_j,g_{j+1}$ for $j<d-1$; for the desired ordered block $V$, the final controlled one-qubit gate uses native block $V$ when the differing target bit of $g_{d-1}$ is $0$, and $XVX$ when that bit is $1$. In the latter case the native target order is $(y,g_{d-1})$, so conjugating by $X$ gives precisely $V$ in the required order $(g_{d-1},y)$. Reversing the swaps therefore gives the exact ordered two-level action. Both possible native blocks remain in $SU(2)$ and have polynomial-time Cauchy names. Every intermediate controlled-$X$ is implemented by the conjunction and target construction of step 1.1, including the exact $H{T}^{4}H$ expansion for its target $X$. With middle block $X$, the same path conjugation is the exact basis transposition used in step 1.1. When $q=1$, the order-corrected native block is itself an unconditional one-qubit $SU(2)$ gate. For $q\ge 2$, reduce each multi-control to one control by computing its $q-1$-bit conjunction into clean bits with the exact Toffoli gates from step 1.1 and then uncomputing. For a one-controlled $SU(2)$ block, choose $R_z(\alpha )R_y(\beta )R_z(\gamma )$. For $R=R_z$ or $R_y$, the chronological sequence “apply $R(\theta \mathrm{/}2)$ to the target, CNOT, apply $R(-\theta \mathrm{/}2)$ to the target, CNOT” has denotation $\mathrm{CNOT}(I\otimes R(-\theta \mathrm{/}2))\mathrm{CNOT}(I\otimes R(\theta \mathrm{/}2))\mathrm{.}$ On control $0$ the two rotations cancel; on control $1$, $XR(-\theta \mathrm{/}2)X=R(\theta \mathrm{/}2)$ by the exact $R_y,R_z$ matrices in [F9], so the active block is $R(\theta )$. This proves the controlled Euler product using only unconditional one-qubit rotations and CNOTs. The closed forms from [F9] give $R_z(\theta +4\pi )=R_z(\theta )$ and $R_y(\theta +4\pi )=R_y(\theta )$; reduce each Euler angle modulo $4\pi$ to a representative in $[0,4\pi )$. For a candidate mesh angle $\theta \in [0,16]$ and $a\in \{y,z\}$, write $R_a(\theta )=e^{A_a(\theta )}$ with $A_a(\theta )=-i\theta {\sigma }_a\mathrm{/}2$. Since $\mathrm{\parallel }{A}_a(\theta )\mathrm{/}9\mathrm{\parallel }\le 8\mathrm{/}9<1$, the interval routine [F7] evaluates $e^{A_a(\theta )\mathrm{/}9}$ in its stated domain; multiplying nine such matrices evaluates $R_a(\theta )$, with guard precision chosen so each three-rotation product and target has certified Frobenius error at most $\eta \mathrm{/}(100C_D)$. Put $M=\lceil 1600C_D\mathrm{/}\eta \rceil$ and use the rational mesh $\{16j\mathrm{/}M:0\le j\le M\}$ in each coordinate. Since $4\pi <16$, each reduced Euler angle is within $16\mathrm{/}M\le \eta \mathrm{/}(100C_D)$ of a mesh point. The exact rotation formula gives $\mathrm{\parallel }{R}_a(u)-R_a(v)\mathrm{\parallel }\le \mathrm{\mid }u-v\mathrm{\mid }\mathrm{/}2$, so the product at one such mesh triple is within $\eta \mathrm{/}(8C_D)$ of the target. For each candidate, compute a certified Frobenius-distance upper bound from the entry intervals; its square-root input is scaled by $1\mathrm{/}9$, since the squared distance between two $2\times 2$ unitaries is at most $8$, and then rescaled by $3$. Select the first mesh product whose upper bound is at most $\eta \mathrm{/}(4C_D)$; the guaranteed nearby mesh point passes because its true Frobenius distance is at most $\sqrt{2}\eta \mathrm{/}(8C_D)$ and the interval error is at most $\eta \mathrm{/}(100C_D)$. Every selected product therefore has operator error at most $\eta \mathrm{/}(4C_D)$. Here $C_D\ge 1$ is a fixed upper bound for the total number of rotation factors requiring approximation, including the recursive diagonal construction described below; for example, for $q\ge 1$ take $C_D=\max \{1,3D(D-1)+(D-1)(2q-1)\}$. The search uses $O((C_D\mathrm{/}\eta {)}^3)$ candidates and only rational interval comparisons, not an exact-real branch test.

Factor the diagonal remainder as $\mathrm{\Delta }=d_0\mathrm{diag}(1,(d_z\mathrm{/}{d}_0{)}_{z\mathrm{\ne }0})$. Since $\mathrm{\mid }{d}_0\mathrm{\mid }=1$, every ratio ${\tilde{d}}_z=d_z\mathrm{/}{d}_0$ is a unit scalar with a polynomial-time Cauchy name by [F7]: the denominator has the uniform lower bound one. For each $z\mathrm{\ne }0$, choose a bit position where $z$ is one, compute the condition that all other bits match $z$, and apply $\mathrm{diag}(1,{\tilde{d}}_z)$ to the chosen bit controlled by that condition; this phases $\mathrm{\mid }z⟩$ and leaves its partner with chosen bit zero unchanged. If $q=1$ the condition is empty and the phase is unconditional. The common factor $d_0$ is the single global scalar for the complete diagonal remainder. Approximate each ${\tilde{d}}_z$ by scanning an $M$-point rational angle grid, with $M\ge 16\pi D\mathrm{/}\eta$, and accept a grid point whose certified chordal distance is at most $4\pi \mathrm{/}M$; a nearest grid point is within $\pi \mathrm{/}M$, so a valid one is found after $O(M)$ evaluations using [F7]. Write its phase as $e^{i\theta }$. Implement a phase on a pattern of $k$ original data bits by induction on $k$. For $k=1$, use $\mathrm{diag}(1,e^{i\theta })=e^{i\theta \mathrm{/}2}{R}_z(\theta )$ on that data bit (conjugated by exact $X$ gates for pattern zero), retaining its scalar as a whole-circuit scalar. For $k\ge 2$, choose an original data target and compute the conjunction of the other $k-1$ original data controls with the exact Boolean circuits of step 1.1 (one control needs no workspace). Apply controlled $R_z(\theta )$ to the original target by the two target rotations and two CNOTs of step 2.1, and uncompute the conjunction immediately. For a signed pattern, conjugate the zero-valued controls by exact $X$ gates before computing the conjunction and undo them immediately after uncomputing; conjugate a zero-valued target by $X$ around the controlled rotation. Thus all data bits are restored to their original pattern coordinates before recursion. Apply, recursively, phase $e^{i\theta \mathrm{/}2}$ on the matching pattern of the $k-1$ original control data bits. On a nonmatching control pattern both ideal operations are identity; on a matching one their product is $e^{i\theta \mathrm{/}2}{R}_z(\theta )=\mathrm{diag}(1,e^{i\theta })$ on the target, or its $X$-conjugate when the target pattern bit is zero. This proves the required pattern phase, up to just the base case's whole-circuit scalar. Crucially, every rotation is on an original data bit: no computed flag receives a rotation or an approximating word. Each conjunction block is uncomputed before recursion changes any of its data controls. Its clean bits therefore return exactly to zero even when arbitrary one-qubit words replace the target rotations, because those words and their controlling CNOTs never alter the conjunction inputs or flags. The same argument applies to the Givens blocks in step 2.1. The phase recursion uses $b_1=1$, $b_k=b_{k-1}+2=2k-1$ one-qubit factors and $O(k^2)$ exact Boolean gates, reusing $O(k)$ clean bits. Thus the diagonal remainder is implemented by unconditional rotations, CNOTs and the fixed conjunction circuits above, with total phase error at most $\eta \mathrm{/}4$, since there are fewer than $D$ entries and $M\ge 16\pi D\mathrm{/}\eta$.

All one-qubit rotations in step 2.1 and step 3.1 are unconditional factors. Compile their determinant-one matrices using [F2]–[F3]; any scalar phases from normalized Clifford–T letters then multiply the full circuit by a single global scalar, never a control block. Since $D$ is fixed, take $M_D=C_D$, which also bounds the recursive phase factors. The accepted mesh approximations in step 2.1 contribute at most $\eta \mathrm{/}4$ total error, and step 3.1 contributes at most $\eta \mathrm{/}4$ for diagonal phases. For each factor request Solovay–Kitaev error $\min \{\eta \mathrm{/}(2M_D),{\eta }_0\}$; this lies in the compiler's stated domain and is no larger than $\eta \mathrm{/}(2M_D)$, so synthesis contributes at most $\eta \mathrm{/}2$. After factoring out whole-circuit scalars, the telescoping identity bounds total operator error by the sum, at most $\eta$. The Givens pivots stay at least $1\mathrm{/}(2\sqrt{D})$; the Euler mesh has $O((C_D\mathrm{/}\eta {)}^3)$ candidates and each diagonal phase grid has $O(D\mathrm{/}\eta )$ candidates, with fixed $C_D,D$. Parse the binary numerator and denominator of $\eta$ in $O(\mathrm{\ell }(\eta ))$ time. The mesh sizes, rational comparisons, and compiler tolerances are computed by integer arithmetic on numbers of $O(\mathrm{\ell }(\eta )+\log (1\mathrm{/}\eta )+1)$ bits. The certified arithmetic precision is $O(\log (1\mathrm{/}\eta )+1)$; [F1] charges each target query polynomial time in $b$ plus this precision, and [F3] also charges the encoding length of each derived tolerance. Thus all arithmetic and compiler bit time, including reading $\eta$ and printing the full gate list, is polynomial in $b+\mathrm{\ell }(\eta )+1\mathrm{/}\eta$. The number of rotation factors is fixed, and [F3] bounds each compiled word length polynomially in $\log (1\mathrm{/}\eta )+1$, giving the claimed gate-count bound independent of the tolerance encoding length. In the coordinates of [F10], the output gate count and wire count are polynomial, as is the deterministic full-list generator time; the ancilla count is constant because $q$ is fixed and the decompositions reuse $O(q)$ work bits. Each compiled word acts only on original data wires; the exact Boolean compute/control/uncompute blocks return every work bit exactly to zero, so the resulting data operator $V$ is well-defined with exact clean-ancilla return, not merely small workspace leakage.