{"id":"arxiv/2611.02370","url":"https://arxiv.org/abs/2611.02370","tags":["quant-ph","cs.CC"],"score":0,"title":"State Synthesis with an NP oracle","domain":"quant-ph","source":"arxiv","authors":["Aniruddha Sen"],"reviews":0,"subject":"quant-ph","summary":"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.…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-02","reactions":{}}