Shor doesn't solve an NP hard problem. It's even possible that factoring and discrete log are in P, while P != NP. The paper builds on the results of "Nonline

Shor doesn't solve an NP hard problem. It's even possible that factoring and discrete log are in P, while P != NP. The paper builds on the results of "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems" by Abrams and Loyd [1], from which I quote: > The last qubit now contains all the information that we need; however, for small s, a measurement of the last qubit will almost always return |0>, yielding no information. > We wish to distinguish between the cases s=0 and s>0. > Step 4. Repeatedly apply the nonlinear operation to drive the states representing these two cases apart at an exponential rate: eventually, at a time determined by a polynomial function of the number of qubits n, the number of solutions s, and the rate of spreading (Lyapunov exponent) λ, the two cases will become macroscopically distinguishable. [1] https://arxiv.org/abs/quant-ph/9801041 https://arxiv.org/abs/quant-ph/9801041