Uniform interpretation of an input-generated quantum circuit

Let $r(n)=3+2\lceil {\log }_2\max \{2,W(n)\}\rceil$ be a fixed record width, with three type bits and two address fields, and let $B(n)=L(n)r(n)$ be the padded program bit length. For each bit position $1\le i\le B(n)$, define a fixed polynomial-time machine $M^{\mathrm{\prime }}(x,i)$ that runs $M(x)$ and returns the $i$th bit of its padded record string. Apply [F1] to $M^{\mathrm{\prime }}$. The uniform generator can specialize the index input $i$ to each constant $1,\dots ,B(n)$, enumerate every Boolean gate record using [F4]'s logarithmic-space size/type/predecessor queries, and concatenate the $B(n)$ circuits. The resulting multi-output Boolean circuit computes the entire gate program; it has polynomial size and is generated in polynomial time from $1^n$.

Allocate one clean value wire per Boolean node and traverse the circuit's topological order. A constant zero leaves its target zero; a constant one applies $X=H{T}^{4}H$; a NOT node writes $1\oplus a$ by $X$ followed by CNOT; an AND node writes $ab$ into a zero target with Toffoli; and an OR node writes $a\oplus b\oplus ab=a\vee b$ with two CNOTs and one Toffoli. If both input ports name the same source, one CNOT copies that source for either AND or OR. Copy each designated circuit output into its separate program bit by CNOTs, then reverse all node computations to return their value wires to zero. The exact Toffoli circuit is supplied by [F5]'s construction.

For each record position $t$ and each candidate gate/address tuple, compute into a clean condition bit the conjunction that all type and address fields match that tuple. Bitwise comparison uses $X$ on negative controls and an AND tree of Toffoli gates; reverse it after the controlled operation. Apply the fixed controlled target $I\oplus G$ to this bit and the one or two selected data wires, where $G$ is the candidate gate $H,T,T^{†}$, or CNOT. The target dimension is at most $2^3$ and its matrix is fixed, so [F5] produces a QC14 template with operator error $\xi$ up to one global phase on the full target. For a valid record exactly one candidate condition is true; the exact product of all candidate templates at position $t$ is therefore the specified gate, while a blank record applies identity.

Put $P_0(n)=L(n)(3W(n)+W(n)(W(n)-1))$ and $P(n)=\max \{1,P_0(n)\}$; there are at most $P_0(n)$ candidate templates, including the case $P_0(n)=0$. Choose $\xi =\delta (n)\mathrm{/}(2P(n))$. Each comparison and its inverse are exact, so conjugating a template error preserves its operator norm; the global phases of the templates multiply the entire unconditional interpreter by one scalar. Telescoping the $P_0(n)$ unitary replacements bounds the implemented program's operator error by $P_0(n)\xi \le \delta (n)\mathrm{/}2$; when $P_0(n)=0$ there are no replacements and the error is zero. The reversible program generator is exact on every basis input and leaves $x$ unchanged; its program bits can be included among the terminal unmeasured wires. Thus the full circuit implements $P_x$ to error at most $\delta (n)$ for every classical $x$.

If two output unitaries differ by operator norm at most $\delta$, then for every unit input vector their output vectors differ in norm by at most $\delta$; for any accepting projection $P$, the acceptance probabilities differ by at most $2\delta$, since $\mathrm{\mid }⟨Pv,v⟩-⟨Pw,w⟩\mathrm{\mid }\le \mathrm{\parallel }v-w\mathrm{\parallel }(\mathrm{\parallel }v\mathrm{\parallel }+\mathrm{\parallel }w\mathrm{\parallel })\le 2\delta \mathrm{.}$ This also holds for mixed inputs by finite linearity. The polynomial bounds on $L,W$ and $1\mathrm{/}\delta$ make the complete full-list generator and circuit size polynomial in the separate coordinates of [F8]. No nonstandard axiom is used.