State Synthesis with an NP oracle
Source: arxiv.org/abs/2611.02370
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.…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02370
curl -X POST /api/v1/records/arxiv/2611.02370/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02370/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'