Skip to content
 
If you can read this, either the style sheet didn't load or you have an older browser that doesn't support style sheets. Try clearing your browser cache and refreshing the page.

(ZDNet)   A quantum computer just solved a difficult problem 3 million times faster than a conventional computer. Public key cryptography is starting to look a little shaky   (zdnet.com) divider line
    More: Interesting, Computer, Computation, Universal quantum simulator, Quantum computer, Qubit, company D-Wave, Simulation, Nobel Prize  
•       •       •

890 clicks; posted to STEM » on 24 Feb 2021 at 5:19 PM (11 weeks ago)   |   Favorite    |   share:  Share on Twitter share via Email Share on Facebook



31 Comments     (+0 »)
View Voting Results: Smartest and Funniest
 
2021-02-24 3:27:10 PM  
Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.
 
2021-02-24 3:28:34 PM  
I wonder how it does at Bitcoin mining.
 
2021-02-24 3:44:53 PM  
Secrets From The Future
Youtube FUPstXCqyus
 
2021-02-24 3:49:48 PM  
Oh boy.
 
2021-02-24 4:18:04 PM  

HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.


Just to put a slightly finer point on an excellent summary. There is no known way to map classic cryptographic problems into that space of problems that quantum annealing machines solve well, and it is unlikely there ever will be.
 
2021-02-24 4:18:38 PM  
As already said, quantum computers are very good at some things. And very bad at other things.

This is one of the things they are very good at.
 
2021-02-24 4:28:08 PM  
I never thought I'd see the day when real honest-to-god quantum computers were solving useful real-world problems. I still don't.

/I keed, I keed
//no, they're great
///for me to poop on!
 
2021-02-24 5:24:27 PM  
Just wait until Alice and Bob hear about this....
 
2021-02-24 5:44:31 PM  

HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.


You skipped over the most important part too


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.
 
2021-02-24 5:50:32 PM  

lifeslammer: HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.

You skipped over the most important part too


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.


Indeed.  All that's happened here is that D-Wave have claimed their box could have solved it really fast.
How much of that extra speed is really the box?  How much is an algorithm designed with the box in mind and knowing what the answer is?  Why focus on a solved problem rather than an unsolved problem - wouldn't the latter be much more impressive?
Company has a bit of a history of being vague about the details.
 
2021-02-24 6:09:01 PM  
Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.
 
2021-02-24 6:12:54 PM  

leeksfromchichis: Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.


You forgot quantum Crysis.
 
2021-02-24 6:21:03 PM  

HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.


What I came to say...
 
2021-02-24 7:10:37 PM  
Now tell it to decode the Phaistos Disk.
 
2021-02-24 7:21:42 PM  
How interesting it would be if our processing ability became so powerful, that the concept of security for anyone with less-than state-level resources could only be obtained with air-gapped systems.

I mean, it would probably kill Facebook so, I'm game.

/why yes, i am playing the disappointment known as Cyberpunk
 
2021-02-24 8:59:16 PM  
3 million times faster you say?  So, instead of taking 3 Bajillion years to break encryption, it will only 1 brazilion years.  I'm ok with that.
 
2021-02-24 9:00:13 PM  

Gubbo: As already said, quantum computers are very good at some things. And very bad at other things.

This is one of the things they are very good at.


Can they be good and bad at things at the same time?
 
2021-02-24 9:16:50 PM  

boozehat: Just wait until Alice and Bob hear about this....


They both will, simultaneously.
 
2021-02-24 9:25:56 PM  
Or you could use a $5 hammer
 
2021-02-24 11:52:19 PM  
See, I read this article as that they fed the computer a problem that had a known solution to see just how quickly the computer could resolve it.    Compare that to the time it took the computers that the humans entered the problem into and see how much faster it was.  And much, it was.

So, the lay understanding of computers do awesome calculations = haxors the cryptoz, is fair and legitimate.

However, the point is made that breaking cryptography is quite different from the problem that was solved.  (How, I don't know, that's other big brain stuff but I wouldn't mind a TL;DR if someone does know.)
 
2021-02-25 12:30:26 AM  

Driedsponge: leeksfromchichis: Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.

You forgot quantum Crysis.


That's still 20 years away...
 
2021-02-25 1:16:11 AM  

leeksfromchichis: Until it runs Quantum Doom and loads Quantum Porn on a Quantum Private Mode Browser, I don't believe it's quantum.


Duke Nukem 4-D will be out any time now....
 
2021-02-25 5:48:22 AM  

DocUi: See, I read this article as that they fed the computer a problem that had a known solution to see just how quickly the computer could resolve it.    Compare that to the time it took the computers that the humans entered the problem into and see how much faster it was.  And much, it was.

So, the lay understanding of computers do awesome calculations = haxors the cryptoz, is fair and legitimate.

However, the point is made that breaking cryptography is quite different from the problem that was solved.  (How, I don't know, that's other big brain stuff but I wouldn't mind a TL;DR if someone does know.)


Basically crypto relies on P vs NP in math, and any solution to that would instantly become a national security issue

Basically encryption is unsolvable problems even for a computer, and p v np is saying that any problem that can be quickly verified by a computer could also be quickly solved by a computer. So while right now it takes literal ages for a computer to brute force the equations that encryption is based on, a successful proof to solve that would basically make encryption as good as a fence with a hole in it

So while people fear quantum computing for being able to just brute force things without a solution to that, its far more probable that people would use a quantum computer to try and solve p vs np instead, and then write the software to bypass every security format on the planet


I think....all my understanding on encryption comes from one episode of elementry so it may not be totally accurate
 
2021-02-25 7:38:13 AM  
Not a fan of quantum gaming. Ran a Pokemon emulator on one once. Put my pikachu in a box. System froze up trying to tell me if it was alive or fainted.
 
2021-02-25 8:08:57 AM  

Dave2042: lifeslammer: HugeMistake: Cryptography is still safe. This was a D-Wave, which uses a niche approach (quantum annealing) that happens to be very effective for a certain class of problems that happen to be exceptionally difficult for an ordinary digital computer - primarily ones involving quantum simulations.

You skipped over the most important part too


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.

Indeed.  All that's happened here is that D-Wave have claimed their box could have solved it really fast.
How much of that extra speed is really the box?  How much is an algorithm designed with the box in mind and knowing what the answer is?  Why focus on a solved problem rather than an unsolved problem - wouldn't the latter be much more impressive?
Company has a bit of a history of being vague about the details.


Regardless, the criticisms here are like pointing to an Apple II in 1981 and saying "What good is it?".  Not much, but that's besides the point.  It increased the ability to do calculations by orders of magnitude over previous manual methods, and it was still very limited in its capacity and power.

Quantum computing is in that stage right now, it's relative infancy, and it's showing improvements (if TFA is to be believed) of six whole orders of magnitude over conventional computing.

And yeah, if it's an algorithm designed specifically to take advantage of how quantum computers work, how is that a problem?  Do you think other algorithms won't be designed with that in mind?   And in fact, they already have:   https://en.wikipedia.org/wiki/Shor%2​7s​_algorithm

The idea behind public key cryptography is that there are functions that are easy to compute one way, and very difficult to reverse.   A sufficiently powerful quantum computer running Shor's algorithm can break pretty much all of the commonly used public key crypto used today in a reasonable time frame by being able to do the reverse calculation before the heat death of the Universe.

In this case, they demonstrated a machine using 2,000 qubits, which is designed for a specific problem not necessarily related to cryptography, but that doesn't mean you couldn't build one that is.

I mean, sure, you can look at the Bleriot IX and say "What use is it?", not imagining that something like the SR-71 is possible.
 
2021-02-25 8:43:36 AM  

dittybopper: Regardless, the criticisms here are like pointing to an Apple II in 1981 and saying "What good is it?".  Not much, but that's besides the point.  It increased the ability to do calculations by orders of magnitude over previous manual methods, and it was still very limited in its capacity and power.

Quantum computing is in that stage right now, it's relative infancy, and it's showing improvements (if TFA is to be believed) of six whole orders of magnitude over conventional computing.


No, not really. The criticisms here are like pointing to an Apple II and saying "even with decades of speed doubling and density improvements and costs dropping, it still won't be able to break strong encryption" because strong encryption is fundamentally, mathematically, formally Hard with a capital H. Exponentially hard - which means that orders of magnitude don't help.

There is a class of problems that quantum computers are, in theory, going to be much better at solving. There is a smaller class of problems that this particular approach (quantum annealing) is well-suited to and that are particularly ill-suited to digital computers. But it is fundamentally wrong to think that quantum computers are regular computers, only faster.

dittybopper: I mean, sure, you can look at the Bleriot IX and say "What use is it?", not imagining that something like the SR-71 is possible.


No. This is more like looking at a Ford Model T, imagining that a Mercedes Formula One car is possible, and still understanding that it's never going to get you across an ocean because it's a car, not a plane.
 
2021-02-25 9:09:22 AM  

lifeslammer: Basically encryption is unsolvable problems even for a computer, and p v np is saying that any problem that can be quickly verified by a computer could also be quickly solved by a computer. So while right now it takes literal ages for a computer to brute force the equations that encryption is based on, a successful proof to solve that would basically make encryption as good as a fence with a hole in it


Sort-of.  My only quibble is "unsolvable problems even for a computer".   There is only one known unsolvable problem in cryptography, and that's breaking a properly implemented one-time pad system.  It's the only provably unbreakable system, simply because brute forcing it would just give you every possible message of the same length without being able to distinguish the correct one from all of the incorrect ones.

All of the others are *EXCEPTIONALLY* difficult.  While they are solvable from a theoretical standpoint with conventional computers, from a practical standpoint they aren't because of the huge amount of time it would take to solve them.

However, relying on the "Takes a huge amount of time to break" is a *VERY* weak leg to stand on.   It's the mistake the Nazi's made with the Engima.  They *KNEW* that Enigma wasn't unbreakable.  But they figured that even if you had an Enigma machine, or even dozens or hundreds, having people test all of the possibilities would take too long to break.  They didn't think about using machines with large numbers of parallel Enigma rotors all grinding away at high speed to break them.

Having said that, I believe that as early as mid-1943, and certainly by the fall of 1944, the Germans *KNEW* that Enigma was being broken, because they acted like it was.  Perhaps the two biggest things were the U-boat messages and the Ardennes Offensive.

In the fall of 1944, the Ubootwaffe started experimenting with giving each U-boat going on operational patrol it's own unique set of daily Enigma keys.  Prior to that, U-boats heading for the same operational areas would be given the same keys, so they could read each other's traffic.  So if U-89 hears U-372 report a convoy sighting, the commander of U-89 can start intercepting the convoy before getting an order from BdU* to do so.

The problem is that with a number of U-boats all reporting things like convoys, ship sightings, weather reports, and simply status reports, and messages from BdU requesting reports or ordering the U-boats to and fro, you can build up a lot of traffic in the same key, and that's bad.

With each U-boat having it's own key, there isn't anywhere near as much traffic, and by that time a lot of it was one-way traffic, because the U-boats spent most of their time submerged or snorkeling, so they couldn't transmit.  They could receive while underwater, though, via the powerful VLF transmitter at Nauen.

The Germans started this in the Fall of 1944, and by February 1945, all U-boats on war patrol had their own individual unique keys.  And the Allies were blacked out of U-boat Enigma traffic all the way to the end of the War, simply because each key for each U-boat had to be broken each and every day.   So even if you managed to  break U-897's key for March 3rd, 1945, that didn't help you with U-734's traffic, even if they were both operating in the same general area.

The other major event was the Ardennes Offensive.  The orders for the offensive were not transmitted over the airwaves, and certainly not by Enigma:  By that time, regulations stated that nothing classified could be sent over the air encrypted by Enigma, it had to be either via the secure teleprinter (which was ironically less secure than the Enigma), or via courier.   The orders for the Ardennes Offensive were sent via courier, which is part of the reason why the Allies were caught unaware.

Here is a very interesting NSA monograph on what the Germans knew about Allied efforts to break Enigma, and it comes *CLOSE* but not quite there to saying basically "Yeah, the Germans knew it wasn't secure, but couldn't switch horses midstream".

https://www.nsa.gov/Portals/70/docume​n​ts/news-features/declassified-document​s/tech-journals/der-fall-wicher.pdf


So the whole idea that with conventional means public key cryptography is safe just reminds me of the Germans saying that Enigma was safe, when in fact it had been broken years before WWII even started.

For all we know, the NSA broke public key cryptography years ago.  We wouldn't know about it, because it's classified.


*BdU = Befehlshaber der Unterseeboote, literally "Commander of U-boats", but basically U-boat HQ.
 
2021-02-25 9:26:57 AM  
It solved a problem that had already been solved?
 
2021-02-25 9:50:04 AM  

dryknife: It solved a problem that had already been solved?


Yes, in 1/3,000,000th of the time it took previously.
 
2021-02-25 10:10:58 AM  

HugeMistake: No. This is more like looking at a Ford Model T, imagining that a Mercedes Formula One car is possible, and still understanding that it's never going to get you across an ocean because it's a car, not a plane.


upload.wikimedia.orgView Full Size


upload.wikimedia.orgView Full Size


And if you need examples actually powered by a Ford Model T engine:

simanaitissays.files.wordpress.comView Full Size


And it wasn't just the really primitive aircraft:

https://en.wikipedia.org/wiki/Pietenp​o​l_Sky_Scout#Specifications_(Pietenpol_​Sky_Scout)
mtfca.comView Full Size



Oh, and Model T engines were used in boats, too:

http://www.mtfca.com/discus/messages/​3​31880/350074.html?1364148479

Given the ubiquity of Ford Model T engines, and their use in aircraft and boats, you picked a really poor example.

Granted, none of them were ocean crossers (though the boats could be: Doesn't take a lot of HP to push even a fairly large sailboat).
 
2021-02-25 1:13:12 PM  

vygramul: I wonder how it does at Bitcoin mining.


It'd be hilarious if it cuts mining time by a couple orders of magnitude
 
Displayed 31 of 31 comments

View Voting Results: Smartest and Funniest

This thread is closed to new comments.

Continue Farking




On Twitter


  1. Links are submitted by members of the Fark community.

  2. When community members submit a link, they also write a custom headline for the story.

  3. Other Farkers comment on the links. This is the number of comments. Click here to read them.

  4. Click here to submit a link.