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.

  • $\begingroup$ If you don't make this more precise you can claim virtually anything this way. $\endgroup$ Commented Mar 11, 2019 at 10:22
  • $\begingroup$ @NorbertSchuch I don't understand. It's well known that quantum computers can carry out quantum algorithms, and that the medium does not affect computational complexity. $\endgroup$ Commented Mar 11, 2019 at 13:45
  • $\begingroup$ At the preparation stage, it sounds to me like the preparation of the $y_i$ might already violate no-cloning. This is assuming that "independent" means "separable," and that you care about the phase of the $y_i$. $\endgroup$
    – user4552
    Commented Mar 11, 2019 at 18:20
  • $\begingroup$ @BenCrowell I mean that they are all separate qubits that just so happen to be described by that quantum state. They have nothing to do with each other. $\endgroup$ Commented Mar 11, 2019 at 18:36

1 Answer 1


The operation applied to $x$ is not unitary, making it nonphysical.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.