Slashdot Mirror

← Back to Stories (view on slashdot.org)

Quantum Computing for Dummies

Posted by Hemos on from the excellent-coverage dept.

nsanch writes "I just noticed this article at Cryptome. It's one of the better explanations of quantum computing I've ever read, and it's pretty thorough too, detailing some algorithms, including one that the author wrote. Seems it'll be a while before we ever get to see one in action though. " It's true-it'll be sometime before a true quantum computer is actually in use. Very good article, tho'.

83 comments

  1. Re:Computers only use bits? by j-p.s · · Score: 1

    Computers in the Turing sense have to have a finite set of internal states: they then move between the states depending on the input to the computer. Otherwise it'd just be a transformer, converting one form of analogue data into another. It'd be an electrically-powered barometer.

    So it depends a lot on the processing of your "computer" as to whether it really is one. Is there no digitisation at any point, at all? Does it not react to its input in a way suggesting it has discrete internal states, other than producing an analogue output with a fairly simple relationship to its input?

  2. Re:Implications of QC by Admiral+Burrito · · Score: 1

    A Pure Math Major I once knew explained to me that Quantum Computers could factor large numbers in polynomial time (a fact the article confirmed). This means RSA would be transparent to anyone with a QC. It seems that any current cryptographic system would suddenly become obsolete, as the computer could simultaneously check every key/password and give you the correct one. This is almost like proving P=NP (for those of you who don't know any Complexity Theory, encryption and 'one-way' algorithms are possible because we think P=NP is untrue; but it has never been proven). But it's a little bit different.

    Factoring is not an NP time problem. Nobody has ever claimed it was. It just seems hard in practice.

    Cryptosystems that are based on NP problems are safe even with quantum computers, so long as you square the complexity (like, double the key size).

  3. Re:More FUD from Microsoft? by Field+Marshall+Stack · · Score: 1
    Everything a computer does -- whether synthesizing speech, calculating the billionth digit of pi or beating Garry Kasparov at chess -- ultimately comes about through the transformation of bits by gates.

    Scary isn't it?

    Nah, *coooool*.

    And then there's that everything Kasparov does just might come about through transformation of bits by gates, and that's just...waah, that's nifty.
    --
    "HORSE."

    --
    "HORSE."
    -Flaming Carrot
  4. PGP vs. OTP by Anonymous Coward · · Score: 0

    Ok will all you people who were blabbling about the uselesness of OTP over the weekend please shut up now? Sure, the guy's program sucks, and you can't go using a pad "over and over again", but hey, it's open source, so fix it! PGP stands for "Pretty Good Privacy" and that it is. It's just not absolute privacy. If it can theoretically be done then it will be. We went to the dam moon, and only fifty years prior to that it was thought impossible. We think about PGP that way today but in ten years it will be toast. Yes it will take all of the atoms in the universe, each acting as a computer 1000000 times more powerful than all the computers we have today, all connected together in a beowulf cluster the lifetime of a million universes to crack your 4096 bit PGP key by doing an exaustive search. But that aint going to be how it's broken.

  5. Re:Implications of QC by Field+Marshall+Stack · · Score: 1
    In a way, it's like defining a new model of computation, the first one since the Turing Machine. (I wonder if this disproves Church's Thesis, which states that the Turing Machine is the most powerful model of computation possible.) It would redefine the boundaries of P and NP. Thus, we may find a new class of NP-complete problems, that would allow the foundation for totally new encryption schemes.

    Um, geez, I don't even know enough to be incompetent, but best as I can figure QCs aren't more powerful per se than Turing Machines, it's just that they're a way to fit a very large number of Turing Machines into a very very small space. Anyone who actualy knows what they're talking about, please feel free to smack/moderate me down.
    --
    "HORSE."

    --
    "HORSE."
    -Flaming Carrot
  6. Re:Artificial brain maybe? by Anonymous Coward · · Score: 0

    Same goes for the "quantum" scheme!

  7. Earth = One big computer by Omar+Djabji · · Score: 1


    We all know that Earth is one big computer that is calculating the question for life, the universe and everything. If it is a quantum computer, then when the mice read off the answer it will colapse the system and the earth will sudenly stop existing in it's current state of quantum flux.

    If only Vorgon construction fleets had quantum state analizers as standard issue. It would save them alot of time. "we have to clear out this world for a highway. Lets just observe its quantum state and colapse it." Plus there would be much fewer pissed of mice in the universe.

    1. Re:Earth = One big computer by pSyk · · Score: 1

      You know, the whole thing with the quantum concept of an observer and the fact that we think the act of observation collapses the quantum wave function is based on the fact that we don't bevieve that faster than light travel is possible.
      Now if that were true a lot of this mysterious quantum affects would probably be reduced to straight forward 'math'.

    2. Re:Earth = One big computer by Omar+Djabji · · Score: 1

      Actually, some of the quantum wackyness has been proven (demonstrated) by experiment.

      I forget the exact details of the test, but it goes something like this:

      1) fire a particle at a wall with 2 slits.

      2) the particle will go through either one slit or the other (actually both)

      3) the particle actually leaves a wave patern on the photo-sensitive wall behind. It went through both, and made an interferance pattern with itself.

      4) now we observe the partice _AFTER_ it goes through the slits and behold, it only went through one. No interference pattern.

      Wacky!

    3. Re:Earth = One big computer by pSyk · · Score: 1

      Uhm... You are talking about something aspect has done recently. This doesn't actualy prove anything tho! All it tells us is that
      a) the photons know what we think and mess around with our minds
      b) something 'feels' out the path 'faster than light' ahead of the photon thereby telling it where it will end up.
      c) any number of other wacky QM enterpretations.

      And what i meant with my previous post is that i tend to believe b).

  8. Re:Implications of QC by Omar+Djabji · · Score: 1

    This would NOT disprove Church's Thesis. Any problem that can be accomplished by the massive parallel qualities of a quantum computer could be accomplished by searching through all possible quantum states with a turing machine.

    Remember that computability theory does not care at all about speed. Just power. Quantum computing does not add any power.

    What quantum computers do, is give us a method of building a non-deterministic turing machine. If someone could implement a non-deterministic turing machine with a quantum computer (I think it could be done), then programming many problems would be trivial.

  9. Re:Owwww by xQx · · Score: 1

    60 years ago, before computers were avalable, or even existant, the best encryption avalable was worked out by Nazis on pen and paper (don't mention the war). Encryption like this was able to be cracked by the US millatary in a week; but imagine what 12bit incryption would have been like back in those times. It would have been impossible to crack, yet now it is generally regarded as a simple task for a home computer to crack. Yes, PGP and algorithims like that will be obsolete, and a simple task for QCs, but the software industry will adapt quickly, and as before encryption WILL be invented which WILL tax these computers. Think back 5 years, running WordPerfect 5.1 on a DOS box at 4MHz. If someone said they had a 400MHz computer, would you assume you would be able to write messages quicker, because your program would be lightening fast, and wouldn't crash. Now fire up Word2000 on your PII 400 and see how stable it is.

  10. Re:Implications of QC by rew2 · · Score: 1

    Quantum computers can *not* do arbitrary nondeterministic computations. If they could, the factoring algorithm would be trivial (just guess the factors and verify that their product is the number you want to factor). Instead, Peter Shor had to devise a very clever scheme based on estimating the period of a long sequence. Quantum computers are restricted to operations that are definable by a unitary matrix. So while they can effectively get exponential amounts of parallelism, the kind of things they can do in parallel is severely restricted.

  11. Re:Can we handle the power? =] by pSyk · · Score: 1

    Just watch, we develop a unified theory over /. and wont' realize it:)

  12. Re:i guess i need the for dummies primer then... by pSyk · · Score: 1

    Heh you guys have been suckered into this "zen/voodoo/mystical" QM crap.
    The mystery here is how no one yet disputed Einsteins theory of relativity which prohibits things from being allowed to go faster than light.

    IF that was out of the way, we'd happily go on discovering how gravity and magnetism fit into the picture and have a unified theory in the works.

    Until then, we are stuck thinking that the chair isn't really there because we haven't looked at it recently.

  13. Owwww by SpamapS · · Score: 1

    My head hurts.. I think I need to play qUAKE for a while to ease the throbbing.

    But Seriously, this stuff is very cool. Once those are out, I guess it won't matter if you have a 4096 or 8192 bit PGP key... you're still toast!

    --
    SpamapS -- Undernet #Linuxhelp
  14. Non-determinism and QC by Snibor+Eoj · · Score: 1

    As other people have pointed out already, this would not make P=NP. That's a purely theoretical question, regardless of what practical applications there are.

    Recall that the 'N' in NP means "non-deterministic". What we have here is a non-deterministic computing machine, almost. (See below to find out why I say almost.) Thus, this machine could compute any problem in NP in polynomial time, whereas a deterministic one can only do those in P. If NP != P, then this machine simply has a wider range of problems it can feasibly compute.

    The reason I have to qualify this with an "almost" is that we don't have pure non-deterministic computing. Look at the example in the article of finding the pair (1,0) out of all four binary pairs. We non-deterministically find the answer in one or two steps. However, while the answer exists in some state now, we can't extract it, so we don't really have the answer yet. Unfortunately, we have to run through a deterministic set of steps to extract that answer. Thus, we don't have a purely non-deterministic computing machine.

    The question that arises, then, is how much this additional extraction step factors into the computation. If the steps are fixed within polynomial bounds of the size of the problem, then a QC actually could compute any problem in NP in polynomial time, since the deterministic portion would be polynomial time, and the non-deterministic portion is also polynomial time. Unfortunately, I suspect that the extraction may sometimes take more than polynomial time, in which case we've lost the benefit of the non-determinism in the deterministic portion.

    -Snibor Eoj

  15. A tiny little charge? by Snibor+Eoj · · Score: 1

    Another thought has caught my mind...

    In the article, he talks about how a tiny jolt will flip the polarity from up to down, or down to up, and a lesser jolt will give it a probability of being one way or the other.

    Question is: How finely measured do these jolts have to be? What does it do to the computation if we accidentally end up with 49/51 probabilities instead of 50/50? Are we capable of consistently providing that exact measurement of juice? Is this going to be a limiting factor to the technology?

    Anyone know any of this stuff?

    -Snibor Eoj

  16. Re:Implications of QC by oldmacdonald · · Score: 1
    Let me try to clarify the situation with regards to factoring as an NP problem. I believe the situation is this (I'm a physicist working on quantum information, rather than a computer scientist, so the classical computer sciencey stuff you should take with a grain of salt):

    Polynomial problems are said to be in NP since they are a subset of NP, so it is not right to say factoring is not in NP, since all polynomial problems are "in" NP. There are also problems that are NP hard but not NP complete, meaning they are harder than polynomial, but that a fast solution to one of them doesn't solve all other NP problems.

    Factoring is known to NOT be NP-complete.

    Factoring might be NP hard, or might be polynomial.

    P might be the same as NP.

    So fast factoring on a quantum computer doesn't mean all NP problems are easy.

    It is not known if quantum computers can solve NP complete problems in polynomial time. Most people doubt it.

    Computer scientists certainly are working to try to understand the new complexity classes which result from the presence of quantum computers. I'm not quite sure if they have a class which is NP hard to a quantum computer, but even harder to a classical computer as Kreep suggests, but I am sure people think about such things.

    I am not aware of crypto systems based on NP complete problems. Even these might turn out to be breakable, if P=NP or if P=NP when you have a quantum computer. If anyone knows of a crypto system based on an NP complete problem (rather than just one that is NP hard) I'd like to take a look at it.

    Nearly all the papers in the field come out first on the web at quant-phys.

    John

  17. Factoring is NOT NP-complete by Anonymous Coward · · Score: 0

    Factoring has not been shown to be NP-complete. Of course that does not imply that your concluding idea is incorrect. Which leads me to the question,"Are there any interesting problems more difficult than NP-complete problems?" Can any of you answer this?

    1. Re:Factoring is NOT NP-complete by rew2 · · Score: 1

      Certainly. NP-complete problems are pretty far down the complexity hierarchy, there are lots of harder problems. There are PSPACE-complete problems, EXPTIME-complete problems, NEXPTIME-complete problems, etc. The game of go, generalized to an n x n board, is EXPTIME-complete. That means that, given an arbitrary configuration on an n x n go board, determining if there is a win for black *provably* takes exponential time in n (no assumptions like P != NP required, since it is known that EXPTIME != P by diagonalization).

      A lot of the sort of decision problems for various mathematical theories that you'd like your AI expert system to solve are PSPACE-complete or worse. And of course there are the problems that can't be computed at all, such as determining if a multivariate polynomial has integer values for its variable that make it equal to 0.

  18. Re:Implications of QC by Anonymous Coward · · Score: 0
    Again, as someone said, Factoring is in NP but not known to be NPC. So, knowing an "efficient" algorithm for Factoring with a QC is not the same as saying a QC can do 3SAT, for example.

    BQP (the class of problems "efficiently" solved by a QC) is not known to equal NP. There has been evidence either way, so it is not a closed problem yet.

    Another introduction can be found off the execelent e-print archive of LALN: http://xxx.lanl.gov/abs/quant-ph/9809016

  19. Sort the phone book by tipjar+administrator · · Score: 1

    Sort your phone book to reduce search time from N/2 to log2(N). No decent looker-upper system will do more than twenty comparisons to find one entry from among a million.

    1. Re:Sort the phone book by Anonymous Coward · · Score: 0

      Don't forget that your sort takes NlgN, do the entire operation is still greater than N/2.

  20. Re:Can we handle the power? by pSyk · · Score: 1

    >>What stops a programmer from say recording all the quantum states of the gates during an execution of the code in other qubits and after the culculation completes, reviewing what you saved up?

    >>Quantum mechanics. In order to save the states you have to read them. If you read them, you destroy them. If you can't read them until the operation is through, you have a black box.


    Not nessecerely. Quantum duality implies that you don't have to know the state of the particle to be able to 'replicate' it on another particle.

    So, therefore debugging would be possible just like it is now.

    Just my 2 cents

  21. Re:Implications of QC by Apparition · · Score: 1

    Actually, it has never actually been proven that factoring problems are NP-complete. So the fact that quantum computers may be able to solve them in polynomial time may be more of a demonstration that they are not in fact NP-complete rather than that P=NP. As has been pointed out by others, there has yet to be a quantum algorithm demonstrated that solves a problem that is KNOWN to be NP-complete in polynomial time.

  22. Re:Can we handle the power? by Anonymous Coward · · Score: 0

    That's not exactly true. The flaw is that all operations you perform on either the original particle or the new one, will effect both. Thus if you duplicate the state and then read the state of this duplicate, you would still cause the wave function to collapse for the original particle. So, therefore debugging would NOT be possible just like it is now.

  23. Re:Computers only use bits? by Yarn · · Score: 1

    depends what you call simple, analogue computers can add, subtract, divide, multiply, integrate, differentiate, do fourier transforms etc. Their main problem is that noise is always increased, limiting the number of steps you can perform.

    The only digitisation would be due to the electrons :)

    --
    -Yarn - Rio Karma: Excellent
  24. Hitchhikers guide to: by meme · · Score: 1

    According to the Hitchhikers guide to the Universe, i believe the answer to life's question is 42. Hopefully someday in the future, we'll be able to check this answer.

    --
    an enigma wrapped around a paradox driven by a paradigm shift
  25. My heart is beating... by Anonymous Coward · · Score: 0

    a little dab'll do ya...

  26. cryptome.org? by sfid · · Score: 1

    What kind of site is cryptome.org? It looked pretty crypytic to me...

  27. Quantum Computing for Smarties by anatoli · · Score: 1

    Here.
    --

    --
    Industrial space for lease in Flatlandia.
  28. schizophrenia by RoLlEr_CoAsTeR · · Score: 1

    BUT THE REAL MAGIC transpires when a two-qubit gate acts on a particle that is in a superposition of spin states.
    Kinda like mutliple personalities. ;-)

    Seriously though, it was a very interesting article, especially for blockheads such as myself, and I'm just hoping that they're over-estimating the time it'll take to develop this into something usable.

    --

    Insert mind here.
  29. More FUD from Microsoft? by The+Big+D · · Score: 1
    Everything a computer does -- whether synthesizing speech, calculating the billionth digit of pi or beating Garry Kasparov at chess -- ultimately comes about through the transformation of bits by gates.
    Scary isn't it?

  30. Coding for quantum computers by Anonymous Coward · · Score: 0

    Would you even need to write code for quantum computers ? Couldn't they just run every possible program simultaneously and see which one came up with the right answer ?

    1. Re:Coding for quantum computers by G27+Radio · · Score: 1

      The universe is a quantum computer that does exactly that...I still can't believe the answer is only 42...

      numb

    2. Re:Coding for quantum computers by Steve+B · · Score: 1

      It seems to me that the problem of coding a quantum computer to give the answer to a specific problem is going to turn out to be just as difficult as solving the problem the old-fashioned way.
      /.

      --
      /. If the government wants us to respect the law, it should set a better example.
    3. Re:Coding for quantum computers by PigleT · · Score: 1

      Quite possibly...

      I can see it now: "my other .sig is an electron", "quantum spods do it with fuzzy bits", "I computed but I didn't inhale", and similar things :)

      ~Tim
      --

      --
      ~Tim
      --
      .|` Clouds cross the black moonlight,
      Rushing on down to the circle of the turn
    4. Re:Coding for quantum computers by Anonymous Coward · · Score: 0

      Not so,
      this would be quite the same as saying that making a program to solve a problem would be just as hard as solving the problem itself.

      Any programmer can tell you that making a program to put one and one together takes longer then writing it down -or doing it without paper at all.

      Also, any programmer can tell you that any mathematical calculation which would not draw upon recursion takes longer to be programmed by computer then by hand.
      However, since most calculations draw upon recursion for simplicity (thereby reducing the chance at errors), for problems with large recursion loops writing a program might be quicker then to actually calculate it (using the example in the program, factorizing might be done quicker, etc.).

      Finally, when the problem itself is repeating, (i.e. it needs to be solved multiple times), then it would be interesting to have a program do it for you. It is there that timeloss is lessened. (this is another form of recursion, though now applied)

      Regards,

      Koos Gadellaa
      student computer sciences

    5. Re:Coding for quantum computers by pSyk · · Score: 1

      hitchhickers guide to the galaxy rulez!!!!!!!!!
      it incorporates lots of interesting ideas that have been flying through our minds lately.

      but as far as 42 goes.. well it's not even what question you ask or how.
      it's all in what data you feed your algorithms =P
      I mean we get a real live answer to the question of life every moment of our existance. Only we choose to take it as yet another dreadfull moment in space and time.

    6. Re:Coding for quantum computers by Anonymous Coward · · Score: 0

      I think the problem with the idea of having a quantum computer program itself is that, given a problem and a solution, there are many "wrong" programs that will work. You'd probably have to know the problem and every possible solution to be assured a correct program, and once you know that, do you really need a program at all?

  31. Implications of QC by Kreep · · Score: 1


    I heard about this a couple of years ago and I still have a lot of unanswered questions.

    A Pure Math Major I once knew explained to me that Quantum Computers could factor large numbers in polynomial time (a fact the article confirmed). This means RSA would be transparent to anyone with a QC. It seems that any current cryptographic system would suddenly become obsolete, as the computer could simultaneously check every key/password and give you the correct one.

    This is almost like proving P=NP (for those of you who don't know any Complexity Theory, encryption and 'one-way' algorithms are possible because we think P=NP is untrue; but it has never been proven). But it's a little bit different.

    In a way, it's like defining a new model of computation, the first one since the Turing Machine. (I wonder if this disproves Church's Thesis, which states that the Turing Machine is the most powerful model of computation possible.) It would redefine the boundaries of P and NP. Thus, we may find a new class of NP-complete problems, that would allow the foundation for totally new encryption schemes.

    (These schemes would not exist for modern computers, as our current machines would not be able to break the code even WITH the key!)

    It's probably a good thing that QCs are a long way down the line. I'm sure it would be easy to interface one to a current computer, and then the Internet, and crack everything on it. How could the transition possibly safely occur, short of dismantling the Internet while everyone buys a new computer?

    Anyone seen the movie 'Sneakers'?

    1. Re:Implications of QC by MarkKomus · · Score: 1

      I don't know if it would redefine P/NP, maybe give us a new class of problems which are NP put can be solved using quantum computers. From what I understand in some ways a QC is just like using a brute force approach, only it does run fast enough it is possible, unlike many brute force approaches today.

      I don't think you would be able to crack every machine on the net that easily though, your QC may be able to try every possible password at once, but my machine waiting for your login can only process one at a time.

    2. Re:Implications of QC by rew2 · · Score: 1

      You are correct that when and if quantum computers become practical, RSA will be dead (as will any other cryptographic scheme that relies upon the assumption that factoring is hard).

      However, this is not the same as proving P=NP. So far no one has found a way to use quantum computing to solve NP-complete problems quickly, and it's likely that NP-hard problems will remain intractable even for quantum computers.

      Quantum computing does not disprove the Church-Turing thesis. Quantum computers can be simulated by Turing Machines, albeit with an exponential slowdown.

      I will say that for many years many theorists believed a "strong" form of the Church-Turing thesis, to wit, that any realizable model of computation can be simulated by a TM with only a polynomial slowdown. This strong form of the Church-Turing thesis does seem likely to be disproved by QC. I say "likely" because it's possible (though improbable) that some one tomorrow might show how to simulate a QC on a classical computer with only a polynomial slowdown. (That would give a fast *non-quantum* algorithm for factoring.)

    3. Re:Implications of QC by Anonymous Coward · · Score: 0
      I say "likely" because it's possible (though improbable) that some one tomorrow might show how to simulate a QC on a classical computer with only a polynomial slowdown. (That would give a fast *non-quantum* algorithm for factoring.)

      1. It is not improbable, it is *impossible* IIRC. For a collection of n two-state quantum particles, there are 2^n measurable states; since we are dealing w/ quantum mechanics, at any particular moment the system can be in a superposition of all these states. Thus, we have a 2^n dimensional space. On a classical computer, to encode these superpositions, we need 2^n bits---if you have less, you cannot describe all the possible states the system can be in. However, a quantum computer needs only n qubits since these n qubits can encode the superposition of states (the "entanglement") since they are quantum particles themselves.

      2. However, just because you cannot simulate a QC efficiently on a classical computer does not mean factoring cannot be done in polynomial time. Factoring is not known not to be in P, after all (though it is thought not to be).

    4. Re:Implications of QC by jovlinger · · Score: 1
      Thus from, say, 500 particles you could, in principle, create a quantum system that is a superposition of as many as 2500 states. Each state would be a single list of 500 1's and 0's. Any quantum operation on that system-a particular pulse of radio waves, for instance, whose action was, say, to execute a controlled-NOT operation on the 175th and 176th qubits-would simultaneously operate on all 2500 states. Hence with one machine cycle, one tick of the computer clock, a quantum operation could compute not just on one machine state, as serial computers do, but on 2500 machine states at once! That number, which is approximately equal to a 1 followed by 150 zeros, is far larger than the number of atoms in the known universe. Eventually, of course, observing the system would cause it to collapse into a single quantum state corresponding to a single answer. a single list of 500 1's and 0's -- but that answer would have been derived from the massive parallelism of quantum computing.


      This seems like it is setting up a 3-sat problem. 3-sat is the quissisential (sp?) NP complete problem. IT would be neat if QC could solve NP complete problems in P time. Note that all current small-key (as opposed to one time pads) encryptions schemes are in NP .

      However, I imagine that I have missed some detail, as I seem to recall that QC doesn't fully implement a nondeterministic turing machine. Very likely, as the previous poster stated, there is a subset of NP problems that are ammenable to QC.

      3-SAT would not be one of them, unless all NP complete problems were, which in turn would imply that all NP problems are in QP.

      As for Church, the turing machine's power says nothing about efficiency. A QC would still only be able to solve deciable problems (just like a TM), but a lot faster. The holy grail -- the halting problem -- is provably unsolvable.
    5. Re:Implications of QC by jovlinger · · Score: 1

      ok, so whilst I was drafting my reply, about 10 bazillion other posters beat me to it. Anyway, just trying to add something nonredundant, I seem to recall that given the difficulty of setting up QCs, the interesting question is not what time class problems are in, but rather what space class:

      "How many qubits do you need to factor an n-bit number?" That sort of thing.

    6. Re:Implications of QC by Grueben · · Score: 1

      Obviously that would be the case...unless you had a quantum login program that could accept all possible passwords simultaneously. ;)

      Seriously tho, the idea is not that a QC would be able to instantly crack into every 'puter on the 'net. What a QC could do, tho, is decrypt pretty much any encrypted message you threw at it using current encryption techniques, and do it a hell of a lot faster than anything we can do today. Heaven help you tho if the QC got a hold of your passwd file... ;)

    7. Re:Implications of QC by Admiral+Burrito · · Score: 1

      I am not aware of crypto systems based on NP complete problems. Even these might turn out to be breakable, if P=NP or if P=NP when you have a quantum computer. If anyone knows of a crypto system based on an NP complete problem (rather than just one that is NP hard) I'd like to take a look at it.

      There are quite a few... One of the first PK systems was based on the knapsack algorithm. Most of these are easily broken. Just because a cryptosystem is based on an NP-complete problem doesn't mean the cryptosystem itself is NP-complete.

      I think IBM filed a patent a year or two ago for a PK algorithm that was NP-complete and had a proof that all instances were equally hard. I don't recall the details.

      The are zero-knowledge proofs for NP-complete problems. You can prove you have a hamiltonian cycle for a graph without revealing any information about the hamiltonian cycle. I'm pretty sure this can be used as an identification scheme: The graph is the public part of your ID, the hamiltonian cycle is the private part. I think it's possible to turn any such identification scheme into a general PK algorithm but I'm not sure.

      In any case NP-complete cryptosystems are not likely to replace RSA until large quantum computers really become practical, because RSA is so much simpler to implement.

      As for the possibility that P=NP with a quantum computer, I thought Grover's algorithm was proven to be the most efficient algorithm possible?

    8. Re:Implications of QC by oldmacdonald · · Score: 1
      I'll have to read up on NP-complete cryptosystems and see if I think they are broken by quantum computeres. It is always possible that the cryptosystems are all broken without actually sovling the NP-complete problem itself. One possibility is that there is no PK crypto if there are quantum computers. I don't think we know.

      As for Grover's algorithm being optimal: It is optimal for finding a single marked item in a list of N elements, which it does in square root of N time. But an NP problem may have more structure than simply being a random element in a list. So I believe the jury is still out on if quantum computers can solve NP-complete problems in polynomial time.

      John

    9. Re:Implications of QC by Kreep · · Score: 1

      I can see what you mean about the Church-Turing thesis, in that QCs would not likely represent a new model of computation.

      However, I don't think you understood my comments on the P=NP question.

      First of all, because of the nature of NP, any polynomial solution to an NP-complete problem can be used to solve ALL NP-complete problems (bootstrap method). For instance, earlier this year I saw Steve Cook from the University of Toronto (author of Cook's Theorem which proved the original NP-Complete problem, Circuit Satisfiability) demonstrate how a 3-SAT solution could be used to crack DES in O(n^2) time.

      Once one NP-complete problem is solved in polynomial time, the rest will follow like dominoes. Therefore an algorithm that factors large numbers in polynomial time (an NP-hard problem) will immediately mean any known problem in NP will be polynomially solvable.

      And since this algorithm theoretically exists for Quantum Computers, all known problems in NP will be polynomially solvable.

      But here's the rub:
      Is it possible that a new class of problems could be discovered that are in NP for QCs, but are not in NP for standard computers?

      That is, standard computers do not even have non-deterministic polynomial time algorithms to solve them, but QCs will. I don't know if this is true, but it warrants investigation if no one already has an answer.

    10. Re:Implications of QC by Hobbes_ · · Score: 1
      It's probably a good thing that QCs are a long way down the line. I'm sure it would be easy to interface one to a current computer, and then the Internet, and crack everything on it



      But think of all the pron sites you could get into! :))

      The more intresting thing is, who is working on these? Something like this would normally be funded by the military, but any company with this wouldn't have to worry about the military.

  32. Computer Scientists might face more complex math? by Anonymous Coward · · Score: 0

    This year I finally completed the traditional math requirements for Computer Scientists after completing Differntial Equations and 3 dimensional Calculus. If this article is indicative of future requirements for Computer Science majors, learning the newest API's and algorithyms might not rank high on our requirements. I didn't particularly enjoy my introduction to quantum mechanics course, but it might be prudent to take another semester of physics. Being forced to solve the Shrodinger equation to develop a new program will certainly put a new twist on coding.

  33. Parallel Universes? by BiGGO · · Score: 1

    I heard quantum computers are related to parallel universes somehow,
    and I heard about a "EPR bridge" on the tv show "sliders".

    Can someone explain to me what does it mean?
    Does it mean that every outcome of the superpositiion is in a different universe?
    (ie for a 500 atom computer it will happend it 500^2 universes?)


    ---
    The day Microsoft makes something that doesn't suck,

    --


    ---
    I'm going to live forever, or die in the attempt.
    1. Re:Parallel Universes? by pSyk · · Score: 1

      Parallel universes is only one interpretation of the quantum postulate. You can think of it how ever you like... super position, multiple universes, or some people even believe that faster than light signaling is possible. I would suggest for you to research this topic deeper, and read through this article for dummies. it tells you among other things about the number of things you can store in any number of 2 qubits == 2^q,
      which grows exponentialy as you add more and more of them.

      good luck, m0n.

    2. Re:Parallel Universes? by Anonymous Coward · · Score: 0

      There are many implications of modern physics. Superluminal (Faster than light) connectivity and the "Many worlds theory" are just two. There was a book written back in the late 70's or early 80's called "The Dancing Wu Li Masters" I think the author was Gary Zutav SP?. It was a pretty good "Quantum Physics for dummies" book, and explained things like EPR bridge and Bell's theorem. Despite being an old book it still might be worth the read. I loved the quote at the end.
      I think my basic problem with understanding modern physics is that I still keep trying to seperate The Dancers from the Dance.

    3. Re:Parallel Universes? by kps · · Score: 1

      A book suitable for laymen (i.e. no math/physics background necessary) that covers this is The Fabric of Reality by David Deutsch, one of the pioneers of quantum computing mentioned in the article. See here.

  34. Nice one by irish_spic · · Score: 1

    Academically more complete; however, I still felt that there were some leaps in reasoning... maybe I am just an uninitiated one ;)

    frank

    --
    A truth that's told with bad intent, Beats all the lies you can invent. -- William Blake
  35. Can we handle the power? by Shotgun · · Score: 0

    I could install a supercharged dragster engine in my Nissan pickup truck; unfortunately, if the excessive power didn't rip my transmission apart or spin all the rubber off my tires, I doubt that I could control the acceleration. My point is that as a general purpose computer this technology will be useless unless someone developes tools that will make normal developers smarter.

    The operation of today's processors are easy to understand. They perform one step at a time progressing from known state to known state. And yet most of the software available is infested with bugs. One of the easiest ways to debug this software is to single step through the code with a debugger in order to completely understand its operation. If we now introduce a system that cannot be read until the final answer is available, how will software improve.

    Does anyone remember how 'self-modifying code' was going to save us all? Why aren't genetic algoritmns taking over programmer jobs? It's something that is understood in all engineering circles. More is not always better. If you can't harness and control the energy then it will usually do more harm than good.

    --
    Aah, change is good. -- Rafiki
    Yeah, but it ain't easy. -- Simba
    1. Re:Can we handle the power? by pSyk · · Score: 1

      What if there are dual quantum processors, that collapse the calculation and the debugging function at the same time?
      wouldn't it allow for something like that?

      *THUD* --- sound of me hitting a book

    2. Re:Can we handle the power? by pSyk · · Score: 1

      Oh Please!! I, as a programmer don't agree.
      Back in the day of vaccum tubes people thought
      that debugging a solid state processor instructions that work over thousands of different registers would also be highly difficult if not impossible.
      But, we managed! Still here, using the computers as you can see.
      With quantum computers lots of things change, but as more change, the more stays the same. What stops a programmer from say recording all the quantum states of the gates during an execution of the code in other qubits and after the culculation completes, reviewing what you saved up?

      Same basic principle, ma'm =)

    3. Re:Can we handle the power? by Anonymous Coward · · Score: 0

      Doh!! For that matter, even if you had only one quantum processor, you could just restart the program stopping it at subsequent steps and look at the current state, restarting after each read. Very redundant yes, but much the same as debugging with two equivalent processors. As I understand it, what is important isn't so much what the wave funtion collapses to. What matters is the complete state before the collapse, which is really a set of propabilities between 0 and 1 for each qbit. A single read would tell you very little about the state before collapse. Since many of the qbits might hold values other than 0 or 1 at steps before the final answer is found, each time you read the state you will get different values. This could make debugging a severe headache. What you would really need to do is be able to run the program through to a given break point and record the values of the qbits enough times to give you a rough idea of what the actual probablities for each qbit were before the collapse. I'll have to check my stats book on how many times one would have to check 500 qbits to have say a 95% guarentee that all averages are within say 5% of their correct values. Shouldn't have to be that large a number though. Maybe this debugging thing might be possible afterall. That doesn't mean that most of us mortals would be able to make heads or tails of what all the prob were or should have been doing in any given algorithm.

    4. Re:Can we handle the power? by Shotgun · · Score: 1

      >>What stops a programmer from say recording all the quantum states of the gates during an execution of the code in other qubits and after the culculation completes, reviewing what you saved up?

      Quantum mechanics. In order to save the states you have to read them. If you read them, you destroy them. If you can't read them until the operation is through, you have a black box.

      I'm not saying that it is impossible to program a QC. I'm saying it is very difficult. We work with black boxes all the time (most API's, the C libraries, etc). Someone can design a 'search coprocessor' that could remove the complexity of actually programming one of these beast. The API would in effect harness the power.

      Designing a more powerful computer, car, drill, bulldozer, etc, is as much about being able to harness the power as much as it is about creating it in the first place. Harnessing the power of a computer is an excercise in enabling a person to abstract a process and formalize it in code. Programming is made simpler for most people when the abstraction and coding are simple serialized steps. A secretary doesn't find it hard to say, "I do A, then B, then C." It's the recipe mentallity and people are used to thinking that way.

      The referenced article takes a page or two to explain how to do a seqential search. Granted it's a new way of thinking about a search, and therefore takes longer to explain. But that IS my point. It's a new way of thinking. It's hard to change the way people think. Add to that a lack of debugging techniques and you get buggy software.

      --
      Aah, change is good. -- Rafiki
      Yeah, but it ain't easy. -- Simba
  36. Can we handle the power? by Shotgun · · Score: 1

    I could install a supercharged dragster engine in my Nissan pickup truck; unfortunately, if the excessive power didn't rip my transmission apart or spin all the rubber off my tires, I doubt that I could control the acceleration. My point is that as a general purpose computer this technology will be useless unless someone developes tools that will make normal developers smarter.

    The operation of today's processors are easy to understand. They perform one step at a time progressing from known state to known state. And yet most of the software available is infested with bugs. One of the easiest ways to debug this software is to single step through the code with a debugger in order to completely understand its operation. If we now introduce a system that cannot be read until the final answer is available, how will software improve.

    Does anyone remember how 'self-modifying code' was going to save us all? Why aren't genetic algoritmns taking over programmer jobs? It's something that is understood in all engineering circles. More is not always better. If you can't harness and control the energy then it will usually do more harm than good.

    Please note that I'm not saying that this technology can't be created. What I'm saying is that if it does become mainstream, the average programmer won't be intelligent enough to write and debug programs with it.

    --
    Aah, change is good. -- Rafiki
    Yeah, but it ain't easy. -- Simba
  37. Artificial brain maybe? by Anonymous Coward · · Score: 0

    The article sounded to me as an approach to creating an artificial brain, especially the part about complex molecules-computers submerged in brine.
    Yet I've got a comment. Massively parallel computing is very possible with the present tech. All you have to do is to merge processing capability into the memory chips, leaving only the most complex operations (like floating point) to the CPU, and eventually overcoming the very idea of CPU. In such a system, the example with the "telephone directory" can be exactly as fast. I.e. one set of data is filled with "telephone directory" another set of the same topology - with blank data except for the "street address" fields that has to be filled with the known "street address". Then these two layers can be compared in one cycle if their corresponding memory cells are interconnected by processing cells. This means that to accomplish that particular kind of task one has to arrange "processing-capable memory" in cells of two independent memory bits plus one elementary processing unit. By increasing the number of independent memory bits served per processing unit, the resulting array will eventually become capable of tensor-like calculations.
    All in all, it's a highly simplified example of the "neuron net" idea. (The BRAIN is still lurking around, isn't it?)
    The great shame is that all that stops the idea, is the higher cost of combined memory/processor type silicon plus the inertia pertaining to computer industry.
    (you can also reply to agorabasta@usa.net)

    1. Re:Artificial brain maybe? by Cpt.+Fwiffo · · Score: 1

      Not entirely true,

      It would only need one operation.
      However, to do that operation, the normal O(N) steps are required, since it is still sequential.

  38. Re:Computers only use bits? by Anonymous Coward · · Score: 0

    I thought I saw somewhere that quantum computers weren't limited to base 2 computations? Oh never mind that was just a futurama episode.

    01011001110102

  39. There is a major unresolved issue here. by Anonymous Coward · · Score: 0

    All these discussions of Quantum Computing assume that one can generate arbitrarily complex superpositions that will evolve according to the Hamiltonian until we, the users, feel like it and collapse the wave function. Thus the basic idea is premised on this voodoo/zen/mystical aspect of QM that supposedly what causes the collapse of the wave function is human consciousness. If you haven't been suckered into this nonsense, there are various other viewpoints as to what causes collapse of the wave function. The simplest assume a constant collapse (rate of x per unit mass per unit time). The most interesting (IMHO) assume that what causes the collapse is that the discrepancies between the gravitational curvature generate by the different superpositions grows beyond a Planck length. (Lots of handwaving here as to exactly what that means of course.) Why does this matter? Because it sets a limit of how large these quantum computers can be (theoretically, not just practically), and that limit may not be especially large. (For more details on the stuff I mentioned about collapse of the wave function, read Chapters 5 and 6 of _Shadows of the Mind_ by Oliver Penrose, pretty much the only QM book aimed at the public that's not complete crap.)

    1. Re:There is a major unresolved issue here. by Anonymous Coward · · Score: 0

      That's "Roger" not "Oliver". BTW, I'd stick with the Feynman Lectures. They are dated and aimed at physics students, but far better introductions to the subject.

    2. Re:There is a major unresolved issue here. by Anonymous Coward · · Score: 0

      Did you not see the section on quantum error correction? And as for `what causes the collapse is that the discrepancies between the gravitational curvature generate(d) by the different superpositions grows beyond a Planck length.' That's a pretty tenuous conjecture to be making predictions from.

  40. Re:Computer Scientists might face more complex mat by jflynn · · Score: 1

    They're calling it "3 dimensional calculus" now? Arrggh. I think I liked "multivariable analysis" better.

    The problem you bring up is exactly why schools have to concentrate harder on teaching students to research and solve problems. Whatever facts you learn in college, be sure they will be largely obsolete or irrelevant in 20 years. Your problem solving skills will last your lifetime.

    Jim

  41. Bad link, no donut by 23skidoo · · Score: 1

    Here's a link that will work: http://cryptome.org/qc-grover.htm

  42. "For Dummies" trademark by antizeus · · Score: 1
    Careful, you're likely to get a threatening letter from IDG Books for using their registered trademark.

    --
    -- $SIGNATURE
  43. Computers only use bits? by Yarn · · Score: 1

    Boiled down to its essentials, any computer must meet two requirements: it must be able to store information as strings of 1's and 0's, or bits

    If this is the case what is this analogue computer that I built? Admittedly binary computers are what are used on our desks with monitors attached, but analogue computers are often used for temperature control etc. Any why cant a computer operate on muliple levels? It could even be faster.

    --
    -Yarn - Rio Karma: Excellent
    1. Re:Computers only use bits? by cultobill · · Score: 1

      Try bits as being read, "binary pieces of information", ok?

      --
      -- Bill "Houdini" Weiss
  44. Quantum Switching vs Quantum Computing by Anonymous Coward · · Score: 0

    I think the speach that you want to was talking about quantum switching, which I belive is different than quantum computing. Quantum computing is about using the nature of quantum mechanics to form systems to solve problems, whereas quantum switching refers to using quantum mechanical properties of a device to make a really small switch that behaves like transistors to in modern digital circuits. I haven't seen the article about the molecular switches by HP yet, but I think that is allong the same line.

    Anyhow, I wasn't there so maybe I'm reading too much into it. This is just how I've thought of the situation.

    Matt

  45. i guess i need the for dummies primer then... by x0 · · Score: 1

    In the article, the author states that he knows the know outcome. He also states that observing the computation destroys the state of the superposition. So, what this means is that I still don't quite understand exactly how this works. If only one state provides the 'answer', and that the answer is returned by observing the state to return the answer. wtf?

    --
    In the immortal words of Socrates, who said; 'I drank what?'
  46. Bulls__t by Anonymous Coward · · Score: 0

    This just sounds like standard probability until you get to the part he glosses over. Sure, I need N computational units, and I can evaluate N^2 states.

    Look: 8 bits can store a value (or a state) from 0-255. If you initialize this byte from a random number generator, you have a superposition of 256 states until you tell the user what the value is. Nothing quantum here, just normal probability. Don't forget, you actually have 8 1-bit CPUs.Then a miracle happens - I do a special calculation that collapses the probability to the solution.

    When is someone going to explain this with a little less hand waving? Until they do, I'm skeptical that is anything more than a theory of calculation with random numbers.

    Q: But how do you get that magical N/2 solution time?

    A: Optimize your conventional algorithm for 8 CPUs and report back.

    1. Re:Bulls__t by Anonymous Coward · · Score: 0

      The difference is that the quantum computer evaluates all the states equally, but some states are more equal than others. (You've probably grasped the basics. Build some apparatus that even in classical terms is capable of sorting out "right" from "wrong" answers. Shoot some "quantum" photons, etc. through it. Observe the result: the "wrong" solutions have cancelled out. Apply for grant.)

  47. Intel by Kalil · · Score: 1

    I went to an open forum with Craig Barrett(CEO Intel) and someone asked him a question about quantum switching. I just thought this would be an interesting input on the subject. Barrett thought it would be at least 20 years before they started to explore that option. Because according to Moore's Law they will be able to reduce the manufacturing process to about .05 micron. Right now they are at .18 micron. Then after it has become that small, they can start using 3 dimensional layers of transistors. So the transistor still has a long time ahead of it.

    --
    People, their what's for dinner.
  48. Beowolf! by Anonymous Coward · · Score: 0

    Even better, imagine a Beowolf of THESE puppies!

  49. Wow, in 30 years we can crack anything... by Anders+H�ckersten · · Score: 1

    Or, we can just get that autistic boy from "Mercury Rising" and do it today.

  50. Read the paper! It's O(sqrt(N)), not O(1) !!! by Admiral+Burrito · · Score: 1

    Would you even need to write code for quantum computers ? Couldn't they just run every possible program simultaneously and see which one came up with the right answer ?

    Seems a lot of slashdotters think quantum computers can solve any problem instantly. Not so. Read the paper!

    MOST SEARCHES, OF COURSE, WOULD SCAN a list longer than four items. To do so, the algorithm might repeat the three quantum operations many times, nudging the system toward the desired state with every pass through the loop. What makes quantum searching so powerful is that, for a list of N items, the algorithm requires only about the square root of N steps to find its quarry-not the N/2 steps of the classical trial-and-error search. Thus a quantum computer could search a million-name phone book in 1,000 tries instead of half a million. The longer the list, the more dramatically the quantum algorithm will outpace its classical rival.