[cryptography] Grover's Algo Beaten?

Russell Leidich pkejjy at gmail.com
Sun Jul 28 01:49:22 EDT 2013


Thanks, Noon. It's good to know that some searches are still "hard" in the
sense of square root as opposed to log of classical.

So based on his actual claims in the papers you cited, when the EE Times
article says:

"And he claims the process worked so well that even the largest data set of
all -- every bit in the universe, which he describes in his book *Programming
the Universe* <http://www.amazon.com/books/dp/1400033861>, would only
require a quantum computer with 300 q-bits to query in real-time."

...they don't mean "query" in the literal sense of a text search for an
exact match of "Joe Smith". What they really mean is more like: given a
database of billions of car photos (support vectors), then look at my new
car photo, and tell me what brand it is. In short, a vector classifier.

Nevertheless, his putative exponential speedup over classical methods would
be astounding, if it could be implemented, even if it really doesn't relate
to Grover.



On Sun, Jul 28, 2013 at 5:13 AM, Noon Silk <noonslists at gmail.com> wrote:

>
> 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
>
> --
> Noon
>
>
>
>
>
>
>>
>> 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/7089eb5c/attachment.html>


More information about the cryptography mailing list