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
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
