Re: [cryptography] Grover's Algo Beaten?
On Sun, Jul 28, 2013 at 3:49 PM, Russell Leidich pke...@gmail.com wrote: 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. I don't know exactly what they mean by this. I guess he's just saying something like suppose I know that the number of bits of information the universe is less than some number K, then I only need log2(K) qubits to represent that many bits of information in a quantum computer. I'm not sure it's particularly interesting. ...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. In the recent machine learning paper[1], they describe an algorithm that does supervised machine learning (i.e. deciding whether a thing is either truck-like or car-like, two choices for simplicity) in O(log (N M)) on a quantum computer, instead of O(poly (N M)) on a classical computer, where M is the number of samples from each of the clusters you're trying to assign to (say M truck-like things, and M car-like things), and N is the dimension of vector you're trying to assign (i.e. a thing that is either truck-like or car-like). 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. It's a cool result, no doubt. But you'll note that the classical algorithm is already in P. The trouble is to find a quantum algorithm that solves a problem that is hard classically, but easy quantumly. More technically, it would be really astounding if we could separate BPP[2] and BQP[3]. -- Noon [1] http://arxiv.org/abs/1307.0411 [2] http://en.wikipedia.org/wiki/BPP_%28complexity%29 [3] http://en.wikipedia.org/wiki/BQP ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
On Jul 27, 2013, at 9: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. Grover’s original paper included a proof that his result was near a lower bound. I don’t understand QM well enough (my linear algebra sucks) to have understood the proof sufficiently to see clearly what assumptions it relies on. Cheers, -j ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
Is it better than a radix sort? ___ cryptography mailing list cryptography@randombit.net http://lists.randombit.net/mailman/listinfo/cryptography
Re: [cryptography] Grover's Algo Beaten?
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
Re: [cryptography] Grover's Algo Beaten?
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
Re: [cryptography] Grover's Algo Beaten?
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 noonsli...@gmail.com wrote: 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
