# What's wrong with this method of solving NP problems using a quantum computer?

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.

• If you don't make this more precise you can claim virtually anything this way. – Norbert Schuch Mar 11 '19 at 10:22
• @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. – PyRulez Mar 11 '19 at 13:45
• 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$. – user4552 Mar 11 '19 at 18:20
• @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. – PyRulez Mar 11 '19 at 18:36

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