Slashdot Mirror
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. "
[...] 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, 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.
ANY "Quantum Algorithm" that exists that is NOT translatable to one computable on a TM is NOT merely parallel, but exists in a class of it's own.
The question is, does this apply to this search algorith?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
Which is why I think that those ads for QUANTUM airlines (you know, the ones with the little koala bear?) are so cool. Talk about understated, they don't even mention that their planes are so much faster than the other airlines and that they can fly in all different directions at the same time! Hah! Not like those binary planes that can only fly from point 0 to point 1.....
carlos
--
As a matter of fact, I am a lawyer. But I play an actor on TV.
I like the general principle of quantum searching, and think that it may have glossed over the single most important issue in actual practice:
... there is a high probability you will get the right result."
"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
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!
_____________
If you can go to bed, knowing you did a valuable thing today, you're very lucky. If you can't... it's not bedtime
I raised my hand and asked if I could get my hands on the algorithm so I could take it to Vegas.
We had a different instructor after lunch.
carlos
--
As a matter of fact, I am a lawyer. But I play an actor on TV.
Similar claims used to be made for holographic storage.
If this stuff ever goes anywhere, it's probably going to be for non-textual data, like images. The speed problem on textual material has been solved.
On the other hand, if you can't assign meaningful probabilties to "how sure" you are about these guesses, or if your subjective probability estimates don't match up to anything in the real world, you're kind of fucked.
Is it just me, or is this a prime example of the kind of shit people will swallow if the word "quantum" is prefixed to it? It's quite obvious that this search algorithm depends on someone being able to attach probabilities of correctness to their own statements, a proposition which looks to be in very dodgy epistemic standing. If you're reduced to guessing, how are you going to be able to guess (accurately, perforce -- GIGO hasn't been repealed here) how accurate your own wild-assed guess is?
28 posts so far, and nobody except me has read enough of the article to realise it's full of crap. And I'm a fucking lawyer, for God's sake. I sincerely hope that the fucking world of the future will be designed by the posters at advogato.net rather than the Slashbots.
--montoya
-- the most controversial site on the Web
Beg to differ on this, QC allows something called superimposition, that has no parallel in ordinary computation. This allows for bits (actually called qubits in QC) to hold more than one state/value at any time. Through interference, and the like, we get a result (or in the case of this new algorithm, we get a sampling). This is by no means the only difference.
Articles on quantum searching are always confusing. For example, they say that "a conventional database (with 1,000,000 items) would have to search 500,000 items to find the one desired". Well, that's only true if the conventional database has no index whatsoever! Adding a few simple indexes makes searches much, much faster.
Besides, surely the time to search 1,000,000 records is bounded by the time needed to load them all into the QC? Or, if they're already loaded into some kind of quantum soup, isn't this just some weird new kind of index?
Furthermore, I totally fail to see how this could improve Web searches. All it seems to do is allow you to add probabilistic search terms -- and existing search engines could handle those now if they wanted to, but they don't because no user would ever use it. Most of their scenarios require access to structured data (such as a phone book), but Web searches aren't structured.
Does anyone really know what's going on? Can they explain the technology in hype- (and condescension-) free terms?
Where can I find stock quotes for quantum corp?
Where can I find a search engine specializing in academia?
How do I search a PDF (Acrobat) document?
Could you please direct me to the internet search engine 37.com?
A firewall can not protect you from yourself. Turn off what you do not need. Do not use the firewall to do your work.
I am an InfoSec professional in real life, but I am not speaking in my professional capacity here.
.5--that is to say, a keyspace of 1,000,000 elements gets pulled down to 1,000 elements. This sounds like a lot, and it is; being able to take the root of the keyspace is a big achievement for some sorts of computation.
If quantum computers ever come to the forfront, security as we know it today will be a thing of the past..
Poppycock. The theoretical ramifications of quantum computers have been well-known for many years now, and there's been a lot of good academic research on exactly what quantum computers are capable of. They will be neat toys when they arrive, but they will not mean the end of security as we know it.
Put bluntly, using quantum computers you can manage to cut the keyspace by an exponential factor of
Crypto is not necessarily one of them. One of my current clients is concerned about quantum computers being invented and fielded in the next twenty years. So what we're doing is figuring out what sort of keyspace could be reasonably searched in 20 years (assuming a steady progression of Moore's Law), then moving one step past that... and then squaring it.
To give you an idea, 256-bit ciphers will be immune to brute force attack for as long as we're living in the Solar System. Do the power analysis on it; to break a 256-bit cipher by brute force using quantum computers requires an amount of power which borders on the absurd.
Now, that being said, any kind of serious projection about "how much key is enough" is preposterous, especially once you get past five years in the future. That only underscores the ludicrousness of your "security as we know it will be a thing of the past" statement. Security professionals already assume that the opposition has access to ten billion quantum Turing machines. We're paranoid. We're professional paranoids.
Am I concerned for what quantum tech will do to crypto? Yes. Am I shaking in my boots over it? Not hardly.
Since the topic seems to have presented itself, what do people think about quantum computing? Does everybody think that it will be the end-all-be-all of computing? Do you think it will allow for more advanced searching/forcasting/etc/etc? Is there some fields that have yet been untouched because it would require to much computing power? Do you think quantum computing will solve these problems? Any way, I just wanted to know what people thought about quantum computing and where it will take not only us geeks, but society in general.
Is there a module at CPAN yet? :)
Iron_Slinger
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
Reality does not happen until you analyze the dots. -Don DeLillo (Underworld)
You can hook icons into a script or use a vague query and have the parser build long scripts for you.
The point of the article is not that vague searches can be performed - it is that an efficient algorithm for performing searches, vague and non-vague, has been found for quantum computers.
Quantum computers and quantum computing algorithms allow you to solve many problems of exponential difficulty in polynomial time. These problems would be intractible on conventional computers, no matter how fast.
Searching large databases can be very, very time consuming. With this algorithm on quantum hardware, it is far, far less so.
Vague query matching is just something that shows up as an added bonus.
ChAoS
WARNING: May contain traces of nut
I just don't get it.
How can it be that a search engine with a huge database can return really precise results from a vague query?
If I construct a query poorly, how will it know what I'm looking for? If I type in "geek festival", how would it know that I'm looking for the GeekPride Festival homepage, and not the guy who swallows mice at the circus?
Doesn't it really come down to asking the right questions?
The wired article is very vague on the claims of increased precision in the search, so I wouldn't make any judgement about that as the /. headline implies.
Quantum computing does not change any of the basic tenents of computability, as far as I know. SO, if Grover's new algorithm does lead to more precise searches, it should lead to more precise searches in traditonal algorithms and computers.
Here's an article in the New Scientist on various kinds of encryption methods for use with quantum computers. Here's an excerpt:
Does anyone know what's the "embargo" the IBM researcher is mentioning in the wired article???
On a whim I plugged my name into various search engines and saw how amazingly easy it was to track me down and get reams of information about me. It didn't bother me too much - I could have done it with a phone book and a decent library. It did reduce the time, though. This would reduce it even further, and probably be a bit more accurate.
How odd, I did that a couple of days ago and well, according to the internet I don't exist. At all. Anywhere. I found 3 other people who have my same first and last name, and a lot of peopel with my last name, but none that are me....
Kintanon
Check out JoshJitsu.info for Brazilian Ji
I was under the impression that the one downside of quantum entanglement was that it turned out to be useless for communication.
I thought that you can find out the value of one, then you know the value of the other. You can't set one, thus setting the other.
Am I right?
thenerd
The camels are coming. I'm in love.
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. Anyway, even setting aside that a video stream is not necessarily totally random, if pre-agreeing on a giant key to draw from for small messages were a practical scheme, folks would use it now.
-------
"Whatever happened to fair use?"
-- Duff-Man
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.
A really quick google search yielded:
http://home.plutonium.net/~dagreve/qdd. html
It's GPL so now the question is, are there any public domain QC emulators.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
The speed at which quantum computers could break current key based technology is phenomenal. Entirely new encryption methods based on new (quantum?) Algorithms would have to be invented 'cos if a quantum computer got in the hands of a criminal they could breeze through most anything.
One-time pads would still work. As long as you're just trying to send text instead of video clips, you should be able to give your prospective message recipient a few gigabytes of dedicated pad _once_, and be able to communicate securely for many years after.
That having been said, quantum encryption methods have indeed been postulated. The main problem with the ones that I know of is that they have engineering difficulties (sending a single photon to your recipient half a continent away is difficult, for instance).
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...
if a quantum computer got in the hands of a criminal they could breeze through most anything
What really worries me is the day John Carmack gets his hands on the first prototype of 3DFX's Quantum-processing video card..
.sig: Now legally binding!
The question is what to search for: what constitutes meaningful answers to a query. Once we figure that out, then we can worry about speed.
I heard about Grover's algorithm two years ago, and there have been papers about it on the LANL archive from as far back 1996! It apparently allows unordered searches in a list of N elements in O(sqrt(N)) time, whereas the best a classical machine can do is O(N). See quant-ph/9605043: "A fast quantum mechanical algorithm for database search", by Lov K. Grover (Bell Labs, Murray Hill NJ). Where has everyone been? This is old, old news. Now all that we need is someone to implement a quantum computer...
Qu'on me donne six lignes écrites de la main du plus honnête homme, j'y trouverai de quoi le faire pendre.
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.
-- Still waiting for the Nike endorsement
At the moment you submit your query, the universe splits into multiple different tracks. In each track the engine chooses a random URL to return to you. At lest one version of you in one universe will get exactly the URL you want. You indicate this to the web search engine ("Was this item helpful to you?"). Then the engine collapses wavefunction so that you and your universe are once again the only ones.
Which brings up the real reason they aren't using this in public: People doing web-queries might experience disturbing side-effects like spontaneously self-unshuffling cards and having their dogs turn into talking penguins.
--
Have Exchange users? Want to run Linux? Can't afford OpenMail?
Linux MAPI Server!
http://www.openone.com/software/MailOne/
(Exchange Migration HOWTO coming soon)