[cryptography] Grover's Algo Beaten?

Noon Silk noonslists at gmail.com
Sun Jul 28 02:20:21 EDT 2013

On Sun, Jul 28, 2013 at 3:49 PM, Russell Leidich <pkejjy at 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].


[1] http://arxiv.org/abs/1307.0411
[2] http://en.wikipedia.org/wiki/BPP_%28complexity%29
[3] http://en.wikipedia.org/wiki/BQP
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20130728/d8a02651/attachment.html>

More information about the cryptography mailing list