As far as we know, Quantum Computers can not solve arbitrary NP problems in polynomial time. I have what appears to be a solution, but it is obviously to simple to be correct, since otherwise the problem would have been solved almost instantly. However, I do not know enough QM to find the error.
The idea is that you prepare a qubit $x$ in the state $\frac{1}{\sqrt 2}\left|0\right> + \frac{1}{\sqrt 2}\left|1\right>$, and some other qubits $y_i$, each in an independent state equal to $\frac{1}{\sqrt 2}\left|0\right> + \frac{1}{\sqrt 2}\left|1\right>$. Now, solve the NP problem using a non-deterministic turing machine, using the $y_i$ to make the nondeterminstic decisions. If it accepts, apply an operation of $x$ that maps $\left|1\right>$ to $\left|0\right>$ and leaves $\left|0\right>$ unchanged. If it rejects, apply an operation to $x$ that maps $\left|1\right>$ to ${-\left|0\right>}$ and leaves $\left|0\right>$ unchanged. Then all the qubits are observed, and a solution can be extracted from the $y_i$.
It appears that all the rejection paths should cancel out in this scenario. I think the flaw is that the operation applied to $x$ is not physically possible, but I'm not sure why.
