optimality of grover's algorithm as proof P != NP

staym@accessdata.com
Thu, 18 Feb 1999 15:48:37 -0700

• Next message: Jim Morris: "Hi, Hello not an importend mail."
• Previous message: Julian Assange: "Re: Announcing New Dual Mount Copy Holder by Rubbermaid"

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?

-- 
Mike Stay
Cryptographer / Programmer
AccessData Corp.
mailto:staym@accessdata.com

• Next message: Jim Morris: "Hi, Hello not an importend mail."
• Previous message: Julian Assange: "Re: Announcing New Dual Mount Copy Holder by Rubbermaid"