Unitary synthesis from a Boolean oracle: coherent encodings and recursion

Source and verification

This article explains family 283 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

Overview

An arbitrary $n$-qubit unitary has an exponentially large matrix. Family 283 asks whether a polynomial-size quantum circuit can implement it when a suitably chosen Boolean oracle stores the target-dependent information. The manuscript gives a positive constant-error result, counting gates, qubits, queries, and query-address length. The circuit is generated from $n$ alone; finding the oracle is not part of the efficient algorithm. (OpenAI, 2026)

🏷️ Preliminaries: coherent queries and channel error

The prerequisites are finite-dimensional linear algebra, singular values, Fourier orthogonality, and basic quantum circuits. A state on $n$ qubits is a unit vector in ${\mathbb{C}}^{2^n}$, or more generally a positive semidefinite matrix $\rho$ of trace one. A unitary $U$ induces the channel $\mathcal{U}(\rho )=U\rho U^{†}$.

A Boolean oracle $f:\{0,1{\}}^m\to \{0,1\}$ is accessed coherently:

$$O_f|x,b⟩=|x,b\oplus f(x)⟩.$$

Thus it acts linearly on superpositions of addresses, and querying twice erases an answer when the address is unchanged. The truth table may be enormous even though an address contains only $m$ bits.

Error is measured in the full diamond norm. For two channels on $n$ qubits, one takes the supremum of their output trace-norm difference over inputs entangled with an $n$-qubit reference register. The trace norm is $\Vert X{\Vert }_1=\mathrm{Tr}\sqrt{X^{†}X}$; there is no factor $1/2$ in this convention.

The manuscript's oracle synthesis theorem

A deterministic classical algorithm, given $1^n$, produces in polynomial time a circuit $A_n$ using the fixed gates $H,T,T^{†},\mathrm{CNOT}$ and one Boolean oracle. Its qubits, elementary gates, oracle calls, and address length are polynomial in $n$. For every $U\in U(2^n)$, some Boolean function $f$ makes its output channel satisfy

$$\Vert {\Phi }_{n,f}-\mathcal{U}{\Vert }_{\diamond }\le \frac{1}{2}.$$

The circuit depends only on $n$; the oracle may depend on $U$. (OpenAI, 2026)

There is no bound on the classical circuit complexity or truth-table size of $f$, no mandated matrix-entry encoding, and no efficient construction of $f$ from a description of $U$. This quantifier order permits target information to reside in the oracle while requiring the circuit that uses it to be uniform.

Preparing each column of $U$ does not directly solve the problem. The transformation $|i⟩|0⟩\mapsto |i⟩U|i⟩$ leaves a record of $i$. Tracing that record destroys interference between different input columns. The proof must erase the input label coherently.

🏷️ Programmable slots and clean-workspace estimates

The intermediate model allows a programmable slot: one target qubit undergoes an arbitrary matrix $W_y\in U(2)$ selected by the other qubits’ control value $y$. A circuit skeleton specifies slot positions and controls while leaving their tables unspecified.

In this model, a state on $u$ qubits can be prepared with $u+1$ slots. Conditional rotations successively distribute the probability mass among binary prefixes, and a final diagonal slot supplies phases. A basis permutation can likewise be implemented by writing its image into temporary bits, erasing the original index with its inverse, and swapping registers. These are inexpensive slot constructions; their large tables still have to be compiled into oracle access later.

The recursion handles entire families $U_{\lambda }$ coherently. If $\iota$ appends zero workspace, the required estimate is

$$\begin{array}{c}\Vert C\iota -\iota \mathcal{U}\Vert \le \delta ,\\ \mathcal{U}=\sum _{\lambda }|\lambda ⟩⟨\lambda |\otimes U_{\lambda }.\end{array}$$

The norm is operator norm with the actual phases retained. It includes restoration of workspace in the ideal comparison and remains valid with any additional reference system. No promise is made about the circuit on initially nonzero workspace.

🏷️ Removing a contracting block

At dimension $2\le d\le 2^n$, choose

$$\begin{array}{c}M=4096(n+1{)}^2,r=\frac{3}{4},\\ q=2^{\lfloor {\log }_{2}d\rfloor },\\ s=\max \{1,\lfloor q/M\rfloor \},\\ k=d-s.\end{array}$$

The proof finds short slot changes of basis $P_{\mathrm{L}},P_{\mathrm{R}}$ such that

$$\begin{array}{c}V=P_{\mathrm{L}}U{P}_{\mathrm{R}}=\left(\begin{array}{cc}A& B\\ C& D\end{array}\right),\\ \Vert D\Vert \le r.\end{array}$$

The $k$ retained coordinates are called ports, and the $s$ removed coordinates are internal. If $s=1$, a row permutation moves an entry of size at most $1/\sqrt{d}$ to the required position.

For larger $s$, Walsh transforms and two sets of random diagonal signs suffice. The first signs bound every entry of an intermediate matrix by $4\sqrt{(n+1)/q}$, using a subgaussian tail estimate and a union bound. The second signs control its compressed operator norm.

The key matrix estimate bounds $\mathbb{E}\Vert {\sum }_i{\epsilon }_i{L}_i\Vert$ for Hermitian matrices by $2h^{1/(2a)}\sqrt{(2a-1)v}$, where $h$ is their dimension and $v=\Vert {\sum }_i{L}_i^2\Vert$. To prove it, replace the signs by Gaussians, apply integration by parts to $\mathbb{E}\mathrm{Tr}{X}^{2a}$, and iterate

$$\mathbb{E}\mathrm{Tr}{X}^{2a}\le (2a-1)v\mathbb{E}\mathrm{Tr}{X}^{2a-2}.$$

Conditional Jensen returns from Gaussians to signs. Applied to the Hermitian dilation of the compressed block, this gives $\mathbb{E}\Vert D\Vert \le 16(n+1)\sqrt{s/q}\le 1/4$. Hence a suitable fixed choice exists. Randomness proves existence of oracle table entries; the resulting circuit need not sample these signs.

Since $s\ge d/(4M)$, fewer than $J=8M(n+1)$ reductions reach dimension one. At dimension one, the remaining unitary is a label-dependent scalar phase, implemented directly by a slot on a zero index bit. Polynomially many levels are possible despite the initial dimension $2^n$.

🏷️ Feedback and the smaller unitary

Let $Z$ be a diagonal unitary on the internal coordinates. Feeding internal output $v$ back as input $Zv$ gives

$$\begin{array}{c}y=Au+BZv,\\ v=Cu+DZv.\end{array}$$

Because $\Vert DZ\Vert <1$, these equations yield

$$\begin{array}{c}X=(I-DZ{)}^{-1}C,\\ F=A+BZX.\end{array}$$

The smaller matrix $F$ is unitary. Indeed, $V(u,ZXu)=(Fu,Xu)$, and norm conservation cancels the internal norms, giving $\Vert Fu\Vert =\Vert u\Vert$. Since $F$ is square, it is unitary.

Introduce $E=(I,ZX{)}^{\mathsf{T}}$ and $R=(I,X{F}^{\ast }{)}^{\mathsf{T}}$. The exact relation $VE=RF$ implies

$$F{E}^{\ast }=R^{\ast }V.$$

This identity suggests encoding an input with $E^{\ast }$, applying one controlled copy of $F$, and decoding with the matching map from $R^{\ast }$. Individual maps at a fixed $Z$ need not preserve norm. The next step averages a structured family of phases to obtain nearly isometric encodings.

🏷️ Phase averaging and Fourier support

Choose a truncation length $L$ and let

$$\begin{array}{c}b=nL+\lceil {\log }_2(L+1)\rceil ,\\ \mathcal{G}=(\mathbb{Z}/2^b\mathbb{Z}{)}^{L+1},\\ v_i=(1,i,i^2,\dots ,i^L).\end{array}$$

For $z\in \mathcal{G}$, put $Z_{ii}(z)=\exp (2\pi i{v}_i\cdot z/2^b)$. Truncate the forward and backward geometric series defining $E$ and $R$ after $L$ terms, giving $E_L(z),R_L(z)$. Each tail has norm at most $\tau =r^L/(1-r)$.

The field map ${\mathcal{E}}_L$ sends $x$ to the uniform superposition of $|z⟩E_L(z{)}^{\ast }x$; define ${\mathcal{R}}_L$ similarly. Averaging the first coordinate of $z$ cancels products with unequal phase degree. For equal degrees, unitarity supplies $C{C}^{\ast }=I-D{D}^{\ast }$, so the Gram sum telescopes:

$$\begin{array}{c}\sum _{\ell =0}^{L-1}{W}^{\ell }(I-W{W}^{\ast })(W^{\ast }{)}^{\ell }\\ =I-W^L(W^{\ast }{)}^L,W=D{Z}^{\prime }.\end{array}$$

Here $Z^{\prime }$ retains the other phase coordinates. The backward series has the corresponding identity. Consequently both maps satisfy

$$\begin{array}{c}(1-r^{2L})I\le {\mathcal{T}}^{\ast }\mathcal{T}\le I,\\ \Vert \tilde{F}{\mathcal{E}}_L-{\mathcal{R}}_{L}V\Vert \le 2\tau ,\end{array}$$

where $\tilde{F}$ applies $F(z)$ controlled by $z$.

In Fourier coordinates, every row of either map has at most $L$ nonzero input columns. To see why, each monomial records a multiset of at most $L$ internal visits. Its frequency is the signed sum of the corresponding $v_i$. There is no modular wraparound: each ordinary coordinate sum is less than $2^b$.

The first coordinate gives the multiset size and the remaining coordinates its power sums. Newton’s identities recover its monic root polynomial, hence the multiset. Every contributing input index belongs to that multiset. Different orders of visits can change a coefficient, but cannot introduce additional input indices. At zero frequency, each output port has just its matching input-port column.

For example, an entry of $BZDZ$ has terms $B_{aj}{D}_{ji}{\chi }_{v_j+v_i}(z)$. A fixed frequency remembers the unordered pair $\{i,j\}$, so at most those two input columns contribute.

🏷️ Coherent erasure and amplitude amplification

Consider a matrix $T$ with at most $L$ nonzeros per row and $(1-\epsilon )I\le T^{\ast }T\le I$. Prepare its $i$th column while retaining $i$, placing missing column norm in a failure flag.

For each output row $u$, an oracle table provides a padded list of exactly $L$ possible input indices. Inverse preparation of their uniform superposition maps each valid index to zero with amplitude $1/\sqrt{L}$. A second flag reduces the selected block to $t_{0}T$, where

$$\theta =\frac{\pi }{4L+2},t_0=\sin \theta .$$

Two reflections perform amplitude amplification without measuring or conditioning on the good flag. On a singular direction with singular value $\sigma$, the initial angle is $\beta =\arcsin (t_0\sigma )$. After $L$ rounds it is $(2L+1)\beta$. Because $\sigma \in [\sqrt{1-\epsilon },1]$ and $(2L+1)\theta =\pi /2$, the output differs from $\sigma$ times the desired singular vector by at most $5\epsilon$.

The singular-direction planes are mutually orthogonal, so this is an operator-norm estimate for arbitrary superpositions. Applied to the Fourier fields, each encoder has error at most $5r^{2L}$. Columns may be dense; only the bound on the number of nonzeros in each row is used.

🏷️ A recursion with one inner call

One level applies the first encoder, the smaller controlled synthesis circuit, and the inverse of the second encoder. If the inner circuit’s error is ${\delta }^{\prime }$, the new error is at most

$${\delta }^{\prime }+\frac{2r^L}{1-r}+10r^{2L}.$$

The inner approximation is invoked only on the ideal encoded subspace. Any actual leakage is covered by the encoder error and preserved in norm by the inner unitary. Thus no assumption about the inner circuit’s behavior outside its promised subspace is needed.

Most importantly, each level uses the inner circuit once. Amplitude amplification repeats the encoder’s preparation circuits, without repeating the recursive circuit. Otherwise a polynomial recursion depth could still produce exponential size.

The source takes $L=10000J$. With $r=3/4$, Bernoulli’s inequality gives $r^L\le 3/L$, so total recursion error is at most $18J{r}^L\le 54/10000<1/100$. The resulting skeleton has $O((n+1{)}^{10})$ qubits and $O((n+1{)}^{13})$ slots. These deliberately loose polynomial bounds describe an existence construction, not a practical implementation.

🏷️ Compilation and the phase issue

The final step replaces every slot table by words over the fixed gate set. A table entry factors as $W_y=e^{i{\gamma }_y}{S}_y$ with $S_y\in SU(2)$. Approximate $S_y$ on the target, and approximate $\mathrm{diag}(e^{i{\gamma }_y},e^{-i{\gamma }_y})$ on a zero scratch qubit. The latter retains the branch’s scalar phase while ideally returning scratch to zero.

Dropping that phase would be wrong under coherent control: different $y$ values would acquire incorrect relative phases. The source proves a polynomial word-length bound for phase-sensitive determinant-one approximations and stores the chosen words in the oracle.

An address records the slot, control value, which of the two words is being applied, word position, and symbol bit. The circuit reads a symbol, applies its gate conditionally, queries again to erase the symbol, and uncomputes the address. Controls are unchanged during the operation, so erasure works in superposition.

For $S$ slots, choosing per-slot accuracy $\eta =1/[100(S+1)]$ makes compilation error less than $1/100$. A telescoping product compares each erroneous slot after an ideal prefix, which keeps scratch zero. This justifies the sum of errors even though actual phase scratch may have a small nonzero component.

The final circuit is within $1/10$ of the ideal clean-workspace isometry. For actual and ideal final unit vectors $a,b$, including a reference,

$$\Vert a{a}^{†}-b{b}^{†}{\Vert }_1\le 2\Vert a-b\Vert \le \frac{1}{5}.$$

Partial trace and convexity preserve this bound, proving the advertised diamond-norm error at most $1/2$ with room to spare. The result is constant-error synthesis with polynomial total resources relative to an unrestricted target-dependent Boolean oracle.

🏷️ Reading and verification scope

The main file and all seven principal sections were read, including the contraction estimate, Fourier support argument, encoder singular-value calculation, recursion, and phase-sensitive compilation. This is a source audit of the exposition, not an implemented synthesis circuit or an independent certification of every research claim. External cited results were not separately audited.

🏷️ Key steps and proof outlines

Why the matrix moment bound tolerates noncommuting summands

The contraction argument uses a trace inequality whose proof explains where noncommutativity is handled. Set $X={\sum }_i{g}_i{L}_i$, with Hermitian $L_i$ and independent standard real Gaussians $g_i$. Differentiating each factor of $X^{2a-1}$ under Gaussian integration by parts gives

$$\mathbb{E}\mathrm{Tr}{X}^{2a}=\sum _i\sum _{\ell =0}^{2a-2}\mathbb{E}\mathrm{Tr}(L_i{X}^{\ell }{L}_i{X}^{2a-2-\ell }).$$

One cannot move $L_i$ past $X$. Instead diagonalize $X$, put $m=2a-2$, and use

$$|{\lambda }_k{|}^{\ell }|{\lambda }_j{|}^{m-\ell }\le \frac{\ell }{m}|{\lambda }_k{|}^m+\frac{m-\ell }{m}|{\lambda }_j{|}^m.$$

For $m>0$, symmetry of $|(L_i{)}_{jk}{|}^2$ under exchanging $j,k$ makes the resulting sum exactly $\mathrm{Tr}(L_i^2{X}^m)$. The case $m=0$ is immediate. As $m$ is even, $X^m$ is positive, so ${\sum }_i{L}_i^2⪯vI$ yields the moment recurrence in the earlier section.

Iteration produces

$$\mathbb{E}\mathrm{Tr}{X}^{2a}\le h(2a-1)!!v^a.$$

Taking the $2a$-th root turns the matrix dimension into $h^{1/(2a)}$; choosing moment order comparable to its logarithm controls this factor. Finally write $g_i={\epsilon }_i|g_i|$. Conditional Jensen, with $\mathbb{E}|g_i|=\sqrt{2/\pi }$, transfers the Gaussian estimate to signs. Thus the random basis changes are justified by a positive trace argument rather than a scalar concentration claim applied entry by entry. (OpenAI, 2026, p.m atrix sign estimate)

Why coherent erasure is uniform over all input superpositions

The encoder’s singular-value calculation also needs an orthogonality check. If $T{v}_j={\sigma }_j{e}_j$, the preliminary unitary has

$$\mathsf{B}{v}_j=\sin {\beta }_j{e}_j+\cos {\beta }_j{e}_j^{\prime },\sin {\beta }_j=t_0{\sigma }_j.$$

The $e_j$ lie in the good output space and the $e_j^{\prime }$ in its orthogonal complement. Unitarity of $\mathsf{B}$ and orthogonality of both the inputs and good singular vectors imply that the $e_j^{\prime }$ are mutually orthogonal. Hence the two reflections preserve mutually orthogonal two-dimensional planes, not merely individual success probabilities.

After $L$ rounds, the angle error from $\pi /2=(2L+1)\theta$ is at most

$$(2L+1)(\theta -{\beta }_j)\le 2(2L+1)t_0(1-{\sigma }_j)\le \pi (1-{\sigma }_j).$$

Adding the radial discrepancy $1-{\sigma }_j$ bounds the full output-vector error by $5\epsilon$. Since the errors occupy orthogonal planes, their norm on an arbitrary superposition is bounded by the largest individual error, with no dimension factor. This is what permits one coherent recursive call for all phase labels and all inputs, including inputs entangled with a reference. (OpenAI, 2026)

See Also

• Exact quantum factoring explains another finite-gate construction where coherent workspace and exact reflection phases matter; its input and exactness requirements differ from this oracle-assisted approximation theorem.
• Quantum parity and localization provides a complementary circuit-complexity perspective on restricting quantum operations.

🏷️ Manuscripts and verification scope

• Polynomial-Time Unitary Synthesis from a Boolean Oracle — pinned manuscript and companion source.

No family scope page was present at lean/docs/283.md in the pinned snapshot. This does not establish that all related formalization code is absent. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Polynomial-Time Unitary Synthesis from a Boolean Oracle.