nonlinear operations are allowed, then it is not hard to see that we could even solve $\mathsf{PSPACE}$-complete problems in polynomial time.  It suffices to solve the following problem: given a Boolean function $f$ of $n$ bits $x_{1},\ldots,x_{n}$, does there exist a setting of $x_{1}$ such that for all settings of $x_{2}$ there exists a setting of $x_{3}$ such that… $f\left(  x_{1},\ldots,x_{n}\right)  =1$?  To solve this, we can first prepare the state$$\frac{1}{2^{n/2}}\sum_{x_{1},\ldots,x_{n}}\left\vert x_{1}\ldots
x_{n},f\left(  x_{1}\ldots x_{n}\right)  \right\rangle .$$ We then apply a nonlinear AND gate to the $n^{th}$ and $\left(  n+1\right)  ^{st}$ qubits, which maps $\left\vert
00\right\rangle +\left\vert 10\right\rangle $, $\left\vert 00\right\rangle
+\left\vert 11\right\rangle $, and $\left\vert 01\right\rangle +\left\vert
10\right\rangle $ to $\left\vert 00\right\rangle +\left\vert 10\right\rangle
$, and $\left\vert 01\right\rangle +\left\vert 11\right\rangle $ to itself (omitting the $\sqrt{2}$ normalization).  Next we apply a nonlinear OR gate to the $\left(  n-1\right)  ^{st}$ and $\left(  n+1\right)  ^{st}$ qubits, which maps $\left\vert 00\right\rangle
+\left\vert 11\right\rangle $, $\left\vert 01\right\rangle +\left\vert
10\right\rangle $, and $\left\vert 01\right\rangle +\left\vert 11\right\rangle
$ to $\left\vert 01\right\rangle +\left\vert 11\right\rangle $, and $\left\vert 00\right\rangle +\left\vert 10\right\rangle $ to itself.  We continue to alternate between AND and OR in this manner, while moving the control qubit leftward towards $x_{1}$.  At the end, the 