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

 


Forgot your password?
Close
typodupeerror
×
Science

Creeping Toward 10 Qbits: Atomic Computing 113

Posted by timothy from the one-for-each-toe dept.
RetroGeek points to this "New York Times article about a computer using atoms as switches. Give me twenty atoms and I'll break the RC5 contest." Going from 7 atoms to 10 is the order of the year, and if this keeps up maybe soon we'll need some slightly longer encryption keys, thanks.
This discussion has been archived. No new comments can be posted.

Creeping Toward 10: Atomic Computing More

Creeping Toward 10: Atomic Computing

Comments Filter:
  • Belongs to the #$%&%^# NY Times that requires an atomic (sic.) password to log in. Only if atom is used in the Greek fashion.
    I had too many atomic quantitities of C2H4Oh so do not blast me as a troll
    Later
  • How exactly do these quantum computers work? Are there wires involved? What about the processors? Are there transistors, etc... I am hopelessly uninformed, yet facinated.
  • virtual valery needs more AI , just imagine the possibilities ;)

  • After years of being behind, it looks like this might be the equalizer in the neverending battle between those who write and those who break crypto. Now all we need to know is how many atoms need to be manipulated so that users won't put their passphrase on a Post-It(TM) note and stick it to their computer screen.

  • Bill Gates is ahead of his time (Score:4)

    by selectspec ( 74651 ) on Monday March 26, 2001 @08:30PM (#338128)
    Not only does the incredible computational power of quantum computing render current encryption keys useless, but it also will provide enough computing power to run windows 2000.

  • Re:Best Atomic Encryption Prize (Score:3)

    by jeffsenter ( 95083 ) on Monday March 26, 2001 @08:35PM (#338129) Homepage
    Defeat NYTimes awesome password technology with...
    user slashdot2000
    pword slashdot2000
  • something i'm really looking forward to isn't the tiny tiny computers which will be possible with QC. it's the normal-sized computers which are, in actually, thousands of quantum processors working like mad in parallel. massively parallel systems making supercomputers possible in our toasters.

    i'm gettin wet. i should go.

  • The powerful field is emanating from the supercooled superconducting magnets inside a tanklike machine called a nuclear magnetic resonance spectrometer.

    Might wanna warn Gordon about the possibility of a resonance cascade. ;)


    The One,
    The Only,
    --The Kid

  • thougths (Score:4)

    by deran9ed ( 300694 ) on Monday March 26, 2001 @08:44PM (#338132) Homepage
    Give me twenty atoms and I'll break the RC5 contest."

    I'm sure the Czech crew [i.cz] who released the PGP advisory this week would love the same kind of computing. (more historical [antioffline.com] codebreaking)

    Seems entirely over my head (the level of computing obviously) but here would be some nice uses for this level of computing.

    An international powerhouse computer to track the DNA mapping databases in one powerful machine. This would help scientists, and their companies to focus solely on those matters as opposed to wondering whether current technology would support them to fullest extent. It may also be networked in order to help assist them in mapping, cataloging information, sorting, etc.


    Space Race... Scientists, astronomers, etc., could have a super computer assist them in fully mapping, catalogging the universe, its planets, stars, etc.
    I wonder how old I'll be before a computer like this is something like what a c64 is in nowadays. Just think scientists where developing this starting in 1994 (from what I saw on NYTimes), imagine when the level of computing in 20 years, or would it all come crashing down. Scary thought. Anyone care to reply with links to basic quantum computing information you care to share?

    Privacy Links [antioffline.com]
  • The chances of that happening are insignifi.... Hey, did you see that guy in the suit?
  • Yes, but will it provide enough power to factor large prime numbers...
  • According to this law, they will only have to get one more atom to dance every 18 months...

    Also, will the software industry be able to keep pace, writing bloated code to run on these things? :)

    -Scott
  • It's a joke, it's from the "Gates" book "The Road Ahead"
  • So if I've understood the article correctly (possibly not, since it's 6am and I've been up all night), your QBIT (quantum bit) can be in 1 of 3 states:

    1) up
    2) down
    3) dead kitten AND live kitten (superposition)

    Does this mean that we'll use a new, post-boolean algebra on trinary computers, or will we be running a binary system which gets internally compiled down into operations involving QBITS?

    Maybe the third state will be soaked up by the error correction mentioned in the article...

    I actually think it would be cooler to have a binary computer, but the third state really did represent an unknown and mysterious simultaneously true and false state...

    dim x as boolean
    x=MyComplexMethod("goat",45,"all your base")
    if x=true then
    print "Yes- true"
    else
    if x=false then
    print "No- false"
    else
    print "WTF is up with this?"
    endif
    endif
  • Well searching for my own links on Quantum computing, I came across... Quantum Teleportation. Seems like something out of a movie (its description) but judging by some of the dates on the findings scientists concluded (some dating back to Albert Einstein), would it be safe to say, quantum computing would only see the light of day in government labs?
    What is teleportation? A straightforward definition, inspired by science fiction series on TV would be `transportation from A to B without traversing the intermediate space'. Practically speaking, one should send the complete information of the object from A to B, where clever technicians rebuild the object. But by means of this definition, we already have lots of forms of teleportation. In a fax, a telephone and a television images and sounds are `converted into' information (electrical currents in a cable), sent and translated to comprehensive images and sounds again.


    Nothing prevents us from keeping the original image and perhaps `teleport' it to yet another receiver. But then we could have called it `copying' just as well. Intuitively, we want the original object to vanish in the process of real teleportation.

    Suppose Alice has an unknown superposition of horizontal and vertical polarization. She can of course send her photon directly to Bob by means of an optical fibre, but then there is the danger of altering the superposition in an unpredictable way due to interactions with the fibre. This effect is called decoherence, and causes severe difficulties when one wants to manipulate quantum states.

    Alice can teleport her quantum state to Bob. The information of her state (the exact superposition) must then be dissected into classical and quantum information. It works as follows: Alice and Bob both receive a part of an EPR-pair (one photon for Alice and one for Bob). This EPR-pair will become the transmitter of the quantum information. The classical information can be sent by cable or radio. The EPR-photons are correlated in the way described above: if Alice after a measurement finds her photon in vertical polarization, then Bob's photon is in horizontal polarization and vice versa. But Alice doesn't perform her measurement yet! It is very important that the correlation remains: `the line should be left open,' and a measurement destroys the correlation

    Quantum Teleportation [bangor.ac.uk]

  • here are some good introductory articles, and btw (Score:3)

    by phr1 ( 211689 ) on Monday March 26, 2001 @09:00PM (#338139)
    you need 64 qubits to break rc5-64.

    Introductory articles on quantum computation> [qubit.org]

  • read on... quantum crypto [mcgill.ca]
  • It is an interesting side effect indeed . . . however, the minute quantum forces become significant at this level so I think you reach a limit where "Adding one more atom" really is as difficult as 18 months of research and design, and then perhaps to the point where it is impossible.
    Hey, I've got an idea! Let's use gluon fields with the gluons as the transistors in thequantum computer - that way, when we need another gluon, we just increase the field size! Just another interesting quantum effect tidbit you really wouldn't care to know: by increasing the distance between two gluons, you can make more between them - which is why the strong force increases in strength with distance, to a point.
    Yet I digress.
    -Leo
  • that would require that I actually take my eyes off of /. to which I am hopelessly glued... =)
  • Yeah, and now we can watch Windows crash faster.

  • And with the power of a Quantum Computer, VB programs might actually be able to run with reasonable speed...
  • Anyone care to reply with links to basic quantum computing information you care to share?

    A great Scientific American article on the subject ("Quantum Computing with Molecules") can be found at http://www.sciam.com/1998/0698issue/0698gershenfel d.html [sciam.com].

  • High Hopes, Big Lasers... (Score:4)

    by Anonymous Coward on Monday March 26, 2001 @09:16PM (#338146)
    I don't mean to rain on anyone's parade. I really don't. Its just I think we may be getting a LITTLE ahead of ourselves, here. Contrary to a lot of posts on /., Quantum Computing is not so much a issue of EE as it is of good, old-fashioned AMO Physics - lasers (BIG lasers), nonlinear optics, RF Ion Traps and more lasers. This is not your granddad's transistor (which, even in its original form, probably could be safely operated at Johny and Susie's house in Peoria). From my experience as a research assistant in a quantum computing laboratory at a big academic institution, trapped-ion quantum computing is not the type of thing that'll be running your palm pilot 10, 30 or even 50 years down the road - the (absolutely crucial) electronics of the trap, alone, would make it insanely dangerous to have in your home, let alone your pocket (ions will still require the same EM containment fields 1,000 years down the road as they do now - its what makes 'em ions).

    And no one has EVER gotten an Ion-Trap quantum computer to do ANYTHING. Not add two numbers. Not factor a number. Not multiply two numbers. The potential is there - the qubits - its just no one has ever tapped it in a feasible way.

    I'm sure people said the same things about transistor based computer back in the day, but I really, really feel that the Ion Trapping method is not going to be the type of QC we'll see in practical use anytime down the road.
  • Each atom can be thought of as a little switch, a register that holds a 1 or a 0, and the latest Pentium chip contains 42 million such devices. But the paradoxical laws of quantum mechanics confer a powerful advantage: a single atom can do two calculations at once. Two atoms can do four, three atoms can do eight. By the time you reach 10, doubling and doubling and doubling along the way, you have an invisibly tiny computer that can carry out 1,024 (210) calculations at the same time.

    Just when we we getting worried about Moore's law failing, here comes someone getting ready to take the acceleration curve and golf it into warp drive.

    Damn!

  • The atom itself is not the qbit. The qbit is the quantum state of a 2P electron which makes transitions back and forth between a 1s state. The atom merely holds this electron (and only ONE such electron, per the exclusion principle.)
  • Ok, that's an overly inflammatory subject header. However, I once had a chat with a friend and we tried to work out what practical effect it would have on the world if you could solve NP problems reliably in polynomial time. I'm sure a lot of things would become slightly better, but neither of us could think of any revolutionary new applications that would become possible that weren't previously possible.

    Remember that a lot of the problems that are in NP can be approximated pretty well. If you were actually routing travelling salesmen around the US, you might not mind a solution that's off by a few percent (particularly when there are going to be a whole pile of other sources of error; your salesmen getting stuck in traffic jams or dallying with housewives, etc.).

    Can anyone offer some problem domains where quantum computing would offer more than an incremental improvement (discounting crypto, which seems to be a case of gain a little, lose a little)? I'm not claiming that such domains don't exist, btw. I'd be delighted if someone could point out a few.

  • AC First Posters suck

  • Here [sciam.com] is an article from Scientific American giving a good overview of the basics of quantum computing.

    It's a bit dated (from 1998) but the principles are the same.
  • It is belived, but not (as far as I know proven) that a QC is *NOT* a completely general NDFA (thus capable of solving NP in polynomial time). Thus the question is sort of moot in this context.

    Second, I believe an algorithm is known that can do lookups in unsorted, unindexed lists in O(log(n)) time. That is certainly an interesting proposition.

    Third, encryption *is* a big deal. You or I are not necessarily worried about someone developing a QC to read our email, but governments are.

    Finally, there are a number of protocols in quantum cryptography and quantum information that are not general purpose quantum computers, but might be very useful. Also, we don't really know what a quantum computer might be capable of, and won't until we have one built.

    Right now, the reason people are building bigger quantum computers is because they want to study them, not because their computing power (even for "easy" quantum problems like finding large prime factors) is going to be usable any time soon.
  • wouldn't be able to keep up with writing bloated code....unless they come up with a quantum computer to write the code for them....

  • This [howstuffworks.com] might answer a few questions for you.

    "The good thing about Alzheimer's is that you can hide your own Easter eggs."

  • practically every combinatorial optimization prob (Score:3)

    by phr1 ( 211689 ) on Monday March 26, 2001 @09:39PM (#338155)
    VLSI design, code optimization, resource allocation, you name it.

    For more info on P vs. NP, see the classic Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson.

    Note, by the way, that quantum computers are not generally thought able to solve NP-hard problems in P-time. They can solve in P-time a class of problems called QBP, which is believed to sit between P and NP in difficulty. Quantum computing suddenly got a lot of press when Peter Shor discovered that factoring is in QBP. However, factoring is probably not NP-hard.

  • As soon as you compare x to true or false, its value is known, so you will never get to the "WTF" part. Your third state isn't a logical state, it's just the state of the variable before it is examined.
  • There are many different types of quantum computing being developed by different scientists, but from what I understand, there are no wires. The processor and memory for the quantum computer is made up of a group of molecules. Each molecule is called a qubit. So a 10 qubit quantum computer is made of 10 molecules.

    Each bit is always a 1 or a 0. In a quantum computer they are represented by an elections spin, so if it is spinning clockwise it is a one, counter-clockwise is a zero. Because of all sorts of wierd arsed quantum stuff an electon can have multiple states, so it can represent a 1 and a 0 at once which is why in the article it says the quantum computer can perform multiple instructions at once. The electrons state is then manipulated using lasers, or radio waves.

    The main problem which this article is saying they are closer to solving is that the state of an electron is very unstable and can be easily corrupted by all sorts of things, another passing electron for example.

    I may be wrong about all of this, so if I am wrong please tell me, but this is how I think they are working.

  • Re:Can somebody explain this? (Score:2)

    by Anonymous Coward
    There was a lecturer at my university who was working on quantum computers, I forget his name though. Here's what I understood of what he said: Quantum computers amke use of some of the peculiar quantum mechanical effects which occur is certain types of systems, like cold trapped atoms. One of these properties is superposition, whereby the spin of an atom in a quantum computer is not really up or down(1 or 0) but a superposition of both states at once, and it only has a probability of being in any one once one makes a measurement(at which point the wave equation collapses to a discrete value). A set of quantum bits(each an atom in this type of implementation, there are several kinds being pursued) can be an information storage vector. As long as one maintains the systems quantum coherence(whatever this means) one can have this set of qubits represent a real vector in a space with dimension equal to that of the number of qubits. ie an n bit array of qubits can represent a vector in an n dimentional vector space, not just 2^n discrete values, which n conventional bits can represent. When one makes there measurement, one gets values of one or zero for each value. The beauty is that until one makes their measurement, the system represents all possible values, so that one can perform their operations of a system which represents the vector to infinite precision(or as good as one maintains coherence), only reducing the answer to n bit precision when they make the final measurement. One interesting thing that the speaker said is that there aren't enough barionic particles(electron, protons, neutrons) in the known universe to construct a conventional computer which could simulate a 200 qubit quantum computer. Hope this has been helpful, and I hope I did not make too many glaring errors. empathogen
  • Wasn't it bruce sterling who talked about a kind of organic based computer?

    This will get really interesting when we have computing at a molecular level, but we can grow huge clusters of them like fruit or vines. Now that'll rock. Welcome to the next universe, baby!

    Is this my idea or has anyone read about this organic computer idea somewhere before?

    http://www.hyperpoem.net

  • This work is impressive, but NMR-based quantum computers have some special scaling problems. The net spin polarization of these liquids at room temperature is very small- about one part in a thousand roughly. This means that the quantum computation is done with only the slightest of distinction between 0 and 1. That can be handled for small computations, but the signal to noise problem becomes severe for larger systems.

    The current quantum error correction codes impose a large bit overhead (factor of three or so), which compounds the signal/noise difficulty of the NMR technique.

    The nice thing about this method is that the nuclei are well-isolated inside the electron clouds and decohere slowly. However, my guess is that NMR-based quantum computing will be first out of the gates, but will lag behind other implementations before reaching the finish line.

  • They were building structures measuring in the hundreds of cubits three thousand years ago.
    --
  • there is of course post-boolean logic: fuzzy logic [uni-linz.ac.at].
  • By the time you can buy it it will be just another component fitting in a socket.

  • What I gave was a *very* rough sketch of the mechanics behind it. I don't claim to be an expert on quantum information theory, nor on constructing ion traps. I can assure you however that the manipulation of the electron's quantum state involves much less "fumbling" than you described. These spin-spin manipulations are carried out with a finely tuned YAG laser which is optically doubled (a few times over) to the correct frequency for the desired transition (the laser is referenced to a rubidium cell, perhaps, as reference). I'm certainly not denying the potential of the types of QC's you mention - perhaps you might elaborate on the enhanced "computing power" you'd expect from nuclear-based quantum computers? As for evidence of the merits of these ion-trap QCs, I suggest articles by D. Wineland (NIST) and C. Monroe (Formerly of NIST, now at Univ. Michigan).
  • I agree with these comments: long-term applications of quantum computing are more likely to come from solid-state based devices, possibly using electron spin or nuclear spins of embedded impurity atoms as qubits. Optical atom traps (and NMR magnets) are very expensive and likely to remain so for quite a while. But in the end it's really too early to say, of course, since we're looking ahead a long way.
  • For N.M.R. (used in the article) it is not the spin of an electron but the spin of the nucleii, in this case the spin of a carbon 13 nucleus. The spin is induced by irradiating the sample in the magnet with a short narrow radio frequency pulse, for some atoms in some molecules it is possible to selectively change the spin state (up or down) without changing the spin states of the other atoms. The particular atom (or nuclei if you like) irradiated will not permanently hold that spin state, and if I remember correctly, the signal obtained during an N.M.R. experiment requires some form of decay of the spin state (better explanation someone?). I assume this decay could be partly responsible for the introduction of error into this particular form of quantum computing...
  • I'm not sure there would be a lot of practical consequences. "Polynomial time" does not mean "tractable". And you are right that approximations are pretty good. In fact, an exact solution would only be a one-time gain, dwarfed by many more down-to-earth improvements in efficiency and technology.

    In any case, whether quantum computing can solve NP-complete problems in polynomial time is an open question.

  • Second, I believe an algorithm is known that can do lookups in unsorted, unindexed lists in O(log(n)) time. That is certainly an interesting proposition.

    Grover's algorithm is O(n^0.5).

  • It's qubit, not qbit.
  • not to take the edge off the humour, or anything, but i run a w2k/rh7 dual boot, and with gnome 1.4 (including nautilus) on the linux side, the w2k system runs smoother, faster, and uses less memory.

    matt
  • 1. We might be soon approaching the point where we should need longer encryption keys due to the amount of computing power available to the researcher.
    2. We all know that the NSA is de facto "a little bit" ahead in this subject, due to their obfuscation of their existance and all the matter of cryptology during the 70s.
    3. The US government decided to "open up" to allow the use of "strong" encryption to the rest of the world.

    1+2+3=> I'm seriously thinking that the NSA itself could have gained enough computing power (quantum computing? does it look less impossible now?) at the time they started opening the key-size barrier.

    time will prove me wrong, hopefully.
  • Java runtime is also quite slow.
  • Of course this article is not about ion trap QC.

    It's about NMR based QC, using multiple 13C atoms in a molecule as multiple q-bits.
  • Don't forget, it was once said with great enthusiasm that one day computers might weigh under a ton!

    Seriously, there are two sides to the story, or in this case the research. Your side, with big fat equipment which hits the news every now and then when it breaks another barrier, and the side looking at how nature et al implements quantum computers. AFAIK, there is still ongoing investigation into whether and how every one of our cells utilises the quantum nature of particles in DNA manipulation - and if it is possible under the conditions in a human cell, it should certainly be possible in a home PC.

    Going back to your analogy of the transistor, I would disagree slightly. I would say that quantum computing is still in its 'valve' era or even before that. Noone has yet made the 'quantum transistor' that will help it take the leap from the theoretical and laboratories into first business and then the home.

    Of course, it may yet just not work ;-)


    Beg:

  • How long for all these 'developing technologies' to hit our shelves? And how long till transistor based systems start to run out of steam?

    Personally, I think the major advances will happen once companies such as Intel begin to hit fundemental barriers in creating silicone chips. Then we'll see some real money being thrown at optical and quantum computing, by companies who work by results rather than by scientific interest.

    This is kind of an informed guess, but:
    - 7 to 10 years: Silicone begins to run out of steam
    - 15 years: First useful optical computers
    - 20 to 25 years: Silicone is gone, optical is mainstream
    - 50 years: Quantum computers do something useful for the first time
    - 75 years: Quantum computers begin to be used by large companies
    - 100 years: Quantum computing is mainstream

    Hopefully, I'll be around to see all of the above!

    Anyone else care to reply with their own timescale?


    Beg:

  • Any former CS student from a decent school will probably have done some NP complete proofs. You remember these: you create an algorithm of order O(N^x) to transform from known NP complete problem (A) to NP open (B), proving that if A can be solved in polynomial time then B can to.

    If QC is achieved these transformation algorithms will have practical importance. Yet another thing I learnt in school that seemed useless at the time but maybe isn't :-)
  • NMR Quantum Computers have even more problems than the Ion Trap models -- including scalability to large numbers of qubits and (if my memory serves), a very short decoherence time.

  • The main problem here is that nobody has shown that any of the quantum computer algorithms solves an NP-Complete problem. True, we have NP problems, but we still don't know if NP-Complete is the same as NP.
  • 3) dead kitten AND live kitten (superposition) and superposition of dead and live dog

    The only reason you get superpositions is because you haven't measured the state yet, as when you have a kitten and a puppy (in separate sound proof boxes of course.)
    Without looking in the boxes you can't tell whether the kitten or the puppy are dead or alive.
    (obviously if you forgot to put holes in the box so they could breathe, they'd both be dead.)

    By opening the box the kitten decides whether it is alive or dead and the same with the puppy.

    Which asks the questions.

    Can you use animals for quantum computing, or are the costs of feeding them too high?
    and
    If a tree is in a wood, and no one is around, is it still standing or is it falling down or is it in a supositioned state, until someone goes to look at it?

    And of course then you have to ask if you don't know nothing about anything does anything exist?
  • Possibly so, but my intuition is that these should be easier to resolve. Scalability needs bigger molecules and more precise spectral control of the NMR setup, but this doesn't seem improbable. Decoherence could be partly resolved by quantum error correction, and partly, perhaps, by careful choice of solvent, temperature, sample size, etc.

    I admit that this is no more than gut feeling, though, I am neither a chemist nor a physicist.

  • heh, the problem being that by virtue of VB programs' tendancy to allocate memory extremely poorly, VB:QE (quantum edition) might inadvertantly be running out of control one day and by virtue Heisenberg (et al.) end up running on (and screwing up) every atom in the known universe. Maybe this is MS's secret plot for world domination by atomic subjugation[1]?

    [1] Bill. Boris. Natasha. Lordy, do I need sleep.


    --
    News for geeks in Austin: www.geekaustin.org [geekaustin.org]
  • or ignore it altogether, as many people keep posting, by replacing www with channel:
    http://channel.nytimes.com/2001/03/27/science/27 QU AN.html
  • You cretinous, cock-sucking, camel-kissing, crap-cuddling coward. Anyone with even a quarter a cerebral cortex could check the status bar of their browser and ken that this isn't a goatse.cx link. Fucking loser.
  • ... or only 63 bits to break it in 2 "clock cycles". or 62 bits to break it in 4 "clock cycles". etc etc etc.
  • I feel I must contest that this line, is in fact, funnier:

    Oh dear, I do appear to have been seriously wounded.

    C'mon, a crowbar? You're kidding, surely man! I scarcely touched you! But my, what a nasty cut.

  • Not relevant.

    Moore's Law is _not_ to do with computing power, but with gate size/density.

    e.g. here is the first thing a web search provided:

    http://www.webopedia.com/TERM/M/Moores_Law.html

    THL
    --
  • I'm speaking from 'gut feel' not knowledge here, but don't the Qbits need to be able to 'interact' with each other in order to solve the larger problem. If so you might need to be able to arrange 64^2 paths along which they could pairwise interact without interfering with their interaction with the other 62 Qbits? Even if they don't need pairwise interactions, but 'broadcast', you still need to get the 64 bits to be able to interact without interfering.

    I've got a nasty feeling I haven't got a clue what I'm asking... Ooops!

    THL
    --
  • from my understanding the superposition is both true and false (we partially) so your statements should be if x != true then print "false"... etc. or else
  • Has anyone found a way to crack that with quantum computers?

    Can anything be proven about the possibility of such a "quantum algorithm" existing if not?
  • THe dangerous electronics are a crucial part of the Quantum Copyright Rights Protection Management Scheme [posternow.com] now being developed by Microsoft, IBM, the RIAA and Sandia Labs.

    Surfing the net and other cliches...
  • AFAIK, there is still ongoing investigation into whether and how every one of our cells utilises the quantum nature of particles in DNA manipulation

    Wow, I never knew Roger Penrose was an expert in DNA as well as neurology.

    I've heard he's working on a theory that motor cars operate at the quantum level also.

  • Windows already uses quantum effects (Score:3)

    by wowbagger ( 69688 ) on Tuesday March 27, 2001 @04:27AM (#338193) Homepage Journal
    <Humor>
    Windows already uses quantum effects. Just looking at it will make it crash....
    </Humor>
  • Could you imagine a beowulf cluster of qubits in Natalie Portman's pants, running Linux?!
  • And no one has EVER gotten an Ion-Trap quantum computer to do ANYTHING. Not add two numbers. Not factor a number. Not multiply two numbers. The potential is there - the qubits - its just no one has ever tapped it in a feasible way.

    I'm confused; what sort of quantum system ran Shor's system or the basic quantum search algorithm?
  • Keys based on biometric security can be tens of thousands of bytes long, have nothing crackable about them and are entirely consistent. and much more secure.

    They'll also need 64-bit hardware. Goodbye 32-bits and that other unportable OS won't make it there will it?
  • this [cryptome.org] article was posted on slashdot before; that where I learned 'bout it. It's well written and covers the theory and a bit of the mechanics. Worth a read (and a re-read) if you're interested.
  • .... will be needed to write a CSS Decoder?

  • What about conventional computers that connect to small quantum computers to perform small but frequent tasks? Isn't this a little more realistic and concrete goal in the near future?

    Or are they completely incompatible?
  • This doesn't make sense. The thing with quantum computing is that any group of calculations are done in one step.
    ie. Finding a 2048 bit encryption key with a 2048 qubit quantum computer would take no more than ONE calculation.

    So, by adding more qubits, you're not 'doubling' the processing speed because a 2049 qubit quantum computer will still solve things as fase as a 2048 qubit computer .... in one calculation.
    The only difference is now the 2049 qubit quantum computer can solve a bigger problem.

  • Factoring "probably" not NP-hard? (Score:3)

    by BillyGoatThree ( 324006 ) on Tuesday March 27, 2001 @04:59AM (#338201)
    It ISN'T NP-hard. Remember that an NP-hard problem is one where, even if you had a proposed solution, you can't verify the answer in polynomial time. Verifying a factorization answer is easy: just multiply. That's polynomial time, therefore factoring isn't NP-hard.

    That's as opposed to Travelling Salesman where even if you have a proposed path, you'd have to check all possible paths to decide if yours was the minimum.
    --
  • The obvious mathematical breakthrough would be development of an easy way to factor large prime numbers.

    --Bill Gates, The Road Ahead, Viking Penguin (1995), p. 265.

  • maybe soon we'll need some slightly longer encryption keys, thanks.

    The uber-paranoid may want to revoke their old private keys and issue new ones anyhow... According to this report [cryptome.org] on cryptome.org [cryptome.org], a serious flaw was found in OpenPGP and its derivatives which leaves your private key vulnerable to attack.

  • Well, let's see:

    10 atoms this year
    20 atoms by early 2003
    40 atoms by late 2004...

    By the 22nd century, the entire universe will be a computer. Or is it already?

  • Rather than depend upon a single 2048 bit key I'd rather use my pocket atomic encryption computer. It's...no, that's some lint...that's a pebble, some sand, dried mud -- wait, that will work. A little water and I put it in this message encrypter to make a cup of really hot tea...
  • 7 qubits ought to be enough for everybody.

    --

  • EEEeeeewwww!!!
  • He's also an expert in artificial intelligence, apparently. Beware the aging mathematical physicist who strays outside his discipline!

  • "Nobody will ever need more than 640KB RAM." -- Bill Gates.

    Maybe he meant 'more than 640 atoms' or 'more than 640KB RSA'?

  • This sure does promising enough. Another alternative using an identical technology is coupling two SQUIDs - Superconducting QUantum Interference Devices. SQUIDs.

    These devices have excellent magnetic sensitivity. And when two of these thingies are coupled, you have your information travelling between one another through insulators at awesome speed (in these, even the superconducting electrons tunnel through).

    Incidentally, I'm also working on SQUIDs, although on a theoretical basis. Getting to make a SQUID is, well, a little tough... So we are trying to find guys who'd give us Liquid Helium for free ;-)

    Another interesting thing to do would be to quantumly couple 2 SQUIDs!!! And imagine building a Beowulf cluster of *those* !!! ;-)

    "...Fear the people who fear your computer"
  • Shor's algorithm has never run on anything; it's just a theoretical algorithm written for a theoretical quantum computer architecture.

    It's like when you write programs for PRAMs in your parallel algorithms class. The algorithms are fine and all, but PRAMs don't exist.

    --

  • It ISN'T NP-hard. Remember that an NP-hard problem is one where, even if you had a proposed solution, you can't verify the answer in polynomial time.

    Your definition of NP-hard is way off. A problem being NP-hard means that all problems in NP are reducible to that problem. In plain english, it means that a quick solution to an NP-hard problem would yield a quick solution to all problems in NP. A problem that is both NP-hard and in the set NP is called NP-complete.

    Satisfiability is NP-hard (as it is NP-complete), and it can be verified in polynomial time (just verify that the formula evaluates to true given the binding). In fact, any NP-complete problem can be verified in polynomial time as having this property is one way to define the set NP (languages with polynomial time verification proofs).

    Verifying a factorization answer is easy: just multiply. That's polynomial time, therefore factoring isn't NP-hard.

    Again, this is way off. Most problems in NP are known to be either NP-complete or in the set P. Factoring is one of the few that is not known to be in either category. I believe graph isomorphism is another. You can't just say factoring "isn't" NP-hard. It hasn't been proven that it is not. Researchers don't think it is, but until it is proven to be in P, this is just a hunch.

    That's as opposed to Travelling Salesman where even if you have a proposed path, you'd have to check all possible paths to decide if yours was the minimum.

    Here you are confusing problems and languages. Technically, when I mentioned 'problem' earlier, I should have said 'language'. Problems must be phrased as languages to apply complexity theory to them. When you frame Travelling Salesman as a language, it looks something like: "Does this graph have a salesman path of length less than x?" Languages must have yes/no answers, unlike the open-ended Travelling Salesman problem. Phrased as a language, even Travelling Salesman has polynomial time verification (as it should as it is NP-complete).

  • Why do you need EM containment fields for the ions? Why not just neutralize them? wave a big grounded conductor around in there and *poof*, no more ions.

    Ions are not magic, they're just electrically charged atoms. I've got four tubes of ions right over my head; I use them to light my office. Electric arc are visible because of the ionization of the air and the recombination of the ions with the free electrons. The Sun is a ball of ionized gas.

    Here at work we have desk-top ionizers to reduce the chance of ESD damage to electronic components. They emit a spray of charged particles that are good at slowly, safely dissapating static charges on nearby objects.

    Ions are not dangerous. Beta-particle radiation, which is of course merely helium nuclei, are +2 ions. They don't penetrate the human body past the first few layers of skin. A piece of paper is an adequate shield against beta radiation.

    Oh-- how many of you drink Gatoraid or other salt-containing drinks? In what form does one find NaCl dissolved in water? Here's a hint: NaCl contains an ionic bond between the atoms. In water, the sodium and the chlorine atoms disassociate and become free ions.

    I'm going to go now and drink my ion-laden sports drink ;)

  • Silicone computers? I've been inside plenty of boxes, but I've not yet seen any RTV or breast implants ;)

    Perhaps you meant Silicon, without the "e."

    Remember, there are other semiconductors other than Silicon. Gallium Arsenide (GaAs), for instance, is used extensively in MMIC (Microwave Monolithic Integrated Circut) chips, where Silicon would not perform as well.

  • Usually I'm enthralled when new technology comes along. Organic LEDs? Cool! New ways to squeeze transistors onto a chip? Great! Super-fast wireless networks? Hubba hubba!

    Yet. Quantum computers. There's one technology I hope never comes real in my lifetime. Looks like I'll be disappointed, I had no idea they had come this far.

    Why? Because it will mean an end to public-key cryptography forever. Even if we manage to restore secure communication through quantum cryptography, digital signature technology will be lost.
    I had great hopes for digital signatures. Here was a technology that gave the truth an edge over lies. Imagine a digital videocamera with a tamper-resistant chip wired into it that signs the video data regularly. Then connect it to a UMTS mobile or a satelite phone, give it to a brave man and send him to say Palestine. Make it so that it can't easily be turned on and off. You have a pretty damn good witness.
    The loss for crypto is also sad. Today if I e-mail with a teacher at Birzeit, we can use crypto to aid in his safety. If the adversary, in this case Israel, gets a QC they can easily intercept this mail, kill him and create credible faked reports supporting their case. And if QC's become a reality, states will get it first, and possibly the public will never get it.

    Public-key cryptography seemed to provide an antidote to big-brother type scenarios. But in a world where states have QC's we will be back were we was most of the 20th century: where you can never know very much about what's truth and what's propaganda, and the best you can do is support "your side". The best I can think of is praying.

    Better suggestions are welcome.
  • Other posters are quite correct when they point out that the physical constraints (superconducting magnets, strong RF fields, etc.) may keep these computers from ever being used in PC formats. There are theoreticals that might get around that (organic superconducters, faraday cages, even some advanced applications of Stealth technology), but all seem less tractable than quantum computing itself.

    If it works out that Q-Comps are both *incredibly* more powerful in raw capacity (likely) and require special facilities (also likely), then we'll see a return to the architectures of the 70's and 80's, when Iron was Big and the Glass House was king.

    In such an architecture, distributed platforms would be used to handle UI and interpretation, and the processor time to brute-force the calculations would be rented. A lot of the paradigm we've come to take for granted is very recent, and would have to be rethought in such an environment. Just as an example: Q-Comps could have the raw power to accurately simulate the physics of an FPS with hundreds of simulataneous players down to a microscopic level. Then an abstract of that could be transmitted to the players. Welcome to the Holodeck, boys.

    --Dave Rickey

  • Yet. Quantum computers. There's one technology I hope never comes real in my lifetime. Looks like I'll be disappointed, I had no idea they had come this far.

    Why? Because it will mean an end to public-key cryptography forever.

    What?! This just is absolutely FALSE!

    (1) Public key cryptography is secure because of the difficulty of a particular computational task. For example, in RSA, that task can be mapped onto factoring numbers

    (2) Quantum computers provide algorithmic speedup of some algorithmic tasks. For example, quantum computers can factor numbers efficiently.

    Now (1) plus (2) does NOT imply all public key cryptography schemes are insecure because not all public key cryptography schemes are built on problems that quantum computers are known to be able to handle efficiently. For example, it is possible (though encoding and decoding times are ugly, I've been told) to use an NP-complete problem as the computational roadblock in codebreaking. As of today, we do now know how to solve NP-complete problems efficiently on either a classical or a quantum computer.

    And remember, the security of public key cryptography like RSA is not "proven": it relies on the "difficulty" of a computational task. People really believe it is difficult to factor numbers classically. Why? Because they have been banging their heads up against the problem for quite a few years. But proof by exhaustion is no proof at all: just evidence.

    So the main jist is: public key cryptography as a whole will NOT be destroyed by building quantum computers. Certain schemes which you bought into because you believed that factoring is hard WILL be broken, however.

    Finally I would like to point out that quantum cryptography is a way to establish a secure key distribution. The security of this scheme is based not on some conjectured hardness of a problem, but instead on the belief that quantum mechanics governs the physics of the universe.


    Dave Bacon
  • Regardless of what you think, you can not solve a NP or NP-Complete problem in P time. The only true way to do this is to prove that an NP problem can be reduced to a P problem.

    Solving something faster doesn't mean that it's not in polynomial time...you just did it faster. Hell, the P problems will be even faster too...doesn't meant that they're now done instantly...they're just done faster.

    Now, if someone can reduce a NP-Complete problem to P...that would be pretty friggin cool...that and it would destroy all modern mathematics theory as we know it.

  • Be my guest. I'm due for new one anyway. Enjoy!

    Rick

    p.s. Bob Sewell is a friend of mine, known far and wide for the level of cynicism expressed in this quote. OTOH, he's good enough to earn being cynical.
  • It would be interesting to know, if you could say something about it with certainity, whether discrete log or elliptic curve discrete log based PK systems will be vulnerable to attacks from a quantum computer.

    There is to my knowledge no PK system today that uses an NP-complete problem. I believe Diffie and Hellman experimented with a knapsack-based system which was NP-complete (or it's possible it was just proven to be NP-hard), but it turned out you didn't need to solve the underlying problem after all. So they used a discrete log based system instead.

    I admit I don't know so much about this as I wish I did, if you can reassure me there's no need to worry then that's great :-) But the number field sieve can be used against elgamal/DH too somehow. Doesn't this mean that these systems will be hit as hard as RSA? the number field sieve is just a factoring technique after all, and so is that nasty quantum program.

    As to elliptic curve problems, I've read that the main objection is that although NFS won't work, there's nothing mathematically that says that elliptic curve problems will be harder to solve in polynomial time than the others; it just hasn't been worked on so long.

    If you know of a working public-key system that uses an NP-complete problem, please give me a link!
  • oh, why not sniff some ether and call it a day?
  • Bah, give it another year or two, 640 kb of ram will be dinosaur-like, I'm sure, the way the market is these days
  • the NYT is now officially slashdotted. :-)

Slashdot Top Deals

He has not acquired a fortune; the fortune has acquired him. -- Bion

Close