{"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":3,"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","author":"Scott Aaronson"},{"url":"https://mathoverflow.net/a/515911","date":"2026-10-10","kind":"web","site":"mathoverflow.net","text":"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…","added":"2026-11-04","title":"Answer to: Which of the results released by OpenAI went against the conventional mathematical wisdom?","author":"Timothy Chow"},{"url":"https://dakshitakhurana.substack.com/p/classical-at-heart","date":"2026-10-14","kind":"web","site":"dakshitakhurana.substack.com","text":"We mathematicians try something, it breaks, and we try again, sometimes for years, before the ‘aha’ moment arrives.","added":"2026-11-03","title":"Classical at Heart","author":"Dakshita Khurana"}],"formalized":false,"family_title":"Polynomial-time unitary synthesis from a Boolean oracle"}