In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.
AI Summary
The paper asks how weak a classical oracle can be while allowing a fixed quantum algorithm to prepare arbitrary states efficiently, assuming a separate oracle $O$ gives access to their amplitudes. It gives a state-synthesis algorithm using an $\mathsf{NP}^O$ oracle, improving the previous $\mathsf{PP}^O$ upper bound on oracle complexity while allowing polynomially many queries.
For an $n$-qubit target state, the algorithm achieves fidelity at least $1-\epsilon$ in $\operatorname{poly}(n,\log(1/\epsilon))$ time with $\operatorname{poly}(n)$ oracle queries. With a $\mathsf{P}^{\mathsf{NP}}$ oracle, the query count becomes $O(n/\log n)$. The construction first uses approximate counting with an NP oracle to estimate prefix probabilities and prepare a distribution whose probabilities approximate the target pointwise within a factor of two. Quantum rejection sampling then corrects the amplitudes using direct amplitude access. Its success probability is approximately $1/2$, enabling a constant number of exact-amplitude-amplification steps to obtain inverse-exponential accuracy.
The paper also states a $\widetilde{\Omega}(2^{n/2})$ query lower bound for synthesis using $\mathsf{P}^O$ or $\mathsf{P/poly}^O$ oracles, via reduction from unstructured search. It discusses consequences for relating amplitude computation to state preparation and for oracle approaches to QMA search-to-decision reductions.
The result assumes amplitude access; it does not provide efficient preparation from arbitrary succinct state descriptions. Constant-query synthesis with an NP oracle and an analogous NP-oracle upper bound for unitary synthesis remain open. The QMA discussion does not establish a general search-to-decision reduction.
No sign of AI-generated textPossible errorOverclaims
Error found: The appendix fails to establish the claimed P/poly-oracle lower bound because its search reduction treats target-dependent oracle circuits as target-independent advice; its proposed hard basis states can instead be prepared using polynomially many queries to an allowed function encoding the target's bits.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP. I provide evidence that NP is the best possible upper bound by showing that any quantum algorithm using a P oracle, or even a P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA search-to-decision problem and unitary synthesis.
The paper asks how weak a classical oracle can be while allowing a fixed quantum algorithm to prepare arbitrary states efficiently, assuming a separate oracle O gives access to their amplitudes. It gives a state-synthesis algorithm using an NPO oracle, improving the previous PPO upper bound on oracle complexity while allowing polynomially many queries.
For an n-qubit target state, the algorithm achieves fidelity at least 1−ϵ in poly(n,log(1/ϵ)) time with poly(n) oracle queries. With a PNP oracle, the query count becomes O(n/logn). The construction first uses approximate counting with an NP oracle to estimate prefix probabilities and prepare a distribution whose probabilities approximate the target pointwise within a factor of two. Quantum rejection sampling then corrects the amplitudes using direct amplitude access. Its success probability is approximately 1/2, enabling a constant number of exact-amplitude-amplification steps to obtain inverse-exponential accuracy.
The paper also states a Ω(2n/2) query lower bound for synthesis using PO or P/polyO oracles, via reduction from unstructured search. It discusses consequences for relating amplitude computation to state preparation and for oracle approaches to QMA search-to-decision reductions.
The result assumes amplitude access; it does not provide efficient preparation from arbitrary succinct state descriptions. Constant-query synthesis with an NP oracle and an analogous NP-oracle upper bound for unitary synthesis remain open. The QMA discussion does not establish a general search-to-decision reduction.
It is a useful fact in classical computer science that many search problems are reducible to decision problems; this has led to decision problems being regarded as the de facto computational task to study in complexity theory. In this work, we explore search-to-decision reductions for quantum search problems, wherein a quantum algorithm makes queries to a classical decision oracle to output a desired quantum state. In particular, we focus on search-to-decision reductions for QMA, and show that there exists a quantum polynomial-time algorithm that can generate a witness for a QMA problem up to inverse polynomial precision by making one query to a PP decision oracle. We complement this result by showing that QMA-search does not reduce to QMA-decision in polynomial-time, relative to a quantum oracle. We also explore the more general state synthesis problem, in which the goal is to efficiently synthesize a target state by making queries to a classical oracle encoding the state. We prove that there exists a classical oracle with which any quantum state can be synthesized to inverse polynomial precision using only one oracle query and to inverse exponential precision using two oracle queries. This answers an open question of Aaronson from 2016, who presented a state synthesis algorithm that makes O(n) queries to a classical oracle to prepare an n-qubit state, and asked if the query complexity could be made sublinear.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every n-qubit unitary U is computable by efficient quantum circuits relative to some classical oracle f=fU depending on U. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE would imply breakthrough classical lower bounds such as NC=NP.
Along the way, we propose new definitions for the unitary complexity classes unitaryP and unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
In the quantum linear systems problem (QLSP), we are given query access to a d-sparse N×N matrix A with condition number κ, and the ability to prepare a quantum state proportional to a vector b. The goal is to output an ε-approximation to the quantum state proportional to the solution x of Ax=b. Following a long line of work, the best previously known quantum algorithms for the QLSP had query complexities O(κdlog(1/ε)) and κd(κd/ε)o(1), while the best known lower bounds were Ω(κlog(1/ε)) and Ω(κd). We improve these bounds and show that the complexity of the QLSP is Θ(κdlog(1/ε)). We also resolve an open problem of Berry and Childs by showing that any N×N unitary can be implemented with bounded error using O(N) queries to its matrix entries.
What is the power of polynomial-time quantum computation with access to an NP oracle? In this work, we focus on two fundamental tasks from the study of Boolean satisfiability (SAT) problems: search-to-decision reductions, and approximate counting. We first show that, in strong contrast to the classical setting where a poly-time Turing machine requires Θ(n) queries to an NP oracle to compute a witness to a given SAT formula, quantumly Θ(logn) queries suffice. We then show this is tight in the black-box model - any quantum algorithm with "NP-like" query access to a formula requires Ω(logn) queries to extract a solution with constant probability. Moving to approximate counting of SAT solutions, by exploiting a quantum link between search-to-decision reductions and approximate counting, we show that existing classical approximate counting algorithms are likely optimal. First, we give a lower bound in the "NP-like" black-box query setting: Approximate counting requires Ω(logn) queries, even on a quantum computer. We then give a "white-box" lower bound (i.e. where the input formula is not hidden in the oracle) - if there exists a randomized poly-time classical or quantum algorithm for approximate counting making o(logn) NP queries, then BPPNP[o(n)] contains a PNP-complete problem if the algorithm is classical and FBQPNP[o(n)] contains an FPNP-complete problem if the algorithm is quantum.