Polynomial-Time Unitary Synthesis from a Boolean Oracle

Introduction

A 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], Section 7, Problem (4); Aaronson later highlighted it among open problems in quantum query complexity [1], Problem 6.

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 result

We use the fixed elementary gate set

where $\mathrm{CNOT}|a,b\rangle= |a,a \oplus b\rangle$. A Boolean oracle $f : \{0,1\}^{m} \to\{0,1\}$ supplies the gate

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

where $R$ is an $n$-qubit reference register and $\rho$ ranges over density operators on the input and $R$. Thus the norm in (1.2) has no factor of $1/2$.

Theorem 1.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$, 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

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 work

State 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.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 reduction

The 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/\operatorname{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

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

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

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.1.

Controlled tasks and programmable slots

We 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 \le2^{n}$, write

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

Let $\iota$ append all working qubits in state $\lvert0\rangle$. A circuit $C$ solves this controlled task with error $\delta$ if

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

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.1 (State preparation). For every $u\ge1$ there is a skeleton of $u+1$ slots that maps $\lvert\lambda\rangle\lvert0\rangle^{u}$ 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}\lvert a_{x}\rvert^{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

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 2.2 (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:

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 $|0\rangle|\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 2.3 (Fourier transforms). The unitary

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 block

The 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], Sections 6–7 for the Gaussian integration-by-parts and trace-product method. We include the proof with the constants used below.

Lemma 3.1 (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 = \left\|\sum_i L_i^2\right\|$. For every integer $a \ge1$,

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

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$,

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_i L_i^2 \preceq vI$, equation (3.2) implies

Iterating from $\operatorname{Tr} I = h$ yields

Here $(2a-1)!! = 1\cdot3\cdots(2a-1)$. Therefore

To return to signs, write $g_i = \varepsilon_it_i$, where the $t_i = |g_i|$ are independent of the signs and have common mean $\mu= \sqrt{2/\pi}$. Conditional Jensen gives

Average over the signs, apply (3.3), and use $\mu^{-1} < 2$. □

Fix throughout the construction

For an integer $2 \le d \le2^n$, let $q$ be the largest power of two not exceeding $d$, and define

We call the first $k$ indices ports and the last $s$ indices internal indices. Both groups are nonempty.

Proposition 3.2 (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

where the block sizes are $k,s$ from (3.5). 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\le1/\sqrt{d}<3/4$, and the permutation has the claimed slot implementation by Lemma 2.2.

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_{2}q}$, 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_{q}E_{1}$ on the left and $E_{2}H_{q}$ on the right, acting as the identity on the remaining $d-q$ indices. The resulting internal block is

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}\le1/q$. For completeness, a real sign sum with squared coefficient sum at most $1/q$ satisfies

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

There are $qs$ entries. With $u=4\sqrt{(n+1)/q}$, the union-bound failure probability is at most

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\le1$.

Let $h_i,c_i$ be row $i$ of $W,C'$, respectively, regarded as row vectors. Then

Choosing independent signs $\varepsilon_i$ for $E_{1}$, write

The two diagonal blocks of $\sum_i L_i^2$ satisfy

The norm of $\sum_i \varepsilon_i L_i$ equals $\|D\|$. Apply Lemma 3.1 with $h=2s$ and $a=n+1$. Since $(2s)^{1/(2n+2)}\le\sqrt{2}$, we obtain

The last inequality uses $s\le q/M$. Some choice of $E_1$ consequently satisfies $\|D\|\le1/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 2.2 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 3.3 (Dimension decrease). For the parameters in (3.5), $s\ge d/(4M)$. Starting at any $d\le2^n$ and repeatedly replacing $d\ge2$ by $d-s$, one reaches $d=1$ in fewer than

steps.

Proof. If $q/M\ge2$, then $s=\lfloor q/M\rfloor\ge 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

contrary to its being a positive integer.

Fourier fields for a smaller unitary

Let $d=k+s\le2^n$, with $k,s\ge1$, and suppose that

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 coordinates

For 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

Since $\lVert DZ\rVert< 1$, the second equation has the unique solution $v = Xu$, and the first then gives $y = Fu$, where

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], Section 3. The same conservation of norm proves unitarity with independently chosen diagonal phases.

Lemma 4.1. For the unitary block matrix in (4.1) and any diagonal unitary $Z$, the matrix $F$ in (4.2) is unitary. If

then

Proof. The definitions give $VE = O$. Consequently,

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 (4.4). Comparing the bottom blocks of $V^{*}R = EF^{*}$ gives

Multiplication by $Z^{*}$ and $\lVert Z^{*}D^{*}\rVert\le r < 1$ give the second identity.

Truncation and averaging

Fix an integer truncation length $L \ge1$, and set

For $w,z \in\mathcal{G}$, write

Number the internal coordinates by $i = 1,\ldots,s$ and put

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 4.3. These two properties will give the norm bound and the row bound, respectively.

Apply Lemma 4.1 at each $z$ to obtain $F(z)$, $E(z)$, $R(z)$. Truncate the two Neumann expansions by defining

Here and below, products containing $Z$ are evaluated at the same $z$. Since every block of a unitary has norm at most one,

Define the field maps $\mathcal{E}_L,\mathcal{R}_L:\mathbb{C}^d\to\mathbb{C}^{G}\otimes\mathbb{C}^k$ by

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 4.2. For either $\mathcal{T}=\mathcal{E}_L$ or $\mathcal{T}=\mathcal{R}_L$,

In addition, let $\widetilde{F}$ apply $F(z)$ to the port register, controlled on $z$. Then

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

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

Unitarity of $V$ gives $CC^*=I-DD^*=I-WW^*$. Therefore the sum telescopes:

As $\lVert W\rVert\leq 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

so the internal Gram block is exactly the sum in (4.12), with these choices of $W,C_0$. This proves (4.10) for both maps.

Finally, Lemma 4.1 and (4.8) give, pointwise,

Apply this bound to a fixed vector and average its squared norm over $z$ to obtain (4.11).

Few possible input indices at each Fourier frequency

The norm bounds supply nearly isometric maps. To implement them, we also need a restriction on their matrix entries. Use the Fourier basis

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 4.3. 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

These identities follow by taking the logarithmic derivative of $\prod_{t=1}^m(1+i_tx)=\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

whereas those of $R_L^*$ are sums of

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

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 encodings

A 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], Section 2. Preparing states to realize a matrix as a block of a larger unitary is also a standard block-encoding method [10], Lemmas 47–48. Here arbitrary table-controlled column preparation permits us to use sparsity only in the rows.

A construction for a nearly isometric matrix

Let $\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\leq2^n$. Fix an integer $L\geq1$. Suppose that every row has at most $L$ nonzero entries and

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 5.1. Under (5.1), an exact-slot unitary $U_T$ satisfies

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

We first construct a unitary B with the prescribed block

For each valid input $i$, the column norm is at most one. Conditional on $i$, use Lemma 2.1 to prepare the row register and first flag in a unit vector whose flag-one part is

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

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 (5.4). All three operations together form B.

Starting with B, perform $L$ rounds of

These are implementable with 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

where the $e_j$ are orthonormal. In this calculation identify the input and output spaces with their embeddings $\iota$ and $\jmath$. By (5.4),

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 (5.6), using unitarity of 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 $BP_0$, which is spanned by the mutually orthogonal vectors $Bv_j$. 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 (5.5) sends

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

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-\epsilon}\le\epsilon$. The error vectors lie in mutually orthogonal planes. The same bound therefore holds in operator norm on the whole input space, proving (5.2).

The first preparation uses $O(w+1)$ slots and the second $O(n+h)$, so B uses $O(n+w+h)$ slots. The complete circuit contains $2L+1$ occurrences of B or 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 fields

In the preceding section, a row is a frequency and a port. Let

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 5.2. Under the hypotheses and definitions of Section 4, there are exact-slot unitaries $U_E,U_R$ such that

Each uses $O(L(K+n+h)+K)$ 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 4.3 gives at most $L$ nonzero entries in each row, and Proposition 4.2 supplies (5.1) with $\epsilon=r^{2L}$. Apply Lemma 5.1, 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 $|w\rangle$ becomes $|G|^{-1/2}\sum_z\chi_w(z)|z\rangle$. The same physical register now holds the phase label $z$, rather than the Fourier frequency $w$. Lemma 2.3 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 (5.8) and the stated resource bounds.

Assembling the recursion

The 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 6.1 (One synthesis step). Let $V$ be a unitary on $\mathbb{C}^{k+s}$ in the block form of Proposition 3.2, and let $\lVert D\rVert\le 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 $U_{\mathrm{E}}$ and followed by $U_{\mathrm{R}}^{*}$, synthesizes $V$ with clean-workspace error at most

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}^{G} \otimes\mathbb{C}^{k}$ into the encoder’s good subspace, again with the smaller circuit’s fresh workspace zero. Write $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

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 5.2 gives

The field maps are contractions by Proposition 4.2, and their intertwining bound is (4.11). Consequently,

Multiplication by $U_{\mathrm{R}}^{*}$ proves (6.1). 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 $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 $U_{\mathrm{E}}$ and $U_{\mathrm{R}}$ repeats only their own state-preparation circuits. It never repeats $C$.

We can now choose one set of parameters for all recursion levels. Keep $M,r,J$ from (3.4) and (3.8), and set

Thus $K$ is the number of qubits in each field’s phase register.

Proposition 6.2 (Uniform programmable synthesis). Let $n \ge1$, $1 \le d \le2^n$, and $t \ge0$. 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 (2.1). The circuit uses

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 \ge2$, Proposition 3.2 gives $V_\lambda=P_{L,\lambda}U_\lambda P_{R,\lambda}$ with internal order $s$ and port order $k=d-s$. Apply the one-step construction of Lemma 6.1, 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^*_{R,\lambda}$ before this construction and $P^*_{L,\lambda}$ afterward. These transformations have exact slot implementations, so they introduce no further error. Their order is correct because $P^*_{L,\lambda}V_\lambda P^*_{R,\lambda}=U_\lambda$.

At each step, Lemma 6.1 adds at most

to the error of the smaller circuit. There are fewer than $J$ steps by Lemma 3.3. Bernoulli’s inequality gives $(4/3)^L\ge1+L/3$, and hence $r^L\le3/L$. The total error is therefore

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

Proposition 5.2 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

total qubits. Summing the slots gives

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 (6.4).

Compilation into one Boolean oracle

The skeleton of Proposition 6.2 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 approximation

We 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 7.1. 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_{\mathrm{p}},Y_{\mathrm{p}},Z_{\mathrm{p}}$ for the Pauli matrices, with $Y_{\mathrm{p}}=iX_{\mathrm{p}}Z_{\mathrm{p}}$, and put $\boldsymbol{\sigma}=(X_{\mathrm{p}},Y_{\mathrm{p}},Z_{\mathrm{p}})$. We first show that the determinant-one words are dense in $SU(2)$. Up to their scalar factors,

Thus $W=(HTH)T=e^{i\pi/4}V$, where $V\in SU(2)$ has trace

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

sends $(t_1,t_2,t_3)$ to $i(\sum_j t_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 $SW_0^\dagger$ has the form

for sufficiently small $\varepsilon$. The Pauli commutator identity gives skew-Hermitian matrices

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

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,

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

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$. $\square$

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 space

Proposition 7.2 (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},\operatorname{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

By Lemma 7.1, choose words within $\eta/2$ of $S_y$ and of

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 $\lvert0\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

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 $H T^4 H=X_p$. On bits $a,b,c$, the integer identity

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

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

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

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.1. Apply Proposition 6.2 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

Proposition 7.2 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\leq1/10$. Since the trace norm of a rank-one matrix $uv^\dagger$ is $\lVert u\rVert\lVert v\rVert$,

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.1, with its $n$-qubit reference, is at most $1/5<1/2$.