Become a fan of Slashdot on Facebook

 


Forgot your password?
Close
typodupeerror
×
Technology

Quantum Computing for Dummies 83

Posted by Hemos 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'.
This discussion has been archived. No new comments can be posted.

Quantum Computing for Dummies More

Quantum Computing for Dummies

Comments Filter:
  • 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?

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

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

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


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

  • Re:Owwww (Score:1)

    by xQx ( 5744 )
    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.
  • 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.
  • 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'.
  • Just watch, we develop a unified theory over /. and wont' realize it:)

  • 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.
  • 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!
  • 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
  • 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
  • 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 [lanl.gov].

    John

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

  • >>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
  • 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!
  • 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.
  • 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).
  • 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 :)
  • 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.
  • What kind of site is cryptome.org? It looked pretty crypytic to me...
  • Here [weizmann.ac.il].
    --
  • 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.
  • 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?


  • 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'?
  • The universe is a quantum computer that does exactly that...I still can't believe the answer is only 42...

    numb
  • 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,
  • 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.
    /.
  • Academically more complete; however, I still felt that there were some leaps in reasoning... maybe I am just an uninitiated one ;)

    frank
  • 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.
  • 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
    --
  • 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.
  • 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.)
  • 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.
  • 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
  • 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 =)
  • 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.
  • 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.
  • 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.
  • 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.
  • 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.
  • 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
  • Here's a link that will work: http://cryptome.org/qc-grover.htm
  • Careful, you're likely to get a threatening letter from IDG Books for using their registered trademark.

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

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

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

  • 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?
  • Try bits as being read, "binary pieces of information", ok?

  • 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 [qubit.org].

  • 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

  • Intel (Score:1)

    by Kalil ( 67667 )
    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.
  • >>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.

  • 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.
  • Or, we can just get that autistic boy from "Mercury Rising" and do it today.
  • 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.

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

Slashdot Top Deals

E = MC ** 2 +- 3db

Close