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…
Comments and reviews
No comments yet.
Discussed elsewhere
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-OptimizedOct 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…