[cryptography] Grover's Algo Beaten?

James A. Donald jamesd at echeque.com
Sun Jul 28 01:39:37 EDT 2013


On 2013-07-28 1:29 PM, Russell Leidich 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.)
>
> 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.
>

DWave uses a different algorithm.  You might say that they create a 
hamiltonian whose ground state corresponds to the solution.

Loyd proposes to create a hamiltonian that moves  to a non ground state 
that corresponds to the solution.

DWave's algorithm is based on what their hardware can actually do - 
DWave is not a general purpose quantum computer, far from it.  Loyd is 
writing programs for a hypothetical general purpose quantum computer


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130728/5521fa67/attachment.html>


More information about the cryptography mailing list