Polynomial-Time Unitary Synthesis from a Boolean Oracle
There are a polynomial and a deterministic classical algorithm which, on input for any integer , outputs in time at most a quantum oracle circuit using the gates and a single Boolean oracle of input length , with total number of qubits, elementary gates, and oracle calls each at most , such that for every unitary there is a function for which the output channel of satisfies .
The proof of Theorem 1.1 rigorously combines Proposition 6.2 and Proposition 7.2, and the conversion from clean-workspace operator norm error (≤ 1/10) to full diamond-norm error (≤ 1/5 < 1/2) is mathematically sound.
“There are a polynomial p and a deterministic classical algorithm which, on input 1n for any integer n ≥ 1, outputs in time at most p(n) a quantum oracle circuit An with the following properties. The circuit uses the gates H, T, T†, CNOT and a single Boolean oracle of input length m(n) ≤ p(n). Its total number of qubits, elementary gates, and oracle calls are each at most p(n). For every unitary U ∈ U(2n) there is a function f : {0, 1}m(n) → {0, 1} for which the output channel Φn,f of AOf n satisfies ∥Φn,f − U∥⋄ ≤ 1/2.” · Show in paper