{"id":"openai-math/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle","pdf":"https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf","url":"https://github.com/openai/math/tree/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026","tags":["quantum-computing","quantum-circuits","complexity"],"score":0,"title":"Polynomial-Time Unitary Synthesis from a Boolean Oracle","domain":"Mathematical physics","family":"283","origin":"ai-generated","source":"openai-math","authors":["OpenAI"],"reviews":0,"subject":"math.MP","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":1,"published":"2026-10-05","reactions":{},"discussion":[{"url":"https://scottaaronson.blog/?p=10169#:~:text=This%20is%20the%20opposite%20of%20what%20most%20of%20us%20expected","date":"2026-10-07","kind":"web","site":"Shtetl-Optimized","text":"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…","added":"2026-10-24","title":"The Mathocalypse"}],"formalized":false,"family_title":"Polynomial-time unitary synthesis from a Boolean oracle"}