On Sun, Jul 28, 2013 at 1:29 PM, Russell Leidich <pke...@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@randombit.net > http://lists.randombit.net/mailman/listinfo/cryptography > >
_______________________________________________ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
