[cryptography] Grover's Algo Beaten?

Noon Silk noonslists at gmail.com
Sun Jul 28 01:13:10 EDT 2013

On Sun, Jul 28, 2013 at 1:29 PM, Russell Leidich <pkejjy at gmail.com> wrote:

> 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.)

No, he doesn't make any such claim (even if your claim was well-formed...)

The papers on machine learning can be found here:
  - http://arxiv.org/abs/1307.0411
  - http://arxiv.org/abs/1307.0471

Grover's algorithm is known to be optimal:
  - http://arxiv.org/abs/quant-ph/9711070
  - http://arxiv.org/abs/quant-ph/9605034


> 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.
> _______________________________________________
> cryptography mailing list
> cryptography at randombit.net
> http://lists.randombit.net/mailman/listinfo/cryptography
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130728/2f1bf629/attachment-0001.html>

More information about the cryptography mailing list