Polynomial-Time Unitary Synthesis from a Boolean Oracle

Proof. Fix a label and write a=\sum_x a_x\ket{x}. 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

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].□

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 \ket{0}\ket{\pi_\lambda(x)}. Swap them using three CNOTs per pair of bits.□

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

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 \E[g_iP(g)]=\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_iL_i^2\preceq vI, equation (3.2) implies

Iterating from \Tr I=h yields

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

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

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

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 \norm D\leq1/\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_2q}, and let W consist of its last s columns. We will choose diagonal sign matrices E_1,E_2 on \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

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

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 \norm{C'}\leq1.

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_iL_i^2 satisfy

The norm of \sum_i\varepsilon_iL_i equals \norm D. Apply Lemma 3.1 with h=2s and a=n+1. Since (2s)^{1/(2n+2)}\leq\sqrt2, we obtain

The last inequality uses s\leq q/M. Some choice of E_1 consequently satisfies \norm D\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 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.□

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

contrary to its being a positive integer.□

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 \norm{Z^*D^*}\le r<1 give the second identity.□

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 \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 \norm{W}\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

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).□

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_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

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

Proof. Set

We first construct a unitary \mathsf 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 \mathsf B.

Starting with \mathsf B, perform L rounds of

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

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 \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 jth 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-\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 (5.2).

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

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 \varepsilon=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 \ket w becomes |\mathcal G|^{-1/2}\sum_z\chi_w(z)\ket z. 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.□

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 \C^{\mathcal G}\otimes\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

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 \mathsf U_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 \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.□

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 3.2 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 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_{\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 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\geq1+L/3, and hence r^L\leq3/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).□

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,

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\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_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 \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

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

with \norm{P},\norm{Q}=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 (\norm P+\norm Q)^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.□

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 \ket0. 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 HT^4H=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 \ket\psi 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 \norm{a-b}\le1/10. Since the trace norm of a rank-one matrix uv^\dagger is \norm u\norm v,

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