Polynomial-time unitary synthesis from a Boolean oracle

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 timeSource 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 factorsSource 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 generalSource 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 problemSource 4. One circuit, built from n alone, uses polynomially many gates, qubits and queries, each of polynomial lengthSource 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 systemSource 6. The oracle may depend on the target unitary, and the paper gives no fast way to build itSource 7.

The key step trades one big task for one smaller task. Each step removes at least a fixed polynomial fraction of the dimensionSource 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 stepSource 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.