# Polynomial-time unitary synthesis from a Boolean oracle > Claims a polynomial-size quantum circuit can carry out any n-qubit operation, given a suitable Boolean oracle. Plain-English explainer with sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-283/ Last updated: 2026-10-14 **Claims a polynomial-size quantum circuit can carry out any n-qubit operation, given a suitable Boolean oracle.** **Trust:** Claimed, not checked · **Papers:** 1 · **First paper:** October 5, 2026 · **Field:** Mathematical physics · **Entry:** 283 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. Describing a general quantum operation on n qubits takes far more numbers than any small circuit can hold. A Boolean oracle is a black box that answers yes-or-no questions, and it can hold that description instead. Aaronson and Kuperberg asked in 2007 whether a small circuit plus such an oracle could run any operation. This paper claims yes, with error at most 1/2 in the diamond norm. The oracle depends on the target operation, and the paper gives no fast way to build it. ## At a glance - **First step:** 2007 (Scott Aaronson and Greg Kuperberg, who posed the unitary synthesis problem) - **Significance:** Major. It answers a named open problem in quantum query complexity in its constant-error form. - **Trust:** Claimed, not checked - **Field:** Mathematical physics (1 paper) ## The explanation A quantum computer with 10 qubits holds a state described by 2¹⁰ = 1,024 complex numbers. An operation on those qubits, a unitary, is a square table of 1,024 by 1,024 entries. Pinning down a general one takes 4¹⁰ = 1,048,576 real numbers. At 50 qubits that becomes about 1.27 × 10³⁰ numbers. A circuit with a few million gates cannot store that much detail. One way around this is an oracle. An oracle is a black box that answers yes-or-no questions about a long string of bits. A quantum circuit can ask it questions in superposition, many at once. The unitary's description can live inside the oracle, while the circuit stays small. Aaronson and Kuperberg asked in 2007 whether every unitary can be run this way in polynomial time[1]. Polynomial means the cost grows like a fixed power of n, such as n³. For n = 50 qubits, n³ is 125,000. Earlier results fell short. Rosenthal gave a method whose running time grows like 2^(n/2), up to polynomial factors[2]. At 50 qubits, 2^25 is 33,554,432, before those factors. In the other direction, Lombardi, Ma and Wright showed that one query is not enough in general[3]. The obstacle is coherence. The circuit must act correctly on every input at once, including superpositions. Preparing one target column is easier, but it leaves behind a record of which input was used. This paper claims a positive answer to the constant-error form of the problem[4]. One circuit, built from n alone, uses polynomially many gates, qubits and queries, each of polynomial length[5]. Its error is at most 1/2 in the diamond norm, a worst-case distance between two operations. This norm can be as large as 2, so 1/2 is a quarter of the maximum. The bound holds even for inputs entangled with an outside system[6]. The oracle may depend on the target unitary, and the paper gives no fast way to build it[7]. The key step trades one big task for one smaller task. Each step removes at least a fixed polynomial fraction of the dimension[8]. Suppose each step removed one fiftieth. Starting from dimension 2⁵⁰, about 1,716 steps would bring it down to 1. The smaller circuit is used exactly once at each step[9]. That stops the recursion from growing into an exponentially large circuit. How sure is this? A computer proof checker called Lean has not checked any part of it. The argument rests on the paper's own analysis of the recursion and its error terms. No specialist review of the paper has been published. **What it doesn't show.** This does not give a fast classical way to build the oracle, and it does not reach small error, only error at most 1/2. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major if the proof holds. It reaches only constant error, gives no fast way to build the oracle, and has no Lean check or published specialist review. ## Words used - **Qubit:** The basic unit of quantum information, which can be in a blend of 0 and 1. - **Unitary:** A reversible operation on qubits; for n qubits it is a 2ⁿ by 2ⁿ table of complex numbers. - **Boolean oracle:** A black box that answers yes-or-no questions about bit strings; a quantum circuit can query it in superposition. - **Polynomial:** Growing like a fixed power of n, such as n³, rather than exponentially like 2ⁿ. - **Diamond norm:** A worst-case distance between two quantum operations, allowing inputs linked to an outside system; it ranges from 0 to 2 here. - **Entangled:** Linked so that two quantum systems cannot be described separately. ## The original paper - [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf) - October 5, 2026 ## Quoted lines from the paper (9) [1] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > Aaronson and Kuperberg posed this question in 2007; Aaronson later highlighted it among open problems in quantum query complexity. [2] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > For unitary synthesis, Rosenthal gave a running-time upper bound of order $2^{n/2}$ up to polynomial factors, using an oracle suited to the target unitary. [3] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > In the other direction, Lombardi, Ma, and Wright proved a general one-query lower bound, which also rules out polynomially many parallel queries of polynomial length. [4] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > We give a positive answer to the constant-error formulation. [5] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > The circuit uses polynomially many gates, qubits, and queries, and each query has polynomial length. [6] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > The error bound holds for arbitrary input states, including states entangled with a reference system. [7] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > The oracle may depend on the target unitary; the theorem does not give an efficient classical procedure for constructing it. [8] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > Each reduction removes a fraction at least $1/\poly(n)$ of the dimension, so only polynomially many reductions are needed even when $d=2^n$. [9] From [Polynomial-Time Unitary Synthesis from a Boolean Oracle](https://github.com/openai/math/blob/main/preprints/Polynomial-Time-Unitary-Synthesis-from-a-Boolean-Oracle-October-5-2026/paper.pdf): > The smaller synthesis circuit is used exactly once at each step. ## Other sources - [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” ## Related - [The optimal quartic separation between randomized and quantum queries](https://closedform.nishachay.tech/e/openai-math-2026-284/) - Mathematical physics - [Exact quantum factoring over a fixed finite gate set](https://closedform.nishachay.tech/e/openai-math-2026-279/) - Mathematical physics - [Classical capacity of generalized amplitude damping](https://closedform.nishachay.tech/e/openai-math-2026-276/) - Mathematical physics - [Parity is not in QAC 0](https://closedform.nishachay.tech/e/openai-math-2026-274/) - Mathematical physics - [Bloch's law, its lattice correction, and the spherical magnetization law](https://closedform.nishachay.tech/e/openai-math-2026-271/) - Mathematical physics - [Mathematical physics](https://closedform.nishachay.tech/science/mathematics/mathematical-physics/) - Field · 25 results - [Quantum theory](https://closedform.nishachay.tech/topic/quantum/) - Topic · 9 results - [Open since the 2000s](https://closedform.nishachay.tech/open-since/2000s/) - Era · 48 results - [Claimed, not yet checked](https://closedform.nishachay.tech/trust/claimed/) - Trust · 130 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20283%5D%20)