quantum computing came along, it was hoped that finally we might have a type of parallelism commensurate with the difficulty of $\mathsf{NP}$-complete problems.  For in quantum mechanics, we need a vector of $2^{n}$ complex numbers called amplitudes just to specify the state of an $n$-bit computer (see [@aar:thesis; @fortnow:qc; @nc] for more details).  Surely we could exploit this exponentiality inherent in Nature to try out all $2^{n}$ possible solutions to an $\mathsf{NP}$-complete problem in parallel?  Indeed, many popular articles on quantum computing have given precisely that impression.

The trouble is that if we measure the computer’s state, we see only *one* candidate solution $x$, with probability depending on its amplitude $\alpha_{x}$.[^7]  The challenge is to arrange the computation in such a way that only the $x$’s we wish to see wind up with large values of $\alpha_{x}$.  For the special case of factoring, Shor [@shor] showed that this could be done using a polynomial number of operations—but what about for $\mathsf{NP}$-complete problems?

The short answer is that we don’t know.  Indeed, letting $\mathsf{BQP}$ be the class of problems solvable in polynomial time by a quantum computer, we do not even know whether $\mathsf{NP}\subseteq\mathsf{BQP}$ would imply $\mathsf{P}=\mathsf{NP}$ or some other unlikely 