Big Step in Quantum Searching

Penguin_99 writes "Wired.com has an article about a Lucent Technologies' Bell Labs researcher (Lov Grover) who came up with a quantum algorithm that is able to instantly search a massive database (of websites or whatever you might have) and return amazingly precise results even if the input is vague or incomplete. This particular algorithm can be used for other things besides searching for instance solving equations. Apperently this algorithm is only one of a handful of quantum algorithms in existance. The down side is that it requires a quantum computer so you are not likely to see Yahoo! using it anytime soon. Imagine a day when you do not have to wade through pages of usless websites after performing a search. "

Not as fast as you might wish

Just like Grover's original search algorithm, this new extention to more flexible search terms still requires O(srqt(N)) quantum operations. From the abstract: [lanl.gov]

[...] This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps.[...]

So while providing a significant speedup over the classic O(N/2) steps, this search algorithms does not overcome the barrier from exponential to polynomial search times (like e.g. Shor's quantum algorithm for prime factorisation); i.e. you would still require O(2^(k/2)) steps to find some k-bit string.

If you are interested in quantum computation, check out QCL [tuwien.ac.at], my quantum computation language and QC simulator (for Linux, you guessed it ;-)). An implementation of Grover's original search algorithm is included in the tarball.

Re:Precision is cool...

I like the general principle of quantum searching, and think that it may have glossed over the single most important issue in actual practice:

"It would be most useful where you have partial information and probabilities," Grover explained. "(If) you are 90 percent sure it is John and 10 percent it's James and 50 percent it's on Broadway ... there is a high probability you will get the right result."

Unfortunately, this never happens, and for good reason: I'm never 90% sure (or 10% or 50%) of anything. I may use those terms in speech, but they are mathematically meaningless (undefined) -- no matter what my lifeline says on "Who Wants to be a Millionaire?"

If it turns out I'm *really* looking for Jahn on Boardwalk, the quantum search engine can tell me I must've had my probablilities wrong. But there is no way that I can ascertain this in advance. Though I can construct test data to represent defined amounts of uncertainty, here is no tool for measuring "How sure I am" (40%? 50%? 60%?)

In short: {i}The trick to quantum searching is formulating the right query -- and that may be impractical or impossible[/i] [b] I hereby dub this the 'Jeopardy' Problem[/b] -- how do I phrase it in the form of a question? (short of "What is the phone number of John Smith of 4225 Broadway Apt 3c?")

Will the search engine give me the same answer if I say I'm 40% sure it's John as it would if I'm 60% sure its John? Should it? On one hand, the two situations may be very different, on the other, they may be essentially identical.

There are many other very down-to-earth and practical problems that we'd see instantly, if it weren't for that magic word "quantum" -- do you have *any* idea how many people named John or Jim live on Broadway? Hundreds. And how many live "off Broadway"? Possibly thousands depending on how far "off" you're willing to accept.

A boolean search can find that list for you. Tell me how a "quantum search" can derive additional information from the query -- when you are looking for John Smith, and I am looking for John Doe. Quantum ain't magic. It can't read minds. Not with current technology!
_____________

Precision is cool...

Precision is searching is good. Cutting time and getting exactly what you are looking for is good to. But how many times have you searched for foo, and come up with a great many inks for bar and really learned alot about bar? In a way, the imprecision of web searches makes the web really fun. I can not remember where it was posted (here?) but there was a little program that pointed you to totally random pages, and "played" them in your browser. Kind of like making random visual web music! Tom

Ahhhh....

But if it gives out quantum results, will it mean we can know the title of a site or the URL of a site but never both at once... ;)

ChAoS

Quantum Encryption

.... if folks have a link to confirm or deny this, that'd be keen.

Here's an article [newscientist.co.uk] in the New Scientist on various kinds of encryption methods for use with quantum computers. Here's an excerpt:

• The one-time pad cipher is so called because each key used to be written on a separate sheet of a pad of paper. After being used once, the sheet was torn off and destroyed, leaving the new key on the next sheet ready to encrypt the next message. Despite being theoretically perfect, the one-time pad cipher suffers from several practical flaws, which have prevented its widespread use. Making random keys is a difficult task, and making a new one for each message is time-consuming. The real killer, though, is distributing the keys. After Alice has manufactured a random key, encrypted her message, and sent the encrypted text, she somehow has to get the key to Bob so that he can decrypt the message. She cannot send the key unencrypted because Eve will steal it, and she cannot encrypt it because she then has to tell Bob the key she used to encrypt the key that she used to encrypt the message.

• The key-distribution problem was traditionally solved by employing trusted couriers to deliver the keys by hand, but this solution doesn't have much appeal in the age of satellite communications and e-mail. It is here that quantum physics comes to the rescue. In the early 1980s, Charles Bennett, an IBM researcher, and Gilles Brassard, a computer scientist at the University of Montreal, proposed that Alice and Bob should use individual photons to exchange their key. By operating at the quantum level, they argued, Alice and Bob could exploit the laws of quantum physics to protect the key.

• Bennett and Brassard proposed using photons polarised in different directions to represent 1 or 0. If Eve tried to intercept the key, she would have to measure the photons, which would effectively mean absorbing them. To avoid being spotted, Eve would have to retransmit the photon to Bob. However, because of the strange way that quantum particles work, Eve does not always measure the same polarisation that Alice sent. That in turn means that she cannot be sure that she is retransmitting the correct orientation. Thus Eve's interception will inevitably affect the transmission of the key, and Alice and Bob should be able to spot this, discard the key, and try again with a new one.

Indeed Poppycock

I am an InfoSec professional in real life, but I am not speaking in my professional capacity here.

That is probably the wisest thing you said in your entire post. As it happens, I too am a security professional, posting anonymously (while at work and wishing not to be identified on the job).

"If quantum computers ever come to the forfront, security as we know it today will be a thing of the past.. "

Poppycock.

Indeed, your comments are mostly Poppycock.

It would appear your paranoia is aimed far too specifically: paranoia at our profession being shaken up, perhaps fundamentally.

Theoretically, quantum algorithms can test all of the potential factorizations for a key of arbitrary length at once. The fact that this one, practical algorithm, doesn't posses that characteristic doesn't mean no other algorithm does. Indeed, other algorithms that do have this characteristic have been demonstrated on a very small scale (two and four qubits, if I recall correctly).

Only once a "quantum" algorithm (I've never liked that terminology, as it misuses the term quantum, as in quanta) has completed are the results actually observed, thus collapsing the eigenstates to the one which provides the desired result.

If and when this happens, security as we know it, at least with respect to public key/private key encryption, will most certainly be a thing of the past. All of our algorithms which rely on the difficulty of factoring arbitary prime numbers will suddenly be completley useless and obsolete. Moors law plays absolutely no role in this, as this is a fundamental shift in paradigms, not a function of mere computing power. Your feeling of security at having anticipated any reasonable increase in computational ability is thus completely misplaced and inappropriate.

Of course, quantum coupling provides a possible solution in the form of an unbreakable one-time pad, but how this can be applied to problem sets which public key/private key encryption addresses remains to be seen.

If and when quantum computing does become feasable, security as we know it will be turned on its head, and keylengths of whatever length will be compromized, regardless of your level of paranoia. The entire paradigm will be obsolete, and the entire security infrastructure will have to be rethought from the ground up.

In other words, security as we know it will be history.

Current Limits

First we need to make the distinction between _quantum_ and parallel. Certain phenomenon in nature exist on in discrete packets or _quanta_. Things on a subatomic level demonstrate these properties and are studied as quantum mechanics. An alogrithm cannot be quantum. An algorithm cna be massively parallel. As it turns out, massively parallel algorithm can be executed _very_ rapidly using the quantum mechanical properties seen in nature. Thus the big push in quantum computing. There are two main approches currently being pursued, each has their limits. The first in on the atomic level. The first using atomic magnetic propoerties in a magnetic field to make measurements (this is traditional "coffee cup" model). The current limitation is that the quantum mechanical properties begin to break break down at qubit sizes larger than around 15. This is a physical limitation and there is no current solution. The second approach is molecule clusters in some superconducting materials have been shown to demonstrate quantum properties. The limitations here are that we don't understand these systems very well yet. If research ever breaks through in quantum computing (it may, it may not), it will have a tremendous impact on everything from the military to e-commerce. This is because on the parallel algorithms that can be used in prime factorization (one of the key steps in breaking encryption.) If quantum computers ever come to the forfront, security as we know it today will be a thing of the past...

Re:OTPs

Remember, one time pads are only genuinely secure if the pad is at least as long as the message, the pad is genuinely random, and the pad is never reused. If any of these is not true, the encryption is breakable.

All of this is true. However, these conditions are easy to meet:

1) Your pad is several gigabytes, or more. How much space will your text messages take up?

2) Diode noise and other schemes can easily produce truly randum pads. Hardware exists for this in many places already; there just isn't much demand right now.

3) You are unlikely to send more than several gigabytes of text in communications in your lifetime. You never need to reuse the pad.

I don't see a problem.

Anyway, even setting aside that a video stream is not necessarily totally random

Perhaps I was not clear enough in my original post - you aren't using a video stream as a key. I was giving "video clips" as an example of _message_data_ that would quickly overflow your pad. The same applies if you want to email your pr0n collection to a friend. OTPs are only really, _really_ practical for text messages.

if pre-agreeing on a giant key to draw from for small messages were a practical scheme, folks would use it now.

Not true. It's practical, and it works - it's just more conventient to use a public key scheme. People will usually go with the most convenient option unless there is a reason not to (for instance, quantum computing breaking public-key systems).

Analysis of the algorithm's uses

From the Paper's Abstract:

This paper extends the quantum search class of algorithms to the multiple solution case. It is shown that, like the basic search algorithm, these too can be represented as a rotation in an appropriately defined two dimensional vector space. This yields new applications - an algorithm is presented that can create an arbitrarily specified quantum superposition on a space of size N in O(sqrt(N)) steps. By making a measurement on this superposition, it is possible to obtain a sample according to an arbitrarily specified classical probability distribution in O(sqrt(N)) steps. A classical algorithm would need O(N) steps.

This is not the instant set-em-up-and-let-em-fall answer of quantum computing mythology. The algorithm is substantially faster than a linear algorithm - it would really show this in a case with a database of such size as to be unsearchable with a classic algorithm, say a very partial retinal scan against a database including every retinal print in the world - but what isn't clear is the cost in setup. I scanned the paper, but couldn't figure out how many qbits this would require. If the number grows with the database size, which is possible, this search might not be doable on a real scale. I'm sure when quantum coprocessors are commonplace, the algorithm will be widely used... I just wonder what it would take to create a situation where the quantum solution to the vague search is faster than a smarter solution on a classical computer... one that restricts enough to dump most of the searchable steps before it starts, then broadens criteria as required.