Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28
Lewis McCarthy (lmccarth@cs.umass.edu)
Fri, 19 Feb 1999 04:51:57 -0500
Mike Stay writes:
> If the proofs of the optimality Grover's algorithm are correct, one
> cannot distinguish between a test function with no solutions and one
> with one solution in less than O(2^(k/2)) steps, where k is the number
> of input bits. Since a quantum computer can trivially simulate a
> classical computer, doesn't that proof mean that P != NP?
My short answer is that I doubt it because no-one has been whooping and
jumping about here. :-) But I'll try to offer a little technical
justification for this belief.
As far as I can tell the "unstructured" DB search problem addressed by
Grover's algorithm is not (known to be) NP-complete. By exploiting the
structure of a search problem it is possible to do better than the
lower bound obtained for the unstructured case.
Here's an excerpt from a June `98 paper by Cerf, Grover, and Williams
that seems relevant. (Any typoes are due to me; I'm typing this in from
the PostScript available at <http://xxx.lanl.gov/abs/quant-ph/9806078>.)
Cerf et al.:
"While there is now good evidence that for unstructured
problems, the quantum search algorithm is optimal [9-11],
these results have raised the question of whether faster
quantum search algorithms might be found for problems that
possess <i>structure</i> [6, 12-14]. It so happens that NP-
complete problems have such structure in the sense that one
can often build up complete solutions (i.e. value assignments
for all the variables) by extending <i>partial</i> solutions
(i.e., value assignments for a subset of the variables)."
-Lewis http://www.cs.umass.edu/~lmccarth
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:18:28