consequence in classical complexity.[^8]  But in 1994, Bennett, Bernstein, Brassard, and Vazirani [@bbbv] did show that $\mathsf{NP}\not \subset \mathsf{BQP}$ relative to an oracle.  In particular, they showed that any quantum algorithm that searches an unordered database of $N$ items for a single marked item must query the database $\sim\sqrt{N}$ times.  (Soon afterward, Grover [@grover] showed that this is tight.)

If we interpret the space of $2^{n}$ possible assignments to a Boolean formula $\varphi$ as a database, and the satisfying assignments of $\varphi$ as marked items, then Bennett et al.’s result says that any quantum algorithm needs at least $\sim2^{n/2}$ steps to find a satisfying assignment of $\varphi$ with high probability, *unless* the algorithm exploits the structure of $\varphi$ in a nontrivial way.  In other words, there is no brute-force quantum algorithm to solve $\mathsf{NP}$-complete problems in polynomial time, just as there is no brute-force classical algorithm.

In Bennett et al.’s original proof, we first run our quantum algorithm on a database with no marked items.  We then mark the item that was queried with the smallest total probability, and show that the algorithm will need many queries to notice this change.  By now, many other proofs have been discovered, including 