Effective Exact Gate Factors for Fixed Local Unitaries

Fixed finite compositions of polynomial-Cauchy scalars remain polynomial-Cauchy under the operations of [F1], provided each nonzero divisor has a fixed positive lower bound. There are only finitely many scalars in a fixed finite expression tree, so for its nonzero divisors some integer $B$ has $\mathrm{\mid }z\mathrm{\mid }\ge 2^{-B}$ throughout; $B$ may be hardcoded. A fixed zero is returned as zero. Nonnegative roots are allowed even at zero, and nested roots only multiply the requested precision by a fixed constant at each of finitely many levels. Thus the finite compositions still use polynomial time in $p+1$. Conjugation merely changes an imaginary sign.

The path instruction in [F3] is an exact factorization. Each prescribed pattern-controlled $X$ exchanges precisely the adjacent path labels $g_j,g_{j+1}$ and fixes every other computational-basis label, because its $n-1$ controls must match the common bits. Let $P$ be the permutation effected by the swaps in their stated order. Then $P(x)=g_{d-1}$ and $P(y)=y=g_d$. The middle block, with the stated block reversal when the target bit of $g_{d-1}$ is $1$, acts by $V$ on the ordered pair $(g_{d-1},g_d)$ and fixes its complement. The complete chronological list therefore has matrix $P^{\ast }MP$, where $M$ is that middle block. Since $P$ is a permutation and maps $x,y$ to the selected pair, no other basis label maps into that pair; the conjugate acts by $V$ on $(x,y)$ and fixes every other basis vector. The controlled-gate expansions are exact by [F4] and [F5], and the negative-control conjugations retain their exact matrices. Thus every two-level factor used here is exactly the one specified by [F3], including its scalar phase.

A square root of any fixed polynomial-Cauchy unit scalar $u$ can also be selected polynomially. Choose a fixed $\zeta \in \{1,-1,i,-i\}$ with $\mathrm{Re}(\zeta u)\ge 1\mathrm{/}2$; such a choice exists because the larger absolute coordinate of a unit complex number is at least $1\mathrm{/}\sqrt{2}$. Put $v=\zeta u$ and $a=\sqrt{(1+\mathrm{Re}v)\mathrm{/}2}$, $b=\mathrm{Im}v\mathrm{/}(2a)$. Then $a\ge \sqrt{3}\mathrm{/}2$ and $(a+ib{)}^2=v$. Multiply by either fixed algebraic square root of ${\zeta }^{-1}$ and choose its fixed sign to obtain either desired root of $u$. Step 1.1 applies with a positive constant denominator. Iterating gives any fixed finite tower of coherently chosen phase half-roots. A root of a fixed nonzero complex scalar $z$ is obtained by first normalizing $z\mathrm{/}\mathrm{\mid }z\mathrm{\mid }$ and multiplying its unit root by $\sqrt{\mathrm{\mid }z\mathrm{\mid }}$; the zero case is hardcoded separately.

For each $U\in \mathcal{U}$, run the finite algebraic Givens construction [F2] as a mathematical factorization. Hardcode its actual finite skip decisions $b=0$; no run-time zero test on a varying Cauchy name is required. In each unskipped operation $h>0$ is a fixed constant, so all entries of that Givens matrix and the updated matrix are polynomial-Cauchy by step 1.1. There are at most $2^k(2^k-1)\mathrm{/}2$ operations, a constant. The terminal diagonal entries and the exact two-level adjoints therefore have polynomial-Cauchy entries. A phase on one chosen computational word is a pattern-controlled $\mathrm{diag}(1,\lambda )$ or $\mathrm{diag}(\lambda ,1)$ on a selected wire, with the other wires matching that word; hence the terminal diagonal is a fixed finite product of pattern-controlled one-qubit matrices of the same effective class.

The square roots required by [F4] preserve this effective class. For a fixed two-dimensional unitary $W$, if $W=\lambda I$ choose a unit root $\mu$ by step 2.1 and take $\mu I$. Otherwise the spectral theorem [F6] gives two distinct eigenvalues. The nonzero discriminant $d_0=(\mathrm{tr}W{)}^2-4\det W$ has a root $d$ as in step 2.1, and ${\lambda }_{\pm }=(\mathrm{tr}W\pm d)\mathrm{/}2$ have modulus one. The projector $P_{+}=(W-{\lambda }_{-}I)\mathrm{/}({\lambda }_{+}-{\lambda }_{-})$ and $P_{-}=I-P_{+}$ are orthogonal by [F6]. Choose unit roots ${\mu }_{\pm }$ and put $V={\mu }_{+}{P}_{+}+{\mu }_{-}{P}_{-}$. Then $V$ is unitary, $V^2=W$, and every entry is polynomial-Cauchy by step 1.1 and step 2.1. The scalar/nonscalar branch and the positive eigenvalue-gap lower bound are fixed choices, not input-dependent equality decisions.

The constant one-control construction [F5] is effective as well. Choose a unit root $\lambda$ of $\det W$ by step 2.1 and normalize $S={\lambda }^{-1}W\in SU(2)$. Write $S=\left(\begin{array}{cc}a& -\bar{c}\\ c& \bar{a}\end{array}\right)$ and $\rho =\mathrm{\mid }a\mathrm{\mid }$, $\sigma =\mathrm{\mid }c\mathrm{\mid }$. If $\rho >0$ use $a\mathrm{/}\rho$ for its phase, otherwise fix its arbitrary phase to $1$; treat $c\mathrm{/}\sigma$ the same way. Choose fixed real arguments $\gamma ,\eta$ with $a=e^{-i\gamma }\rho$ and $c=e^{i\eta }\sigma$, and choose $0\le \theta \le \pi$ with $\cos (\theta \mathrm{/}2)=\rho$, $\sin (\theta \mathrm{/}2)=\sigma$. These are only notation: the algorithm never computes their real arguments. Every matrix entry of the Euler factors and of $A,B,C$ in [F5] is a finite sum or product of the unit phases and their coherently selected half-roots, together with $\rho ,\sigma$, $\sqrt{(1+\rho )\mathrm{/}2}$ and $\sqrt{(1-\rho )\mathrm{/}2}$. Indeed the latter are $\cos (\theta \mathrm{/}4),\sin (\theta \mathrm{/}4)$; the z-rotation entries are exponentials of half-angles of $\alpha =\gamma +\eta$ and $\beta =\gamma -\eta$, hence phase roots from step 2.1. Choose their fixed signs to match these displayed arguments. Thus all four arbitrary one-qubit matrices in the exact controlled construction are polynomial-Cauchy; their multiplication retains the control phase $\mathrm{diag}(1,\lambda )$ exactly. No numerical angle oracle is assumed.

Apply the Gray-path implementation [F3] to each two-level block from step 2.2, and apply the no-workspace recursion [F4] to its pattern-controlled gates and to the diagonal phase gates. Negative controls and permutation gates have fixed algebraic entries. Each root step stays in the effective class by step 3.1 and each controlled base case does so by step 3.2. The number of controls, recursion depth, blocks, and elementary gates is bounded by a constant depending on $k$ and the finite fixed collection. Therefore only finitely many branch choices and divisor lower bounds are needed in total; hardcode them and the corresponding polynomial-Cauchy programs into the simulator. Exact factorization follows from step 1.2 and step 3.1 and step 3.2 and [F2]–[F5], including each scalar phase; the resulting gate factors and lengths have precisely the asserted properties.