A Boolean oracle for every quantum unitary

← All digests

Family 283 · Mathematical physics
Importance 4/5 · Provisional editorial rating
Sources consulted 2026-10-25

1. The question

An arbitrary operation on $n$ qubits is a unitary matrix of dimension $2^n$. Describing it usually requires exponentially many numbers. Suppose this description is stored behind a Boolean oracle that a quantum circuit can query coherently. Can a polynomial-size circuit use that access to perform the operation?

This question separates the size of stored information from the work required to use it. The oracle can be enormously complicated, but each query address, the workspace and the computation must remain polynomial in $n$.

Family 283 reports a positive answer to the constant-error version of the Aaronson–Kuperberg unitary synthesis problem. One circuit generated from $n$ alone can approximate every $n$-qubit unitary after a suitable oracle is chosen. The oracle may depend on the target; the theorem does not efficiently construct it from a given matrix description.

2. Background and essential definitions

A classical function queried quantum mechanically

A Boolean function $f:\{0,1\}^m\to\{0,1\}$ supplies the reversible gate

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

Although its answers are bits, a query can use a superposition of addresses. The oracle then acts coherently on the entire superposition. This is more powerful than reading one classical table entry and forgetting its address.

The oracle’s input length is $m$, while its truth table has $2^m$ entries. Polynomial address length therefore permits an exponentially large table. Query complexity counts calls to $O_f$; circuit complexity additionally counts ordinary gates and qubits. Small query count does not imply small query width or total resources.

A unitary $U$ acts on states by the channel $\mathcal U(\rho)=U\rho U^\dagger$. The proposed circuit begins with zero workspace, retains $n$ designated output qubits and discards the rest, producing a channel $\Phi$.

Error on every input, including entangled ones

The full diamond-norm error is

$$\|\Phi-\mathcal U\|_\diamond =\sup_\rho\|((\Phi-\mathcal U)\otimes\operatorname{id}_R)(\rho)\|_1.$$

The supremum includes density matrices on the input and an $n$-qubit reference $R$. The trace norm is $\|X\|_1=\operatorname{Tr}\sqrt{X^\dagger X}$. This convention has no factor of one half; the maximum distance between channels is two.

Including a reference tests whether the circuit preserves correlations with systems it never touches. Agreement on a few basis inputs, or even preparation of each desired output column separately, would not establish this guarantee.

Uniform generation means a deterministic classical algorithm outputs the circuit in polynomial time from the input length. Its wiring and resource bounds cannot be redesigned separately for every target unitary; only the oracle changes.

3. Development history and previous partial results

Aaronson and Kuperberg posed the unitary synthesis question in their work on quantum and classical proofs and advice. Aaronson later highlighted it as an open problem in quantum query complexity.

State synthesis is an easier comparison problem: prepare one specified state from a fixed initial state. Irani, Natarajan, Nirkhe, Rao and Yuen obtained low-query constructions with polynomial space. Rosenthal subsequently gave uniform polynomial-size state preparation with one Boolean query when workspace may be discarded, and four when it must be cleared.

Why does this not immediately solve unitary synthesis? Preparing a column $U|j\rangle$ while retaining its input label gives $|j\rangle U|j\rangle$. On a superposition of labels, discarding the first register can destroy coherence. Erasing that label while retaining the correct quantum output is a separate task.

For unitaries, Rosenthal obtained an upper bound of order $2^{n/2}$, up to polynomial factors, with a target-dependent oracle. Lombardi, Ma and Wright established a general one-query obstruction, also ruling out polynomially many parallel queries of polynomial length. Dong, Lombardi and Ma gave explicit one-query separations for structured unitary families. These bounds leave room for multiple queries interleaved with computation.

The manuscript also compares with the September 2026 Nehoran–Yuen construction, in the cited version. It achieves a constant number of suitable phase or Boolean queries but uses resources exponential in the number of input qubits. Thus the remaining issue is polynomial total resources, including the oracle interface width. The present claim addresses that requirement, not merely the number of queries.

4. What the new manuscript claims

There is a fixed polynomial $p$ and a deterministic generator that, on input $1^n$, outputs an oracle circuit $A_n$ within time $p(n)$. The circuit uses only

$$H,\quad T=\operatorname{diag}(1,e^{i\pi/4}),\quad T^\dagger,\quad\operatorname{CNOT}$$

and one Boolean oracle with input length $m(n)\leq p(n)$. Its qubit count, elementary-gate count and oracle-call count are each at most $p(n)$.

For every $U\in U(2^n)$, there exists a Boolean function $f$ on those addresses such that

$$\|\Phi_{n,f}-\mathcal U\|_\diamond\leq\frac12.$$

The quantifier order is essential:

$$\text{one circuit }A_n\quad\text{for every }U\quad\text{with a suitable }f_U.$$

There is no restriction on the truth-table size or classical circuit complexity of $f_U$, and no prescribed matrix-entry encoding that the algorithm must use. The statement supplies an existence theorem for an encoding suited to the synthesis procedure.

Consequently this is not a polynomial-time classical compiler from an arbitrary explicitly listed unitary. It is also not an oracle-free polynomial-size implementation of every unitary. The target-dependent information remains in the oracle, whose evaluation is treated as a primitive query.

The headline guarantee is constant error in the full diamond norm. The proof obtains room within that bound through stronger intermediate estimates, but the reported theorem should not be replaced by an unstated optimal precision-resource tradeoff.

5. Why the advance matters

Importance: 4/5, provisional. The result addresses a longstanding general synthesis problem and removes the exponential total-resource cost of earlier approaches in the stated oracle setting.

It clarifies how classical information can control a coherent quantum operation. State preparation alone leaves an input-label problem; the construction claims a way to erase that label efficiently while maintaining a uniform action on all inputs and references.

The distinction between storing and producing the oracle is central to its significance. The theorem says that an appropriate description can be used efficiently, not that every target admits a short efficiently computable classical description. This is a major structural result in oracle computation if correct, without implying a generic practical shortcut for compiling arbitrary quantum matrices.

6. The main idea

Reduce the dimension without duplicating the recursive call

The construction reduces synthesis of a $d$-dimensional unitary to synthesis of one smaller controlled unitary. Each step removes at least an inverse-polynomial fraction of the dimension. Since $d\leq2^n$, polynomially many steps suffice.

A recursive reduction can still become exponential if it calls the smaller synthesis routine several times at each level. The manuscript’s reduction uses that smaller routine exactly once, surrounded by two encoding operations. This is the key resource-accounting feature.

After suitable permutations, signs and Walsh transforms, partition the current unitary as

$$V=\begin{pmatrix}A&B\\C&D\end{pmatrix}, \qquad\|D\|\leq\frac34.$$

The lower block is the part to be removed. For a diagonal unitary $Z$ on those coordinates, feeding the lower output back into the lower input gives the transfer matrix

$$F=A+BZ(I-DZ)^{-1}C.$$

Because $D$ is a contraction, the inverse has a convergent geometric-series expansion. Unitarity of $V$ makes $F$ unitary on the remaining coordinates.

Encode the feedback coherently

The manuscript builds forward and backward encoding maps from the original space into a phase-label register and a smaller state. Truncating the two geometric series gives nearly isometric maps and an approximate intertwining relation around one controlled application of $F$.

Averaging a common phase cancels terms of unequal degree. The remaining Gram-matrix sums telescope by unitarity, leaving errors that decay exponentially in truncation length. Thus the feedback identity becomes a controlled circuit reduction rather than merely a matrix formula.

Erase the input label through sparse rows

The encoders’ Fourier coefficients are arranged using frequencies $(1,i,i^2,\ldots,i^L)$ for each removed coordinate $i$. Products of at most $L$ phases record coordinate multisets through power sums.

This arrangement means each row of the coefficient matrix has only polynomially many possible input labels, even when a column is dense. After coherently preparing a column, the circuit can use the short row list to erase the original input index. Amplitude amplification converts the resulting scaled map into the needed approximate encoding.

Finally, the proof begins with programmable controlled one-qubit gates and compiles their tables into finite words over the fixed gate set, read through a single Boolean oracle. The compilation preserves relative phases between different control labels. Uniform approximation on zero-workspace inputs, including reference systems, yields the final channel bound after workspace is discarded.

7. Scope, limitations, and open questions

The oracle may be arbitrarily hard to construct or evaluate classically. Its assumed unit-cost availability is part of the model. There is no contradiction with counting arguments showing that most unitaries lack small ordinary circuits: the oracle carries a potentially enormous description.

The theorem allows polynomially many interleaved queries. It does not evade the earlier one-query or parallel-query lower bounds by claiming those restricted models suffice. It also counts query width, which distinguishes it from constant-query constructions with exponential workspace.

The stated target is constant-error channel synthesis. Efficient construction of useful oracles from natural descriptions, sharper precision dependence and practical gate counts are further questions. They are not supplied by the existence theorem itself.

8. Sources and further reading

Aaronson–Kuperberg’s original problem and the cited constant-query predecessor are linked above. Rosenthal’s query and depth upper bounds give the earlier exponential-time comparison. The source below provides the dimension-reduction, encoding and compilation claims, reported with their oracle quantifiers intact.

Source manuscripts

• M1. OpenAI, Polynomial-Time Unitary Synthesis from a Boolean Oracle (October 5, 2026).

Sources consulted on 25 October 2026 at repository revision 1581d4c. Download the manuscript citations.