Quantum algorithm prepares states using NP oracle efficiently
State Synthesis with an NP oracle
Computational Complexity
Summary
Preparing a specific quantum state exactly is usually very hard. The authors describe a quantum method that can build any desired state very precisely and quickly, as long as you can ask a special kind of question called an NP oracle. They also show that simpler types of questions can't do this efficiently, which helps understand the limits of quantum computing. This finding affects some important problems in quantum information and how complicated certain tasks really are.
What this means in practice
- •For quantum algorithm designers: Clarify the complexity resources needed for exact quantum state preparation using NP oracles, guiding algorithm design limits.
- •For quantum hardware developers: Inform limitations on efficient quantum state preparation protocols relevant for hardware requiring precise state initialization.
A theory result. No direct application yet.
Authors
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.