The Aaronson-Kuperberg unitary synthesis problem at constant diamond-norm error

Aaronson and Kuperberg (2007) asked whether, for every $n$ -qubit unitary $U$ , there is a Boolean oracle $A$ such that a polynomial-time quantum algorithm with access to $A$ implements $U$ . Aaronson (2021, Problem 6) named it the Unitary Synthesis Problem, called it wide open and conjectured a negative answer. Known results: state synthesis with one query (Irani et al., Rosenthal), a $2^{n/2}$ -time upper bound for unitaries (Rosenthal), and one-query and parallel-query lower bounds (Lombardi-Ma-Wright). Is there a polynomial-size quantum oracle circuit family which, for every $n$ -qubit $U$ and a suitable Boolean oracle depending on $U$ , implements $U$ approximately?

Result: Proved(see note)
Status: Partial result
AI contribution: AI-discovered
Method: Construction
Field: Quantum query complexity; oracle synthesis of unitaries
Posed by: S. Aaronson and G. Kuperberg, Quantum versus classical proofs and advice, Theory of Computing 3 (2007), Section 7, Problem (4); restated in Aaronson (2021), Problem 6
Year posed: 2007
Years open: 19y
Solved: 2026-10-05
Model: Unreleased internal OpenAI model
Vendor: OpenAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Collection: OpenAI math release (October 2026), version adc7f12
Significance: 35 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Theorem 1.1: there are a polynomial $p$ and a deterministic algorithm outputting, on $1^n$ , an oracle circuit $A_n$ with at most $p(n)$ qubits, gates and oracle calls and oracle input length at most $p(n)$ , such that for every $U\in U(2^n)$ some $f$ gives $\|\Phi_{n,f}-\mathcal U\|_\diamond\le1/2$ . The method is a recursive dimension reduction using one coherently controlled smaller synthesis per step. It does not achieve arbitrarily small error, does not give an efficient classical procedure for the oracle, and answers positively a question on which Aaronson (2021) had conjectured a negative answer.

What the AI did

Produced by an unreleased internal OpenAI model as part of the openai/math release (pinned commit adc7f12). The release README says results were produced by one fixed procedure averaging about three hours of ChatGPT Pro thinking compute each; this result is not among the README exceptions (the Hodge conjecture for CM abelian varieties and the Re(s) > 11/12 zero-free region). The manuscript is authored as OpenAI with no human author named. No Lean formalization accompanies it.

Verification

No independent mathematician has checked this yet. Checked here: abstract, introduction and Theorem 1.1 of the TeX source, read against Aaronson's 2021 statement of Problem 6 (fetched for this check). Theorem 1.1 gives a circuit family generated in time polynomial in $n$ from $1^n$ (gates $H,T,T^\dagger,\mathrm{CNOT}$ ; polynomial qubits, gates, queries and query length) such that for every $U$ some Boolean oracle yields full diamond-norm error at most $1/2$ (no factor $1/2$ in the norm). The paper calls this the constant-error formulation; Aaronson's statement does not fix the error, and smaller-error versions are not addressed. The oracle is existential with no efficient construction. Not refereed here. No Lean formalization.

The Aaronson-Kuperberg unitary synthesis problem at constant diamond-norm error

What was actually shown

What the AI did

Verification

Sources

Discussion