Any unitary from a table, proved at last?
An AI preprint claims a positive answer to the constant-error unitary synthesis problem
Covers result 283 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.
3:23. English captions available. The video loads from YouTube when you press play.
Chapters
The claim, in plain words
A quantum computer on n qubits can in principle apply any unitary transformation, but counting shows that most of them need exponentially many gates. The obstacle is not storing the description: pinning down a 10-qubit unitary to precision 0.1 takes about 3.5 million bits, which a lookup table addressed by about 22 bits can hold. So Aaronson and Kuperberg asked: is there one polynomial-size quantum circuit that, given the right Boolean lookup table for each target, approximately implements every unitary? Aaronson later named it the unitary synthesis problem, and in 2021 wrote, “my conjecture is that the answer is negative.” For preparing quantum states, one query to a suitable table is enough, and Rosenthal made that efficient in 2023. For unitaries, Lombardi, Ma and Wright proved that one query is not enough, and a recent result needs only a few queries, but each one exponentially long.
Result 283 is one OpenAI preprint, 21 pages, dated October 5, 2026. It claims a positive answer. For each n, one uniform circuit of polynomial size, built from Hadamard, T, T inverse and CNOT gates and making polynomially many queries of polynomial length to a single Boolean oracle, implements every n-qubit unitary within diamond-norm error 1/2, once the oracle is chosen for that unitary.
What it doesn’t claim
Smaller error, an efficient way to build the oracle (whose truth table is exponentially long), or a practical size; the constants are astronomical. For one qubit, error 1/2 lets the gate’s two phases slip about 14.5 degrees either way, ignoring overall phase; the proof actually gets 1/5, about 5.7 degrees.
Where it stands
- Posted as a preprint
- OpenAI, 21 pages, dated October 5, 2026
- Peer reviewed
- Not yet
- Checked in Lean
- No
Last checked October 19, 2026. The preprint has not been revised. There is no Lean formalization. Scott Aaronson, who posed the problem with Greg Kuperberg, called it “the opposite of what most of us expected,” while noting that the paper gives no efficient way to construct the oracle. OSVerify has not reviewed it, and we found no published check by specialists.
How the proof goes
- Peel off a corner, feed it back. The proof scrambles the target with well-chosen signs and Walsh–Hadamard transforms, so that one corner block becomes a contraction, with norm at most 3/4. Feeding that corner back through a phase gives a smaller unitary, and the original is recovered from it, approximately, by a truncated series.
- Recurse, and store everything in one table. Labels made of powers of each coordinate’s index, decoded with Newton’s identities, keep each step sparse enough to run coherently with amplitude amplification, and each level calls the smaller problem only once, so the recursion stays polynomial. Every gate choice is stored in the oracle as a word of Hadamard, T and T inverse gates, phase included.
The numbers in the video
- Ours: describing a 10-qubit unitary to precision 0.1 takes about 3.5 million bits; a table with about 22 address bits holds them.
- Ours: diamond-norm error 1/2 corresponds to phases slipping about 14.5 degrees, and 1/5 to about 5.7 degrees.
- Ours: in a toy table of gate words, keeping the stored phases gives error 0.1; dropping them gives error 2.
Read the source
- Polynomial-Time Unitary Synthesis from a Boolean Oracle (PDF), 21 pages.
- The collection’s catalog, where this is result 283.
The paper
OpenAI groups related papers into one result; this one has a single paper.
Transcript
Read the full script
0:00The question
A quantum computer on n qubits can in principle apply any unitary transformation, but counting shows that most of them need exponentially many gates. The obstacle is not storing the description. Our computer finds that pinning down a 10-qubit unitary to precision 0.1 takes about 3.5 million bits, which a lookup table addressed by about 22 bits can hold. So Aaronson and Kuperberg asked: is there one polynomial-size quantum circuit that, given the right Boolean lookup table for each target, approximately implements every unitary? Aaronson later named it the unitary synthesis problem, and in 2021 wrote, “my conjecture is that the answer is negative”. For preparing quantum states, one query to a suitable table is enough, and Rosenthal made that efficient in 2023. For unitaries, Lombardi, Ma and Wright proved that one query is not enough, and a recent result needs only a few queries, but each one exponentially long.
1:03The claims
Result 283 is one OpenAI preprint, 21 pages, dated October 5, 2026. It claims a positive answer. For each n, one uniform circuit of polynomial size, built from Hadamard, T, T inverse and CNOT gates and making polynomially many queries of polynomial length to a single Boolean oracle, implements every n-qubit unitary within diamond-norm error 1/2, once the oracle is chosen for that unitary. What does error 1/2 mean? For one qubit, our computer finds it lets the gate’s two phases slip about 14.5 degrees either way, ignoring overall phase; the proof actually gets 1/5, about 5.7 degrees. Not claimed: smaller error, an efficient way to build the oracle, whose truth table is exponentially long, or a practical size. The constants are astronomical.
1:58How the proof goes
The proof scrambles the target with well-chosen signs and Walsh–Hadamard transforms, so that one corner block becomes a contraction, with norm at most 3/4. Feeding that corner back through a phase gives a smaller unitary, and the original is recovered from it, approximately, by a truncated series. Labels made of powers of each coordinate’s number, decoded with Newton’s identities, keep each step sparse enough to run coherently with amplitude amplification, and each level calls the smaller problem only once, so the recursion stays polynomial. Every gate choice is stored in the oracle as a word of Hadamard, T and T inverse gates, phase included. In our toy table, dropping the stored phases raises the error from 0.1 to 2.
2:45Where it stands
The preprint is unrefereed and unchanged since release, with no Lean formalization. Aaronson, who posed the problem with Kuperberg, called it “the opposite of what most of us expected”, while noting that the paper gives no efficient way to construct the oracle. OSVerify has not reviewed it, and we found no published check by specialists. If it holds, a polynomial-size quantum circuit with the right enormous table can carry out any unitary operation to within a fixed, coarse error, though nobody yet knows how to write the table.
Spot a mistake?
This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.