Big Step in Quantum Searching 106
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 (Score:3)
[...] 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.
Big Deal (Score:1)
---
Re:Analysis of the algorithm's uses (Score:1)
Re:Vague on increased precision (Score:1)
Actually, am I even able to use such words when discussing QC?
---
How long have you been listening to the world's famous?
'Bout six weeks.
Six weeks!
Re:Enabling Big Brother to do his thing (Score:1)
They did it back then too, and they could get away with it publicly then. They kept tabs on suspected Communists from about 1910 on. With all of that trouble brewing in Czarist Russia, they weren't taking any chances..
Re:Current Limits (Score:2)
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?
Quantum computers will be misused like all others (Score:1)
Re:Here's how (Score:1)
That's actually something I hadn't thought of -- the deconstructuralist turn: that information itself only exists because its binary opposition ("no-information") also exists. Without one, there is no possibility of the other. (Now the good deconstructuralist will ask which of the oppositions is "privileged" above the other -- but I digress...)
If all permutations of information exist, then it ceases to be information. So it begs the question: what makes information? Is it the thing itself? Or the thing(s) which it lacks? And if information consists primarily of the differences between itself and not-itself -- then what exactly are we referring to when we talk about information?
Kinda like the donut and donut hole, no? Without the donut, there would be no hole. But the hole itself is really the absence of the whole (pun intended) -- or is it?
Or is the hole a presence? Is what quanitifies the donut hole the donut around the hole? Or is the hole a thing in itself -- the empty space within a donut?
And what do you make of actual donut holes -- the clumps of dough served up as "donut holes." Are these the actual holes? Or are these donuts without holes? (And if they're donut without holes, why are they called donut holes?)
Not to mention the fact that if the hole is an absence -- how can it be named? Can we name something that doesn't exist? Doesn't naming require acknowledgement of existence? And if we don't name it, then does it not exist -- or does it exist because it does not exist?
Damn.
Re:Here's how (Score:1)
Hey, if you want to read an example of this, check out Jorge Borge's story "The Library of Babel."
In the story Borges posits a library in which every possible permutation of every possible book has been written. So you find stuff like true histories of the world, true histories of the world off by only one letter, false histories of the world, true histories of the creation of the false histories, false histories of the creation of the true histories, and so on.
The trick is to locate the "true" index which points to all the "true" texts. So, of course, librarians are always looking for the true index -- but they can never be sure if they've found it.
It's an amazing story -- it blew my mind in high school, and it's one of the few stories I think about on a daily basis.
I can see the ads now (Score:1)
A complete quantum computing solution.
Featuring
Financing Available.
Re:OS/2 already has this (Score:2)
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
Re:Precision is cool... (Score:3)
"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!
_____________
Other Interesting Bell Labs Algorithms (Score:2)
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
Re:Huh? (Score:1)
Re:Precision is cool... (Score:1)
Tom
Re:OTPs (Score:1)
You call it practical, and it may be practical for spies and secret agents, but it's not for normal people. You first have to exchange the key by non-electronic means (ie fysically, by giving them a disk, CD or listing...). Can you imagine everyone exchanging CDRs with all the people they want to talk with?
The great thing about public key encryption is that your communication can be completely public from beginning to end. If quantum computers enable us to break that encryption before it gives us a way to replace it, we will be facing some interesting problems (security by obscurity?)
From what I've read i got the impression that quantum encryption might be the first to become practical. Anyone with more knowledge on the subject who could enlighten us?
Overhyped (Score:2)
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.
Re:Here's how (Score:1)
Fastest Q search in SciAm (Score:1)
Unfortunately I have neither the magazine nor yet able to read the above article. Apparently the inventor had proven that his own algorithm was the fastest possible one, though the definition of searching may have been stretched to fit the probabilistic algorithm now in the news.
I do not remember if the basic idea was to assign one qubit to each letter of a name, or just one qubit to each item in a database, but it seemed quite powerful even with a small number of qubits.
A more interesting question in the short term might be whether a <=15 qubit computer can make serious inroads on big factoring problems.
Re:Quantum Encryption (Score:1)
From a communications security standpoint this is an intersting theory, but I see a hole (if I understand the concept correctly). Although Eve can never read Alice's message to Bob, she can apparently prevent its reception (just capture every photon Alice sends). Am I missing something or is this a serious problem... In many instances a message prevented can be just as dangerous as a message intercepted.
Re:Security (Score:1)
Read the article, all will be revealed (Score:2)
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 [olsentwins.com] rather than the Slashbots.
--montoya
Re:Vague on increased precision (Score:1)
I think we may be able to use this now... (Score:1)
The massively parallel part could come through efforts such as seti and distributed.net type efforts. Hopefully that would be enough.
I think this might be perfect for
1. Geneology (searching ancestors)
2. DNA decoding
both of these have good questions that will only have one answer, and both are popular enough that folks would donate screensaver time.
Both are also fields where partial data is thrown in, with good estimates of accuracy on the partial data.
hanzie
They don't actually have a working quantum machine (Score:1)
Re:Vague on increased precision (Score:2)
Re:OS/2 already has this (Score:1)
How does this compare to conventional indexing? (Score:2)
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?
PAH! Jeeves is enough for me! (Score:2)
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?
Poppycock (Score:2)
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.
I already get good search results! (Score:1)
That day is today - I use Google [google.com].
(I can't believe somebody hasn't said this already...)
Adam
One of the two "magic" words (Score:1)
That may change, but for now those terms send up a big ol' red flag.
Slashdot needs to hire some science consultants (Score:1)
--
Quantum Programing (Score:1)
Based on what we have seen in binary computers, I would say that to write low level assembler (or the quantum equivlant of writing in binary) stuff you would have to understand the physics (just like you do to write low level assembler and binary language stuff on binary systems, why do you think so many early programers started life as EE's). It would also probably help to understand it in OS and compiler programing, but just like many programmers don't REALLY understand how their binary systems work (Let us count the number of programming manuals that start off with a primer on how computers "think" using '0's and '1's.), I am sure many high level programmers of quantum computers won't REALLY understand the physics.
Re:Security (Score:1)
Unless you've got two quantum machines, one tapping the line, the other one generating the new (false) signals. I think this possibility has been dealt with already(ie the laws of quantum physics make it impossible),but I'm not sure.
NI3(getting drunk..)
All this makes me wonder... (Score:1)
Re:Read the article, all will be revealed (Score:2)
Hardly. Statistics deal with this all the time. If surveys show that 80% of slashdotters prefer hot grits, 10% prefer cold grits, and another 10% a naked and petrified Hemos, you have that data next time you want to search for what cowboy neal prefers. A win if that survey data wasn't indexed.
Re:Here's how (Score:1)
Re:Quantum computers will be misused like all othe (Score:1)
Actually, I disagree with nearly everything you've said.
In everything that we do there is always progress but there is always a waste here and there and usually it's abig one. Programs used to be small, fast, efficient. Now we have programs that do basically the same things but tack some hokey little graphical mess on the front and make everything seem all right while sucking the preformance down the drain.
Yes, we spend more cycles to perform the same tasks now. However, consider what we've gained; Nearly anyone can use a computer, you can do multiple things at once (I defy you to claim you'd like to go back to DOS as the prevalent operating system for personal computers, or to CP/M for minicomputers.) Heck, MP/M was wasteful compared to CP/M, but it let multiple people execute code on the same box at the same time, provided it was designed for it.
Also the mathmetical requirements to actually program a computer like that would really be quite massive. One of the major stumbling blocks short of maybe latin historically has been mathmetics.
Wait, do you mean that one of the major stumbling blocks to programming is latin? printf('Quis Custodiet Ipsos Custodes?\n');
I can't tell you how a new breed of people has seen fit to make programming an old boys club like they have with most other sciences. Forcing quantum mechanics into the picture will really set back the development time table significantly because only a small ammount of people will ever be able to grasp concepts like that.
I think you're actually facing entirely the wrong direction from the truth. Programming (And really, every branch of computing) is becoming less and less an old boy's club as more and more people get into computers. Five years ago you would have been hard pressed to name a Systems Administrator, or a well-known programmer that wasn't male; Today, anyone should be able to come up with a few. Also, mathematics isn't something that only fat white guys have aptitude for; Frequently, we see Russians and Iranians excelling past the "Americans" in this field, and frequently they're people who are extremely odd or that we consider to be not right in the head. Heck, good old Albert was one funky mofo, but that didn't stop him.
Then when people do get it they wil simply just write software that will also appear equally slow and then convince us we "need" to develop something else that really takes even more time. People are constantly changing the spec and generally that's bad for any design process.
People are also constantly fulfilling the spec, and then going on to improve upon the product in a new revision. The reason we have reusable code is that codebases weren't meant to be static.
I appreciate pessimism as much as the next guy, but let's face it, this is a scare message worthy of spin from those who have stock in companies that make their money on transistors. Don't fear progress, fear people.
Re:Here's how (Score:1)
Neither. The thing that makes information is trust. If you trust the source of data, then the data transmitted is information. If the source is untrustworthy, then the data transmitted is noise. A library filled with every possible text ever written, with no trusted source for any of them, is all noise.
Even the 'correct' texts. In fact, a library filled with every possible 'correct' text ever written, with no trusted source for any of them, is noise too. But, of course, in this case, one could test the texts against reality enough to say, "Hey, 100% of the first million books are 100% right, I think I can probably trust the author."
Tangent: there is a third possibility here, which is that if you think that the data is pleasing/interesting, then it is "artistic," regardless of the trustworthiness of the author. Art can be information, I think, but probably does not fit the definition of noise ("noise" music isn't usually pure noise).
Re:Here's how (Score:1)
I'm interested -- at least in this particular dialog -- in the notion of what constitutes information. If all information equates to no information, then you're implying that no-information somehow constitutes information (a part of the whole) or that information is derived from no-information. (Much like how, for example, Freud explains that the unconscious must exist before the conscious -- and that consciousness is only that which has been found to bubble up through the unconscious. You can't have one without the other, and both are bound to each other -- but unconsciousness is privileged over consciousness.)
Trust seems to me to be a particular 'view' brought to information. I mean, is it possible to have information apart from trust? I say, yes, that trust is simply another word for the experience of the 'reader' -- and that different readers have different experiences -- and therefore different notions of trust.
And if everyone has different notions of trust -- you trust A, but I trust B -- then you're not really talking about the information itself -- you're talking about the experience of the reader -- the 'trust' that he/she carries around as baggage interacting with this thing that is (not yet) information. So what is this thing that exists before it is trusted? Is it information? Or is it simply uninformed information?
Or, another way of looking at it, if trust determines information, then what determines trust? In order to trust one must know what to trust, and to know what to trust, one must have information. (This is possible because, as I said in the previous paragraph, different people have different notions -- different experiences -- of trust.)
So what you're really defining when you proclaim that 'trust determines information' isn't information so much as trust -- which, in this case, doesn't help much to define information.
Wouldn't it also mean .. (Score:1)
Ideas? (Score:2)
Perls of wisdom. (Score:2)
Iron_Slinger
Precision is cool... (Score:3)
Security (Score:1)
ChAoS
OS/2 already has this (Score:1)
Could it be sorta-sentient? (Score:1)
This algorithm has far better time performance. (Score:2)
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.
Just imagine the fun (Score:1)
It shouldn't bother us. Faster and more reliable searches will keep coming, and people will keep screaming about how their privacy is intruded upon. Other people will say "Forget it, I don't care if I get junk mail" and then even others will say "You don't understand! A stalker can come find and kill you now!"
I think I had a point to this at the start, but it's disgustingly early in the morning, and I still need to get my breakfast from the vending machine here at work.
Ahhhh.... (Score:5)
ChAoS
<!DOCTYPE SLASHTML "-//DTD KARMAWHORE 1.0"> (Score:1)
-----
Huh? (Score:2)
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?
Vaporware! (Score:1)
Vague on increased precision (Score:2)
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.
Don't you just know... (Score:1)
For every great speed increase, theres always a pig of an application waiting to ruin it.
Quantum Encryption (Score:3)
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:
Embargo? (Score:2)
Another question (Score:1)
Re:What is quantim computing? (Score:1)
Re:Ideas? (Score:1)
Re:Just imagine the fun (Score:2)
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
Re:Enabling Big Brother to do his thing (Score:1)
Now that you mention it, maybe we shouldn't allow powerful applications like this.
Actually, we should stop all technological advances right now to prevent Big Brother from gaining anymore control over us.
Actually, we should go back to the thirties when the government didn't have the technology to store all my personal information.
I guess we'd have to send our posts to /. via telegraph...
Re:you only need to build one (Score:2)
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
OTPs (Score:2)
-------
Indeed Poppycock (Score:3)
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.
Re:Here's how (Score:1)
The library doesn't have to be anything like as big as the one Borges described. He's talking about large, quarto volumes, perhaps with 2,000,000 characters per volume. Therefore, for all the combinations of (say) uppercase letters plus space, full stop and comma, we're thinking about 2,000,000^28 -- a huge number of volumes.
But you can build it smaller than this by halving the length of a volume. It doesn't matter that they'll only have 1,000,000 characters, because there will always be a volume somewhere else in the library that carries on and contains the "second half" of the book. 1,000,000^28 is still huge, but it's much smaller than 2000,000^28.
Carry this on even further, and we can get to the point at which a "volume" is a small slip of paper with only 100 characters on it. 100^28 is a pretty huge number, but you could probably store this many small slips of paper on microfilm if you had both World Trade Centres to spare. Now we're getting into the realms of feasibility. There's a trade-off in terms of time spent searching for the correct "continuation" of the slip you just finished, but the index was always a problem, even in the original library of Babel.
The obvious further simplification is to reduce the number of characters per volume to 1. 1^28 is still 1, so you can now carry around the entire library of Babel in your pocket. Now you'll really have trouble combining the volumes accurately, but it's still possible -- you can make every possible combination of characters, out of the characters, and that's all that the original Library contained.
Still a bit cumbersome? Thought so. Well, let's assign the numbers 0 through 27 to the characters, and represent those numbers by their binary equivalent. Now you can wear the Library of Babel as cufflinks -- just have a 1 on your left hand and a 0 on your right (or vice versa, I don't care). You'll have to look back and forth a lot, and translate on the fly, but you can still produce any volume in the original Tower of Babel.
The point is that Borges' Library contains no information at all. Exhaustive iterations of permutations don't contain any more information than the original elements. Hey ho hum.
Re:OTPs (Score:2)
-------
28 characters? What the hell? (Score:1)
Re:Precision is cool... (Score:1)
Re:All this makes me wonder... (Score:1)
--
Re:Poppycock (Score:1)
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.
True. BUT, performance predictions almost always underestimate human ingenuity. Can anyone really say they saw Moore's Law coming ... no. In truth, the amount of research performed in this area has been relatively small (compared to the research put into silicon for example). There are many parallel algorithms yet to come, and its very possible factorization problems will turn into easy problems.
Put bluntly, using quantum computers you can manage to cut the keyspace by an exponential factor of .5--that is to say, a keyspace of 1,000,000 elements gets pulled down to 1,000 elements. Put bluntly, using quantum computers you can manage to cut the keyspace by an exponential factor of .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. Crypto is not necessarily one of them.
??? There are a couple things that are not clear to me here. 1) Where are you getting these numbers!? Technically, quantum computers do NOTHING to size of the keyspace. They alter the amount you have to search, but there is no reason why that number is limited to an exponential of 1/2! Assuming your number refers to the current factorization algorithm, it is only one of more to come. Plus, changing a O(N2) algorithm to a O(N) one is a huge achievment for any computation, and since you're talking about keyspace, crypto is by definition one of them.
Am I concerned for what quantum tech will do to crypto? Yes. Am I shaking in my boots over it? Not hardly.
As a _paranoid_ security professional, you of all people should beware of overconfident statements like the above.
Re:All this makes me wonder... (Score:2)
A really quick google search yielded:
http://home.plutonium.net/~dagreve/qdd. html [plutonium.net]
It's GPL so now the question is, are there any public domain QC emulators.
Re:Here's how (Score:1)
I think what I'm REALLY saying is that "all data" equates to no information. Data that that doesn't contain valid data (or, in this context, communication) (such as a staticky television, a book of random letters, or a book of random concepts) doesn't really qualify as "information." To me, information is meaningful communication.
Trust seems to me to be a particular 'view' brought to information. I mean, is it possible to have information apart from trust?
I think no. Trust seems to me to be what makes data information. Without trust, without any way to come to a personal judgement on the value of data, it cannot inform. You might as well flip a coin.
And if everyone has different notions of trust -- you trust A, but I trust B -- then you're not really talking about the information itself -- you're talking about the experience of the reader -- the 'trust' that he/she carries around as baggage interacting with this thing that is (not yet) information.
True. Trust, communication, what constitutes information, and how the world is viewed are all subjective. The same book can be meaningful information to one person and pure mindless drivel to another. I run into this effect on
Or, another way of looking at it, if trust determines information, then what determines trust? In order to trust one must know what to trust, and to know what to trust, one must have information.
Everything begins with faith. I know that "faith" can be an ugly word in techie parts, but it's true. Somewhere, at the beginning, everyone decides who and what to trust based on, essentially, emotional bias. Things other than logical analysis of data. Many start at a young age by trusting their parents (which has a genetic basis), and everything spins off (develops from) that original trust. Note that the original trust is not based from trust or information.
So what you're really defining when you proclaim that 'trust determines information' isn't information so much as trust -- which, in this case, doesn't help much to define information.
True. Defining trust, and trusted sources, is a bit twitchy. It's probably a lot more difficult and involved than defining information, which is simplistic.
Here is my simplistic definition, which seems to reflect how the world acts: information is "meaningful data." Or, in this context (the Library of Babel), information is "meaningful communication" would probably be better.
And I went on far too long with this.
Re:Ideas? (Score:1)
If it's technically cost-prohibitive to put them on every desktop machine, then we'll probably only be using this technology in a "client-server" capacity, where your internet server will have the quantum coprocessor equipment, and you'll have to submit queries via network, but I think due to the nature of the quantum computer, CPU bandwidthe won't be a limiting factor, it will be I/O, or bandwidth of the network to submit queries and yeild results, which will be the main limiting factor, so these machines will necessarily *not* be on commodity hardware (x86), but rather, very high-end mainframe-type systems that can handle all the I/O from the transactions.
These two scenarios, depend on how easy it is to mass produce these processors, and how expensive they are to integrate, and especially, how widespread the technology is. If one corporation "solves" the problem, and patents it, and if nobody can reverse-engineer it (DMCA), then I'm guessing it's utility (which drives demand) will put the price well out of the reach of most mid-sized corporations, and we'll see a very select few VERY large quantum computation service providers arise, of course, outside of government and research applications.
But since this is still largely theoretical, and I'm just a karma whore, not a quantum computation scientist, there may be processing limitations that I'm not aware of that may figure into how this technology gets utilized.
I just remembered this old Metallica song. . .
Re:Poppycock (Score:1)
Nobody has tried yet to come up with a quantum algorithm to crack DES, or other symmetric cyphers, but there is no theoretical reason one couldn't be made... (nor any that one could, it's just not known what all QC can do yet).
Re:Enabling Big Brother to do his thing (Score:1)
Re:Poppycock (Score:2)
Um, Moore did... ;-)
(Then again, IMNSHO think "Moore's Law" is load of crap arrived at by massaging reality to fit one's beliefs. The current popular version seems ammount to "Intel's flagship line doubles in benchmark performance about every 18 months", which I must admit doesn't impress me that much, assuming even it is true.)
"There are a couple things that are not clear to me here..."
At least one [clara.net] of the PGP FAQ's mentions this (this may not be the freshest link), an includes links to relevant papers. I couldn't care less about whether it's true or not, so I haven't bothered to follow up.
-jcl
Re:Indeed Poppycock (Score:1)
Perhaps your are referring to Quantum Encryption (sometimes known as Quantum Key Exchange); sending photons down an optical fiber with a guarantee that no eavesdropping has occurred (which would collapse the wave function, alerting the recipient that the photon has been observed...).
Burris
Download time from classical to quantum? (Score:1)
What it is good for is unstructured virtual databases -- such as find the key to this cyphertext / plaintext combination. (As there is no real database, just a predicate to find the value of.). Grover's finds x such that P(x) is true, in (about) sqrt(x) time, I think. P is any boolean function (predicate) you can implement on a quantum computer.
I'm no expert in the field, just doing a C.S. paper at 'varsity in this stuff. (kinda.)
Re:Indeed Poppycock (Score:2)
In particular, I thought that the encryption algorithms being worked out using elliptical curves as a basis were still thought to be immune to the ability to break them through massively parallel factorization and/or discrete logarithm techniques.
Search Engine Broken, Call Quantum Mechanic... (Score:1)
The simple solution? Type in more words!
Search Results (Score:1)
What I want to see is a quantum search of the web in real-time. That should eliminate dead links. But would bandwidth ever be able to support that?
Re:Security (Score:2)
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).
Re:Ideas? (Score:1)
The upside of this, of course, is that private conversations would be safe as never before. the downside is that corprate entities would have the same powers. I personally trumpet governmental attempts to regulate corporations -- not business, but the megalithic entities that have are wrapped around the concept of "business" like a tumor -- and I feel that one of the most useful tools in chasing them down are internal communiques. Imagine if these were locked behind an encryption where even the attempt to decrypt them automatically made them further unreadable. Perhaps I'm assuming that storage of quantum-encrypted messages is possible, which I don't think it is yet.... This isn't a screed about the need for less privacy, but rather that corporate entities shouldn't receive all the benefits that private citizens do with respect to this (and many other things).
The way I see it... (Score:1)
slashdot needlessly hyping a story from 1996. (Score:1)
cheers,
sh_
Current Limits (Score:3)
Re:Vague on increased precision (Score:1)
Re:Security (Score:2)
What really worries me is the day John Carmack gets his hands on the first prototype of 3DFX's Quantum-processing video card..
Re:OTPs (Score:3)
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).
Cool or not it's stil unproven. (Score:1)
Now what? (Score:1)
So all the soon to be unemployed human genome researchers can start retooling for looking for needles in hay stacks now, eh?
The funny thing about a quantum search algorithm is that by the time a computer exists on which to implement the algorithm, a brute force linear search will have already solved the problem.
This is like holographic data retrieval (Score:1)
The principle is something like this: It is possible to store thousands of 2-D images in a 3-D crystal using holographic techniques. Point your laser beam at a different angle to store/retrieve a different image. Each of these images is stored throughout the crystal.
The really cool bit is this: Suppose you have a picture archive stored in the crystal, and you want to find a picture that looks a bit like X. Simply shine an image of X into the crystal, and beams of light shoot out of it that point in the direction of the laser beam that was used to store the image. The stronger the resemblance, the brighter the beam. Instant archive searching, through the magic of quantum mechanics.
Furthermore, this technology works. Prototypes have been built.
it's not "how fast", it's "what" (Score:2)
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.
Where has everyone been? (Score:2)
Re:Indeed Poppycock (Score:2)
I like fundamental shakeups. I consider the invention of quantum cryptography to be a far more interesting shakeup than quantum computation. Even quantum cryptanalysis is more interesting than quantum computation.
Theoretically, quantum algorithms can test all of the potential factorizations for a key of arbitrary length at once.
You confuse `theory' with `practice'. In theory, a massively parallel Turing machine can compute all of the potential factorizations at once. In practice, we don't worry about this--why? Because it's not going to happen, and we've got a lot of mathematics and physics to back us up.
How many electron energy states are there? That number is on some level fundamentally connected to how much computation can be done--every state corresponds to a different aspect of the number-crunching. There are a finite number of energy states; there is a finite amount of computation a quantum computer can do.
At a conference recently when a paper was presented detailing the latest results of quantum computing, Schneier was heard to mutter "well, gee, any RSA modulus less than three bits is in real trouble..." Will quantum computers get better? Yes--up until about 15 qubits in length. At that point, our current models break down and we're going to have to invent entirely new technology.
Currently, we have absolutely no clue--not even well-thought-out theoretical models--of how to proceed from the 15-qubit level.
All of our algorithms which rely on the difficulty of factoring arbitary prime numbers will suddenly be completley useless and obsolete.
Yadda yadda yadda. I've heard "The Death of Public-Key" for twenty-five years, thank you--yours is nothing new. To factor a 3,072-bit RSA modulus, you'd need something on the order of a 1,536-qubit computer.
That's right. 1,536 qubits.
Even assuming that quantum computation follows a modified Moore's Law and our qubits double every 18-24 months, we're still looking at 15-20 years.
Let me repeat: I am not worried.
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.
Quantum computation does not provide any kind of unbreakable Vernam cipher. Quantum cryptography permits secure negotiation of symmetric keys over insecure lines of communication, but that's in no way related to the Vernam cipher. What the heck are you talking about here?
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.
Quantum computing is already feasible. The first electronic computers were used to break fairly sophisticated mechanical ciphers, and they had far less computing horsepower than your alarm clock today. When a wildly divisive technology is introduced, its repercussions are seen and felt almost immediately--look at how much digital computers have overturned our world in the last fifty years.
Quantum computers are not an "if and when" proposition. They are feasible, right now, albeit in a very limited state. So is Leonard Adleman's biological computing paradigm. Both of those have the potential to be incredibly disruptive to whatever fields of CS haven't thought of its ramifications.
keylengths of whatever length will be compromized
Oh, give me a break. Look this stuff up--it reduces the keyspace by an exponential factor of
Analysis of the algorithm's uses (Score:4)
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.
Re:Huh? (Score:2)
//rdj
Here's how (Score:2)
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?