Polynomial-Time Unitary Synthesis from a Boolean Oracle
Source: github.com/openai/math/tree/main/preprints/Polynomial-Time-…
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…
Comments and reviews
No comments yet.
Discussed elsewhere
From Scott Aaronson's blog : Positive solution to the Unitary Synthesis Problem, which Greg Kuperberg and I posed back in 2007. For every n-qubit unitary transformation U, there exists a classical oracle A such that U can be implemented in quantum polynomial time with access to A. This is the…
We mathematicians try something, it breaks, and we try again, sometimes for years, before the ‘aha’ moment arrives.
API
curl /api/v1/records/openai-math/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle
curl -X POST /api/v1/records/openai-math/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/openai-math/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'
The MathocalypseShtetl-OptimizedScott AaronsonOct 7, 2026
This is the opposite of what most of us expected, and could have implications for e.g. the computational problem of decoding Hawking radiation from a black hole and many other problems in quantum complexity theory— if we had an efficient way to construct the oracle A, which this paper doesn’t…