A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
Polynomial-Time Unitary Synthesis from a Boolean Oracle
expertly designed by an internal OpenAI model · released 2026-10-05
· original PDF
IntroductionA classical description of a quantum operation can be much longer than the register on which the operation acts. Oracle access offers a way to separate the size of that description from the work needed to use it. The unitary synthesis problem asks whether every operation on \(n\) qubits can be performed in quantum polynomial time when a suitable classical description is available through coherent queries to a Boolean function. Aaronson and Kuperberg posed this question in 2007 [2]; Aaronson later highlighted it among open problems in quantum query complexity [1]. We give a positive answer to the constant-error formulation. One circuit, determined only by \(n\), works for every \(n\)-qubit unitary after an appropriate Boolean oracle is chosen. The circuit uses polynomially many gates, qubits, and queries, and each query has polynomial length. The error bound holds for arbitrary input states, including states entangled with a reference system. Model and main resultWe use the fixed elementary gate set \[H=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix}, \qquad T=\begin{pmatrix}1&0\\0&e^{i\pi/4}\end{pmatrix}, \qquad T^\dagger,\qquad \mathrm{CNOT},\] where \(\mathrm{CNOT}\lvert a,b\rangle=\lvert a,a\oplus b\rangle\). A Boolean oracle \(f:\{0,1\}^m\to\{0,1\}\) supplies the gate \[ O_f\lvert x,b\rangle=\lvert x,b\oplus f(x)\rangle. \tag{1}\] A circuit receives an \(n\)-qubit input and workspace initialized to zero. Its output channel is obtained by retaining \(n\) designated qubits and tracing out the remaining qubits. For a unitary \(U\), write \(\mathcal U(\rho)=U\rho U^\dagger\). Our convention for channel error is the full diamond norm: if \(\Phi\) is another channel on \(n\) qubits, then \[ \lVert \Phi-\mathcal U\rVert_\diamond =\sup_{\rho}\lVert \bigl((\Phi-\mathcal U)\otimes\mathrm{id}_R\bigr)(\rho)\rVert_1, \qquad \lVert X\rVert_1=\mathop{\mathrm{Tr}}\sqrt{X^\dagger X}, \tag{2}\] where \(R\) is an \(n\)-qubit reference register and \(\rho\) ranges over density operators on the input and \(R\). Thus the norm in (2) has no factor of \(1/2\). Theorem 1 (Polynomial-time unitary synthesis). There are a polynomial \(p\) and a deterministic classical algorithm which, on input \(1^n\) for any integer \(n\ge1\), outputs in time at most \(p(n)\) a quantum oracle circuit \(A_n\) with the following properties. The circuit uses the gates \(H,T,T^\dagger,\mathrm{CNOT}\) and a single Boolean oracle of input length \(m(n)\le p(n)\). Its total number of qubits, elementary gates, and oracle calls are each at most \(p(n)\). For every unitary \(U\in U(2^n)\) there is a function \(f:\{0,1\}^{m(n)}\to\{0,1\}\) for which the output channel \(\Phi_{n,f}\) of \(A_n^{O_f}\) satisfies \[\lVert \Phi_{n,f}-\mathcal U\rVert_\diamond\le\frac12.\] The quantifiers are essential. The circuit and its resource bounds depend only on \(n\); the oracle may depend on \(U\). There is no restriction on the truth-table size or classical circuit complexity of \(f\), and no prescribed encoding of \(U\) that the algorithm must use. The theorem is an existence statement about such an encoding. It does not give an efficient classical procedure for constructing the oracle from a description of \(U\). Earlier workState synthesis provides a useful comparison. It asks for preparation of one specified state from a fixed input, whereas unitary synthesis must act coherently on every input. Irani, Natarajan, Nirkhe, Rao, and Yuen obtained one- and two-query state-synthesis results with polynomial space [11]. Rosenthal subsequently gave uniform polynomial-size state-synthesis circuits using one Boolean query when workspace may be discarded, and four queries when it must be returned to zero [15]. These results do not immediately implement an arbitrary unitary: preparing a chosen column while retaining its input label does not erase that label coherently on a superposition of inputs. For unitary synthesis, Rosenthal gave a running-time upper bound of order \(2^{n/2}\) up to polynomial factors, using an oracle suited to the target unitary [16]. In the other direction, Lombardi, Ma, and Wright proved a general one-query lower bound, which also rules out polynomially many parallel queries of polynomial length [12]. Dong, Lombardi, and Ma obtained explicit one-query separations for several structured families of unitaries [8]. These lower bounds leave open the use of multiple queries interleaved with quantum computation, as in the construction here. Nehoran and Yuen recently showed that every unitary in dimension \(N\) admits a constant-query implementation using three diagonal-phase queries, or six Boolean queries [14]. The diagonal-phase version uses \(O(N\log\log(N/\varepsilon))\) query qubits for operator-norm error \(\varepsilon\). For \(N=2^n\), this is exponential in the number of input qubits. Theorem 1 concerns polynomial total resources, including the width of the oracle interface. The distinction between query count and query width is therefore indispensable when comparing these results. The reductionThe central construction replaces synthesis of a \(d\)-dimensional unitary by synthesis of one smaller, coherently controlled unitary. Each reduction removes a fraction at least \(1/\mathop{\mathrm{poly}}(n)\) of the dimension, so only polynomially many reductions are needed even when \(d=2^n\). The smaller synthesis circuit is used exactly once at each step. This last property prevents the recursion from producing an exponentially large circuit. Here is the mechanism. After changes of basis built from permutations, diagonal signs, and Walsh transforms, write the current unitary as \[V=\begin{pmatrix}A&B\\C&D\end{pmatrix},\qquad \lVert D\rVert\le\frac34,\] where \(D\) has the dimension to be removed. Random diagonal signs and Walsh transforms supply this contracting block. The needed norm estimate is proved by a Gaussian moment argument in Section 3. For a diagonal unitary \(Z\) on the removed coordinates, close the lower output back into the lower input through \(Z\). Solving the resulting linear equation gives \[F=A+BZ(I-DZ)^{-1}C.\] Conservation of norm makes \(F\) unitary on the remaining coordinates. This is the familiar transfer-function construction for a unitary block matrix [9]; our task is to turn it into a circuit reduction. For that purpose we construct two maps, \(\mathcal E\) and \(\mathcal R\), from the original space into a register holding \(Z\) together with a smaller state. They satisfy an approximate intertwining relation \[\widetilde F\mathcal E\approx\mathcal R V,\] where \(\widetilde F\) applies the corresponding \(F\) controlled by the \(Z\) register. Both maps are nearly isometric. They come from truncating the forward and backward geometric series associated with \((I-DZ)^{-1}\). Averaging over a common phase cancels unequal degrees, and unitarity makes the remaining Gram-matrix sums telescope. The errors decay exponentially with the truncation length. The implementability of these maps depends on their Fourier coefficients. We assign to each removed coordinate \(i\) the frequency vector \((1,i,\ldots,i^L)\), where \(L\) is the truncation length. The Fourier frequency of a product of at most \(L\) phases records a multiset of coordinates through its power sums. For an input on a removed coordinate, each nonzero coefficient records a multiset containing that coordinate. Inputs on the remaining coordinates contribute only at frequency zero, with one input column per output coordinate. Consequently every row of either coefficient matrix has at most \(L\) nonzero entries, although a column may be dense. This row bound lets a circuit coherently erase the input index after preparing a column. Amplitude amplification then converts the resulting scaled map into an approximation to the required encoding. The two encoders surround a single call to the smaller unitary, as shown in Figure 1. The feedback identity, the matching forward and backward encodings, and the multiset argument are developed in Section 4. Section 5 proves the circuit implementation for a general nearly isometric matrix with few nonzero entries per row, and Section 6 assembles the recursion and bounds its resources. These intermediate constructions are stated separately so that their hypotheses and uses remain visible. We first work with controlled single-qubit gates whose entries may be arbitrary functions of their control bits. Section 2 defines these programmable gates and the elementary operations they provide. Section 7 replaces every such gate by a polynomial-length word over the fixed gate set, read from one Boolean oracle. This compilation preserves relative phases between different control values. Throughout the proof, errors are measured on the subspace where the input workspace is zero; a final isometry estimate yields the diamond-norm guarantee in Theorem 1. Controlled tasks and programmable slotsWe first construct circuits whose one-qubit gates can be selected from arbitrary tables. This separates the geometry of the circuit from the information about the target unitary. Section 7 will store finite approximations to these tables in one Boolean oracle. All vector norms are Euclidean, and \(\lVert A\rVert\) denotes the operator norm of a linear map \(A\). Both \(A^*\) and \(A^\dagger\) denote its adjoint. We never minimize this norm over scalar phases. For \(1\le d\le 2^n\), write \[\mathcal H_d=\operatorname{span}\{\lvert 0\rangle,\ldots,\lvert d-1\rangle\} \subseteq (\mathbb C^2)^{\otimes n}.\] The recursion must synthesize many unitaries coherently. Its input therefore includes a label register with basis \(\lvert \lambda\rangle\), \(\lambda\in\{0,1\}^t\), and its prescribed action is \[\mathcal U=\sum_{\lambda}\lvert \lambda\rangle\langle \lambda\rvert\otimes U_\lambda, \qquad U_\lambda\colon\mathcal H_d\longrightarrow\mathcal H_d \text{ unitary}.\] Let \(\iota\) append all working qubits in state \(\lvert 0\rangle\). A circuit \(C\) solves this controlled task with error \(\delta\) if \[ \lVert C\iota-\iota\mathcal U\rVert\le\delta. \tag{3}\] Thus the estimate includes restoration of the working qubits, and is uniform over superpositions of labels. No behavior is prescribed outside the input subspace \(\operatorname{span}\{\lvert \lambda\rangle\}\otimes\mathcal H_d\). The same estimate holds after tensoring with the identity on any further register, because operator norm is unchanged by that operation. A programmable slot specifies one target qubit and an ordered list of other qubits as controls. Given a table of matrices \(W_y\in U(2)\), its action is \[ \sum_{y\in\{0,1\}^c}\lvert y\rangle\langle y\rvert\otimes W_y, \tag{4}\] where \(c\) is the number of controls. A circuit skeleton specifies the registers, targets, and control lists of its slots, but leaves their tables unspecified. The tables may depend on the target unitaries. Their contents are not part of the skeleton that the uniform generator must produce. Reversing a skeleton reverses its slot order and replaces every table by its adjoint table. Slots are uniformly controlled one-qubit gates, or quantum multiplexors, in the terminology of [4]. Every diagonal unitary on \(u\ge1\) qubits uses a single slot: choose one of the qubits as target and put the two diagonal entries for each value of the other \(u-1\) bits in the corresponding \(2\times2\) diagonal table entry. Additional labels can be included among the controls. In particular, reflections in subspaces spanned by specified computational basis states take one slot. A phase depending only on labels can be applied to a zero working qubit, or by scalar matrices on an existing target qubit. Lemma 2 (State preparation). For every \(u\ge1\) there is a skeleton of \(u+1\) slots that maps \(\lvert \lambda\rangle\lvert 0^u\rangle\) to \(\lvert \lambda\rangle\lvert a_\lambda\rangle\) for any prescribed family of unit vectors \(a_\lambda\in\mathbb C^{2^u}\). Its structure depends only on the register sizes. Proof. Fix a label and write \(a=\sum_x a_x\lvert x\rangle\). For a binary prefix \(p\), let \(P(p)=\sum_{x\text{ extending }p}|a_x|^2\). Process the bits from first to last. At the next bit, controlled on the preceding prefix \(p\), apply a real rotation whose first column is \[\begin{pmatrix} \sqrt{P(p0)/P(p)}\\[2pt] \sqrt{P(p1)/P(p)} \end{pmatrix} \quad\text{when }P(p)>0.\] Choose any rotation when \(P(p)=0\). After \(u\) such slots the amplitude at \(x\) is \(|a_x|\). One diagonal slot then supplies the phases of the \(a_x\), choosing arbitrary phases at zero entries. Including \(\lambda\) among the controls makes all these choices simultaneously. This is the usual conditional rotation construction for state preparation; here an entire uniformly controlled rotation is counted as one slot; see [13, 4]. ◻ Lemma 3 (Basis permutations). Any family of permutations of the \(2^u\) computational basis states can be implemented with \(5u\) slots and \(u\) temporary qubits that start and finish at zero. The skeleton is independent of the permutations. Proof. For the permutation \(\pi_\lambda\), use \(u\) slots to write its image bitwise into a temporary register: \[\lvert \lambda\rangle\lvert x\rangle\lvert 0\rangle \longmapsto \lvert \lambda\rangle\lvert x\rangle\lvert \pi_\lambda(x)\rangle.\] Each slot chooses either \(I\) or the bit flip, controlled on \(\lambda\) and \(x\). Next use \(u\) slots to xor \(\pi_\lambda^{-1}(y)\) into the first register, controlled on the second register \(y\). The two registers become \(\lvert 0\rangle\lvert \pi_\lambda(x)\rangle\). Swap them using three CNOTs per pair of bits. ◻ The same convention makes a Fourier transform inexpensive. We use the positive-phase transform, so that a frequency basis vector becomes its character in the computational basis. Lemma 4 (Fourier transforms). The unitary \[\lvert x\rangle\longmapsto 2^{-b/2}\sum_{z=0}^{2^b-1} e^{2\pi i xz/2^b}\lvert z\rangle\] on \(b\ge1\) qubits has a uniformly generated skeleton with \(O(b)\) slots. Products of such transforms have a number of slots linear in their total register width. Proof. Write the input integer as \(x\). Process its bits in decreasing order of place value. At the bit of place value \(2^{b-1-j}\), apply \(H\), then a diagonal slot controlled on the still unprocessed lower bits. Give the state \(1\) the additional phase that, together with its sign from \(H\), makes the ratio of its two amplitudes equal to \(e^{2\pi i x/2^{b-j}}\). Bits above the current bit contribute integral multiples of \(2\pi\) to this expression, and are no longer needed as controls. The resulting bit is the Fourier output bit of place value \(2^j\). A final reversal of bit order gives the stated transform. There are two slots per processed bit and \(O(b)\) CNOTs for the reversal. ◻ These constructions retain the scalar phase of every label branch. This is essential: phases that would be irrelevant for one isolated unitary become relative phases when the same operation is controlled by a quantum register. Producing a contracting blockThe reduction will remove a small group of indices from the synthesis problem. For its geometric series to converge rapidly, the corresponding diagonal block of the unitary must have norm bounded away from one. We now obtain such a block using only permutations, diagonal signs, and Walsh–Hadamard transforms. All these transformations have short programmable-slot implementations. We first record the matrix estimate needed to choose the signs. A Rademacher variable takes the values \(1\) and \(-1\) with equal probability. The following elementary moment argument is a finite-dimensional form of the noncommutative Khintchine estimate; see Tropp [17] for the Gaussian integration-by-parts and trace-product method. We include the proof with the constants used below. Lemma 5 (A matrix sign estimate). Let \(L_1,\ldots,L_q\) be Hermitian \(h\times h\) matrices, and let \(\varepsilon_1,\ldots,\varepsilon_q\) be independent Rademacher variables. Set \(v=\lVert \sum_i L_i^2\rVert\). For every integer \(a\geq1\), \[ \mathbb E\lVert \sum_{i=1}^q\varepsilon_iL_i\rVert \leq 2h^{1/(2a)}\sqrt{(2a-1)v}. \tag{5}\] Proof. We first replace the signs by independent standard real Gaussians \(g_i\) and write \(X=\sum_i g_iL_i\). Gaussian integration by parts, applied to this matrix polynomial, gives \[ \mathbb E\mathop{\mathrm{Tr}}X^{2a} =\sum_{i=1}^q\sum_{l=0}^{2a-2} \mathbb E\mathop{\mathrm{Tr}}\bigl(L_iX^lL_iX^{2a-2-l}\bigr). \tag{6}\] Indeed, write the first factor of \(X^{2a}\) as \(\sum_i g_iL_i\), use \(\mathbb E[g_iP(g)]=\mathbb E[\partial_iP(g)]\), and differentiate each of the remaining \(2a-1\) factors in turn. Put \(m=2a-2\). For a fixed Hermitian \(X\), diagonalize it with real eigenvalues \(\lambda_j\). In this basis, for \(m>0\), \[\begin{align*} \mathop{\mathrm{Tr}}(L_iX^lL_iX^{m-l}) &=\sum_{j,k}|(L_i)_{jk}|^2\lambda_k^l\lambda_j^{m-l}\\ &\leq\sum_{j,k}|(L_i)_{jk}|^2 \left(\frac lm|\lambda_k|^m+ \frac{m-l}{m}|\lambda_j|^m\right) =\mathop{\mathrm{Tr}}(L_i^2X^m). \end{align*}\] The inequality is the weighted arithmetic–geometric mean inequality after taking absolute values. The last equality uses the symmetry \(|(L_i)_{jk}|^2=|(L_i)_{kj}|^2\) and the evenness of \(m\). For \(m=0\) the same assertion is equality. Since \(X^m\) is positive semidefinite and \(\sum_iL_i^2\preceq vI\), equation (6) implies \[\mathbb E\mathop{\mathrm{Tr}}X^{2a}\leq(2a-1)v\,\mathbb E\mathop{\mathrm{Tr}}X^{2a-2}.\] Iterating from \(\mathop{\mathrm{Tr}}I=h\) yields \[\mathbb E\mathop{\mathrm{Tr}}X^{2a} \leq h(2a-1)!!\,v^a \leq h(2a-1)^a v^a.\] Here \((2a-1)!!=1\cdot3\cdots(2a-1)\). Therefore \[ \mathbb E\lVert X\rVert \leq\bigl(\mathbb E\lVert X\rVert^{2a}\bigr)^{1/(2a)} \leq h^{1/(2a)}\sqrt{(2a-1)v}. \tag{7}\] To return to signs, write \(g_i=\varepsilon_i t_i\), where the \(t_i=|g_i|\) are independent of the signs and have common mean \(\mu=\sqrt{2/\pi}\). Conditional Jensen gives \[\mu\,\lVert \sum_i\varepsilon_iL_i\rVert \leq\mathbb E_t\lVert \sum_i\varepsilon_i t_iL_i\rVert.\] Average over the signs, apply (7), and use \(\mu^{-1}<2\). ◻ Fix throughout the construction \[ M=4096(n+1)^2,\qquad r=\frac34. \tag{8}\] For an integer \(2\leq d\leq2^n\), let \(q\) be the largest power of two not exceeding \(d\), and define \[ s=\max\{1,\lfloor q/M\rfloor\},\qquad k=d-s. \tag{9}\] We call the first \(k\) indices ports and the last \(s\) indices internal indices. Both groups are nonempty. Proposition 6 (A block of uniformly small norm). For every unitary \(U\) on \(\mathbb C^d\), there are unitaries \(P_{\mathrm L}\) and \(P_{\mathrm R}\) on \(\mathbb C^d\) such that \[ V=P_{\mathrm L}UP_{\mathrm R} =\begin{pmatrix}A&B\\C&D\end{pmatrix}, \qquad \lVert D\rVert\leq r, \tag{10}\] where the block sizes are \(k,s\) from (9). The transformations \(P_{\mathrm L},P_{\mathrm R}\) and their inverses have implementations using \(O(n)\) programmable slots and \(O(n)\) clean working qubits, with a structure determined by \(n,d\). The same structure works simultaneously for any family \(U_\lambda\), using the label \(\lambda\) as an additional control. Proof. If \(s=1\), the last column of \(U\) has an entry of modulus at most \(1/\sqrt d\). A row permutation moves this entry to the last position. The resulting one-dimensional block satisfies \(\lVert D\rVert\leq1/\sqrt d<3/4\), and the permutation has the claimed slot implementation by Lemma 3. Suppose \(s>1\). Let \(M_0\) be the last-by-last \(q\times q\) submatrix of \(U\); it is a contraction. Set \(H_q=H^{\otimes\log_2q}\), and let \(W\) consist of its last \(s\) columns. We will choose diagonal sign matrices \(E_1,E_2\) on \(\mathbb C^q\) and use \(H_qE_1\) on the left and \(E_2H_q\) on the right, acting as the identity on the remaining \(d-q\) indices. The resulting internal block is \[ D=W^*E_1C',\qquad C'=M_0E_2W. \tag{11}\] We choose \(E_2\) first to bound the entries of \(C'\), then choose \(E_1\) to bound the operator norm of \(D\). For independent signs in \(E_2\), each entry of \(C'\) is a sign sum \(\sum_j\varepsilon_j\alpha_j\) with \(\sum_j|\alpha_j|^2\leq1/q\). For completeness, a real sign sum with squared coefficient sum at most \(1/q\) satisfies \[\mathbb E\exp\left(t\sum_j\varepsilon_j a_j\right) =\prod_j\cosh(ta_j)\leq\exp(t^2/(2q)).\] Markov’s inequality, optimized over \(t\), bounds its two-sided tail at \(u\) by \(2e^{-qu^2/2}\). Applying this to the real and imaginary parts shows \[\Pr\left(\left|\sum_j\varepsilon_j\alpha_j\right|\geq u\right) \leq4e^{-qu^2/4}.\] There are \(qs\) entries. With \(u=4\sqrt{(n+1)/q}\), the union-bound failure probability is at most \[4qs e^{-4(n+1)}\leq4\cdot2^{2n}e^{-4(n+1)}<1.\] We may therefore fix \(E_2\) such that every entry of \(C'\) has modulus at most \(4\sqrt{(n+1)/q}\). Also \(\lVert C'\rVert\leq1\). Let \(h_i,c_i\) be row \(i\) of \(W,C'\), respectively, regarded as row vectors. Then \[\lVert h_i\rVert^2=s/q,\qquad \lVert c_i\rVert^2\leq v:=16s(n+1)/q.\] Choosing independent signs \(\varepsilon_i\) for \(E_1\), write \[D=\sum_i\varepsilon_i h_i^*c_i, \qquad L_i=\begin{pmatrix}0&h_i^*c_i\\c_i^*h_i&0\end{pmatrix}.\] The two diagonal blocks of \(\sum_iL_i^2\) satisfy \[\sum_i\lVert c_i\rVert^2h_i^*h_i\preceq vW^*W=vI_s, \qquad \sum_i\lVert h_i\rVert^2c_i^*c_i =\frac sq C'^*C'\preceq\frac sq I_s\preceq vI_s.\] The norm of \(\sum_i\varepsilon_iL_i\) equals \(\lVert D\rVert\). Apply Lemma 5 with \(h=2s\) and \(a=n+1\). Since \((2s)^{1/(2n+2)}\leq\sqrt2\), we obtain \[\mathbb E\lVert D\rVert \leq 2\sqrt2\sqrt{2(n+1)\,16s(n+1)/q} =16(n+1)\sqrt{s/q} \leq\frac14.\] The last inequality uses \(s\leq q/M\). Some choice of \(E_1\) consequently satisfies \(\lVert D\rVert\leq1/4\), which is more than required. It remains to check the circuit structure. A permutation on the \(n\)-bit index register moves the last \(q\) valid indices to the first \(q\) valid indices, an aligned \(q\)-element block. On that block, \(H_q\) uses at most \(n\) Hadamard slots, controlled on the remaining bits; each diagonal sign matrix uses one diagonal slot. Undo the permutation afterward. Lemma 3 supplies clean \(O(n)\)-slot implementations of the permutations. All operations preserve the valid \(d\)-dimensional subspace and are extended unitarily to unused index states. Labels change only the row permutation or diagonal-sign tables, so the same slot structure works for every \(U_\lambda\). ◻ The random signs are used only to prove that suitable tables exist. Each label may use its own choices; the resulting slot circuit is deterministic. The size of the removed block is large enough to make recursion short. Lemma 7 (Dimension decrease). For the parameters in (9), \(s\geq d/(4M)\). Starting at any \(d\leq2^n\) and repeatedly replacing \(d\geq2\) by \(d-s\), one reaches \(d=1\) in fewer than \[ J=8M(n+1) \tag{12}\] steps. Proof. If \(q/M\geq2\), then \(s=\lfloor q/M\rfloor\geq q/(2M)>d/(4M)\), because \(d<2q\). If \(q/M<2\), then \(s=1\) and \(d<2q<4M\), with the same conclusion. Thus every nontrivial step multiplies the order by at most \(1-1/(4M)\). If there were \(J\) such steps, their final order would be at most \[2^n(1-1/(4M))^J \leq2^n e^{-J/(4M)} =2^n e^{-2(n+1)}<1,\] contrary to its being a positive integer. ◻ Fourier fields for a smaller unitaryLet \(d=k+s\le 2^n\), with \(k,s\ge1\), and suppose that \[ V=\begin{pmatrix}A&B\\ C&D\end{pmatrix}\in U(d), \qquad \lVert D\rVert\le r<1,\quad r\ge0. \tag{13}\] The first \(k\) coordinates are the ports and the last \(s\) coordinates are internal. We will associate to \(V\) a family of \(k\)-dimensional unitaries \(F(z)\) and two nearly isometric maps from \(\mathbb C^d\) into the space of port-valued functions of \(z\). These maps intertwine \(V\) with the controlled application of \(F(z)\). Their Fourier coefficients will have few nonzero entries in each row, which makes the maps implementable by slots. Closing the internal coordinatesFor the moment let \(Z\) be any diagonal unitary of order \(s\). Given a port input \(u\in\mathbb C^k\), feed the internal output \(v\in\mathbb C^s\) back into the internal input through \(Z\). If \(y\in\mathbb C^k\) is the port output, the equation \(V(u,Zv)=(y,v)\) becomes \[y=Au+BZv,\qquad v=Cu+DZv.\] Since \(\lVert DZ\rVert<1\), the second equation has the unique solution \(v=Xu\), and the first then gives \(y=Fu\), where \[ X=(I-DZ)^{-1}C,\qquad F=A+BZX, \qquad E=\begin{pmatrix}I_k\\ ZX\end{pmatrix},\qquad O=\begin{pmatrix}F\\ X\end{pmatrix}. \tag{14}\] Thus \(Eu\) and \(Ou\) collect the full input and output of \(V\) after the internal coordinates have been closed. For a scalar phase \(Z=zI\), this is the standard transfer function of a unitary block matrix; see [9]. The same conservation of norm proves unitarity with independently chosen diagonal phases. Lemma 8. For the unitary block matrix in (13) and any diagonal unitary \(Z\), the matrix \(F\) in (14) is unitary. If \[ R=OF^*=\begin{pmatrix}I_k\\ Y\end{pmatrix}, \qquad Y=XF^*, \tag{15}\] then \[ FE^*=R^*V, \qquad Y=(I-Z^*D^*)^{-1}Z^*B^*. \tag{16}\] Proof. The definitions give \(VE=O\). Consequently, \[I_k+X^*X=E^*E=O^*O=F^*F+X^*X,\] so \(F^*F=I_k\). Because \(F\) is square, it is unitary. Thus \(OF^*\) has the stated top block, and \(V^*R=EF^*\). Taking adjoints proves the first identity in (16). Comparing the bottom blocks of \(V^*R=EF^*\) gives \[B^*+D^*Y=ZY.\] Multiplication by \(Z^*\) and \(\lVert Z^*D^*\rVert\le r<1\) give the second identity. ◻ Truncation and averagingFix an integer truncation length \(L\ge1\), and set \[ b=nL+\lceil\log_2(L+1)\rceil,\qquad \mathcal G=(\mathbb Z/(2^b))^{L+1}. \tag{17}\] For \(w,z\in\mathcal G\), write \[\chi_w(z)=\exp(2\pi i\,w\cdot z/2^b).\] Number the internal coordinates by \(i=1,\ldots,s\) and put \[ v_i=(1,i,i^2,\ldots,i^L)\in\mathcal G, \qquad Z(z)=\mathop{\mathrm{diag}}\bigl(\chi_{v_1}(z),\ldots,\chi_{v_s}(z)\bigr). \tag{18}\] The constant first coordinate of \(v_i\) gives all diagonal entries of \(Z(z)\) a common phase when the first coordinate of \(z\) varies. Averaging that phase will separate terms of different lengths in the truncated series. The remaining coordinates record power sums: the Fourier frequency of a product of at most \(L\) phases will determine its multiset of internal indices, as proved in Proposition 10. These two properties will give the norm bound and the row bound, respectively. Apply Lemma 8 at each \(z\) to obtain \(F(z),E(z),R(z)\). Truncate the two Neumann expansions by defining \[ E_L(z)=\begin{pmatrix} I_k\\[2pt] \displaystyle\sum_{\ell=0}^{L-1}Z(DZ)^\ell C \end{pmatrix},\qquad R_L(z)=\begin{pmatrix} I_k\\[2pt] \displaystyle\sum_{\ell=0}^{L-1}(Z^*D^*)^\ell Z^*B^* \end{pmatrix}. \tag{19}\] Here and below, products containing \(Z\) are evaluated at the same \(z\). Since every block of a unitary has norm at most one, \[ \lVert E_L(z)-E(z)\rVert,\ \lVert R_L(z)-R(z)\rVert \le \tau,\qquad \tau=\frac{r^L}{1-r}. \tag{20}\] Define the field maps \(\mathcal E_L,\mathcal R_L: \mathbb C^d\longrightarrow\mathbb C^{\mathcal G}\otimes\mathbb C^k\) by \[ \mathcal E_L x=\frac1{\sqrt{|\mathcal G|}} \sum_{z\in\mathcal G}\lvert z\rangle\otimes E_L(z)^*x, \qquad \mathcal R_L x=\frac1{\sqrt{|\mathcal G|}} \sum_{z\in\mathcal G}\lvert z\rangle\otimes R_L(z)^*x. \tag{21}\] Although a single matrix \(E_L(z)^*\) need not be a contraction, averaging its squared norm over \(z\) nearly preserves the norm of every input. Proposition 9. For either \(\mathcal T=\mathcal E_L\) or \(\mathcal T=\mathcal R_L\), \[ (1-r^{2L})I_d\ \le\ \mathcal T^*\mathcal T\ \le\ I_d. \tag{22}\] In addition, let \(\widetilde F\) apply \(F(z)\) to the port register, controlled on \(z\). Then \[ \lVert \widetilde F\mathcal E_L-\mathcal R_L V\rVert\le2\tau. \tag{23}\] Proof. The Gram matrix of \(\mathcal E_L\) is the average of \(E_LE_L^*\). Fix the last \(L\) coordinates of \(z\) and vary its first coordinate. Writing \(Z=\omega Z'\), the scalar \(\omega\) ranges uniformly over the \(2^b\)-th roots of unity, while \(Z'\) stays fixed. The summand of index \(\ell\) in the lower block of \(E_L\) is \[\omega^{\ell+1}Z'W^\ell C,\qquad W=DZ'.\] The degrees \(0,1,\ldots,L\) are distinct modulo \(2^b\). Their orthogonality under averaging shows that the port block of \(\mathbb E_\omega E_LE_L^*\) is \(I_k\), that its off-diagonal blocks vanish, and that its internal block is \[Z'\left(\sum_{\ell=0}^{L-1}W^\ell CC^*(W^*)^\ell\right)(Z')^*.\] Unitarity of \(V\) gives \(CC^*=I-DD^*=I-WW^*\). Therefore the sum telescopes: \[ \sum_{\ell=0}^{L-1}W^\ell(I-WW^*)(W^*)^\ell =I-W^L(W^*)^L. \tag{24}\] As \(\lVert W\rVert\le r\), the internal block lies between \((1-r^{2L})I_s\) and \(I_s\). Averaging the remaining coordinates of \(z\) preserves these inequalities. For \(R_L\), set \(W=(Z')^*D^*\) and \(C_0=(Z')^*B^*\). Its lower summand is \(\omega^{-(\ell+1)}W^\ell C_0\). The negative degrees are again distinct from each other and from zero. Now \[C_0C_0^*=(Z')^*(I-D^*D)Z'=I-WW^*,\] so the internal Gram block is exactly the sum in (24), with these choices of \(W,C_0\). This proves (22) for both maps. Finally, Lemma 8 and (20) give, pointwise, \[\lVert F(z)E_L(z)^*-R_L(z)^*V\rVert \le \lVert E_L(z)-E(z)\rVert+\lVert R_L(z)-R(z)\rVert\le2\tau.\] Apply this bound to a fixed vector and average its squared norm over \(z\) to obtain (23). ◻ Few possible input indices at each Fourier frequencyThe norm bounds supply nearly isometric maps. To implement them, we also need a restriction on their matrix entries. Use the Fourier basis \[\lvert \widehat w\rangle=\frac1{\sqrt{|\mathcal G|}} \sum_{z\in\mathcal G}\chi_w(z)\lvert z\rangle, \qquad w\in\mathcal G,\] for the first output register of either field map. A row of the resulting matrix is indexed by a frequency \(w\) and a port \(a\in\{1,\ldots,k\}\); its columns are the \(d\) input coordinates. Proposition 10. In these Fourier coordinates, every row of \(\mathcal E_L\) and of \(\mathcal R_L\) has at most \(L\) nonzero entries. Proof. First, the sum of the vectors \(v_i\) over any multiset of at most \(L\) internal indices determines that multiset uniquely. Indeed, every coordinate of such a sum, regarded as an ordinary nonnegative integer, is at most \(L2^{nL}<2^b\), so reduction modulo \(2^b\) loses no information. Its first coordinate records the length \(m\), and the next \(m\) coordinates record the power sums \(p_j=\sum_{t=1}^m i_t^j\). The elementary symmetric polynomials are recovered successively from Newton’s identities \[e_0=1,\qquad j e_j=\sum_{t=1}^j(-1)^{t-1}e_{j-t}p_t\quad(1\le j\le m).\] These identities follow by taking the logarithmic derivative of \(\prod_{t=1}^m(1+i_t x)=\sum_{j=0}^m e_jx^j\) and comparing coefficients. Consequently the monic polynomial \(T^m-e_1T^{m-1}+\cdots+(-1)^me_m\), and hence its multiset of roots, is determined. An input port contributes only to frequency zero and the same output port. For an internal input \(i\), the lower columns of \(E_L^*\) are sums of \[C^*Z^*,\quad C^*Z^*D^*Z^*,\quad\ldots,\] whereas those of \(R_L^*\) are sums of \[BZ,\quad BZDZ,\quad BZDZDZ,\quad\ldots.\] In both cases the rightmost diagonal factor acts on input \(i\). Thus every monomial contains the phase belonging to \(i\), and its frequency is the signed sum of the \(v_j\) over a multiset of between \(1\) and \(L\) internal indices containing \(i\). The sign is negative for \(\mathcal E_L\) and positive for \(\mathcal R_L\). For example, the second displayed term on the \(R\) side has entry \[(BZDZ)_{ai}=\sum_j B_{aj}D_{ji}\, \chi_{v_j+v_i}(z).\] Fix a nonzero frequency and an output port. For \(\mathcal E_L\), negate the frequency first to recover the corresponding positive tuple sum. By the uniqueness just proved, all its contributing monomials have the same multiset of internal indices. Only indices belonging to that multiset can therefore occur as nonzero input columns. There are at most \(L\) of them. The ordering of indices in a monomial can change its coefficient but cannot enlarge this column set. No internal monomial has frequency zero, since its first coordinate has absolute value between \(1\) and \(L\) modulo \(2^b\). At frequency zero the single port column gives the required bound as well. ◻ The role of the power-sum phases is now explicit: a frequency remembers an unordered list of internal visits, so it permits only a short list of possible input indices. The next section uses exactly this list to erase the input register coherently. Implementing the field encodingsA matrix with few nonzero entries in each row admits a useful slot construction. First prepare each column while retaining its input index. Then, conditional on the output row, erase that index with an amplitude determined only by the maximum row size. Two reflections amplify the result. When the matrix is nearly isometric, all its singular directions require almost the same amplification angle. The reflection argument is amplitude amplification [6]. Preparing states to realize a matrix as a block of a larger unitary is also a standard block-encoding method [10]. Here arbitrary table-controlled column preparation permits us to use sparsity only in the rows. A construction for a nearly isometric matrixLet \(\mathcal U\) be a set of rows encoded in a \(w\)-qubit register, and let \(T:\mathbb C^d\to\mathbb C^{\mathcal U}\) have entries \(a_{ui}\), where \(d\le2^n\). Fix an integer \(L\ge1\). Suppose that every row has at most \(L\) nonzero entries and \[ (1-\varepsilon)I_d\le T^*T\le I_d, \qquad L\ge1,\quad 0\le\varepsilon<1. \tag{25}\] All these data may depend on a label register, with the same dimensions and bounds for every label. The construction below treats labels as controls. Extend the \(n\)-qubit input index by \(h=\lceil\log_2(L+1)\rceil\) high bits, and add the row register and two one-bit flags. Let \(\iota\) embed \(\mathbb C^d\) with all these new qubits zero. Let \(\jmath\) embed \(\mathbb C^{\mathcal U}\) with the extended index zero and both flags equal to one. Write \(P_0=\iota\iota^*\) and \(Q=\jmath\jmath^*\) for the corresponding projections. Thus \(Q\) allows any valid row, while \(P_0\) allows any of the \(d\) input indices. We call the range of \(Q\) the good subspace. Lemma 11. Under (25), an exact-slot unitary \(\mathsf U_T\) satisfies \[ \lVert \mathsf U_T\iota-\jmath T\rVert\le5\varepsilon. \tag{26}\] It uses \(O(L(n+w+h))\) slots and \(w+h+2\) fresh qubits. Its slot structure depends only on the register sizes, \(d\), and \(L\), and it works coherently for any family of matrices indexed by labels. Proof. Set \[ \theta=\frac\pi{4L+2},\qquad t_0=\sin\theta. \tag{27}\] We first construct a unitary \(\mathsf B\) with the prescribed block \[ \jmath^*\mathsf B\iota=t_0T. \tag{28}\] For each valid input \(i\), the column norm is at most one. Conditional on \(i\), use Lemma 2 to prepare the row register and first flag in a unit vector whose flag-one part is \[\sum_{u\in\mathcal U}a_{ui}\lvert u\rangle\lvert 1\rangle.\] The remaining squared norm is placed in the flag-zero subspace. The input index is unchanged during this preparation. For each row \(u\), choose a list \(I_u\) of exactly \(L\) distinct extended indices containing every \(i\) with \(a_{ui}\ne0\). Such lists exist because the extended index space has dimension \(2^{n+h}\ge2^n(L+1)>L\). Padding indices need not be valid inputs. Conditional on the row, apply the inverse of a state preparation for \[\frac1{\sqrt L}\sum_{i\in I_u}\lvert i\rangle\] on the extended index register. Its matrix element from any \(i\in I_u\) to zero is \(1/\sqrt L\). Finally rotate the second flag so that its amplitude at one is \(t_0\sqrt L\). This is possible because \(t_0\sqrt L\le\theta\sqrt L\le1\). Prescribe arbitrary unitary extensions for invalid indices and rows. Projecting onto index zero and flags one now multiplies each relevant \(a_{ui}\) by \((1/\sqrt L)(t_0\sqrt L)=t_0\), proving (28). All three operations together form \(\mathsf B\). Starting with \(\mathsf B\), perform \(L\) rounds of \[ (2\mathsf B P_0\mathsf B^*-I)(I-2Q). \tag{29}\] These are implementable with \(\mathsf B\), its inverse, and diagonal reflections. We verify their action on every singular direction of \(T\). Let \(v_j\) be an orthonormal basis of right singular vectors and write \[Tv_j=\sigma_j e_j,\qquad \sqrt{1-\varepsilon}\le\sigma_j\le1,\] where the \(e_j\) are orthonormal. In this calculation identify the input and output spaces with their embeddings \(\iota\) and \(\jmath\). By (28), \[ \mathsf Bv_j=\sin\beta_j\,e_j+\cos\beta_j\,e'_j, \qquad \beta_j=\arcsin(t_0\sigma_j), \tag{30}\] for a unit vector \(e'_j\) in the kernel of \(Q\). The \(e'_j\) are mutually orthogonal: this follows by taking pairwise inner products in (30), using unitarity of \(\mathsf B\) and orthogonality of the \(e_j\). Each \(e'_j\) is also orthogonal to every \(e_i\). For completeness, both reflections preserve the plane spanned by \(e_j,e'_j\). The first reflection is about the range of \(\mathsf B P_0\), which is spanned by the mutually orthogonal vectors \(\mathsf Bv_i\). Within the \(j\)th plane it is therefore reflection about \(\sin\beta_j\,e_j+\cos\beta_j\,e'_j\); the second reflection changes the sign of \(e_j\) and fixes \(e'_j\). Their product in the order (29) sends \[\sin\alpha\,e_j+\cos\alpha\,e'_j \quad\hbox{to}\quad \sin(\alpha+2\beta_j)e_j+\cos(\alpha+2\beta_j)e'_j.\] After \(L\) rounds, the angle is \((2L+1)\beta_j\). As \((2L+1)\theta=\pi/2\), the distance of this vector from \(\sigma_j e_j\) is at most \[\begin{align*} (2L+1)(\theta-\beta_j)+(1-\sigma_j) &\le (2L+1)\,2t_0(1-\sigma_j)+(1-\sigma_j)\\ &\le(\pi+1)(1-\sigma_j) \le5\varepsilon. \end{align*}\] Here \(t_0\le1/2\), so the derivative of \(\arcsin\) is at most \(2\) on \([0,t_0]\), and \(1-\sigma_j\le1-\sqrt{1-\varepsilon}\le\varepsilon\). The error vectors lie in mutually orthogonal planes. The same bound therefore holds in operator norm on the whole input space, proving (26). The first preparation uses \(O(w+1)\) slots and the second \(O(n+h)\), so \(\mathsf B\) uses \(O(n+w+h)\) slots. The complete circuit contains \(2L+1\) occurrences of \(\mathsf B\) or \(\mathsf B^*\) and \(2L\) diagonal reflections. A diagonal reflection is one slot, as explained in Section 2. No additional workspace is needed. All prescriptions can be made separately for each label using the same slot positions and controls. Since the resulting maps are block diagonal in the labels, the bounds hold for coherent superpositions of labels as well. ◻ Applying the construction to the Fourier fieldsIn the preceding section, a row is a frequency and a port. Let \[ K=b(L+1),\qquad h=\lceil\log_2(L+1)\rceil. \tag{31}\] Encode the frequency in \(K\) qubits and the port in \(n\) qubits, using the first \(k\) port states. The two field maps have the same row space and therefore use the same output embedding \(\jmath\): extended input index zero, both flags one, and a valid port. This shared layout will allow the second encoding to be reversed after the recursive call. Proposition 12. Under the hypotheses and definitions of Section 4, there are exact-slot unitaries \(\mathsf U_E,\mathsf U_R\) such that \[ \lVert \mathsf U_E\iota-\jmath\mathcal E_L\rVert\le5r^{2L}, \qquad \lVert \mathsf U_R\iota-\jmath\mathcal R_L\rVert\le5r^{2L}. \tag{32}\] Each uses \(O\bigl(L(K+n+h)+K\bigr)\) slots and \(K+n+h+2\) fresh qubits, with slot structure independent of \(V\). The construction works coherently with any additional label register. Proof. Write either field map in Fourier coordinates. Proposition 10 gives at most \(L\) nonzero entries in each row, and Proposition 9 supplies (25) with \(\varepsilon=r^{2L}\). Apply Lemma 11, taking \(w=K+n\), to obtain the corresponding coefficient map with error at most \(5r^{2L}\). Then apply the positive Fourier transform to each of the \(L+1\) frequency factors, so that \(\lvert w\rangle\) becomes \(|\mathcal G|^{-1/2}\sum_z\chi_w(z)\lvert z\rangle\). The same physical register now holds the phase label \(z\), rather than the Fourier frequency \(w\). Lemma 4 implements these transforms using \(O(K)\) slots. They preserve the range of \(Q\), because every frequency is allowed there and the index, flags, and port are unchanged. Thus they convert the coefficient map into the field map in the same embedding \(\jmath\), while preserving the error norm on the full space. Their addition gives (32) and the stated resource bounds. ◻ Assembling the recursionThe two field encodings now reduce synthesis of \(V\) to synthesis of the smaller controlled unitary \(F(z)\). The reduction uses the smaller circuit exactly once. This fact keeps the total circuit size polynomial even though the number of recursion levels grows with \(n\). Lemma 13 (One synthesis step). Let \(V\) be a unitary on \(\mathbb C^{k+s}\) in the block form of Proposition 6, and let \(\lVert D\rVert\leq r<1\). Use the fields and encoders of Sections 4 and 5 with truncation length \(L\). Suppose a circuit synthesizes the family of \(k\)-dimensional unitaries \(F(z)\), controlled by \(z\), with clean-workspace operator norm error \(\delta'\). Then one use of that circuit, preceded by \(\mathsf U_E\) and followed by \(\mathsf U_R^*\), synthesizes \(V\) with clean-workspace error at most \[ \delta'+\frac{2r^L}{1-r}+10r^{2L}. \tag{33}\] The assertion also holds coherently for a family \(V_\lambda\), with the smaller circuit controlled by both \(\lambda\) and \(z\). Proof. Let \(\iota\) embed the current index space into the full register layout by initializing all working qubits to zero. Include the fresh working qubits of the smaller circuit in this definition. Let \(\jmath\) embed the field space \(\mathbb C^{\mathcal G}\otimes\mathbb C^k\) into the encoder’s good subspace, again with the smaller circuit’s fresh workspace zero. Write \(\mathsf C\) for the smaller synthesis circuit acting on its target, control, and fresh working registers, and as the identity on the remaining registers. Its approximation guarantee implies \[ \lVert \mathsf C\jmath-\jmath\widetilde F\rVert\leq\delta'. \tag{34}\] Indeed, the good subspace has a valid port index, and \(\widetilde F\) applies \(F(z)\) with the phase register as control. Put \(\tau=r^L/(1-r)\). Proposition 12 gives \[\lVert \mathsf U_E\iota-\jmath\mathcal E_L\rVert\leq5r^{2L}, \qquad \lVert \mathsf U_R\iota-\jmath\mathcal R_L\rVert\leq5r^{2L}.\] The field maps are contractions by Proposition 9, and their intertwining bound is (23). Consequently, \[\begin{align*} &\lVert \mathsf C\mathsf U_E\iota-\mathsf U_R\iota V\rVert\\ &\quad\leq \lVert \mathsf C(\mathsf U_E\iota-\jmath\mathcal E_L)\rVert +\lVert (\mathsf C\jmath-\jmath\widetilde F)\mathcal E_L\rVert\\ &\qquad\quad +\lVert \jmath(\widetilde F\mathcal E_L-\mathcal R_LV)\rVert +\lVert (\jmath\mathcal R_L-\mathsf U_R\iota)V\rVert\\ &\quad\leq5r^{2L}+\delta'+2\tau+5r^{2L}. \end{align*}\] Multiplication by \(\mathsf U_R^*\) proves (33). This calculation invokes the smaller circuit’s approximation only on the ideal field-map output, whose norm is at most one. Any component of the actual encoded state outside the good subspace is covered by the first error term and is not enlarged by \(\mathsf C\). For additional labels \(\lambda\), all maps are block diagonal in the label basis and all bounds are uniform over the labels. Their operator norms on the full controlled space are the maxima of the block norms. The same calculation therefore applies to arbitrary coherent superpositions of labels. ◻ Figure 1 shows the comparison made in this proof. The amplification inside \(\mathsf U_E\) and \(\mathsf U_R\) repeats only their own state-preparation circuits. It never repeats \(\mathsf C\). We can now choose one set of parameters for all recursion levels. Keep \(M,r,J\) from (8) and (12), and set \[ L=10000J,\qquad b=nL+\lceil\log_2(L+1)\rceil,\qquad K=b(L+1). \tag{35}\] Thus \(K\) is the number of qubits in each field’s phase register. Proposition 14 (Uniform programmable synthesis). Let \(n\geq1\), \(1\leq d\leq2^n\), and \(t\geq0\). There is a programmable-slot circuit structure, determined by \(n,d,t\), with the following property. For every family \((U_\lambda)_{\lambda\in\{0,1\}^t}\) of unitaries on \(\mathbb C^d\), its slot tables can be chosen so that the circuit implements the controlled unitary \(U_\lambda\), preserves the labels, and has clean-workspace operator norm error less than \(1/100\) in the sense of (3). The circuit uses \[ t+O((n+1)^{10})\quad\text{qubits}, \qquad O((n+1)^{13})\quad\text{slots}. \tag{36}\] Its structure, including each slot’s ordered control list, is generated deterministically in time polynomial in \(n+t\) from \(n,d,t\). Proof. We recurse on the valid order \(d\), retaining \(n\)-bit index and port registers at every level. If \(d=1\), each \(U_\lambda\) is a scalar phase, implemented exactly by one slot on an index bit that is zero throughout the valid input subspace. For \(d\geq2\), Proposition 6 gives \(V_\lambda=P_{\mathrm L,\lambda}U_\lambda P_{\mathrm R,\lambda}\) with internal order \(s\) and port order \(k=d-s\). Apply the one-step construction of Lemma 13, prescribing the recursive family to be \(F_\lambda(z)\) and adding \(z\) to the existing control labels. Supply fresh working qubits for this recursive circuit. To implement \(U_\lambda\), apply \(P_{\mathrm R,\lambda}^*\) before this construction and \(P_{\mathrm L,\lambda}^*\) afterward. These transformations have exact slot implementations, so they introduce no further error. Their order is correct because \(P_{\mathrm L,\lambda}^*V_\lambda P_{\mathrm R,\lambda}^*=U_\lambda\). At each step, Lemma 13 adds at most \[\frac{2r^L}{1-r}+10r^{2L} =8r^L+10r^{2L}\leq18r^L\] to the error of the smaller circuit. There are fewer than \(J\) steps by Lemma 7. Bernoulli’s inequality gives \((4/3)^L\geq1+L/3\), and hence \(r^L\leq3/L\). The total error is therefore \[ 18Jr^L\leq\frac{54J}{L}=\frac{54}{10000}<\frac1{100}. \tag{37}\] In particular, all working qubits, including those introduced at inner recursion levels, return to zero in the ideal comparison map. We next count the circuit resources. Write \(N=n+1\) and \(h=\lceil\log_2(L+1)\rceil\). Our parameters satisfy \[J,L=O(N^3),\qquad b=O(N^4),\qquad K=O(N^7),\qquad h=O(N).\] Proposition 12 uses \(O(K+n+h)\) fresh qubits for a pair of encoders and \(O(L(K+n+h)+K)\) slots for each encoder. The two encoders at one level share the same register layout. The pre- and post-conditioning operations require only \(O(n)\) more clean working qubits and slots. All registers from an outer level remain allocated during an inner call, so summing over the at most \(J\) levels gives \[t+O(J(K+n+h))=t+O(N^{10})\] total qubits. Summing the slots gives \[O\bigl(J[L(K+n+h)+K+n]\bigr)=O(N^{13}).\] These sums suffice because there is only one recursive call at a level. The local amplification repetitions have already been included in the factor \(L\) in the encoder cost. Finally, the structure can be generated without computing any of its table contents. The successive orders \(d,q,s,k\) have \(O(n)\)-bit descriptions and are computed in polynomial time. Register allocations, state-preparation bit order, Fourier transforms, reflections, and the fixed number \(L\) of amplification rounds depend only on these sizes. Every operation depending on \(U_\lambda\)—the signs, permutations, state-preparation amplitudes, support lists, and recursively prescribed matrices—changes only a slot table. At most \(t+O(N^{10})\) register positions occur in any ordered control list, so writing all such lists for \(O(N^{13})\) slots still takes polynomial time in \(n+t\). No list of possible label values is generated. This proves both the uniformity assertion and (36). ◻ Compilation into one Boolean oracleThe skeleton of Proposition 14 specifies only polynomially many slots, although each slot may have a large table. We now encode finite gate words for those tables in one Boolean function. Two details require care: the words must approximate matrices with their actual phases, and the resulting circuit must be generated without finding those words. The need to retain scalar phases under coherent control is already present in the general controlled-gate decompositions of [3]. Phase-sensitive one-qubit approximationWe first prove the approximation fact needed for the compilation. The argument combines the irrational-rotation proof of universality for this gate set [5] with the commutator refinement underlying the Solovay–Kitaev theorem [7]. The weaker polynomial bound below is sufficient for our purpose. Lemma 15. There is an absolute positive integer \(K_{\mathrm w}\) such that every \(S\in SU(2)\) and every \(0<\xi<1\) admit a word in \(H,T,T^\dagger\) of length at most \(K_{\mathrm w}\xi^{-3}\) whose matrix has determinant one and differs from \(S\) by at most \(\xi\) in operator norm. Proof. Write \(X_p,Y_p,Z_p\) for the Pauli matrices, with \(Y_p=iX_pZ_p\), and put \(\boldsymbol\sigma=(X_p,Y_p,Z_p)\). We first show that the determinant-one words are dense in \(SU(2)\). Up to their scalar factors, \[T=e^{i\pi/8}e^{-i(\pi/8)Z_p},\qquad HTH=e^{i\pi/8}e^{-i(\pi/8)X_p}.\] Thus \(W=(HTH)T=e^{i\pi/4}V\), where \(V\in SU(2)\) has trace \[\mathop{\mathrm{Tr}}V=2\cos^2(\pi/8)=1+\frac{\sqrt2}{2}.\] Recall that an algebraic integer is a root of a monic polynomial with integer coefficients; equivalently, its monic minimal polynomial over \(\mathbb Q\) has integer coefficients. The displayed trace is not an algebraic integer, because its monic irreducible polynomial is \(x^2-2x+1/2\). Consequently the eigenvalues of \(V\) cannot be roots of unity: roots of unity are algebraic integers, and sums of algebraic integers are algebraic integers. Writing its eigenvalues as \(e^{\pm i\theta}\), we have \(\theta/\pi\notin\mathbb Q\). The word \(W^4=-V^4\) has determinant one, and its powers are dense in the one-parameter circle about the rotation axis of \(V\). For completeness, every matrix in \(SU(2)\) has the form \(\cos t\,I+i\sin t\,\mathbf v\cdot\boldsymbol\sigma\), with \(\mathbf v\in\mathbb R^3\) a unit vector, except that the axis can be chosen arbitrarily when \(\sin t=0\). Multiplying the two rotations defining \(V\) shows that its axis is not parallel to the \(Z_p\) axis. Conjugation by \(T\) rotates this axis through \(\pi/4\) about \(Z_p\), giving a nonparallel axis. The closure of the determinant-one words contains both corresponding circles: conjugation of a determinant-one word by \(T\) is again such a word. Rotating the second axis slightly about the first moves it out of the plane they span. Conjugation by an element of the first circle therefore gives a third circle with a linearly independent axis. Let \(\mathbf v_1,\mathbf v_2,\mathbf v_3\) be the three axes. The derivative at zero of \[(t_1,t_2,t_3)\longmapsto \prod_{j=1}^3\exp(i t_j\mathbf v_j\cdot\boldsymbol\sigma)\] sends \((t_1,t_2,t_3)\) to \(i(\sum_jt_j\mathbf v_j)\cdot\boldsymbol\sigma\), an isomorphism onto the three-dimensional tangent space of \(SU(2)\) at the identity. The inverse function theorem shows that these products contain a neighborhood of the identity. The closure of our words is thus an open subgroup. Every other coset is open as well, so connectedness of \(SU(2)\) forces this subgroup to be all of \(SU(2)\). Here connectedness also follows from the preceding representation of \(SU(2)\) as the unit sphere in \(\mathbb R^4\). We next obtain a uniform length bound. Density and compactness provide a finite \(\varepsilon_0\)-net of determinant-one words of some fixed maximum length \(\ell_0\), where \(\varepsilon_0>0\) will be chosen sufficiently small. Suppose that words of length at most \(\ell\) form an \(\varepsilon\)-net, and choose such a word \(W_0\) within \(\varepsilon\) of a target \(S\). The residual \(S W_0^\dagger\) has the form \[S W_0^\dagger=\exp(i\mathbf a\cdot\boldsymbol\sigma), \qquad |\mathbf a|\le 2\varepsilon,\] for sufficiently small \(\varepsilon\). The Pauli commutator identity gives skew-Hermitian matrices \[P=i\mathbf u\cdot\boldsymbol\sigma,\qquad Q=i\mathbf v\cdot\boldsymbol\sigma, \qquad [P,Q]=i\mathbf a\cdot\boldsymbol\sigma,\] with \(\lVert P\rVert,\lVert Q\rVert=O(\sqrt\varepsilon)\): take perpendicular vectors with \(\mathbf u\times\mathbf v=-\mathbf a/2\) and equal lengths. For \(A=e^P\) and \(B=e^Q\), expansion of the four exponential series through degree two gives \[ABA^\dagger B^\dagger=I+[P,Q]+O(\varepsilon^{3/2}) =S W_0^\dagger+O(\varepsilon^{3/2}).\] All errors here are in operator norm with absolute constants; the remaining terms of the exponential series are bounded by a constant times \((\lVert P\rVert+\lVert Q\rVert)^3\). Choose net words \(\widetilde A,\widetilde B\) within \(\varepsilon\) of \(A,B\). The gain in precision survives this substitution. Indeed, \[\begin{align*} \lVert ABA^\dagger B^\dagger- \widetilde A B\widetilde A^\dagger B^\dagger\rVert &\le 2\varepsilon\lVert B-I\rVert,\\ \lVert \widetilde A B\widetilde A^\dagger B^\dagger- \widetilde A\widetilde B\widetilde A^\dagger\widetilde B^\dagger\rVert &\le 2\varepsilon\lVert \widetilde A-I\rVert. \end{align*}\] The first inequality follows by writing \(B=I+(B-I)\) and cancelling the identity terms; the second is the same calculation with the roles reversed. Both right sides are \(O(\varepsilon^{3/2})\). Therefore the word \[\widetilde A\widetilde B\widetilde A^\dagger \widetilde B^\dagger W_0\] approximates \(S\) to \(C\varepsilon^{3/2}\) and has length at most \(5\ell\). Inverse words are available because \(H^\dagger=H\) and both \(T\) and \(T^\dagger\) belong to the alphabet. Choose the fixed initial net so small that \(C\sqrt{\varepsilon_0}\le1/2\). Repeating the refinement \(j\) times gives error at most \(2^{-j}\varepsilon_0\) and length at most \(5^j\ell_0\). Taking \(j\) just large enough for the former quantity to be at most \(\xi\) gives a length bounded by \(K_{\mathrm w}\xi^{-3}\), since \(\log_2 5<3\). ◻ Only the existence of the fixed integer \(K_{\mathrm w}\) will be used. A generator can hardcode this integer; it does not need the net or a procedure that selects approximating words. Those selections will be stored in the oracle. Lookup, control, and restoration of scratch spaceProposition 16 (Compilation of slots). Let a skeleton have \(S\) slots on \(Q\) qubits, and put \(\eta=1/h\) for an integer \(h\ge2\). There is a deterministic procedure, polynomial in \(Q,S,1/\eta\), that produces a circuit over \(H,T,T^\dagger,\mathrm{CNOT}\) and one Boolean oracle, with polynomially many qubits, gates, calls, and address bits. For every assignment of the slot tables, some contents of that oracle make the circuit differ from the prescribed skeleton by at most \(S\eta\) on inputs with its added scratch qubits zero, with the comparison circuit keeping those scratch qubits zero. Proof. First consider one table entry \(W_y\in U(2)\). Choose a real number \(\gamma_y\) and a matrix \(S_y\in SU(2)\) such that \[W_y=e^{i\gamma_y}S_y.\] By Lemma 15, choose words within \(\eta/2\) of \(S_y\) and of \[P_y=\mathop{\mathrm{diag}}(e^{i\gamma_y},e^{-i\gamma_y}).\] Pad every word with identities to the common length \(\ell=\lceil K_{\mathrm w}(2/\eta)^3\rceil\). Apply the first word to the slot target and the second to a fresh scratch qubit initially in \(\lvert 0\rangle\). Their ideal actions on this input multiply to \(W_y\) on the target and return scratch to zero. The two approximation errors add to at most \(\eta\). Since different \(y\) occupy orthogonal control blocks, this is an operator-norm bound for the entire controlled slot. In particular, the scalar factor \(e^{i\gamma_y}\) has been retained as a relative phase between control values. Use two bits to encode each symbol in \(\{I,H,T,T^\dagger\}\). A single Boolean function stores all symbol bits at addresses containing \[(\text{slot number},\ y,\ \text{which word},\ \text{word position},\ \text{symbol bit}).\] Pad the field for \(y\) to \(Q\) bits. This makes every address have a common length \(O(Q+\log(S+1)+\log(\ell+1))\). For each word position, copy the slot’s controls into the address by CNOTs, set the fixed address bits, and query the two symbol bits into zero qubits. Apply the specified symbol conditionally, then erase the symbol bits by querying again and reverse the address preparation. The original slot controls do not change under any of these target operations, so the erasure is exact even in a superposition of control values. We verify that symbol selection uses only the allowed elementary gates. Bit flips are available as \(HT^4H=X_p\). On bits \(a,b,c\), the integer identity \[ 4abc=a+b+c-(a\oplus b)-(a\oplus c)-(b\oplus c) +(a\oplus b\oplus c) \tag{38}\] implements a doubly controlled \(Z_p\) using \(T,T^\dagger\): compute each parity into clean scratch, apply its indicated phase, and uncompute it. Conjugating the target by \(H\) gives Toffoli. Thus equality tests on symbol bits and all required reversible address operations are exact. To apply \(T\) conditionally, compute the AND of its control and target into a clean scratch bit, apply \(T\) there, and uncompute the AND; the same construction applies to \(T^\dagger\). For a controlled \(H\), define \[D_0=(T^2H)T(T^2H)^\dagger.\] Because \((T^2H)Z_p(T^2H)^\dagger=Y_p\), we have \(D_0=e^{i\pi/8}e^{-i(\pi/8)Y_p}\) and hence \[D_0Z_pD_0^\dagger=(X_p+Z_p)/\sqrt2=H.\] Apply \(D_0^\dagger\) to the target, then a controlled \(Z_p\), then \(D_0\). When the control is zero the two unconditional gates cancel; when it is one their product is exactly \(H\). A controlled \(Z_p\) itself is a CNOT conjugated on its target by \(H\). This proves that every selected symbol, including its phase, can be applied exactly. It remains to compose the approximate slots. Let \(A_j\) denote the actual implementation of slot \(j\), and let \(V_j\) denote the ideal slot acting trivially on all added scratch. The phase scratch may be reused. Although its actual state need not be exactly zero after a slot, the identity \[A_S\cdots A_1-V_S\cdots V_1 =\sum_{j=1}^S A_S\cdots A_{j+1}(A_j-V_j)V_{j-1}\cdots V_1\] uses the error \(A_j-V_j\) only after an ideal prefix. Such a prefix keeps all added scratch at zero, precisely where the one-slot bound applies. The unitary suffix preserves its norm. The total error is therefore at most \(S\eta\) on the claimed input subspace. There are two words per slot, \(O(\ell)\) symbol positions per word, and a polynomial number of elementary operations per lookup. The addresses, scratch, and total circuit size are thus polynomial in \(Q,S,1/\eta\). Generating the circuit requires only the skeleton, the fixed length bound, and ordinary integer arithmetic. In particular, it never selects a word or computes a table entry. Each target merely determines one admissible Boolean function storing all choices. Adjoint slots can have their own addresses and approximating words, or can reverse and invert stored words; either convention uses the same single oracle. ◻ Proof of Theorem 1. Apply Proposition 14 with \(d=2^n\) and no initial labels. Its skeleton has polynomially many qubits and slots, and approximates the target unitary, including restoration of its working qubits, to error less than \(1/100\). If it has \(S\) slots, compile it using \[\eta=\frac{1}{100(S+1)}.\] Proposition 16 adds error less than \(1/100\). The entire circuit is therefore within \(1/10\) in operator norm, on zero-workspace inputs, of applying \(U\) and returning every other qubit to zero. The same polynomial bounds its width, number of gates and calls, oracle address length, and the running time of its deterministic generator, after increasing fixed coefficients if necessary. Take the original index qubits as the designated outputs. For a pure input state \(\lvert \psi\rangle\) together with a reference register, let \(a\) and \(b\) be the actual and ideal final unit vectors before discarding workspace. The operator-norm estimate gives \(\lVert a-b\rVert\le1/10\). Since the trace norm of a rank-one matrix \(uv^\dagger\) is \(\lVert u\rVert\lVert v\rVert\), \[\lVert aa^\dagger-bb^\dagger\rVert_1 \le\lVert (a-b)a^\dagger\rVert_1+\lVert b(a-b)^\dagger\rVert_1 \le2\lVert a-b\rVert\le\frac15.\] Partial trace cannot increase the trace norm of a Hermitian matrix, and convexity gives the same bound for mixed input states. In particular the supremum in Theorem 1, with its \(n\)-qubit reference, is at most \(1/5<1/2\). ◻
|
| ||||||||
|