Polynomial-Time Unitary Synthesis from a Boolean Oracle
We give a positive answer to the constant-error formulation of the Aaronson–Kuperberg unitary synthesis problem. For every n, a quantum oracle circuit generated in polynomial time from n alone can approximate the channel of every n-qubit unitary to full diamond-norm error at most 1/2, after a suitable Boolean oracle is chosen. Using the fixed gates \(H,T,T^\dagger,\mathrm{CNOT}\), the circuit has polynomially many qubits, elementary gates, and oracle calls, and its oracle queries have polynomial length. The oracle may depend on the target unitary; the theorem does not give an efficient classical procedure for constructing it.
Cite
@misc{OAI:Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026,
author = {{OpenAI}},
title = {{Polynomial-Time Unitary Synthesis from a Boolean Oracle}},
howpublished = {OpenAI Math Release preprint
\href{https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf}{OAI:Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026}},
year = {2026}
}