nonlinear variants of quantum mechanics, one could use entangled states to transmit superluminal signals.  More relevant for us, Abrams and Lloyd [@al] showed that one could solve $\mathsf{NP}$-complete and even $\mathsf{\#P}$-complete problems in polynomial time—at least if the computation were error-free.  Let us see why this is, starting with $\mathsf{NP}$.

Given a black-box function $f$ that maps $\left\{  0,1\right\}  ^{n}$ to $\left\{  0,1\right\}  $, we want to decide in polynomial time whether there exists an input $x$ such that $f\left(  x\right)  =1$.  We can start by preparing a uniform superposition over all inputs, denoted $2^{-n/2}\sum
_{x}\left\vert x\right\rangle $, and then querying the oracle for $f$, to produce $2^{-n/2}\sum_{x}\left\vert x\right\rangle \left\vert f\left(
x\right)  \right\rangle $.  If we then apply Hadamard gates to the first register and measure that register, one can show that we will obtain the outcome $\left\vert 0\cdots0\right\rangle $ with probability at least $1/4$.  Furthermore, conditioned on the first register having the state $\left\vert 0\cdots0\right\rangle $, the second register will be in the state$$\frac{\left(  2^{n}-s\right)  \left\vert 0\right\rangle +s\left\vert
1\right\rangle }{\sqrt{\left(  2^{n}-s\right)  ^{2}+s^{2}}}$$ where $s$ is the number of inputs $x$ such that $f\left(  x\right)  =1$.  So the problem reduces to that of distinguishing two possible states of a single 