[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.)
> 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...
More information about the cryptography