arXiv:2611.02370
State Synthesis with an NP oracle
Aniruddha Sen
Abstract
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.
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.
- Comments
- 7 pages