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

 


Forgot your password?
Close
typodupeerror
×
Math Encryption

Quantum Computer Solves Decades-Old Problem Three Million Times Faster Than a Classical Computer (zdnet.com) 77

Posted by EditorDavid from the quantum-quickness dept.
ZDNet reports: Scientists from quantum computing company D-Wave have demonstrated that, using a method called quantum annealing, they could simulate some materials up to three million times faster than it would take with corresponding classical methods.

Together with researchers from Google, the scientists set out to measure the speed of simulation in one of D-Wave's quantum annealing processors, and found that performance increased with both simulation size and problem difficulty, to reach a million-fold speedup over what could be achieved with a classical CPU... The calculation that D-Wave and Google's teams tackled is a real-world problem; in fact, it has already been resolved by the 2016 winners of the Nobel Prize in Physics, Vadim Berezinskii, J. Michael Kosterlitz and David Thouless, who studied the behavior of so-called "exotic magnetism", which occurs in quantum magnetic systems....

Instead of proving quantum supremacy, which happens when a quantum computer runs a calculation that is impossible to resolve with classical means, D-Wave's latest research demonstrates that the company's quantum annealing processors can lead to a computational performance advantage... "What we see is a huge benefit in absolute terms," said Andrew King, director of performance research at D-Wave. "This simulation is a real problem that scientists have already attacked using the algorithms we compared against, marking a significant milestone and an important foundation for future development. This wouldn't have been possible today without D-Wave's lower noise processor."

Equally as significant as the performance milestone, said D-Wave's team, is the fact that the quantum annealing processors were used to run a practical application, instead of a proof-of-concept or an engineered, synthetic problem with little real-world relevance. Until now, quantum methods have mostly been leveraged to prove that the technology has the potential to solve practical problems, and is yet to make tangible marks in the real world.
Looking ahead to the future, long-time Slashdot reader schwit1 asks, "Is this is bad news for encryption that depends on brute-force calculations being prohibitively difficult?"
This discussion has been archived. No new comments can be posted.

Quantum Computer Solves Decades-Old Problem Three Million Times Faster Than a Classical Computer More

Quantum Computer Solves Decades-Old Problem Three Million Times Faster Than a Classical Computer

Comments Filter:

  • No (Score:3)

    by TechyImmigrant ( 175943 ) on Saturday February 27, 2021 @01:41PM (#61106126) Homepage Journal

    >Is this is bad news for encryption that depends on brute-force calculations being prohibitively difficult?

    No.

    I'll let other fill in with an explanation as to why quantum annealing cannot run Shor's algorithm nor can it run Grover's algorithm and the basic scaling problem of standard quantum computation remains unaddressed by any of the 'advances' over many years of trying to build quantum computers.

    • Re: (Score:3)

      by gweihir ( 88907 )

      >Is this is bad news for encryption that depends on brute-force calculations being prohibitively difficult?

      No.

      I'll let other fill in with an explanation as to why quantum annealing cannot run Shor's algorithm nor can it run Grover's algorithm and the basic scaling problem of standard quantum computation remains unaddressed by any of the 'advances' over many years of trying to build quantum computers.

      Make that "several decade" and no, I am not willing either to explain time and again why this is still basically worthless and nobody know whether QCs will ever be a threat to modern encryption or useful for anything else.

      • Re: (Score:3)

        by ceoyoyo ( 59147 )

        nobody know whether QCs will ever be a threat to modern encryption

        Sure we know. Even if you assume a perfect, easily scalable quantum computer, which is probably impossible, it's trivial to simply move to algorithms which are not even theoretically vulnerable to QCs.

        • Re: (Score:2)

          by gweihir ( 88907 )

          "Modern encryption" is a phase in the history of cryptography, specifically the one we are in now. You are talking about "Post-Quantum" encryption, which is a speculation about a next phase. You are right that should QCs ever become a reality, we can move to non-vulnerable algorithms. On the block-cipher side, we do not even need to do that. QCs at best halve the key bits. That means AES-256 will remain secure.

          • Re: (Score:2)

            by ceoyoyo ( 59147 )

            I don't really want to play word games. Current symmetric key encryption is pretty much already quantum safe. The problem is (popular) public key systems, and there are already lots of options for replacing those, including algorithms that have been in use and studied for twenty-five years.

            "Post quantum encryption" isn't "speculation about a next phase." If you want to be generous it's a description of algorithms, old and new, that are likely to become or continue to be the standard. If you want to be accur

            • Re: (Score:2)

              by gweihir ( 88907 )

              Well, I think post-quantum encryption is a very stupid idea that some people use to make themselves seem more important and some "researchers" use to get funding. There is actually no sane reason to believe it will become important anytime soon. It is pure hype, no substance. Also, should Quantum Computing happen to eventually work, there is absolutely no reason to believe it will be able to break the current recommendations of around 4k bits for RSA (which means about 12k QBits to factorize) anytime soon (

              • Re: (Score:2)

                by ceoyoyo ( 59147 )

                I like to think that hype about reading people's mail is funding research into actual useful applications of quantum computing. Kind of like that harebrained scheme to fund Mars exploration with Big Brother in Space.

                • Re: (Score:2)

                  by gweihir ( 88907 )

                  I like to think that hype about reading people's mail is funding research into actual useful applications of quantum computing. Kind of like that harebrained scheme to fund Mars exploration with Big Brother in Space.

                  Well, maybe. If there ever will be any quantum computing that is more than an expensive, useless toy. What I think may come out of this is an eventual result of Quantum Computing _not_ working or not scaling due to some yet unknown Physics. That may then fill in some holes in known Physics, like the missing Quantum-Gravity.

                  • Re: (Score:2)

                    by ceoyoyo ( 59147 )

                    That would certainly be the most interesting outcome. I think it's pretty clear you can use quantum systems to simulate quantum systems though, and having some off the shelf-ish easily configured ones could be a revolution in chemistry. I suspect noise and the difficulty of maintaining coherence in ever larger systems will practically limit their use for solving most abstract problems, even if there isn't anything as interesting as a fundamental physical limit.

                    • Re: (Score:2)

                      by gweihir ( 88907 )

                      Indeed. Or we could have a fundamental physical limit, but scaling will stop long before that is found. But we can hope.

        • Re: (Score:3, Interesting)

          by Gaglia ( 4311287 )

          nobody know whether QCs will ever be a threat to modern encryption

          Sure we know. Even if you assume a perfect, easily scalable quantum computer, which is probably impossible, it's trivial to simply move to algorithms which are not even theoretically vulnerable to QCs.

          Unfortunately it's not that easy. NIST's PQ candidates suffer in terms of performance compared to stuff like RSA and elliptic curve cryptography. Certain advanced features are not possible or not known yet, for example lattice-based t-of-n threshold signatures and compact zero-knowledge proofs for arbitrary circuits.

          This does not mean one should not use these new schemes, on the contrary! But the switch to quantum-resistant solutions is not so easy from an engineering standpoint - albeit possible.

          Regardless

          • Re: (Score:2)

            by ceoyoyo ( 59147 )

            Well, for symmetric key encryption, which is most of the important stuff, it's pretty easy: probably a good idea to double your key size.

            For the admittedly very useful public key stuff, there's some haggling over what's best, but for the average Joe looking for digital signatures and key exchange, there are perfectly good solutions. If you're doing some advanced niche stuff you might have to work a little harder.

        • nobody know whether QCs will ever be a threat to modern encryption

          Sure we know. Even if you assume a perfect, easily scalable quantum computer, which is probably impossible, it's trivial to simply move to algorithms which are not even theoretically vulnerable to QCs.

          PQ key agreement protocols are yet to be established as safe. A proof that an algorithm is PQ-secure does not necessarily make it secure from boring old classical attacks and several candidate algorithms have fallen on that sword. The NIST PQ competition is going on, which will hopefully yield something at least as robust as AES has managed to be over the years, while being reasonably efficient and implementable. Meanwhile PQ RNGs have remained ignored by the crypto standards world and as well all know, RNG

          • Replying to my only post - I suspect the standardized extractor algorithms are in fact PQ-secure (since they are would break external entanglements), but I've yet to see a proof to that effect. If you know of one, kindly post a link.

          • Re: (Score:2)

            by ceoyoyo ( 59147 )

            The NIST competition isn't looking to replace AES. AES is just fine. It's looking to replace RSA. And all the candidates are also just fine, the competition is just to figure out which one is *best*.

            Just as an example, NTRU is faster than RSA, and has a provably secure version. RSA is not proven secure.

            • Yes. The NIST PQ competition basically covers signing and key agreement.

              "Provably Secure" can be a problematic claim. Many provably secure algorithms have been shown to be vulnerable to side channel and fault injection attacks when implemented.

              Cert signing is basically a solved problem, using hash based signatures. But more general uses of signing and key agreement still need to be agreed upon as a standard.

              • Re: (Score:2)

                by ceoyoyo ( 59147 )

                Yes, there's nothing left to do but dot the ts and sign the papers. Quantum secure cryptography is as much of a solved problem as classically secure cryptography, and has been since the mid 90s.

                • Well the winner hasn't been selected yet and I'm not about to run out and implement hardware for all of the finalists to ensure I have it ready ahead of time. I made that mistake with the SHA3 competition. Even then, the wrong candidate (Keccak) won and so implementation is a mess.

                  • Re: (Score:2)

                    by ceoyoyo ( 59147 )

                    Sure. There's the usual logistics to work out, just like the last time we switched encryption algorithms, and the time before that. But the implementation of quantum-safe encryption is like switching from RSA to ECC, not like OMG OMG, the hackerz are gonna p0wn the innernetz!

                    Feynman was speculating about the possibilities of quantum computing in the 70s. Shor's algorithm was published in 1995. If you had something worth hiding for eternity, you've always used one time pads. If it was a bit less important, y

                    • I remember the algorithm agility wars in IEEE802. It's a real bugger - Be able to switch algorithms, but then you open up to downgrade attacks and even if you solve all that stuff, you can never get people to agree to switch to a new algorithm at the same time. I had a nice solution for that problem, but it never made it into the specs because some people had questionable morals.

  • Crypto collapses as quantum computer invalidates all coins.

    • Re: (Score:2)

      by gweihir ( 88907 )

      Nope. This is not even a preliminary step to that. It is completely unclear whether QCs will ever be a threat to modern encryption. But this thing is not even a QC.

  • Not an issue for cryptography - for now (Score:5, Informative)

    by Anonymous Coward on Saturday February 27, 2021 @02:04PM (#61106188)

    D-Wave's quantum annealing cannot be used for breaking cryptography. For that you need to run Shor's or Simon's or Grover's algorithms (or derivatives of those) and this requires high entanglement and long coherence time, both properties that cannot be achieved with quantum annealing.

    However:

    1) "civilian" applications of quantum computers (such as that mentioned in TFA) are the main commercial drive for QC development right now. Talking about finding good chemical catalysts for producing fertilizer is not as exciting as talking about breaking codes, but the reality is that these applications are both more important and easier to achieve (because they require less quantum resources).

    2) Quantum annealing used to be considered a bit more than a joke by scientists. For example, Scott Aaronson uses to bash regularly against D-Wave's "questionable" marketing tricks, and so far quantum annealing algorithms lack explicit evidence of concrete speedup over classical ones (I don't know the computational problem mentioned in the TFA in detail, but my guess is that classical methods to tackle such problem can be still greatly optimized up to the point of closing or nearly closing the gap with D-Wave's machines). That said, it has been recently proven that *at least in theory* quantum annealing can achieve a concrete speedup over classical methods: https://arxiv.org/abs/2005.037... [arxiv.org] - TL;DR, quantum annealing is not "super cool" but cannot be ruled out as quackery anymore.

    3) Despite what "quantum haters" will tell you, QC research *is* progressing fast. Counting "the number of qubits" or "the largest number ever factorized by QC" is *not* a good measure of progress in QC. The Dunning-Kruger is strong when talking about new technologies, and I am expecting the usual smart people with low Slashdot ID ready to jump on the "QC is BS" bandwagon in 3, 2, 1... Google has pretty much proven quantum supremacy in 2019 already** and IBM is planning to produce the first *logical qubits* in a couple of years (and they have been quite accurate in their short-term predictions so far).

    FYI: logical qubits are like the Holy Grail of QC. Once you get one of those, you quickly escalate to full Shor. I am actually expecting IBM to play with the marketing and produce qubits that are only "partially logic" at first, but still the trend is clear. If you are developing cryptographic solutions, switch to quantum-resistant crypto ASAP if you don't want to be caught off-guard.

    (Posting as AC, but just because somebody will ask for my credentials eventually: PhD in theoretical CS here, I work with related technology, which is to mean that if QC are built or not that doesn't affect my salary)

    **yes, I know, IBM has corrected their estimate by an order of magnitude but overall the result still holds IMHO - while another recent paper claiming to simulate Google's result on traditional hardware in a few seconds turned out to be flawed.

    • Re: (Score:3)

      by sjames ( 1099 )

      Mostly true, but there are some serious caveats on your item 3. The "quantum supremacy" demonstrated was just that (SURPRISE) a quantum computer is better at being a quantum computer running random operations than a simulation of a quantum computer on a PC is. That's like saying that a rubber band does a better job being a rubber band than these bits of kite string do.

      That's not to say QC will never be a thing, just that it really isn't yet.

      • Re: (Score:1)

        by Anonymous Coward

        True, but that was the entire point! Quantum supremacy (QS) does not tell you that a QC can solve a *useful* problem faster that a traditional computer, it only says that there is at least *one class of computational problems* for which this happens. The word _class_ here is crucial: for a QS experiment to be meaningful the instance of the problem must be *arbitrarily programmable*, which is what Google did. Otherwise one could take a real-world physical process that is hard to simulate classically (say, a

        • Re: (Score:2)

          by sjames ( 1099 )

          Except the "test" was so close to your example of test tube an chemicals it is practically indistinguishable. It was more language lawyering than it was quantum supremacy. It's a tautology. X is better at being an X than notX is.

          Imagine the problem is how much heat is released when adding 1 g of CaCl2 to 100ml of water. The contestants are a test tube containing 100ml of water and a gram of CaCl2 vs. a PC. But further, just to make it "fair", since the test tube is solving the problem at the quantum level,

          • Re: (Score:3, Interesting)

            by Anonymous Coward

            The analogy is not correct.

            The Google problem was (roughly) the following:

            "given ANY ARBITRARY circuit of 53 superconducting qubits where 1) the gates can be chosen among this particular finite set, and 2) the depth of the circuit is at most 20 layers, and 3) the initial state of the qubits is set to zero, find the distribution of values in output with approximation error at least (small value)"

            In order to qualify for Quantum Supremacy (QS), both the classical and the quantum machines where you run this exp

            • Re: (Score:2)

              by sjames ( 1099 )

              Notice that there is no restriction on how your classical simulator should solve the problem, as long as it works. It does *not* necessarily do it "exclusively by modeling the test [stuff] at the quantum level". In theory you could come up with a classical algorithm that gives you the answer by just extrapolating some algebra from the classical description of the quantum gates.

              But Google's claim only holds if you DO apply that restriction. Note that a week later, IBM optimized the program for the conventional computer and reduced the expected run time from 10,000 years to about 3 days.

              There is a rock on my desk. It does nothing. It is such a powerful rock that it can do nothing just as quickly as all of the worlds computing resources put together. It's an amazing rock! What were the odds my garden would turn out to be full of them?

              • Re: (Score:2)

                by gweihir ( 88907 )

                There is a rock on my desk. It does nothing. It is such a powerful rock that it can do nothing just as quickly as all of the worlds computing resources put together. It's an amazing rock! What were the odds my garden would turn out to be full of them?

                Ah, but you miss the point! Your rock can do nothing _faster_ than conventional computers can simulate doing nothing! Hence you have rock-supremacy right there!

    • Re: (Score:2)

      by ceoyoyo ( 59147 )

      This is a much more interesting story than the usual QC stuff that makes it to Slashdot. Shor's algorithm is interesting theoretically, but it's never going to have any real practical impact. Years before anyone gets close to building a machine that can run it on a decent sized key, the world will have moved on to new encryption algorithms.

      The exciting applications are in advancing materials physics, chemistry and biochemistry.

    • Re: (Score:2)

      by gweihir ( 88907 )

      Despite what "quantum haters" will tell you, QC research *is* progressing fast.

      PhD in theoretical CS here

      Well, if you look at the abysmally slow progress over the past 40 years with the eyes of a _theoretician_, that may look fast to you. With my CS Engineering PhD, it just looks abysmally slow and more like inverse exponential scaling with effort, i.e. it will run into a hard wall before it can do anything useful. Remember that conventional computers were made relevant and then great by exponential scaling. (although that seems to be mostly over now. Communication complexity is a bitch, even on chip layer.) T

    • Re: (Score:2)

      by jythie ( 914043 )
      Heh. As a classical AI person who is now studying 'deep learning', I have learned to be wary of what edges of a discipline are considered a joke. All it takes is one change in a nearby field to flip 'wow, this is useless, only study this if you want to teach and never work in it' completely around.

  • They have lied, cheated and claimed complete bullshit so many times, I will not even start to find out what is wrong with this claim.

  • D-Wave still exists? (Score:3)

    by ocean_soul ( 1019086 ) <tobias DOT verhulst AT gmx DOT com> on Saturday February 27, 2021 @02:54PM (#61106308)

    Seeing as it is D-Wave saying this, their is about 99% chance it is 100% bullshit, and 1% chance it is 99% bullshit.

  • ...it should have no problems checking out all the possible protein folds to cure any sickness of the planet in 17 minutes?

    19 minutes with a cure for cancer.

    • The cure will be calculated. And so will several billion cures that don't work. Your job is to figure which on of those several billion was the cure. Good luck.

    • The problem with cancer is getting proteins that kill the cancer without killing you.

  • Who cares about "classical computer"? (Score:3)

    by RightSaidFred99 ( 874576 ) on Saturday February 27, 2021 @05:03PM (#61106704)

    Their point of comparison should be to an ASIC, not a god damn general purpose CPU. Guess what, an ASIC can crank out bitcoin massively faster than the fastest x86 or ARM CPU, that doesn't make it fucking magical unicorn shit.

    Quantum computing is bullshit and it's going nowhere and doing nothing, and you can come back and mock me in 20 years if we have quantum AI brain implants and shit.

  • I am always suspect of these type of stories. "Classical CPU" could be anything. If you are going to compare against something specify the fucker.
  • They recreated one of the algorithms used along the way to a real solution, and that one simulated algorithm happens to be a lot faster than with a classic computer. They don't say if the result is always right, just that it is faster.

  • Call me when they can solve all problems 3 million times faster

  • From the original article: "King stressed that it is still possible to design highly specialized algorithms to simulate the model once the properties of the model are already known." Clear example of we fined tuned our machine to a problem and it does it faster than a general purpose computer. Nothing quantum happening here

  • Are they solving a quantum problem using a quantum computer to simulate the quantum effects ? Quantum simulation on a classical computer is costly, thus it is still a nice and useful result for physicists, but not really for computer scientist yet.

Slashdot Top Deals

The opossum is a very sophisticated animal. It doesn't even get up until 5 or 6 PM.

Close