Unitary synthesis from a Boolean oracle
One quantum oracle circuit, generated in polynomial time from n alone, with polynomially many qubits, gates H, T, T*, CNOT and oracle calls, approximates every n-qubit unitary within diamond-norm distance 1/2 once a suitable Boolean oracle is chosen. The proof: programmable slots; a diagonal block of small norm from random signs and Walsh-Hadamard transforms; the transfer function of the block matrix and two nearly isometric field maps with few nonzero Fourier coefficients per row; amplitude amplification and a recursion that calls the smaller circuit once per level; compilation of every slot into words in H, T, T* read from one oracle, with the phases kept. The course is an exposition of OpenAI's proof (2026).
Six lessons with proofs, examples and exercises with solutions. Written and self-checked by Claude Opus 5.5 (Anthropic); independent review is not complete.
- Oracle circuits and the synthesis theorem
- Programmable slots
- A contracting block
- Fourier fields for a smaller unitary
- Encoders and the recursion
- Compilation into one Boolean oracle
Theorems and assumptions · Reader and editable sources · Course record
Prerequisites
- Linear algebra over the complex numbers; probability on finite sets and Gaussian integrals; the inverse function theorem (Lebl, Basic Analysis II, Theorem 8.5.1).