[FOM] grovers QM database lookup algorithm, QM's P=?NP

[vznuri@earthlink.net]

hi all. charles silver asked me via email about the result about
database searches in QM in O(sqrt(n)) time, where my soundbite
was just a little too brief. as he pointed
out, the result does not make sense for a linearly sorted
database. (where the standard interval-halving algorithm
gives O(log(n)) time.)

the QM result is for a randomly ordered
database, where a normal lookup takes n/2 time to find
an entry on average, the result is that a QM algorithm
can find the entry in O(sqrt(n)) time. its called Grovers
Algorithm. refs on the web or the papers I cited.
the database must be presented in "quantum form" to the
algorithm.

I found some info on grovers algorithm
in "quest for the quantum computer"
by julian brown, p292. also another excellent book on the
bookstore shelves I recommend, "the feynman processor"
by milburn.

I notice brown dedicates many pages to the "quantum fourier transform" 
(QFT?), which also apparently can be done "faster"
(I dont know the details). in fact the shor algorithm is
closely related to computing a quantum fourier transform.

so as for QM giving seemingly "magical" results at least
with respect to complexity, 
the shor QM-P-time factoring algorithm & the grover database
lookup algorithm are the two key breakthrough theoretical results 
so far, but a general theory remains to be worked out. in particular, 
afaik, the following is a gapingly-achingly open question:

Q. given an arbitrary algorithm, what is the optimal speedup
that can be obtained from a quantum algorithm??

(this is just the theoretical question. a close relative question
is, how close can physical embodiments of QM computers come to their
theoretical optimums? this is where extensive applied noise, error
correction, & decoherence insulation issues arise.)

so far, the astonishing possibility that a QM computer could
solve NP algorithms in P time has **not** been ruled out.
(that sounds remarkable, but remember P!=NP has not been proven
either!!) but even the stronger conjecture, "given that P!=NP, 
could a QM computer could solve an exponential time algorithm in P time"
is not ruled out.

note that a result that maybe the optimal speedup can vary significantly
depending on the algorithm is not ruled out either. e.g. maybe some classical
algorithms that take exponential time can be turned into QM polynomial
time whereas others cannot. (note that it has not been proven that
factoring must take exponential time & many CS scientists currently
conjecture that it does not.)

so.. a vast terra incognita.


I wrote

>its a very active area of research whether QM computers can
>compute faster than "classic" architectures. it is known that
>QM computers can factor large numbers in polynomial time via
>the famous result of shor. there is also a result that they
>can search a database in O(sqrt(n)) time.