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

 


Forgot your password?
Close
typodupeerror
×
Science

First 7-qubit Quantum Computer Developed 223

Posted by timothy from the are-you-drinking-that? dept.
AllynKC wrote: "Wired News has this story on the developments in quantum computing. Federal researchers have developed the worlds first 7-qubit quantum computer. Interesting stuff; but even Wired's toned-down version is, quite honestly, beyond me at some points. Still, the concept of a fully functioning quantum computer intrigues me."
This discussion has been archived. No new comments can be posted.

First 7-qubit Quantum Computer Developed More

First 7-qubit Quantum Computer Developed

Comments Filter:

  • Little more than amusing (Score:1)

    by Anonymous Coward
    When I hear predictions like "quantum computers within five years" I remember the loony life-extension researchers back in the '70s who thought they'd have death licked by 1990 and we'd all be immortals. Looking around me, it appears to be the dawn of the 21st century and yet I still feel quite mortal and in fact I think the world record for longevity is still something like 120 or 130. So much for optimistic predictions.

    There are a lot of issues to be worked out about quantum gates and transistors before anyone can build a working quantum device of any complexity. First of all, there are issues with the nuclear weak force. Experiments have found that complex quantum circuitry just isn't terribly reliable because the weak force tends to break the connections between the quantum components. There are also timing issues, since at that scale there can be relativistic effects related to the speed at which signals are passing back and forth. You can actually have a signal that seems to arrive before it was sent, which plays all sorts of hell with the logic, as you can image if you know anything about programming. Some theorists have suggested that modern lazy functional programming languages such as Haskell may be best suited for programming quantum computers precisely because of this problem; it's already possible today to write Haskell code where information seems to go backwards in time due to lazy evaluation interactions. But anyway, I think quantum computers, if they ever become viable, won't appear for at least twenty to fifty years. People get so optimistic sometimes about their latest successes that they forget how much left there is to do, and how little a piece of the puzzle they've really solved, and that it isn't valid to assume that just because you've solved 10% of the problem in N years, you'll be able to solve the remaining 90% in 9N years. It's not a linear situation.

  • NMR and quantum computing (Score:1)

    by Anonymous Coward
    As an NMR (nuclear magnetic resonance) jock with some knowledge of the systems and methods used for these approaches to quantum computing, I tend to be 'cautiously optimistic' about the future of q-comp, like most. But I do have to comment on the embarrassingly poor reporting in that Wired article, at least as far as the description of NMR methods goes. Admittedly, it's difficult to distill the details of many scientific research techniques into layman's terms, even without the copy length restrictions of most publishing outlets, but this one was pretty bad. In this case the blame should probably be shared equally by the writer and the source, Laflemme ("needles with bulldozers"?!). The comment about 15 qubits being a practical limit for the NMR qcomp approach is probably the only valid detail, barring some new developments in relaxation-cancellation methods (which are not out of the question, given the recent advances in NMR methods for structural biology).
  • Actually, a Qubit is the distance from your elbow to the tips of your fingers.

    /me flashes back to that old Noah skit by Bill Cosby...


  • What, your qubix kernel doesn't want to run in supervisor mode either?

    Does that count as an observer?

    Damn you Heisenberg, and your Uncertainty Principle! :)

    Oh well. I think it already runs QNX...

    ---
    pb Reply or e-mail; don't vaguely moderate [152.7.41.11].
  • Why did the Wired article describe NMR as a specialized version of MRI? If anything, it's the other way around.
    "... nuclear NMR spectromotor, which is a specialized version of the imaging devices commonly used in hospitals."
    Also, "nuclear NMR" is, like " ATM machine", redundant.

  • Is it just me or does this sound a heck of a lot more like a register than a computer?

    It's quite a leap from a simple register type device to even the most primitive ALU ... I'm sure this should be refered to as a computer.

  • (think Bill Cosby)
    --
    John Kramer
  • The problem is not that it isn't a law, it's that fast new processors get dropped on Intel/AMD every 18 months. They get dropped on me something like every four years....
    ~luge
  • Right. What's a cubit?

    Apparently I'm not the only fossil around here : )

    (remember the part about changing the sex of one of the elephants?)

  • Within hours, Intel announced plans for a 14 qubit processor backwards compatable with x86 instructions.

    MS claims they will have a version of windows ready for its release, although its rumored to be months behind schedule.

    Its already running linux.
  • These people mangle chemistry. It's trans-crotic acid. Just like it's not a spectromotor but a spectrometer.

    Dennis
  • Maybe it's just because I know what's involved with this experiment on a practical level that makes me think that something really big is going to need to happen before q-computing makes any significant dent in anything.

    The experiment is done in an NMR, which is completely impractical for any kind of device for widespread use. Any extension to higher qbits involving the same type of experiment seems to me to be of very limited value.

    Conceptually it's interesting, but until the principle can be demonstrated completely at room temperature (the sample is at RT, but the magnets in the NMR are liquid nitrogen and liquid helium cooled), I don't think it's going anywhere.

    Dennis
  • "Actually, a Qubit is the distance from your elbow to the tips of your fingers."

    Isn't that a `cubit'?

    Kwoobit....

  • Okay, so is it mere coincidence that the numbers here are 2^3-1=7 and 2^4-1=15? I can't imagine that powers of two would impact qubits, but the question seems worth asking.

  • Actually, there is a quantum algorithm that is of use in symmetric crypto. A quantum computer can search a set of variables a factor of N^2 faster than a conventional one. So they could be faster for that alone.

    Also, things like the MD5 digest might be invertable faster using a quantum computer than a conventional one. Also, if it turns out quantum computers can solve NP problems in polynomial time, a lot of fundamental assumptions in even symmetric cryptography are going out the window.

    On the other hand, we'll always have one-time-pads. (assuming you use them right, the two time pad is a poor form of encryption)

  • This isn't really correct, you make two incorrect assumptions:

    1. From an application-level standpoint, there's nothing to distinguish a quantum computer from an electronic one except for speed
    2. IIRC, encryption speed scales linearly with key length while (brute force) decryption speed scales exponentially; this means that it will always be far more difficult to break a given key length than it is to encrypt that same key. Advances in technology help both sides of the equasion.
    The advantage of quantum computers is not just that they're faster (in fact, they aren't), but that because of the way they work, they can solve some problems with a better asymptotic running time (that is, in fewer steps), than a conventional computer.

    For example, RSA encryption assumes like you said that factoring a product of primes scales much worse than just multiplying numbers. This is true on a conventional computer, a quantum computer does not need exponential time to factor numbers, it can do it in polynomial time.

    Even brute force quantum computers can do faster (but not a lot faster, just a factor of N^2 faster).

  • >Well, assuming you (eventually) get a quantum
    >CPU... IO and other resources might not like
    >being accessed simultaneously by multiple OSes...

    Well, obviously we'd have to have some level of virtualization going on... some underlying arbitrator of resources.

    We do this now with stuff like VMWare, I don't see why it's such a reach to assume that we couldn't do the same thing with quantum processing.

    -LjM

  • So, in 5 years a quantum computer will triple todays fastest computers in performance?

    But according to moores law (or not really, because that's all about transisitors...) processors double in power every 18 months... so:

    if todays fastest computers are 5's, then quantum computers 5 years from now will be (5*3) 15's, while regular super computers will be (5*2*2*2) 40's... Doesn't sound very exciting to me in that time frame.
  • The port was relatively painfree...

    note "relatively"

    but the simultaneous crash/noncrash superpositions of states. And the blue flash of Cerenkov radiation... Omigawd! it's running a Win OS!

    My new .sig: Join AMSAT [amsat.org]
  • So _thats_ what those little flecks of green stuff are in salad croutons..hmm.

    Bowie J. Poag
    Project Founder, PROPAGANDA For Linux (Moving to MetaLab/UNC!)
  • "Adding more of the same" works only for building bigger classical computers. A 32-bit register can be constructed from 32 individual isolated bits. But for a useful 32-qubit register, you must be able to maintain quantum coherence over the whole ensemble. 32 individual qubits will not suffice.
  • Good explanation, but there's a couple things that are missing. For a somewhat longer explanatory article, people can look at one from Scientific American [sciam.com] a few years back.

    The importance of the 7 qubits is mainly just the same as the importance of bits in a classical computer: this is essentially the memory capacity of the quantum computer. It is also very important to have extra bits since, as you say, you can use redundancies to keep your computer from decohering (becoming non-quantum). But I remember a talk by a guy using chloroform as the molecule (CHCl3, for 2 qubits), and talking about using Shur's factoring algorithm (the quantum algorithm to factor numbers very quickly) to factor a number like 4. Not very exciting from a mathematical standpoint.

    The cute thing about using NMR with organic molecules this way is that different frequencies "talk" to different atoms in the molecule. So you can set or manipulate different qubits using different frequencies. The qubits talk to neighboring qubits as well, through the atomic interactions: this is actually a good thing- it's most of how your calculation gets done (the NMR is essentially I/O). Unfortunately, there's a problem with this approach: there's a physical limit to the size of these molecules (and thus the number of qubits). I think this is where the 15 bit limit came from. It is hard to imagine how you can find arbitrarily large organic molecules where each nuclear spin has an appreciably different resonance frequency, and where the atoms are spaced so that they only talk with

    There may be some breakthrough with this latest announcement, but it looks to me like a straightforward extension of previous results.

    Luckily there are some other approaches to quantum computers that (if they work) should scale up much more easily.
  • Surprisingly, there are collaborating groups around the world (e.g. Australia [unsw.edu.au]) that are in the process of designing building working prototypes of some of these weird and wonderful machines. The problem is that we still don't really have a good grasp of what commercially useful domain will drive the need for mass demand. I suppose it was the same electronically in that early boards were more toys until people mastered the assembly of megagates into useful building blocks. Peole like Pen rose [auckland.ac.nz] have speculated on physiological process underlying a given thought that may initially involve a number of superposed quantum states. I hope there are some really smart guys out there who can take some of the ideas through to the next stage. Now if someone could come up with decent quantum algorithms for massive parallel search and comparisons of multiple genetic strands databases, they'd make a killing. LL
  • Don't need one. It runs every possible program at the same time. But, since it's also doing everything else in the universe the trick is getting Quake the be what shows up on the screen.
  • Alright quantum computing is becoming more and more of a reality, is anyone working on encryption especially public/private key encryption that can withstand quantum factoring?
  • Or "factor large positive composite integers as products of prime integers"

    ^Z
  • Or perhaps "factor large numbers into primes"?

    ^Z
  • ...Thinking Machines Corp would still be around, and Danny Hillis wouldn't be wasting his time dicking around with a huge dumb clock.

    If Mr. Hillis is the genius you say he is, then perhaps he has a better idea of what might be important in the future than you or I.

    Personally I think he realized that there might be more important problems facing Humans than the speed of database queries.

    Hotnutz.com [hotnutz.com] - Funny
  • Try:

    http://www.qubit.org [qubit.org]

    There are some good tutorials there.
  • Haha--so much for the alleged proofread that I did of my post. As you so adroitly pointed out, it should be "factor large number."

    Perhaps you can sell me a deep hole in which to stash my growing embarrassment?
  • It's more meaningful, therefore, to think of the number of qubits in a quantum computer as its memory size, not its addressing capacity. A 30-qubit quantum computer isn't nearly analagous to a 32-bit von Neumann machine; it's much closer to one with 4 *bytes* of RAM!

    I disagree with this statement. If 30 qubits are placed into a coherent superposition, then the number of accessible states is 2^30, (about 1 billion states). This exponentiation of accessible states is part of the charm of quantum computing. To quote an article from the journal Science, A register of say 1500 qubits, if it could be placed in superposition, could access more states than there are particles in the universe. (Peter Knight, Science 2000 January 21; 287: 441-442)

    I'll grant, however, that the number quoted is misleading, and hundred-qubit machines will probably be needed to factor extremely large numbers: In order to do quantum error correction (i.e., making sure the bath of states doesn't lose coherence through interactions with the outside world), then each logical qubit would need to be encoded into 5 physical qubits (minimum). In essence, if Moore's Law holds, then you will have to wait another 3 years or so for such a machine.

  • An advantage quantum computers have over their classical counterparts is that a qubit can be in a superposition between states |1> and |0>. In principle, each qubit can be in an infinity of possible states in between the "pure" |1> and |0> states. Like any quantum mechanical wavefunctions, these qubit states can be made to interfere with each other, which is one of the features of quantum computers that is expoited in quantum algorithms. (Interference is not strictly necessary in a quantum computer calculation, but it is a useful feature of qubits that has no classical counterpart, and it illustrates some of the power of quantum computation). By cleverly packing data into wavefunctions and then interfering wavefunctions with themselves, a quantum computer can perform calculations that would be prohibitive otherwise. As an example, by taking advantage of the quantum mechanical properties of qubits Grover's algorithm allows an unordered database to be searched in O[sqrt(N)] time rather than the O[N] time required by a classical computer.
  • Hard to see that working for Disney offers much opportunity to change the world.

    Well, for what it's worth Alan Kay and the rest of the Smalltalk designers are there, too, and they've always been trying to change the world. Disney seems to be collecting brilliant people and letting them play on Disney's buck, without too much concern for whether they do anything useful. AFAIK, none of them do any real work for the company. (Hillis is what, 'Head Imagineer'? Sounds important ;-)

    Rather, it appears to be the move of a man who found that his doctoral work was not wanted by the market.

    Geeze, you made him sound kinda pathetic.

  • I had the 'real' Q-Bert for my C-64... didn't have a Spectrum 48, tho...
  • I still wish they had never called it a 'law'... though that certainly is more catchy than "Moore's Trend" or "Moore's Guestimate on Human Advancement in Semiconductors"... If it were a law, we wouldn't need the companies to work on things for us, Nature would drop fast new processors on us every 18 months. Kinda like that skittles commercial.....
  • no it means each register can have n states.
    where n is how many quantum states you can distinguish. so this one bit could store 5000 bits of information simultaniusly. one ion of hardware for 16megs of data - yup.
  • go talk to bill joy.

    the future is scary.

    there is no guarantee of parity between encryption being easy and decription being hard. there is no guarantee of me not being hit by a bus tomorrow.
    there is no guarantee of an asteroid not hitting the earth tomorrow. etc..

    worry. sound the alarm. perhaps develop another scheme for security - like a courier. don't panic. it won't solve any problems
  • could find the largest prime number

    Sigh. There is no largest prime number.

    Apart from that, I'm imagining your hyper-computer, and I'm seeing something a lot dumber than a centipede.

  • Yeah - booting and not booting simultaneously is a bitch.
  • I'm working on a port right now. I have some problems with the booting sequence..
  • The halting problem is impossible. It doesn't matter how much computing power you throw at it.

    This is totally different from things like factorization, which are merely impractical because they take so darn long. It's these kinds of problems that QC may help solve.
    --
    Patrick Doyle
  • No, only ADB, ISA and Hercules monochrome graphics at the moment. It plays a mean game of chess though.

  • No, that was Q-Bert.

    Maybe there isn't much difference though, at least to the average person, except that Q-Bert is more fun (unless you are a cryptographer).

  • I understand the idea of using quantum computers to simulate a NFA, and such. But what I don't understand is, how? I mean, how do we encourage the quantum computer to resolve to a solution state?

    Does anybody have a link to a good introductory article on quantum computing?

    --
    Fourth law of programming: Anything that can go wrong wi

  • There should be no real concern about encryption, except in regard to existing encrypted messages. Quantum computing reduces the number of operations necessary to brute-force crack a public key encrypted message to the square root of the number of operations necessary to brute-force on a standard computer. Doubling the number of bits in the key of a public key encryption squares the number of operations necessary to brute-force crack an encrypted message.

    The upshot of this is that even if we get production quality quantum computers, just double the length of your encryption key and you have as much protection as you had before.
  • I haven't seen anyone mention this explicitly...

    If I understand the idea behind qubits, then it should be possible to build a computer that can implement a nondeterministic finite automata. An NFA would permit the solution of a class of problems that are considered NP complete -- they can only be solved in exponential time (prime number factorization being only one application of this). This quantum computer would then be able to solve NP-Complete problems in polynomial time.

    Some examples of these types of problems are planning and routing, Operations Research generally, and general search.

    Many techniques explored in AI have that NP-completeness characteristic, which AI researchers try hard to control/avoid. Could quantum computing be more important for AI/MI than for anything else? (Once we have enough bits to work with, that is...)

    Hmmm......
  • No, 30 q-bits might be useful. You do not need to store any instructions in the memory, just the numbers you need to keep in a super position, as the instructions are imposed on the computer from the MRI machine, i.e. we would use it like a reprogramable circut, not like a universal turing machine.

    If the computer is really good and you do not need any error correction then you could factor a 16 digit number very fast, but more likely you would need serious error correction (might leave you with 4 q-bits if you were lucky; quantum error corrections was pretty expencive as I recall).
  • Actually I read an article a while ago that implied there was a very high probability that the molecular ion channels in the axons can have quantum resonances. Proving that any such resonance has an effect on the neruo transmitters would be a huge breakthrough. Who knows, perhaps our brains are already quantum computers.
  • So the Traveling Salesman is dead?
  • I found Q-Bert on PC once and was immensely disappointed. I later found its speccy clone and my disappointment continuted.

    It is a poor ripoff of the original Speccy game "PI-BALLED". I played this for months on end. Probably the highlight was that I called the frog guy "IRS", but later found out his name was "JAS" and they just used such a pissy small font that it was impossible to tell the difference.

    I don't have pi-balled on my spec em tho :(

  • 30 qubits would not be nearly enough to factor a large number (whether prime or not ;-). Quantum computers store their entire state in the quantum register. This includes not merely data that is currently being operated on (as with traditional computer registers), but also all other state information. The current "instruction" or step is coded in the quantum register, as are all "variables" (including ones that no longer need use; quantum theory prevents us from doing nifty things like "let a = b", which actually makes it harder to reuse register space).

    It's more meaningful, therefore, to think of the number of qubits in a quantum computer as its memory size, not its addressing capacity. A 30-qubit quantum computer isn't nearly analagous to a 32-bit von Neumann machine; it's much closer to one with 4 *bytes* of RAM!

    In reality, it's been estimated that before we can factor reasonably large numbers, we'll need quantum machines possessing hundreds of bits. Quantum programmers of tomorrow will get their kick out of squeezing as much as possible out of their half-kilobyte of register space.

    Random observation: we're seeing e-everything nowadays. Tomorrow will we start seeing q-everything?

  • I thought it was five for birds...
  • For a small fee, I will gladly factor any large prime number you give me, assuming of course that you can assure me that it truly is prime.
    ----------------------------
  • Quantum effects are the very phenomenon that stand the greatest chance of STOPPING Moore's Law in its tracks - and yet it is these same effects quantum computers use to do their work. Which means two things: eventually conventional computing must hit a quantum wall, and on the other side of that wall, quantum computing takes over.

    That said, I still have some doubts about quantum technology - it sounds to me too much like nondeterminism, and I can't help but wonder where you're going to find people who understand it well enough to develop the technology without doing it "by cookbook" as many COBOL programmers do today. But the technology is there, it seems to work, so what the hey.
  • There are a lot of problems where it is much easier to verify an answer than it is to figure out what the answer should be. For instance if I ask you to factor 221, you may have some trouble. If I tell you that 13 is a factor of 221, it is easy for you to test that.

    Well the basic idea of quantum computing applied to factoring would be to set up an experiment that is like trying to divide 221 by every possible number at once. But the trick is that instead of coming back with "yes/no" you would try to cause the no answers to cancel themselves out, so that what an experimenter would see would almost certainly be something that came back with a yes.

    Of course this is easier said than done...

    Cheers,
    Ben
  • If quantum computers are available to the code-breakers, that means that they are also available to the code-makers

    Yes but it's not very egalitarian anymore, is it? The people you're hiding your message from can afford the quantum computers, but not those just wanting to send encrypted email.
  • The only problem i have with the second sentance is moore's law - current technology will have doubled in speed twice and be well on it's way to doubling again by the time he triples it, so, why bother if you're just gonna be playing catch up?

  • The Russians/Soviets have been using one time pads for low volume (text) traffic for over 60 years. The one time pad can't be cracked by a quantum computer (or conventional computer) if properly generated. It's a pain to use but it is provably secure.
  • Read up some... The only thing that Quantum Computing has that relates to Quantum Encryption is the fact that they both have Quantum in their name. They're two completely separate technologies... Quantum computing theoretically could render most of todays cryptography useless, but it won't enable Quantum Encryption...
  • Second sentence:
    if the trend of increasing performance continues, a quantum computer that triples today's fastest computers could be built in five years, according to physicist Raymond Laflamme

    Last sentence:
    "On my optimistic days I think we will have quantum computers in 20, 30, 40 years maybe," he said. "On my pessimistic days, I think quantum computing is crazy."

    Still, it's cool. Personally, I think that ten years is the most likely timeframe, but that the uneducated guess of an uninformed amateur.
  • Looks like somebody's been reading too much Bill Gates... :)
  • The Wired article talks about using a spectromotor is this just a dumb typo for spectrometer and if not what is a spectromotor?
  • You can try this link http://www.imsa.edu/~matth/cs299/ [imsa.edu]. This is introductory stuff - which equates to 'nearly incomprehensible' for us normal humans. I think I've made it through 3 sections.
  • Can anybody provide a link to an intermediate level description of what exactly a quantum computer does? I'm unclear about how they use this mysterious tube of liquid, and large magnets to perform the three basic steps of computing (input, proccessing, output). I'm interrested in how they feed information into the system, how they perform operations (either simple [i would say atomic, but that has a double meaning] operations like addition, division, etc..., or whatever the fundimental operations that they _can_ perform are...), and how they read/verify the results.
  • The path of advancement in computer hardware has been so simple that it can be stated in one sentence -- Add more of the same.

    Even the most advanced silicon coming out of Intel, et al., are nothing but very advanced adders. Once you have the basic adder, the rest is a problem in manufacturing and packaging (how can we make it smaller, and then how do we keep it cool, supply power, etc)

    I predict (with all the authority I can muster) that quantum computers will follow the same path, only faster (since we've already solved many of the problems before). Once the scientist are able to manipulate a few bits, it will be a very fast progression to manipulating a lot of bits. It's just a matter of doing the same. Of course, they have to move out of the realm of "moving pins with bulldozers" first 8*)

  • If Mr. Hillis is the genius you say he is, then perhaps he has a better idea of what might be important in the future than you or I.

    Possibly true, but his day job is at Disney. Hard to see that working for Disney offers much opportunity to change the world. Rather, it appears to be the move of a man who found that his doctoral work was not wanted by the market. The "Long Now Foundation" [longnow.org] and it's big clock is an interesting experiment in pyramid building, but the learn a little about the history of the pyramids to see just how pointless it is trying to build anything less rugged than a huge stone pile.

  • as i (poorly) understand it a quantum bit can store far more data than a regular bit. if we ever start building gates based on quantum physics we should be able to send many signals through the same gate, at the same time, without interfering with each other. ie. a full adder should be able to execute 1, or 2^16 add operations at the same time. the ultimate in parallel processing.

    a full blown pentium, could run linux, windows, be, and bsd simultaniusly with no sharing. each operating system executing on it's own quantum level, with access to the full functionality of the machine.

    a looong way of, but very very cool.
  • Sorry, but this comment is completely wrong: quantum cryptography and quantum computing are two entirely separate areas. Quantum computing is a (possible) method of attacking conventional encryption (see Peter Shor's papers [att.com] and biography for lots of info).

    Quantum cryptography is (assuming quantum theory is correct) an unbreakable cryptosystem. A basic primer of Q Cypto is here [qubit.org]. This also gives details of how to implement Q. Crypto - test of quantum encrypted links of over 1km have already been demonstated: a far cry from "you can't develop [it] until you solve some general problems".

    We need an "I am not a scientist" label (like IANAL) for posts like that one.

  • Some people have tried to argue that the human brain is strictly more powerful than Turing machines...

    FWIW, the arguments I've seen along these line have been pretty bogus. Unless quantum effects play a significant role in the operation of neurons, you could simulate a brain to the necessary exactitude with a TM. (Even if QM plays a role, it most likely randomizes certain interactions and you'd just need a TM with a /dev/random hooked up to, say, diode noise.) Douglas Hofstadter takes this to an interesting conclusion in "A Conversation With Einstein's Brain", which can be found in The Mind's I [2think.org] (highly recommended reading). (I think "A Conversation..." was originally in Godel, Escher, Bach, but I haven't gotten through that yet - maybe I'll make it my summer project.)

    Is there any light on this issue with quantum computers? Is it "strictly more powerful" than Turing machine, or is it just a faster and smaller (no matter how faster and smaller) version of what we already have now?

    I would think that the theoretical version of a quantum computer would be a Turing machine with nondeterminism, which doesn't buy you anything over a vanilla TM in terms of computability.

  • If someone had managed to figure out how to perform a database queries efficiently with this type of massively parallel machine, they would have sold like very expensive hotcakes, Thinking Machines Corp would still be around, and Danny Hillis wouldn't be wasting his time dicking around with a huge dumb clock.

    Hmmm....database queries are among the easiest sorts of algorithms to parallelize. In fact, I had the pleasure of working on a parallel database supercomputer built by NCR in the early nineties. If you've got 256 nodes, for example, you can come pretty close to finding a key 256 times as fast as on a single node. (There is a lot of overhead, of course, but it was per node, note per record.)

    This was a pretty cool machine, built entirely out of 486 and pentium boards with standard hard drives, all running ATT Unix. Cool stuff. Not quite "massively parallel", though, in that I think it only went up to something like 128 or 256 nodes.

    It was really cool to work on. It was fun being able to create a 100 gigibyte table. (Though it is getting less and less cool. Bear in mind that at the time I only had a 100 mb drive on my PC.)

  • of course that you can assure me that it truly is prime

    Isn't there an algorithm that you can run on large numbers to determine with pretty good probability whether a supposed prime number is actually prime?

    --

  • QC will [probably] not solve all problems in NP-C

    Huh? I thought if you "solved" one problem in NP-Complete, you automatically solved them all.

    ("Solving" meaning creating an algorithm that runs in polynomial time instead of exponential time)

    --

  • A quantum bit (qubit) can still only store one piece of information... a bit. A regular bit can either be 1 or 0.
    The thing about a qubit is that it is both 1 and 0, simultaneously. This is called superposition of states-- the qubit exists in all possible states at the same time. If you have a system of 4 qubits, with each bit having 2 superimposed states, then you get 16 possible states at the same time.
    It gets a bit more complicated with quantum logic gates though... but here's one possible application: decryption.
    Today, you have to brute force a key, one at a time, until you find a winner.
    Theoretically, a quantum computer could test ALL POSSIBLE KEYS in one fell swoop, and blammo, the correct one pops right out.
    I'm simplifying this to a sickening excess, but you get the point.

    I believe the first real application of quantum logic gates will be in the upcoming Bit Boys' Glaze3D video chip, which is due to be released 6 months from any given date. (/sarcasm)
  • You can always search for "quantum computing" in a search engine, but here ya go.

    Quantum Computing - Lov Grover [cryptome.org]

    If you want a good book on quantum mechanics but you're not a real physicist, try The Dancing Wu-Li Masters, by somebody whose name I forget. Search for it on Amazon, read the reviews, and then (of course) buy it elsewhere.
  • Yeah, does it mean you'll get an answer like "The answer might be 3.476 or it might be 3.475?"
    ---
  • Implementing a quantum computer would provide an exponential increase in speed for certain algorithms (e.g. factoring large numbers). Now I'm usually not much for conspiracy theories. But right now, we are seeing fledgling attempts in the mainstream scientific community to build these computers.

    Now step back and think about who has the most to gain from them. Furthermore, the NSA has generally led civilian scientists by a couple decades in cryptography work.

    It makes me wonder how far along they are with this type of computer.

    Best regards,

    SEAL

  • Bah.... thanks for the ludite argument.

    These things wont be available to "anyone" for
    quite a long time. Noone except HUGE corperations
    and governments will be building them within the
    next 10 years or even more. Plenty of time.

    Research is important. Science for the sake of
    science I say. Human society will adapt. Maybe
    a few eggs will have to break in the process...
    but in the end we get a good omlet.

    Like any good tool, such things can be used for
    either good or evil. I think we should continue
    as we always have with technology...keep going
    forward and seal with the social raminifcations
    as we go.

    No system is so sacred and important that it
    shouldn't be torn down and rebuilt from scratch.
  • <i>"The path of advancement in computer hardware has been so simple that it can be stated in one sentence -- Add more of the same."</i>

    Absolutely. Problem is, what other options do we have? I mean, I'd like to see something <b>fundamentally</b> different, but with a binary system I'm not sure if it's possible. After all, everything binary can be broken down to NAND gates (if I remember my logic functions)

    On the other hand, this idea of "add more of the same" makes development stunningly easy. (compared to other fields)

  • Actually, brute-force decryption that scales linearly, rather than exponentially, is exactly what quantum computers promise to do that conventional computers can't.

    Many other posters have provided better links and explanations than I could.
  • That's generally true, baring details about semantics and Karp reductions, but nobody has ever shown that factoring or the RSA problem is in NP-Complete! If somebody could demonstrate this, it would be quite a breakthrough in our understanding of the computational complexity of this problem and others related to the RSAP, like the DLP.
  • Actually, QC will make factoring large composites much easier than by a mere square root. Decomposition of large composites into primes can be done in NP-time; a QC will enable us to factor these composites in strictly polynomial time, whereas the best current factoring algorithms (NFS for general numbers, ECM for many medium sized factors) take subexponential time. The square root reduction applies to *conventional* symmetric encryption algorithms in the case of a brute force attack.
  • Knapsack PKC=based on knowing which subset of values in a given set will sum exactly to a certain fixed value (the size of the knapsack)

    L^3 algorithm=Lenstra-Lenstra-Lovasz Lattice reduction algorithm; guaranteed to find a basis for a lattice with elements of length not more than a certain [theoretically exponential, but in practice only superpolynomial] length longer than the shortest basis for such a lattice. Used for reducing the lattice formed when inverting many knapsack PKC into a more easily handled size.
  • Check out these sites for more info on quantum computing

    Qubit.org [qubit.org]

    Quantum computing and information at IBM [ibm.com]

  • If quantum computers are available to the code-breakers, that means that they are also available to the code-makers. From an application-level standpoint, there's nothing to distinguish a quantum computer from an electronic one except for speed -- the quantum computer would be able to execute the same tasks several orders of magnitude faster. While key lengths of 128 (2^7) bits are secure today, in a world with quantum computers you would need key lengths of (for example) 16K bits (2^14) to get an equivilent level of security. It's not practical to use 16Kbit encryption TODAY, because it would take too long to encrypt somthing to that level; however, with a quantum computer kilobit-length encryption keys become as feasable as 128 bit keys are today. IIRC, encryption speed scales linearly with key length while (brute force) decryption speed scales exponentially; this means that it will always be far more difficult to break a given key length than it is to encrypt that same key. Advances in technology help both sides of the equasion.
    "The axiom 'An honest man has nothing to fear from the police'
  • IANAQP, however while Quantum Computing will render existing prime number based cryptography useless, mastery in the Quantum realm will also enable completely secure communications based on the existance of the Uncertainty Principle.

    See www.qubit.org [qubit.org] for some interesting introductory articles.

  • There are some problems with this. (Score:3)

    by Anonymous Coward on Friday March 24, 2000 @07:30AM (#1175932)
    This is very interesting - yet another new scientific frontier to explore. Yet, as always, we must be cautious here - new frontiers bring new dangers. And the danger here is very readily apparent.

    Right now, the world depends on good, strong cryptography. It's how banks, militaries, stock exchanges, and governments communicate securely and reliably. If the cryptography safeguarding these communications were to disappear overnight, what would we have? Global anarchy, as anyone could draw whatever funds they wanted from banks, military units could be given bogus orders, and any communication not done in person would be impossible to authenticate. Not a pretty situation, right?

    Yet this is exactly the set of circumstances that the quantum computer would bring upon us! It's well known that these computers are much faster at factoring large numbers (the basis of all modern cryptography) than conventional computers, and would render our current encryption schemes absolutely worthless. I don't believe that this is something we can allow to happen, at least not until we've taken the time - most likely several decades - to reform our society to the point where we can accept this. Research into this area must be halted immediately.

    And if you disagree with me, just think about the alternative.

  • Open Source Quantum Computing (Score:3)

    by Ignatius ( 6850 ) on Friday March 24, 2000 @09:10AM (#1175933)
    As part of my master thesis, I've developed a programming language [tuwien.ac.at] for quantum computers. While the interpreter is still somewhat experimental, it works under Linux and the best part of it: it's Open Source (GPL). So if you want to play around with quantum algorithms and can't afford the real hardware, you might want to give it a try.

  • Re:Encryption (Score:3)

    by BeBoxer ( 14448 ) on Friday March 24, 2000 @08:03AM (#1175934)
    Let me start with the disclaimer that I am not an expert in either quantum mechanics or number theory. That said, there is a fundamental difference between public and private key crypto. Public key is all based upon various problems which are considered to be "trapdoor" problems. This means that they are easy to compute in one direction, and "hard" to compute in the other. The classic one (which RSA is based upon) is factoring. It is easy to multiply two prime numbers together. It is "hard" to factor the resulting number to get the original primes back. I put "hard" into quotes because no one has ever proven that these problems are actually hard. It's just that no one has ever figured out an efficient algorithm for solving them, at least not with classical computers. The quantum computers, it appears, will be able to brute force these problems by just trying all possible answers at once. This works for factoring because one answer is provably right, and the others are provably wrong.

    On the other hand, private key does not suffer from this problem. The reason being that you can't prove which answer is the correct one. In the most extreme form, we have the one time pad. This is a provably secure encryption method, the reason being that given a ciphertext of a certain size, there exists a key which will decrypt that ciphertext into any possible plaintext of the same size with equal probablility. So, even if you did try every possible key, the results would be every possible plaintext with no way to tell which one is correct. Even the practical private key systems that we use (DES, Blowfish, IDEA), a successful cryptanalysis relies upon there being patterns or detectable traits in the plaintext so that we can distinguish the "junk" produced by bad keys from the correct answer. This is very different from the public-key case where you can mathematically prove that you have the correct answer.

  • Will we be able to program in this way? (Score:3)

    by K8Fan ( 37875 ) on Friday March 24, 2000 @08:09AM (#1175935) Journal

    Reading about this, I can't help thinking about the brilliant and doomed Connection Machine. It was a hypercube of ~65000 processors engineered by Danny Hillis, a genius engineer in the same class as Cray.

    But they never sold well enough, not because of the cost, but because there were few programmers who could imagine how to break a problem down so it could be run efficiently on all these processors. Other than real-time ray-tracing and weather simulations (astonishing particle systems) people couldn't figure it out.

    If someone had managed to figure out how to perform a database queries efficiently with this type of massively parallel machine, they would have sold like very expensive hotcakes, Thinking Machines Corp would still be around, and Danny Hillis wouldn't be wasting his time dicking around with a huge dumb clock.

    Given that we didn't know what to do with a machine that could deliver ~65,000 answers at once, what do we expect to do with one that can deliver all possible answers at once?

  • Yes, and so much more! (Score:3)

    by CausticPuppy ( 82139 ) on Friday March 24, 2000 @08:52AM (#1175936)
    It runs all possible operating systems simultaneously.

  • Qubit.. (Score:3)

    by deefer ( 82630 ) on Friday March 24, 2000 @07:31AM (#1175937) Homepage
    Wasn't Qubit a 3D platform game with a cute jumping sprite about 15 years ago?
    And before anyone gets to it....
    I guess a Beowulf cluster of these things is/is not possible!!!

    Strong data typing is for those with weak minds.

  • Re:A bit more detail for the curious ... (Score:3)

    by yuriwho ( 103805 ) on Friday March 24, 2000 @02:54PM (#1175938)
    Actually trans-crotonic acid (with 4 carbon 13 isotopes) is the quantum computer. It has 7 magnetically nonequivalent nuclei that have spin -/+ 1/2 and interact strongly. When you selectively flip the spin of one nucleus, it affects the neighbouring nuclei through coupling.

    CH3-CH=CH-CO2H

    the three H's in the CH3 are equivalent and are considered collectively as a bit. the two H's on the double bond are two more bits and all of the carbons are bits.

    I think the max limit of 15 relates to the fact that coupling typically only works across 4 bonds max and thus nobody has yet been able to think of a molecule with more than 15 magnetically distinct atoms that are all within 4 bonds of each other. Its a neat puzzle to try and think of one of these, symmetry keeps fusking things up making atoms magnetically equivalent.
  • Check out QED, a transcript of lectures by Feynmann on quantum electrodynamics. Particles evidently don't exactly travel in straight lines; in a way, they go every which way at once, and the path we see them take is the one of least resistance, the most likely path. If you remember your automata theory, they're reminiscent of nondeterministic machines, which can also be thought of as trying every possibility at once. If we have real live quantum computers, then, whether P=NP becomes a question of much less practical importance, because we'd all have NP capable hardware. Hence the concern in other messages on this thread about encryption, since public key cryptosystems count on NP complete problems being extremely tedious to solve.

    (This is a lot of handwaving on my part, and corrections are welcomed!)

  • Re:There are some problems with this. (Score:3)

    by john_many_jars ( 157772 ) on Friday March 24, 2000 @08:08AM (#1175940) Homepage
    It is my understanding of quantum computers that they harness the wave equations of the subatomic particles to solve problems. Using the Heisenberg (sp?) uncertainty principle to do work.

    And you are right that factoring numbers and the Chinese Remainder Theorem is used in todays top notch crypto schemes. However, this is relatively new since the standard for encryption relies mainly on standard fsa's not to gerenrate large prime numbers but to obscure bit patterns. That's how D(igital) E(ncryption) S(tandard) works. Admittedly it is not the best, but it is still more difficult to solve than Caesar.

    All that it would take to solve this problem would be to come up with an encryption technology that relies on the fact that the solution of a very difficult math/CS problem be solved (ie P?=NP) to break the encryption. If this is accomplished, then we move on to the next hard problem like determination of Godel numbers for Number Theory. The numbers exist, just almost impossible to find. It is just a matter of finding the trap door to these problems. The Chinese Remainder Theorem is the key to the trap door in strong crypto, today. (Note: I never said this was easy, but at no point is it impossible)

    All encryption needs to do is apply a very difficult problem to maintain efficency. And according to Godel, these problems will always exist.

    In other words, 1) [I believe anyway] quantum computer are not programmed, but involve a very difficult process of determining a wave equation that describes the problem or solution to a problem and the corresponding work to set up that wave equation in reality, 2) encryption is not just the application of solving the chinese remainder theorem, but merely the application of a known difficult problem that must be solved to encrypt the data (I can think of quite a few problems that are solveable but are extremely difficult), 3) maybe even quantum computers will finally enable perfect one-time pads to exist giving perfect encryption.

    At no point did anyone say solving problems does not raise new ones. As a matter of fact, quite the opposite is true. For every rule there are x exceptions, x>=1. Even that rule has exceptions. Have to be exceptions if the rules describe anything interesting.

    Also, remember necessity is the mother of invention. As long as hard problems exist (and they are guaranteed to exist-- you can always find Godel numbers, each one progressively more difficult to write down, let alone determine), encryption will advance.

  • Moore's law of quantum computing. (Score:4)

    by Claudius ( 32768 ) on Friday March 24, 2000 @07:42AM (#1175941)
    You can read some more information about the work of the Los Alamos scientists at http://www.lanl.gov/w orldview/news/releases/archive/00-041.html [lanl.gov]. Curiously, Moore's Law seems to hold for quantum computers as well, since it was nearly 18 months since the same researchers intoduced the first 3 qubit quantum computer (using nuclear magnetic resonance and a trichloroethylene molecule). To quote the article: Of course, if Moore's Law is at work here," Laflamme added, "then we could have a 30-qubit quantum computer in less than five years." A 30 qubit machine could perform certain tasks (such as Shor's algorithm or a variant for factoring large primes) many times faster than even the most powerful present-day supercomputers.

  • Re:Multiple States? (Score:4)

    by ptbrown ( 79745 ) on Friday March 24, 2000 @08:03AM (#1175942)
    schroedinger:~$ cat >box
    bash: cat: command not found
    schroedinger:~$ whereis cat
    cat: /bin/cat /usr/man/man1/cat.1.gz
    schroedinger:~$ echo $PATH
    /usr/local/bin:/usr/bin:/bin:/usr/bin/X11:/usr/g ames
    schroedinger:~$ cat >box
    bash: cat: command not found
    schroedinger:~$ ls
    GNUstep News
    Mail box
    schroedinger:~$ cat >box
    bash: cat: command not found
    schroedinger:~$ whereis cat
    cat: /bin/cat /usr/man/man1/cat.1.gz
    schroedinger:~$ AAAARRRRRRRRGGGGHHHH!!!!!!
  • The following is a short summary of the effect that quantum computing will have on cryptography by type of cryptographic primitive, as is currently accepted by a consensus of cryptographers:
    public key cryptosystems based on factoring or extracting discrete logs over a prime field- practical quantum computing will make these systems essentially useless, since the sender of the messages will have no inherent computational advantage over the attacker

    public key cryptosystems based on discrete logs over eliptic curve- not much research has been done in this area, but it is not immediately apparent that quantum computing will nesessarily create a trivial break of this problem

    public key cryptosystems based on knapsack problem- pretty much obselete already thanks to the L^3 lattice reduction algorithm; not much to worry about

    public key cryptosystems based on calculations in a truncated polynomial ring modulo different small primes (ie. NTRU)- probably not much to worry about, as there is no apparent reduction from factoring to converting between different ring representations of a polynomial (the main attack is via the L^3 algorithm)

    symmetric algorithms- square root reduction in brute force time

    hash functions- theoretical square root reduction in time to find collisions; it isn't clear how to achieve this, though

    general NP problems - surprisingly, recent results show that quantum computers may not be able to solve general problems in the space NP-Hard. Search on xxx.lanl.gov for a preprints about the (surprising relative lackof) Hamiltonian nonlinearity properties in quantum wave functions.

  • Re:Can anyone paraphrase how it works? (Score:4)

    by balbuzaro ( 159796 ) on Friday March 24, 2000 @07:37AM (#1175944)
    Okay, I found this explanation (link at the end): Quantum Computers

    The memory of a classical computer is a string of 0s and 1s, and a classical computer can do calculations on only one set of numbers at once. The memory of a quantum computer is a quantum state which can be in a superposition of many different numbers at once. A classical computer is made up of bits, and a quantum computer is made up of quantum bits, or qubits. A quantum computer can do an arbitrary reversible classical computation on all the numbers simultaneously, and also has some ability to produce interference, constructive or destructive, between various different numbers. By doing a computation on many different numbers at once, then interfering the results to get a single answer, a quantum computer has the potential to be much more powerful than a classical computer of the same size.

    The most famous example of the extra power of a quantum computer is Peter Shor's algorithm for factoring large numbers. Factoring is an important problem in cryptography; for instance, the security of RSA public key cryptography depends on factoring being a hard problem. Despite much research, no efficient classical factoring algorithm is known.

    Shor actually solved a related problem, the discrete log. Suppose we take a number x to the power r and reduce the answer modulo n (i.e., find the remainder r after dividing xr by n). This is straightforward to calculate. It is much more difficult to find the inverse - given x, n, and y, find r such that xr = y (mod n). For factoring, all we need to do is consider y=1 and find the smallest positive r such that xr = 1 (mod n). Shor's quantum algorithm to do this calculates xr for all r at once. Since xl+r = xl (mod n), this is a periodic function with period r. Then when we take the Fourier transform, we will get something that is peaked at multiples of 1/r. Luckily, there is an efficient quantum algorithm for the Fourier transform, so we can then find r.

    There are many proposals for how to build a quantum computer, with more being made all the time. The 0 and 1 of a qubit might be the ground and excited states of an atom in a linear ion trap; they might be polarizations of photons that interact in an optical cavity; they might even be the excess of one nuclear spin state over another in a liquid sample in an NMR machine. As long as there is a way to put the system in a quantum superposition and there is a way to interact multiple qubits, a system can potentially be used as a quantum computer. In order for a system to be a good choice, it is also important that we can do many operations before losing quantum coherence. It may not ultimately be possible to make a quantum computer that can do a useful calculation before decohering, but if we can get the error rate low enough, we can use a quantum error-correcting code to protect the data even when the individual qubits in the computer decohere.

    http://qso.lanl.gov/~gottesma/QComputers.html

  • A bit more detail for the curious ... (Score:5)

    by Somnus ( 46089 ) on Friday March 24, 2000 @08:05AM (#1175945)
    As a physics major, I have experience with NMR experiments in junior lab; and "spin flipping" is critical to my research group's experiment. So, I'll take a stab at explaining the experiment in greater detail for interested parties who don't appreciate Wired's liberal use of jargon ...

    A qubit, as the article says, is a quantum bit. All this means is that there is some quantum system/subsystem where some quality, like spin or energy, can be decomposed into precisely to two states. An ananology would Fourier's theorem: Broadly speaking, it says that you can decompose any "nice" function into an infinite sum of sines and cosines. The quantum world is cool because often, just two basis functions, up and down, are needed to completely (a pun, for you math people) describe a space in which that numerical quality resides.

    Such is the case here. The scientists, if I am not mistaken, are manipulating spin. Spin is a fundamental quantity in "classical" quantum mechanics; the spin quality of spin 1/2 particles, like electrons, can be wrestled out of special relativity (first finagled by Dirac); arbitrary spin falls out of special relativity + quantum field theory (if you know group theory, it's pretty simple :-).

    Now, I think this experiment uses spin 1/2 particles, i.e. particles whose total "intrinsic angular momentum" is equal to h/(4*pi), where h is Planck's constant. The cool thing about spin 1/2 particles is that their space is completely described by two components, up and down. This is because h/(2*pi) is the smallest angular momentum quantum you can have, so in order for the possible states to be "legal," the differences between any pair of them must be a multiple of h/(2*pi). But since spin 1/2 particles have a total spin of h/(4*pi), the only possible states are -h/(4*pi) and +h/(4*pi).

    So what's the deal with NMR? Well, NMR is nothing more than a method for manipulating/measuring spins/magnetic states using electromagnetic radiation. So, if the molecules in question are placed in a magnetic field, then there will be an energy difference between the up, down, and "mixed" states contingent on the alignment of spins w.r.t. to the direction of the magnetic field. This is as if it were possible for a compass to get stuck in the "south" position -- there's some potential energy caught up in there. In the quantum world, one can shoot a photon a system in the "north," or up, state and have it jump to "south," or down, or high-energy state. The simple requirements for the photon: It must have an energy equal to the difference in energy of the two states; and, it must carry the appropriate amount of angular momentum, important for more complex situations. So, these scientists have been able to manipulate bits by shooting radio waves at'em.

    So why are 7-qubit systems important? Because, in addition to the "external" or ambient magnetic field, each little particle that has a magnetic moment also generates a magnetic field. Having a "strongly interacting" multi-qubit system gives you a much more reliable bit, because when some flip due to a photon, the stragglers are more likely to flip as well. This will help avoid the dreaded mixed states that can screw with your data in untraceable ways. As noted by Wineland of NIST, this cute strategy has sharply diminishing returns past 15.

    The "trans-crotonic" acid is probably just some acid which is transparent to the NMR frequencies they're working at, and is nice all around for refractions, etc.

    There is a simple, but informative page [ucsd.edu] at UCSD that has pretty pictures showing what I've been blabbering about ...

    I hope I've been helpful w/o being condescending!


    *** Proven iconoclast, aspiring epicurean ***

Slashdot Top Deals

"All the people are so happy now, their heads are caving in. I'm glad they are a snowman with protective rubber skin" -- They Might Be Giants

Close