$\left(  n+1\right)
^{st}$ qubit will be $\left\vert 1\right\rangle $ if the answer is ‘yes,’ and $\left\vert 0\right\rangle $ if the answer is ‘no.’

On the other hand, any nonlinear quantum computer can also be simulated in $\mathsf{PSPACE}$.  For even in nonlinear theories, the amplitude of any basis state at time $t$ is an easily-computable function of a small number of amplitudes at time $t-1$, and can therefore be computed in polynomial space using depth-first recursion.  It follows that, assuming arbitrary nonlinear gates and no error, $\mathsf{PSPACE}$ exactly characterizes the power of nonlinear quantum mechanics.

But what if we allow error, as any physically reasonable model of computation must?  In this case, while it *might* still be possible to solve $\mathsf{NP}$-complete problems in polynomial time, I am not convinced that Abrams and Lloyd have demonstrated this.[^10]  Observe that the standard quantum error-correction theorems break down, since just as a tiny probability of success can be magnified exponentially during the course of a computation, so too can a tiny probability of error.  Whether this problem can be overcome might depend on which specific nonlinear gates are available; the issue deserves further investigation.

Hidden-Variable Theories\[HIDDEN\]
----------------------------------

Most people who quote Einstein’s declaration that 