[cryptography] Grover's Algo Beaten?

Russell Leidich pkejjy at gmail.com
Sat Jul 27 23:29:40 EDT 2013


Is this to be taken seriously...

Massachusetts Institute of Technology professor Seth Lloyd claims to have
developed a quantum search algo which can search 2^N (presumably unsorted)
records in O(N) time. (This is the subtext of this mundane article about VC
funding for search engines.)

http://www.eetimes.com/document.asp?doc_id=1319059
http://www.amazon.com/books/dp/1400033861

Reading between the lines, it sounds like the input is a binary pattern,
and the output is a record number where said pattern is found, assuming
that it exists in the database. (If it exists in multiple records, then
each of those matches will be returned with essentially equal probability.)

To the quantum computing notice, this invention is unsurprising. After all,
N qubits in superposition assume 2^N states across multiverses, which
obviously means that shortly after the computer starts up, it will already
have found the desired record if it exists.

But methinks this is all wrong. Grover's algo can only search 2^N unsorted
records in O(2^(0.5N)) time. If I'm not mistaken, this derives from the
difficulty of amplifying the correct result, in the presence of large
numbers of "near" matches. For its part, DWave's operating manual goes into
detail about this issue, involving Maxwell-Boltzmann energy distributions,
providing practical evidence of this severe acceleration impediment.

So it sounds like Lloyd is claiming that he's found a way to amplify the
correct record with 100% probability -- in other words, to exploit quantum
mechanics on a quantum system to mimic classical behavior.

If he's right, then that would appear to be evidence that quantum computers
can provide exponential, as opposed to merely square, acceleration of at
least this one algo, if not others.

I wish I could procure a copy of his book, but I'm geographically
challenged. So nevermind his apparent egomaniacism. Is he right? Is EE
Times just confused about his supposed invention?

Aside: There's another subtle implication here, which is that multiverse
density is for all practical purposes, infinite. In other words, you can in
fact superimpose 2^N multiverse "bubbles" into the physical space occupied
by N qubits, even if N is big enough to subsume all Landauer limit bit
flips that could ever have occurred with all the energy in the universe
(very roughly, N=400). This is a cornerstone of quantum theory which
appears very difficult to test, absent a classically verifiable result like
a Shor's factorization. There's something unsettling about the assumption
that information density can be infinite despite finite systemic energy,
when even inside black holes, that's not allowed (says Mr. Hawking). Maybe
the maximum spatial density of multiverses is just "really big", so that
experiments to date would have not have run up against the limit.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130728/6616d442/attachment.html>


More information about the cryptography mailing list