Efficient Quantum State Synthesis with One Query
Gregory Rosenthal · Society for Industrial and Applied Mathematics eBooks · 2024
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: