Efficient Quantum State Synthesis with One Query

We present a polynomial-time quantum algorithm making a single query (in superposition) to a classical oracle, such that for every state |ψ⟩ there exists a choice of oracle that makes the algorithm construct an exponentially close approximation of |ψ⟩. Previous algorithms for this problem either used a linear number of queries and polynomial time, or a constant number of queries and polynomially many ancillae but no nontrivial bound on the runtime. As corollaries we do the following:

• We simplify the proof that statePSPACE ⊆ stateQIP (a quantum state analogue of PSPACE ⊆ IP) and show that a constant number of rounds of interaction suffices.

• We show that QAC 0 f lower bounds for constructing explicit states would imply breakthrough circuit lower bounds for computing explicit Boolean functions.

• We prove that every n-qubit state can be constructed to within 0.01 error by an O(2 n /n)-size circuit over an appropriate finite gate set. More generally we give a size-error tradeoff which, by a counting argument, is optimal for any finite gate set.