that of Beals et al. [@bbcmw], which represents an efficient quantum algorithm’s acceptance probability by a low-degree polynomial, and then shows that no such polynomial exists; and that of Ambainis [@ambainis], which upper-bounds how much the entanglement between the algorithm and database can increase via a single query.  Both techniques have also led to lower bounds for many other problems besides database search.

The crucial property of quantum mechanics that all three proofs exploit is its *linearity*: the fact that, until a measurement is made, the vector of amplitudes can only evolve by means of linear transformations.  Intuitively, if we think of the components of a superposition as parallel universes, then linearity is what prevents the universe containing the marked item from simply telling all the other universes about it.

Quantum Advice\[ADVICE\]
------------------------

The above assumed that our quantum computer begins in some standard initial state, such as the all-$0$ state (denoted $\left\vert 0\cdots0\right\rangle $).  An interesting twist is to consider the effects of other initial states.  Are there quantum states that could take exponential time to prepare, but that would let us solve $\mathsf{NP}$-complete problems in polynomial time were they given to us by a wizard?  More formally, let 