Implications on P = NP

A common fallacious argument made is that since any quantum algorithm takes $\Omega$($\sqrt{{N}}$) operations to identify a single marked element in a database of N elements, a quantum computer can not be used to attain exponential speed up in a search problem.

This argument is incorrect because this lower bound applies only to queries of the type used in Grover's algorithm, whose queries ask only about a single database element at a time. [Grover97]

Various novel approaches can be used to get around the $\Omega$($\sqrt{{N}}$) queries barrier which still leave hope for a finding some exponential speed up of an NP-Hard problem. These approaches generally try to capitalize on some structure of the problem at hand, which Grover's algorithm does not do at all.

Grover provides an algorithm which will locate a single marked element in a N element database in exactly 1 query. It does however require O(N logN) pre and post processing time. While much slower in overall running time for the best classical and quantum algorithms for the same task, it does demonstrate that the $\Omega$($\sqrt{{N}}$) query limit is not necessarily rule out exponential speed up of quantum computers in a search problem. [Grover97]

It has also been shown that nonlinear quantum mechanics imply polynomial time solutions for NP-complete problems, however the same paper notes that: ``Such nonlinearity is purely hypothetical: all known experiments confirm the linearity of quantum mechanics to a high degree of accuracy'' [Abrams98]