Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
IBM Hardware Technology

IBM Touts Quantum Computing Breakthrough 132

Lucas123 writes "IBM today claimed to have been able to reduce error rates and retain the integrity of quantum mechanical properties in quantum bits or qubits long enough to perform a gate operation, opening the door to new microfabrication techniques that allow engineers to begin designing a quantum computer. While still a long ways off, the creation of a quantum computer would mean data processing power would be exponentially increased over what is possible with today's silicon-based computing."
This discussion has been archived. No new comments can be posted.

IBM Touts Quantum Computing Breakthrough

Comments Filter:
  • by JimCanuck ( 2474366 ) on Tuesday February 28, 2012 @09:50AM (#39184327)
    And people keep telling me IBM isn't innovative and cutting edge anymore. [/Sarcasm]
    • by Anonymous Coward on Tuesday February 28, 2012 @10:15AM (#39184567)

      The depressing thing is that you will never see anything like this out of Apple. Billions of dollars in reserves and no "Jobs Labs".

      • Re: (Score:1, Insightful)

        by Anonymous Coward

        no, but apple has been pretty focused on making technology cool and even desirable to the masses. While perhaps not as interesting to you as Quantum computing, its certainly important, and something that IBM was never able to do.

        • by bws111 ( 1216812 )

          Wait, you mean International Business Machines doesn't make things for the masses? Who'd a thunk it?

        • .. focused on making technology cool and even desirable to the masses.

          You probably mean the middle class

      • by Darth Snowshoe ( 1434515 ) on Tuesday February 28, 2012 @11:00AM (#39185011)

        THIS, like times a million. NYTimes this weekend had an excellent article on the history of Bell Labs (the laser, the transistor, communications satellites, etc). HP, whatever else you may think of them, supported the pure research lab which brought forth the memristor. IBM can point to things such as this, its various efforts to simulate a brain, and Watson. Google, bless their souls, is pushing for automated driving (this may not sound in the same league, until you realize the consequences for everybody who drives or rides in an auto.)

        Where is the pure research at Apple? Do they think they can get by on just making better UIs, for the rest of forever? Are they at all part of a larger community?

        • Re: (Score:1, Interesting)

          by BitZtream ( 692029 )

          BASF, we don't make the things you use.

          We make the things you use BETTER.

          That was the commercial I remember for several years.

          Its not always about making cutting edge front page news break throughs, sometimes its just about refining something until its just right after someone else made the break through and then forgot about it because they moved on to the next shiny thing.

          Both kinds of people/businesses are useful and needed, well atleast until this utopian dream you have becomes reality and everyone work

        • by Anonymous Coward
          No, they think they can get by on just making better UIs and using third-party or licensed hardware in shiny cases put together by suicidal chinese slaves. Also, suing their competitors to death when actual science prevails over the macfaggotry of the jobsian cult.
        • by steelfood ( 895457 ) on Tuesday February 28, 2012 @11:50AM (#39185555)

          Apple doesn't do technological research. Instead, they pour all of that money into usage research, so that they can design an improved user experience.

          It's not necessarily a bad thing. There's a place for both the technological side, and the usability side. Most tech companies focus on the technology side while neglecting the usability, which is why so much technology ends up unusable by laymen.

          Microsoft actually does a lot of usability research too. But the difference between Microsoft and Apple is that Apple has (or had) someone steering the ship. They're a top-down dictatorship-style management house. Microsoft is more about internal competition to see who wins out. They're more of a survival-of-the-fittest, cream-of-the-crop-rises-to-the-top type of management house.

          • by Darth Snowshoe ( 1434515 ) on Tuesday February 28, 2012 @12:14PM (#39185839)

            But Apple SHOULD do technological research. Because it provides a long term competitive edge for them, and because its the right thing to do. Corporations, like people, live in a larger society, culture (and nation) and they benefit from those things. Apple would not exist were it not embedded in the Silicon Valley culture emanating from Stanford and Berkeley. Apple should give something back. Maybe Steve would not understand this, but surely Woz would.

            Yeah, iPhones are great, but honestly, ten years from now, we'll be on to a newer, better UI (glasses, brain implants, holodecks, or whatever.) It turns out we're still using lasers and transistors and communications satellites, all invented by Bell Labs in the 60s.

            Here, I'm pasting the best bit from the NYTimes/Bell Labs article, written by Jon Gertner;

            "But what should our pursuit of innovation actually accomplish? By one definition, innovation is an important new product or process, deployed on a large scale and having a significant impact on society and the economy, that can do a job (as Mr. Kelly once put it) “better, or cheaper, or both.” Regrettably, we now use the term to describe almost anything. It can describe a smartphone app or a social media tool; or it can describe the transistor or the blueprint for a cellphone system. The differences are immense. One type of innovation creates a handful of jobs and modest revenues; another, the type Mr. Kelly and his colleagues at Bell Labs repeatedly sought, creates millions of jobs and a long-lasting platform for society’s wealth and well-being."

            The whole article is here (paywall yadda-yadda)
            http://www.nytimes.com/2012/02/26/opinion/sunday/innovation-and-the-bell-labs-miracle.html?pagewanted=all [nytimes.com]

          • by msobkow ( 48369 )


            Apple invests in PATENTING UI components so they can SUE companies and people who use them.

            IBM, on the other hand, sponsored, developed, published, and GAVE AWAY the Common User Interface Standard.

            Apple has no intent on sharing anything with anyone. They want to OWN the market. All markets. And any device that makes the mistake of using a common sense gesture, icon, or interface that anyone with a functioning brain cell could have come up with.

            Apple is a pimply leech on the ass of compu

          • Given some of the unpolished turds Microsoft has put out in the past, that cream must be pretty curdled...

            In reality though, the stuff Microsoft has put out makes me think more of an organization with tons of internal competition, yes, but one in which people sabotage each other or engage in politicking in order to force pet ideas into projects resulting in products clearly designed by committee and often containing so many compromises that whatever good points are often completely outshone by really horrif

        • It's not a zero-sum game. This would only be a problem if Apple was the only company that ever will exist. Let them do what they do well and let IBM do what they do well.

        • Do they think they can get by on just making better UIs, for the rest of forever?

          I don't know if they can, but they should be able to do just that. As long as they make the best UI (do they make it now?) if you want a nice UI, you go with them. The same way that if you want some revolutionary tech, you get it from IBM, or some other company that invest on tech.

          It is called especialization. It is one of the biggest drivers of growth since the XVIII century.

        • Because Apple isn't that kind of company and seems to hold no ambitions to become one?

          Apple is really good at taking various pieces of existing technology and combining them in a way that nobody else has, or, if a similar product exists, taking it and refining the hell out of the user experience. That's it.

          Why should they spend money on something that's outside their intended domains of expertise? It would be like complaining that the Gap doesn't spend money researching basic materials science so they can m

      • by mcgrew ( 92797 ) *

        Why is that so depressing? Apple is design and marketing, not engineering or research. And they do a damned good job of it, too -- they do usually have the best designs if not the best engineering (e.g., iPhone antenna).

      • by gorzek ( 647352 )

        Apple's not in the business of researching, producing, and selling bleeding-edge computers. Apple's focus is primarily on pleasant design, intuitive user interfaces, and an overall integrated experience using commodity-grade hardware.

        (I say this as someone who doesn't even buy their products.)

      • by TheSkepticalOptimist ( 898384 ) on Tuesday February 28, 2012 @05:50PM (#39189961)

        Apple will wait for everyone else to have quantum computing, and then release a device making the masses believe Apple invented quantum computing because they call it iQuantum.

        But I agree. Apple has 98 billion in the bank and is worth over 1/2 trillion on paper, yet they are only focus on repackaging largely off the shelf components invented by other companies into fancy packages and spending way too much money designing retail stores that boast large sheets of seamless glass.

        What strikes me as really depressing is that while Bill Gates is generally hated among Slashdot readers he had given more back to the world in the terms of his charity work. In his "retirement" he is focused on trying to solve some of the world's biggest issues in poverty and quality of life.

        On the other hand, Steve Job's stayed at Apple pretty much up till his death bed creating an empire where people just thrown them money to buy into a walled garden of content and hardware while Apple shits on any other competitive product or company.

        How has Apple given back to the world? Creating jobs where the pressure is so high people kills themselves when they don't meet Apple's quota's or quality standards? Creating products people actually kill for? Creating a market of "want" that is never satiated until someone becomes bankrupt?

        Apple needs to start giving back, put some of them billions into charity and maybe try to invent something useful for the world that does have an "i" in front of it.

        I sincerely think that Apple has enough money to cure cancer, but the company is more interested in hoarding money and technology patents. Its a shame really that everybody's beloved Apple is probably one of the most evil, greedy, selfish and vindictive companies wrapped in a protective bubble of smugness.

  • by Anonymous Coward on Tuesday February 28, 2012 @09:55AM (#39184373)

    1) Repeated news about being able to perform some operation with a tiny number of qubits do not suggest that it is probably true that a useful quantum computer of practical size can be built;

    2) It wouldn't mean data processing power would be "exponentially increased", but that certain algorithms could be executed asymptotically faster.

    QC remains a second rate branch of mathematics for computer science types who don't want to apply themselves to less glamorous problems in the more mature and challenging fields of classical computing. For engineers, it's still in the nuclear fusion stage: kinda just possible in the right conditions, but under no conditions shown useful.

  • Exponentially? (Score:1, Informative)

    data processing power would be exponentially increased over what is possible with today's silicon-based computing.

    Please, please, please stop misusing the word "exponentially". It just means that something is increasing (or declining) at a constant rate, which is practically the opposite of what is meant here.

    • by JoshuaZ ( 1134087 ) on Tuesday February 28, 2012 @10:10AM (#39184515) Homepage
      Actually, this is a correct use. Some algorithms on quantum computers are exponentially faster than the best known classical algorithms. For example, estimating a Gauss sum http://en.wikipedia.org/wiki/Gauss_sum [wikipedia.org] scales exponentially in time, but the most efficient quantum algorithms are bounded by a polynomial. So exponential speed up is a valid use of the term here.
    • Re:Exponentially? (Score:5, Informative)

      by vlm ( 69642 ) on Tuesday February 28, 2012 @10:15AM (#39184557)

      The whole discussion is fubar

      First of all, the derivative of e to the x ("exponential function") is e to the x. Yeah thats true the D is the same as the function itself. Welcome to 1st semester calculus, kids. Not a constant, not even sure what "constantly increasing" means mathematically, although if AC meant its linear thats a bucket of fail too.

      The next fubar is quantum computing doesn't provide a magic exponential speedup. There is a page length summary on the wikipedia but it should come as No Surprise Whatsoever to anyone in CS that different algorithm designs inherently have different big O notation and magically sprinkling quantum pixie dust doesn't change that, some algos are linear, some poly, some constant, some exponential, all quantum computing does is swap about where some belong. Solve for X where X+1=2 is not gonna change much, factoring into primes is going to change quite a bit. Some of the most interesting problems are polynomial time not exponential in quantum computing. http://en.wikipedia.org/wiki/Quantum_computer#Potential [wikipedia.org]

      • Wouldn't this be a game-changer for encryption, though (if they can actually make it work, that is)? I mean, brute-force decryption seems like exactly the kind of computational task that a quantum computer could easily handle. So a brute-force attack on a key that may take hundreds of years on a current supercomputer could be done in a few minutes. No password would be safe from any organization with access to that kind of computing power. Or am I understanding the potential?

        • by vlm ( 69642 )

          Wouldn't this be a game-changer for encryption, though (if they can actually make it work, that is)? I mean, brute-force decryption seems like exactly the kind of computational task that a quantum computer could easily handle. So a brute-force attack on a key that may take hundreds of years on a current supercomputer could be done in a few minutes. No password would be safe from any organization with access to that kind of computing power. Or am I understanding the potential?

          Not necessarily, no. For any crypto app you can come up with some formula where you chunk in the number of bits and it spits out how long it takes to crack it. It exclusively has to do with scalability in design. Double a linear algo and that number takes twice as long. Most (good) crypto is exponential so triple the number of bits it goes up by 3^3 or 27 times longer or whatever. The deal is quantum computing for some crypto increases by poly instead of exponential.

          What no one wants to talk about is w

      • Re: (Score:2, Troll)

        Oy... The rate is constant, meaning that the increase is in constant proportion to the value of the function at any given time. That's why calculations of continuous compound growth take exponential form, and it's a result of e^x being its own derivative, as you point out.

        Of course neither the OP nor I were talking about the computational order ("Big-O") of a quantum algorithm, because no specific algorithm was under discussion. If such algorithms were typically exponential in N - i.e., O(e^N) - that wouldn

      • First of all, the derivative of e to the x ("exponential function") is e to the x. Yeah thats true the D is the same as the function itself. Welcome to 1st semester calculus, kids

        Me again... This discussion is long dead, but I have to point out that the exponential growth curve is not e^x but rather a*e^(x*t), where a is the initial quantity, t represents time and x is the rate constant. Now differentiate that with repect to t, and you get the slope a*t, as you would expect from a constant x.

        Hence, a population of 1000 that grows by 1% adds 10 times as many as a population of 100 that grows by the same rate. Constant growth rate, exponential growth. I don't see why this is so diffic

    • It could have been worse. They could have said "quantum".
    • I think your main problem is that you said "constant rate". Rate is kind of ambiguous. To you, that meant increasing by a constant ratio, i.e. A(x+n)/A(x) = A(y+n)/A(y), i.e. exponential growth. To a few other people, it obviously meant increasing by a constant amount, i.e. A(x+n)-A(x) = A(y+n)-A(y), i.e. linear growth (as revealed by AC's introducing the derivative and thinking that proved his point).

      And really, if someone said something was "accelerating at a constant rate", I'd typically assume they mean

  • by rgbrenner ( 317308 ) on Tuesday February 28, 2012 @10:07AM (#39184481)

    The Economist had an interesting article a couple days ago.. at least it's interesting if you don't really know the details of quantum computing:

    Quantum computing: An uncertain future [economist.com]

    Each extra qubit in a quantum machine doubles the number of simultaneous operations it can perform. It is this which gives quantum computing its power. Two entangled qubits permit four operations; three permit eight; and so on. A 300-qubit computer could perform more concurrent operations than there are atoms in the visible universe.

    • As the AC said, that's misleading.

      Another way to look at it is by having the computer indeed calculating over the entire domain at once (that means, the computer runs the calculation on all the numbers represented with X bits at once), but when you read you can only get the result of one of the calculations. The actual one you'll get is a random one, with a distribution that you can tune.

      That is equivalent to constraining the operations. I think that way of thinking is more intuitive.

  • by Gary van der Merwe ( 831179 ) on Tuesday February 28, 2012 @10:19AM (#39184599)
    Quote from article:

    A qubit, like today's conventional bit, can have two possible values: a 0 or a 1. The difference is that a bit must be a 0 or 1, and a qubit can be a 0, 1, or a superposition of both. "Suppose you take 2 qubits. You can be in 00, 01, 10, and 11 at the same time. For 3 qubits you can be in 8 states at the same time (000, 001, 111, etc.). For each qubit you double the number of states you can be in at the same time. This is part of the reason why a quantum computer could be much more powerful," Ketchen said.

    I find that to be a terrible explanation. What he said: "For each qubit you double the number of states you can be in at the same time." is also true for normal bits. Huh? Here is a better explanation: http://en.wikipedia.org/wiki/Qubit [wikipedia.org]

    • by Anonymous Coward

      Actually, it is correct. An additional normal bit doubles the number of *possible* states. An additional (entangled) qubit doubles the "number of states you can be in at the same time" (with emphasis being on "at the same time"), which is a colloquial description of doubling the dimension of the state space.

    • by Hatta ( 162192 )

      No. With regular bits, you can only be in one state at once. Adding a bit doubles - 1 the number of states you are not in.

  • does it run GNU/Linux ?
  • by gweihir ( 88907 ) on Tuesday February 28, 2012 @10:22AM (#39184641)

    For conventional computers, as soon as you have "and" and "not" in gate-form, you can do everything, as you can just connect them together. For quantum computers that is not true, as all elements performing the complete computation need to be entangled the whole time.

    IMO, there is now reason to believe that the real-world scalability of quantum computers is so bad that it negates any speed advantage. It seems the complexity of building a quantum computer that can do computations on inputs of size n is at least high-order polynomial or maybe exponential in n. That would explain why no significant advances have been made in keeping larger quantum computing elements entangled in the last 10 years or so and no meaningful sizes have been reached.

    Keep in mind that, for example, to break RSA 2048, you have to keep > 2048 bits entangled while doing computations on them. And you cannot take smaller elements and combine them, the whole > 2048 bits need to represent the input all must be entangled with each other or the computation does not work.

    • by vlm ( 69642 ) on Tuesday February 28, 2012 @10:46AM (#39184869)

      Theres a nice wiki page with pages and pages of detailed explanation of what this post is talking about.

      http://en.wikipedia.org/wiki/Quantum_decoherence [wikipedia.org]

      Here's a nice analogy for quantum computing... its a magic old fashioned analog computer with serious reliability and I/O issues. Imagine at the dawn of the computer era you wanted to simulate the statics of a large railroad bridge. In 8 bits it would take a very long time, 16 bits much longer... And to prevent rounding error propagation you have issues. So why not simulate it with a thundering herd of analog opamps which will "instantly" solve the bridges static loads? OK cool, other than all the opamps must work perfectly the entire time you take a measurement which with vacuum tubes is questionable and qubits maybe impossible. The other problem is if you want 32 bit accuracy now your proto-computer engineer needs to build a 32 bit A/D converter to connect to your analog computer... good luck... This is not a perfect quantum computing analogy, but pretty close in many regards.

      There is a bad trend in computer science to assume "all computers and algorithm programming problems are about the same" which they historically have been, but are not in the real world. So given two roughly identical algorithms and problems on two roughly identical computers, the smaller big-O notation wins every time, more or less. That is a huge mistake to try that thinking across widely different architectures... OK so factoring computation is exponential on classical computers and everyone ignores I/O because thats constant with a normal bus design or at worst linear. OK so factoring computation is poly on quantum computers hooray for us... whoops looks like I/O might go exponential and constant factor might be years/decades to get the thing working.

      The way to keep secure with a classical computer is to pick an algorithm that big O scales such that it can't be broken in this universe. The way to keep secure with a quantum adversary is to pick a key size that seems to make it an engineering impossibility to build a quantum computer, even if by some miracle a quantum computer could solve it in poly time if only it could somehow be built.

      • by gweihir ( 88907 )

        I like your analog computer analogy. Maybe for those that are not into electronics: Building a working 32 bit A/D converter (i.e. one that has 32 bits accuracy) is pretty much impossible, even at 24 bits the lower bits are only noise from several different noise sources. And OpAmps are pretty noisy to when you get to that precision level. 16...20 bits is about the practical limit unless you do things like supercooling and even then you only gain a few bits.

        I also completely agree on the countermeasures. And

    • Re: (Score:2, Insightful)

      by Anonymous Coward

      Another way of explaining this is that in order to take advantage of the exponential speed-up of quantum computing in practical applications, you need exponentially better management of entanglement and decoherence effects, which turns out to be a very difficult engineering problem. People keep proposing different models for quantum computing hoping that if they do these operations in solid state rather than via NMR, or in Bose-Einstein condensates, or using exotic pseudo-particles, or other means that the

    • by TheSync ( 5291 )

      For conventional computers, as soon as you have "and" and "not" in gate-form, you can do everything, as you can just connect them together. For quantum computers that is not true, as all elements performing the complete computation need to be entangled the whole time.

      Actually for conventional computers, to implement any binary function you only need either NAND or NOR [uiowa.edu], the "universal gates".

      For qbit-based Quantum Computing, the universal gate is Controlled Not (CNOT) [wikipedia.org] gate, which can be used to realize any q

      • by gweihir ( 88907 )

        A matter of taste. I like to regard AND and NOT as different constructs, since one is unary and one is binary. May have to do with some background in modern algebra I have. Of course, you can combine them, but whether NAND/NOR is really less complex than AND/OR and NOT is up for debate. When implemented classically as TTL, NAND is easier than AND and only minimally more complex than NOT.

        Anyways, entanglement is the primary foe of scalability, other problems are data input and output, since that has to be do

  • I wonder if IBM will be upgrading Watson with a Quantum computer brain. Won't be long now before they invent HAL.
  • I miss the days when IBM actually made PC's they were always rock solid. You could beat someone to death with one of there laptops and after wiping the blood off it it would still work...
    • by vlm ( 69642 )

      I miss the days when IBM actually made PC's they were always rock solid. You could beat someone to death with one of there laptops and after wiping the blood off it it would still work...

      Model M keyboard with the steel backplate and buckling springs. Still use mine with a PS/2 to usb converter thing (not an adapter, a more expensive converter). Lack of a windows key didn't bother me until I switched to the "awesome" windowmanager which likes to use that key as a control key. Bummer.

      • I didn't even think about the keyboards, which reminds me that I have a few in the basement hooked up to various machines. I don't get to use them as much as I used to because I use my laptop for all of my daily driver stuff. If you ever break it (not likely) you can pick up a replacement from Unicomp: http://www.pckeyboard.com/ [pckeyboard.com] They are expensive but its the only way to get a new model m these days unless you come across an unopened IBM branded one somewhere (in which case its worth a small fortune).
        • by vlm ( 69642 )

          Why I'll be... a brand new 104 key type M... that means a windoze key to drive "awesome" window manager with. I may have to retire my old PS/2 type M...

          They're not expensive, they're only a hundred bucks. If they're as good as a real type M, your grandkids will be using them, which works out to "about a can of soda per month". Expensive is something like an all plastic "gamers keyboard" for $30 that only lives for 6 months before keys start sticking (true anecdotal story).

          • I haven't personally used one of the Unicomp keyboards but from what I understand they hold the rights & are the only company producing the Model M still. Don't retire it, use it on a "retired" machine you can always setup your own router/server with something like clearos or a pbx or better yet both on the same machine ;)
  • Ok, IANAP, but, like many slashdotters, am interested in all things science and especially quantum mechanics. Please explain, if you may, this contradiction, because I've been unable to find a good explanation in anything I've read so far.

    If we consider the many worlds interpretation to be viable, from what I understand :
    - when a scientist will start up the very first quantum computer for the first time -- say, a big 250 qubit computer -- and will test it against a big cypher or whatever, 2^250 univers
    • by Altesse ( 698587 )
      Edit : the other solutions are incorrect
      (In the other worlds, I'm better at learning foreign languages).
    • No. Quantum computing works whether or not MWI is correct. And it doesn't have to do with quantum suicide. In an MWI situation, the vast majority of universes will get the same (correct) result. Essentially, the different universes cooperate with each other before the split off. This isn't quite correct (in MWI there are really discrete universes but rather part of a continuum, and there are a lot of other subtleties involved).
    • That's not how quantum computers work, despite of what you might have read in science popularization articles. Quantum algorithms don't work like classical algorithms work, but "doing all possibilities at once". That wouldn't work because of the contradiction you described -- once you measure the result, all the other "possibilities" go away.

      Quantum algorithms work by not only solving the problem, but also shifting the probabilities of the qubits in such a way that, when you measure it, you get a very high

  • by mathimus1863 ( 1120437 ) on Tuesday February 28, 2012 @11:11AM (#39185143)
    I took a class on Quantum computing, and studied many specific QC algorithms, so I know a little bit about them.

    Quantum Computers are not super-computers. On a bit-for-bit (or qubit-for-qubit) scale, they're not necessarily faster than regular computers, they just process info differently. Since information is stored in a quantum "superposition" of states, as opposed to a deterministic state like regular computers, the qubits exhibit quantum interference when mixed with other qubits. Typically, your qubit starts in 50% '0' and 50% '1', and thus when you measure it, you get a 50% chance of it being one or the other (and then it assumes that state). But if you don't measure, and push it through quantum circuits allowing them to interact with other qubits, you get the quantum phases to interfere and cancel out. If you are damned smart (as I realized you have to be, to design QC algorithms), you can figure out creative ways to encode your problem into qubits, and use the interference to cancel out the information you don't want, and leave the information you do want.

    For instance, some calculations will start with the 50/50 qubit above, and end with 99% '0' and 1% '1' at the end of the calculation, or vice versa, depending on the answer. Then you've got a 99% chance of getting the right answer. If you run the calculation twice, you have a 99.99% chance of measuring the correct answer. However, the details of these circuits which perform quantum algorithms are extremely non-intuitive to most people, even those who study it. I found it to require an amazing degree of creativity, to figure out how leverage quantum interference constructively.

    But what does this get us? Well it turns out that quantum computers can run anything a classical computer can do, and such algorithms can be written identically if you really wanted to, but doing so gets the same results as the classical computer (i.e. same order of growth). But, the smart people who have been publishing papers about this for the past 20 years have been finding new ways to combine qubits, to take advantage of nature of certain problems (usually deep, pure-math concepts), to achieve better orders of growth than possible on a classical computer. For instance, factoring large numbers is difficult on classical computers, which is why RSA/PGP/GPG/PKI/SSL is secure. It's order of growth is e^( n^(1/3) ). It's not quite exponential, but it's still prohibitive. It turns out that Shor figured out how to get it to n^2 on a quantum computer (which is the same order of growth as decrypting with the private key on a classical computer!). Strangely, trying to guess someone's encryption key, normally O(n) on classical computers (where n is the number of possible keys encryption keys) it's only O(sqrt(n)) on QCs using Grover's algorithm. Weird (but sqrt(n) is still usually too big).

    There's a vast number of other problems for which efficient quantum algorithms have been found. Unfortunately, a lot of these problems aren't particularly useful in real life (besides to the curious pure-mathematician). A lot of them are better, but not phenomenal. Like verifying that two sparse matrices were mulitplied correctly has order of growth n^(7/3) on a classical computer, n^(5/3) on a quantum computer. You can find a pretty extensive list by googling "quantum algorithm zoo." But the reality is that "most" problems we face in computer science do not benefit from quantum computers. In these cases, they are no better than a classical computer. But for problems like integer factorization, bringing the compute requirements down to polynomial time isn't just faster: it makes a problem solvable that wasn't before.

    Unfortunately [for humanity], there is no evidence yet that quantum computers will solve NP-complete problems efficiently. Most likely, they won't. So don't get your hopes up about solving the traveling salesmen problem any time soon. But there is still a lot of cool stuff we can do with them. In fact, the theory is so far ahead of the technology, that we're anxiously waiting for breakthroughs like this, so we can start plugging problems through known algorithms.
    • You can't design quantum algorithms to solve classical computer problems faster?
    • Your explanation was awesome. Thank you.

    • by na1led ( 1030470 )
      What about Quantum Entanglement? Being able to communicate instantaneously across any distance, which would be beneficial to probes exploring deep space.
      • by JoshuaZ ( 1134087 ) on Tuesday February 28, 2012 @12:28PM (#39186001) Homepage
        Entagnlement doesn't allow you to communicate information. The following analogy may help. Imagine two coins that whenever they are both flipped they end up either both heads or both tails, but you can't control which one comes up. So if you separate the two coins, you can use them to get a shared source of randomness which you can use for some useful things (like cryptography) but you can't use it to communicate.
        • by dAzED1 ( 33635 )
          sortof. If both sides can instantly know a rapidly changing value, that value can be used to both encrypt and compress communication. The fact that it isn't controllable doesn't mean that it can't be used for such things.
        • You have 2048 randomly entangled bits.
          Somebody on the other side of the world has the matching pair of 2048 randomly entangled bits.

          Not useful for communication per-se if you can't influence them, but if you could *READ* them without influencing them, they'd be darn spiffy for an encryption key or seed shared between two parties.

          Simple XOR encryption would be awesome so long as you both have synchronized reading of the encrypted bits. Take message, XOR it against the encryption key, send to recipient, recip

          • [...] but if you could *READ* them without influencing them [...]

            That would be great, but you can't. Once you read them, the entanglement is broken. As mathimus1863 wrote in the original message in this thread,

            Typically, your qubit starts in 50% '0' and 50% '1', and thus when you measure it, you get a 50% chance of it being one or the other (and then it assumes that state). [my emphasis]

            That means that once you measure a qubit, its state becomes exactly what you measured (this is commonly known as "wave function collapse"), and so it's not entangled anymore.

        • Easy way to think of entanglement that won't lead to thinking of it as an FTL communication mechanism:
          Imagine a machine (hidden from any observers) that flips a coin, cuts it in half, and puts the halves in two sealed boxes. The halves could be either heads up or tails up, you can't tell until you open a box. Both will be in the same state, no matter how far apart you move the boxes. You can drive all day with a half-coin in a box and it won't change. (Had to work a car in.) Knowing the state of one tells
    • "On a bit-for-bit (or qubit-for-qubit) scale, they're not necessarily faster than regular computers, they just process info differently."

      Thank you. I have been trying and failing (in tweets @DrEpperly) to explain the concept you describe very succinctly. I have a telecommunications background so we just think of it as having two channels...sort of like the old 'dual-mode' phones...

      When you get published saying this please send me a link ;)

    • That was a great explanation.

      Just one small nitpick: when you talk about factorization, you use "n" for the number of bits, and when you talk about guessing an encryption key, you use "n" for the number of possible keys, which makes things a little unnecessarily confusing. I'd change the second one to also use number of bits -- so it would be O(2^n) on classical computers and O(2^(n/2)) for quantum computers. This way it's also easier to see that the square root (i.e., the factor of 1/2 in the exponent) doe

  • by Anonymous Coward

    This news story appears the day after IBM laid off a number of engineers in STG. (system and technology group, the part of the company that works on operation systems and hardware like Power, blades, Z, etc)

    Not that IBM would be attempting to deflect any negative news stories which might range from the very tight lipped control on number of employees let go, forbidding those employees let go from talking to the press or lose their severance pay, current number of employees in the US, brain drain of engineer

  • I always thought the contraction was "qubit" for "Quantum Bit".
    Is "quibit" an accepted variant spelling, and, if so, where does the extra letter "i" come from?
  • Promises of quantum computers seem to be suffering from the fusion syndrome. Fusion has been "only 20 years away" for the last 40 years. :P

"For a male and female to live continuously together is... biologically speaking, an extremely unnatural condition." -- Robert Briffault