qubit—for example, the states corresponding to $s=0$ and $s=1$.  The only difficulty is that these states are exponentially close.

But a nonlinear operation need not preserve the angle between quantum states—it can pry them apart.  Indeed, Abrams and Lloyd showed that by repeatedly applying a particular kind of nonlinear gate, which arises in a model of Weinberg [@weinberg], one could increase the angle between two quantum states *exponentially*, and thereby distinguish the $s=0$ and $s=1$ cases with constant bias.  It seems likely that almost any nonlinear gate would confer the same ability, though it is unclear how to formalize this statement.

To solve $\mathsf{\#P}$-complete problems, we use the same basic algorithm, but apply it repeatedly to zoom in on the value of $s$ using binary search.  Given any range $\left[  a,b\right]  $ that we believe contains $s$, by applying the nonlinear gate a suitable number of times we can make the case $s=a$ correspond roughly to $\left\vert
0\right\rangle $, and the case $s=b$ correspond roughly to $\left\vert
1\right\rangle $.  Then measuring the state will provide information about whether $s$ is closer to $a$ or $b$.  This is true even if $\left(
b-a\right)  /2^{n}$ is exponentially small.

Indeed, if arbitrary $1$-qubit 