Polynomial-time unitary synthesis from a Boolean oracle. Solves the constant-error Aaronson–Kuperberg unitary synthesis problem: a uniform polynomial-size quantum oracle circuit approximates every n-qubit unitary channel within diamond-norm error 1/2, after a suitable Boolean oracle is chosen. Gates, qubits, oracle calls and query length are polynomially bounded. The target-dependent oracle may have an unrestricted truth table; its efficient classical construction is not asserted.
released 2026-10-05 | 1 theorem · 9 lemmas · 16 proofs · 9,236 words |
PLAY LEVEL 1 »(pdf)
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 classical procedure for constructing it.