Catch up on stories from the past week (and beyond) at the Slashdot story archive

 


Forgot your password?
Close
typodupeerror
×
Technology

Big Step in Quantum Searching 106

Posted by Hemos from the bleeding-edge dept.
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 discussion has been archived. No new comments can be posted.

Big Step in Quantum Searching More

Big Step in Quantum Searching

Comments Filter:

  • Not as fast as you might wish (Score:3)

    by Ignatius ( 6850 ) on Thursday May 25, 2000 @04:57AM (#1048655)
    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.

  • Chalk another report on a gedanken breakthrough for wired. Now I remember why I don't bother reading the magazine any more. Not only does the article treat a theoretical algorithm only usable on theoretical hardware as real news, the algorithm only has a trivial application in the fantasyland it theoretically works in:
    However, both the GSA and its generalized offspring work only if there is a single right answer to the query, or problem, posed. In other words, the object of the search must exist in the database and it must be the only candidate for that search.

    ---
  • MSNBC's article points out that 7 qubits have been linked together, but we need 25 for such a search as Grover's to be possible.
  • Yeah, there's a huge difference between an algorithm of *instant*, or one operation, run time and a *logorithmic* run time algorithm, when it comes to massive databases.

    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!
  • Actually, we should go back to the thirties when the government didn't have the technology to store all my personal information

    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..
  • True, IF the algorithm reduces to a form that is computable on a Turing Machine.

    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?

  • 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. 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. 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. 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.
  • Yowee.

    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.
  • Ha ha!

    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.
  • New Jane 1.0
    A complete quantum computing solution.
    Featuring
    • The Intel UnobtaniumTM quantum processor
    • IBM Dark MatterTM hard drive with infinite data density
    • integrated 3Com AnsibleTM NIC, infinite bandwidth, zero latency.
    • Integrated Heisenberg search engine, by looking for the data, you've found it!

    Financing Available.
  • "Are you alive? This is a QUANTUM algorithm. I'm SURE that OS/2 does not have any quantum algorithms, because the machines OS/2 runs on are BINARY machines, not QUANTUM. Now go do some reading on what quantum computing is and why it's so dang cool"

    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)

    by orpheus ( 14534 ) on Thursday May 25, 2000 @07:19AM (#1048666)
    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!
    _____________
  • I was in an AT&T class on data transmission in the early 80's and the instructor was explaining cyclical redundancy checking. He claimed that one of the gurus at Bell Labs had developed an algorithm that was able to predict at what point in the data stream noise would occur and how long it would last and substitute good data with dummy bits so it didn't matter if they got blown away. Having access to the same magical formula, the modem at the other end would know that the dummy data was coming and simply discard it as it came in and automatically pick up when the first good bit showed up.

    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

  • Well, as long as you have plugged your nose via USB, your browser client will read personality info extracted from DNA samples found in your nasal hair. Said personality context taken in reference with your _vague_ query geerates precision search vectors through the vast tree of preliminary results returned. Thus relevant results are filtered and presented. Duh.
  • Thanks. Do not mind doing the search. just forgot the name.

    Tom

  • Re:OTPs (Score:1)

    by NI3 ( 129639 )
    Not true. It's practical, and it works

    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?
  • I agree that this is overhyped. All the researcher claims is a speedup, from a brute-force algorithm with speed O(N) to his quantum system requiring O(sqrt(N)). That's nice, but it doesn't make the results any better. It isn't even that great a speedup; most indexing schemes approach O(log(N)). If you have one hard index key, such as the first name suggested in the example, any decent database can return all the hits on that key, on which you then perform a full scan, computing probabilities with whatever formula is desired. That would do what his scheme does, with current technology and cheaply.

    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)

    by Anonymous Coward
    Your math is a bit off there First of all, it's 28^100, which is quite large. But even if it were 100^28 (which is much smaller) that would still be huge! That's 10^56! 2^186!! I'd be willing to wager that all the mass+energgy in the solarsystem, converted to hydrogen atoms at absolute zero wouldn't be able to store that much info, but I digress. The matter at hand is that 28^100 is more like 10^144, which is alot. Man, I wish slashdot had a moderation option "inaccurate".
  • A recent Scientific American article by the discoverer of the fastest possible quantum computer search algorithm describes the issues well. It could have been Shor.

    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.

  • 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.

  • If and when quantum computing comes to pass, it will immediately outdate all of the encryption methods we have now. Would-be crackers would be able to break any standard (current) password or encryption in a matter of milliseconds with a quantum computer. However, there are some primative quantum encryption algorithms in existance now that prove decryption difficult even for another quantum computer without the proper information. In the Code Book [barnesandnoble.com] there is a section about quantum encryption, not the best but it helps a little.
  • This is how the thing works:
    All the algorithm needs is one or two definitive search terms, like the person's first name, and clues to the other items, like a guess at the last name or street, plus a probability associated with each search criteria.

    "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."

    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

  • That is not necessarily true. Read the article and the links on quantum computing on Grover's page [bell-labs.com]. This article [stanford.edu] states that IBM researchers claim that Quantum computers will be so much faster than conventional PCs that searching eight trillion bytes of data searching for one word may take a month but a Quantum computer could do this in 27 minutes. This means that quantum computing algorithms can therefore be much more complex than regular algorithms with imperceptible speed difference on a quantum PC while the same algorithm would be horribly inefficient on a conventional PC. For example a sequential search is considered horribly inefficient on conventinal PCs but with the speed of Quantum computers, it would get the job done in a speedy enough manner. (I haven't studied quantum computing besides reading a few articles so please forgive me if my example isn't technically accurate, maybe a grad student somewhere can shed light on this?)

  • The algorithm apparently relies on massively parallel computing and wants only a single correct answer.

    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
  • By the time that they get one getting more and more anonymous will be almost trivial. Remember what pgp/gpg/etc has done to e-mail communications? Various anonymizing services are also in place. This utterly prevents people from gaining access to your personal data unless you are sloppy with it.
  • 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.
  • Are you alive? This is a QUANTUM algorithm. I'm SURE that OS/2 does not have any quantum algorithms, because the machines OS/2 runs on are BINARY machines, not QUANTUM. Now go do some reading on what quantum computing is and why it's so dang cool
  • 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?
  • Jeeves, what do you know about quantum searching?
    1. Where can I find the web sit for the company quantum corp?

    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?

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

    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 .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. 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.
  • Imagine a day when you do not have to wade through pages of usless websites after performing a search.

    That day is today - I use Google [google.com].

    (I can't believe somebody hasn't said this already...)

    Adam

  • I like to sit around a hypothesize about the future as much as the next guy (as long as the next guy likes to sit around and hypothesize about the future as much as I do) but I've come to believe that the words "quantum" and "nano" are dead-bang indicators of some silly-ass utopian "In the future we'll do everything instantly at no cost" delusion.

    That may change, but for now those terms send up a big ol' red flag.
  • Grover's algorithm is *years* old. I wrote a simulation of it at least two years ago and it was old then. I think a search on a handful of bits has already actually been implemented on a real quantum device. The coollest algorithm is Peter Shor's integer factorisation algorithm - there's a really cool interaction between number theory and physics that allows this algorithm to be expressed very elegantly in quantum hardware.
    --

  • 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.

  • Since quantum fysics could give us a communication line that cannot be tapped without detection, we have a non-problem. Your line is compromised, you choose another one.
    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..)
  • Is there a 'quantum computer emulator' anywhere on the net? I know that it wouldn't have any of the advantages of a quantum computer, but it would be nice to fiddle around with it, and have it tell me, "This process used 10,521,982 cycles. On a actual quantum computer it would have only used 4,042." After all, got to stay ahead of current trends.
  • 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


    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.
  • Right about now I'm wishing for a moderation option "missed the point".

  • 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.

  • 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?

    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).
  • "Trust" is one way of looking about it. But what I was referring to above was the thing itself -- information, in this case -- and not that which is *outside* the thing -- trust, in your example.

    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.

  • .. that the more precisely we try to search, the less accurate the results are?
  • 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 cool... (Score:3)

    by B-B ( 169492 ) on Thursday May 25, 2000 @04:39AM (#1048699)
    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
  • 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...

    ChAoS

  • You can hook icons into a script or use a vague query and have the parser build long scripts for you. Am I the only one who's tired of this witchcraft propaganda? It ain't all that hard.
  • Think about how our own brains work. Neurons are basically very small, very simple processors that don't deal in straight binary, but rather in varying levels of chemical and electrical signals. A quantum computer is also non-binary. Could it be that the key to intelligence is multi-state computing? If so, is it possible that this algorithm is sub-sentient?
  • 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.
  • 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.

    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.

  • 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

  • <pun quality="bad" allusion="Comedy-Drama [scifi.com]">Big Step in Quantum</pun>
    -----
  • 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?

  • Vaporware! (Score:1)

    by Anonymous Coward
    Quantum computing is the most hyped vaporware since fusion. And at least *some* progress is being made with fusion. I can't believe slashdot posted such a deceptive headline. Quantum mechanics will operate just as many computers tomorrow as it did yesterday: zero. Some "big step".
  • 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.

  • But, don't you just know that something will manage to eat up all this incredible speed. A 1GHz chip would have conjuered up unthinkable speeds 10 years ago... but now it still runs Windows 2000 like a slug.

    For every great speed increase, theres always a pig of an application waiting to ruin it.

  • Quantum Encryption (Score:3)

    by Carnage4Life ( 106069 ) on Thursday May 25, 2000 @05:07AM (#1048711) Homepage Journal
    .... 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.


  • Does anyone know what's the "embargo" the IBM researcher is mentioning in the wired article???
  • Based upon what is currently happening in the computer market, is there a foreseeable need for quantum computing for consumers or will this be only for governmental/extremely high-end server market? Also, do you think that quantum computing is a "vapor-ware" technology, or do you believe that it will actually come of age?
  • Follow the link in the article and read about it.
  • Quantum encryption is based on quantum physics, not quantum computing... While I'm not sure how exactly quantum computers work, progress has been made on the front of quantum encryption which is based on the idea of measuring the alignments of photons... I can't articulate any more than that, though, because I know nothing about either! Maybe someone else could clue us all in?
  • 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

  • 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...

  • 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
  • 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.
    -------

  • Indeed Poppycock (Score:3)

    by Anonymous Coward on Thursday May 25, 2000 @06:42AM (#1048720)
    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.
  • Here's something else for you to think about -- it's quite possible to actually build such a library. The theory goes as follows:

    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.

  • Reading again, I must have misread your post regarding video streams. That aside, I think we have different definitions of "practical." Getting OTP to work requires one pad -- sent over a secure channel -- for each pair of users to communicate. While it would be feasible for me to set up a one time pad with, say, my spy contact in Serbia, it wouldn't be feasible for me to set up a one time pad with, say, eBay. (And every other `secure' web site I visit; and it wouldn't be feasible for them to set up huge pads for each user, and the secure channels to transmit them.)
    -------
  • There's no error there -- the uppercase letters plus space, full stop and comma add up to 28 characters, because I was following the Roman alphabet and using the same character for V and U, as I seem to remember Borges claimed the library did.
  • There's a device like that someplace called the Revolving Door but there's so many stupid revolving door companies on the web now that I can't find it without a major search, and let's face it, I'm not that interested in doing the data mining for you.
  • > After all, got to stay ahead of current trends. If you want to stay ahead you'd be better off writing one that using one. It's not hard. I'd send you mine (one of the first I ever saw on the web anywhere) but I accidentally used some quirks of the compiler I was using (KAI C++) and it won't compile with any other compiler :-( It really is very educational to write one because it will give you great insight into where the 'magic' of quantum computing appears.
    --
  • I too deal with security by trade, and as such try to pick my words carefully (admittedly my typing is terrible), but you should be careful about the things your saying. Some of them are true, but some them are nonsense.

    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.

  • 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.

  • 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.

    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 /. every day. There are people here whose thought processes I can't even FATHOM.

    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.
  • I think that quantum methods will be good at solving *some* kinds of problems which are by current methods, computationally prohibitive, so I think we'll start seeing "quantum coprocessors", perhaps as add-in cards at first, and then later, probably on the motherboard, and if technically feasible, on the die with the conventional CPU. The conventional CPU will do the tasks it's good at, and the quantum CPU will take on the problems that the API directs at it.

    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. . .
  • 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.
    Well, that is the worst that quantum computing can do, as there is already an algorithm that can do that. Factoring large numbers can be done in polynomial time, which is a far far bigger improvement than just the .5 exponential you quote. So RSA, and pretty much all assymetric cyper systems are toast when QC's become common.

    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).

  • ummmmmm big guy....dontcha know both the Getstopo and the NKVD (precussor to the KBG/FSB) did a mighty fine job of repression using THREE BY FIVE INDEX CARDS and manual labor. don't confuse the availability of the tools of repression with the will it takes to implement it, or the subservience of the populace that allows it.
  • "Can anyone really say they saw Moore's Law coming ... no."

    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

  • 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.
    Huh? The One-Time-Pad has been unbreakable since it was proven so by Claude Shannon in the 1940's. Quantum computing doesn't change this situation in the slightest. No advances will ever break the One-Time-Pad because it is perfect from an information theory point of view; every possible solution is equally as likely to be the correct solution.

    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

  • Doubful that Grover's algorithm will ever help in a real database. Download time from classical data store -> quantum computer is order(n), so you're confined to that. And if you are going to search multiple times you can simply sort/index the classical data (like a databse) and use this structure to accelerate to something like O(log_2 n).

    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.)
  • I thought that there were already certain mathematical areas of study where the advantages of quantum computers did not apply (in a decryption sense).

    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.
  • All search algorithms suffer from the same fundamental information problem -- insufficient information from the query. Unless the quantum computer is also a mindreader, it has no way of knowing whether the query "trains" has to do with railroads or wedding dresses.

    The simple solution? Type in more words!
  • I would guess that given vague input, even a quantum search engine would return all possible matches, thus leaving people still wading through vast numbers of useless dead links.

    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?

  • 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).
  • My personal favorite possible application is quantum encrypting, where (IIRC) the presence of an interfering (read: listening) party between the parties passing messages instantly causes the encryption to change subtly due to synchronicity between seperated particles of some such.... if folks have a link to confirm or deny this, that'd be keen.

    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).
  • ...it wouldn't be much use any way. (I think)it mentioned in the article that you could only get 1 result. With out having read the paper itself (I don't intend to until I have a vast supply of Asprin for the headaches), my guess is that if you don't get a definite answer, the algorithm will just come up with something like "answer not found". It'll be more useful when it can list all possible alternatives, possibly with there likelyhood of being right. Who knows, the next one might be that, but until then don't get too excited!
  • according to the comment, Grover's search algorithm "instantly search[es] a massive database and return[s] amazingly precise results...". to be more precise, if there are n entries in the database, Grover's algorithm takes O(sqrt(n)) time to find an entry. that's only an improvement on the time it takes to search an *unsorted* database, O(n). if you're going through the trouble of preparing the database for your, cough, lightning fast quantum algorithm--why not just sort it and then search in O(log(n))?

    cheers,

    sh_

  • Current Limits (Score:3)

    by BluesGeek ( 160887 ) on Thursday May 25, 2000 @04:52AM (#1048742)
    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...
  • You're sort of right. QC can be emulated on traditional computers in principle, but not in practice when the computations get large - it would take too long.

  • 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..

  • Re:OTPs (Score:3)

    by Christopher Thomas ( 11717 ) on Thursday May 25, 2000 @05:26AM (#1048745)
    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).
  • Ok like most of the "discoveries" posted to slashdot I have thought oh that's nice but you have to pause and think exactly how will they be able to do any of this? I mean one of the main problems of quantum computing is to get the qubits to functioning within very small tolerances and then to be able to effectively mass produce them in any forseeable way. These two very challenging problems haven't even begun to be addressed. I think when we get closer to the time when all people have at least 64 bit machines or even better 128 bit we just might have a chance but not now. What are the other "hand full" of algorithems besides searching applications? Also pause to think about a few other facts. What is the likelyhood that people will even be able to afford any of this stuff? I think that would surely take about maybe 70 years of more. Also how do you write a compiler or any software for one of these things? Will you have to be a physics major to be a cs major? That would truly such big time.
  • Ok, so we can now instantly search a massive database, given vague query parameters, and come out with precise results.

    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. :)
  • Check out this site in IBM's R&D department for information about holographic data retrieval [ibm.com].

    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.

  • Quantum computers don't compute anything different from regular computers, they just do it faster. But speed isn't really the limitation for returning meaningful results: our processors are plenty fast. And if speed were the limitation, there is plenty of room left in current systems using parallelism and FPGAs.

    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 [lanl.gov] 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 [lanl.gov]: "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...
  • It would appear your paranoia is aimed far too specifically: paranoia at our profession being shaken up, perhaps fundamentally.

    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 .5. It does not magically compromise everything. Breaking a 256-bit cipher with quantum computation is as hard as breaking a 128-bit cipher with a Turing machine.

  • 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.
  • The requirement for the existence of a solution in the database is ofcourse quite a big one.

    //rdj
  • 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?

Slashdot Top Deals

Top Ten Things Overheard At The ANSI C Draft Committee Meetings: (10) Sorry, but that's too useful.

Close