6 ms·

Google Achieves Quantum Supremacy. Is Encryption Safe?

38 points by ItsTotallyOn 7y ago

hartator 7y ago
> Google Achieves Quantum Supremacy Is it another careful crafted academic lie or is it real this time?
- ianai 7y ago
  Previous discussion may deliver: https://news.ycombinator.com/item?id=21053405 https://news.ycombinator.com/item?id=21053405
- gpm 7y ago
  It's like saying a 14 button calculator (0-9, +, *, -, =) achieved mathematical supremacy over humans. Sure, it's better at some specific tasks. It's not a spreadsheet, let along a general purpose theorem prover, yet.
  - lukeschlather 7y ago
    It's more like saying a couple AND gates have achieved mathematical supremacy over humans. They can add 1+1 insanely fast, but that's about it. If we had the quantum equivalent of a 14 button calculator that would be a big deal.
- Filligree 7y ago
  It's true, it just might not mean what you think. "Quantum supremacy" = "This circuit runs faster than it possibly could have under classical rules, no matter how clever it might be," aka. an asymptotic speedup. It proves that quantum computation is possible, and the universe isn't just conspiring to pretend quantum mechanics works while actually following something like Copenhagen, but few people were doubting that in the first place.
  - vcxy 7y ago
    Few people, but enough that it's good to have it conclusively answered. Someone on HN in a previous thread put it nicely. Paraphrasing, this brings quantum computing into science/engineering and out of philosophy.
- abdullahkhalids 7y ago
  There are two subgoals towards the creation of quantum computers * quantum supremacy: this is a scientific goal. This can be achieved by building a quantum device that can solve some, possibly useless, computational problem faster than a classical computer. The Google team claims to have done so. For scientists, wondering whether the extended Church-Turing thesis is true or not, the Google result is a significant result. It provides some evidence that the thesis is not true. * quantum advantage: this is a technological goal (even though it also has scientific implications). This is about building a quantum device that actually solves useful computational problems (like breaking encryption) faster than a classical computer. We are not there yet.
  - api 7y ago
    So basically quantum supremacy helps convince us that it might be worth trying to achieve the latter because it might actually be possible. Its like e.g. sending a sounding rocket into space and back down. It doesn't reach orbit or carry a useful payload, but it shows that a rocket could probably reach orbit. Not a perfect analogy though since in the rocket case it's really a matter of just scaling the rocket while for QC there remain large known unknowns and probably many unknown unknowns.
    - rjf72 7y ago
      Tangential, but Tyranny of the Rocket Equation [1]. The long and short is that your analogy is much better than you might have thought. Increasing rocket power is definitely (and counter intuitively) not just a matter of scale. The reason is that you're surprisingly constrained in rocketry. You have three primary variables that aren't really all that variable: --- 1) deltaV - the change in velocity you need to reach your destination. this is completely fixed. for instance if you want to get into earth's orbit you need to be able to change your velocity by 8km/s regardless of any other variable. 2) specific impulse of your rocket - again this is mostly fixed. it can be improved by technological breakthroughs, but not by things like increasing scale. 3) fuel to mass ratio - what percent of your rocket is made up of fuel --- Any two define the third. deltaV constrains absolutely everything we can do, so we can set it as the goal. Specific impulse is not something that can be readily improved for the most part, so all you're left with is a fuel to mass ratio. And suffice to say making things bigger while making them hold an even larger ratio of fuel is not how things work. Also important is that based on our requirements for the first two variables, our effective fuel to mass ratio is already approaching very close to 100%. We of course take it all for granted now and SpaceX going up and softly autonomously landing back down, sometimes in the middle of the ocean on an autonomous barge, is increasingly starting to look almost mundane. But it's borderline miraculous we can achieve this, and indeed if Earth was just slightly larger (about a 50% greater diameter - just some 4,000 miles) it wouldn't even be possible for us to leave this planet with anything like current technology, regardless of how epic a scale we built upon. [1] - https://www.nasa.gov/mission_pages/station/expeditions/expedition30/tryanny.html https://www.nasa.gov/mission_pages/station/expeditions/exped...
rcardo11 7y ago
That paper just threw a mind-blowing title and abstract but the task they were solving was too narrow. No general-purpose quantum computer for the moment.
- kevinwang 7y ago
  What the heck is a general purpose quantum computer??
ahelwer 7y ago
"Researchers from Canadian company Krypterra believe that we’d need 2,953 logical qubits to break AES-128 and 6,681 logical qubits to break AES-256." Grover's algorithm only gives a sqrt(n) speedup for breaking AES, so the number of bits is irrelevant; breaking 256-bit AES on a quantum computer would take as much time (or gates, rather) as breaking 128-bit AES on a classical computer.
- api 7y ago
  QC is really only a risk to RSA, DH, and elliptic curve, and maybe to small hashes and key sizes. I'd say if your symmetric stuff is bigger than 128 bit you only have to worry about asymmetric crypto.
Xcelerate 7y ago
Has Google officially announced QS yet, or is this all based off of leaks?
- MiroF 7y ago
  Leaks but it's probably true leaks
septafree 7y ago
Almost mandatory link for any informed quatuom computation discussion: https://www.scottaaronson.com/blog/ https://www.scottaaronson.com/blog/
api 7y ago
Somewhat of a tangent but: a big driver for QC investment is breaking encryption for military purposes. We already have encryption that is not believed to be vulnerable to QC, and there is a ton of crypto R&D to make it faster and more practical (e.g. smaller keys and signatures). I wonder if that won't kill some QC investment.
darkmighty 7y ago
https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317 Scott's Quantum Supremacy FAQ
neonate 7y ago
The FT piece the article refers to is here: http://archive.is/ZLiUp http://archive.is/ZLiUp

38 points by ItsTotallyOn 7y ago

hartator 7y ago

> Google Achieves Quantum Supremacy Is it another careful crafted academic lie or is it real this time?

ianai 7y ago
Previous discussion may deliver: https://news.ycombinator.com/item?id=21053405 https://news.ycombinator.com/item?id=21053405
gpm 7y ago
It's like saying a 14 button calculator (0-9, +, *, -, =) achieved mathematical supremacy over humans. Sure, it's better at some specific tasks. It's not a spreadsheet, let along a general purpose theorem prover, yet.
- lukeschlather 7y ago
  It's more like saying a couple AND gates have achieved mathematical supremacy over humans. They can add 1+1 insanely fast, but that's about it. If we had the quantum equivalent of a 14 button calculator that would be a big deal.
Filligree 7y ago
It's true, it just might not mean what you think. "Quantum supremacy" = "This circuit runs faster than it possibly could have under classical rules, no matter how clever it might be," aka. an asymptotic speedup. It proves that quantum computation is possible, and the universe isn't just conspiring to pretend quantum mechanics works while actually following something like Copenhagen, but few people were doubting that in the first place.
- vcxy 7y ago
  Few people, but enough that it's good to have it conclusively answered. Someone on HN in a previous thread put it nicely. Paraphrasing, this brings quantum computing into science/engineering and out of philosophy.
abdullahkhalids 7y ago
There are two subgoals towards the creation of quantum computers * quantum supremacy: this is a scientific goal. This can be achieved by building a quantum device that can solve some, possibly useless, computational problem faster than a classical computer. The Google team claims to have done so. For scientists, wondering whether the extended Church-Turing thesis is true or not, the Google result is a significant result. It provides some evidence that the thesis is not true. * quantum advantage: this is a technological goal (even though it also has scientific implications). This is about building a quantum device that actually solves useful computational problems (like breaking encryption) faster than a classical computer. We are not there yet.
- api 7y ago
  So basically quantum supremacy helps convince us that it might be worth trying to achieve the latter because it might actually be possible. Its like e.g. sending a sounding rocket into space and back down. It doesn't reach orbit or carry a useful payload, but it shows that a rocket could probably reach orbit. Not a perfect analogy though since in the rocket case it's really a matter of just scaling the rocket while for QC there remain large known unknowns and probably many unknown unknowns.
  - rjf72 7y ago
    Tangential, but Tyranny of the Rocket Equation [1]. The long and short is that your analogy is much better than you might have thought. Increasing rocket power is definitely (and counter intuitively) not just a matter of scale. The reason is that you're surprisingly constrained in rocketry. You have three primary variables that aren't really all that variable: --- 1) deltaV - the change in velocity you need to reach your destination. this is completely fixed. for instance if you want to get into earth's orbit you need to be able to change your velocity by 8km/s regardless of any other variable. 2) specific impulse of your rocket - again this is mostly fixed. it can be improved by technological breakthroughs, but not by things like increasing scale. 3) fuel to mass ratio - what percent of your rocket is made up of fuel --- Any two define the third. deltaV constrains absolutely everything we can do, so we can set it as the goal. Specific impulse is not something that can be readily improved for the most part, so all you're left with is a fuel to mass ratio. And suffice to say making things bigger while making them hold an even larger ratio of fuel is not how things work. Also important is that based on our requirements for the first two variables, our effective fuel to mass ratio is already approaching very close to 100%. We of course take it all for granted now and SpaceX going up and softly autonomously landing back down, sometimes in the middle of the ocean on an autonomous barge, is increasingly starting to look almost mundane. But it's borderline miraculous we can achieve this, and indeed if Earth was just slightly larger (about a 50% greater diameter - just some 4,000 miles) it wouldn't even be possible for us to leave this planet with anything like current technology, regardless of how epic a scale we built upon. [1] - https://www.nasa.gov/mission_pages/station/expeditions/expedition30/tryanny.html https://www.nasa.gov/mission_pages/station/expeditions/exped...

rcardo11 7y ago

That paper just threw a mind-blowing title and abstract but the task they were solving was too narrow. No general-purpose quantum computer for the moment.

kevinwang 7y ago
What the heck is a general purpose quantum computer??

ahelwer 7y ago

"Researchers from Canadian company Krypterra believe that we’d need 2,953 logical qubits to break AES-128 and 6,681 logical qubits to break AES-256." Grover's algorithm only gives a sqrt(n) speedup for breaking AES, so the number of bits is irrelevant; breaking 256-bit AES on a quantum computer would take as much time (or gates, rather) as breaking 128-bit AES on a classical computer.

api 7y ago
QC is really only a risk to RSA, DH, and elliptic curve, and maybe to small hashes and key sizes. I'd say if your symmetric stuff is bigger than 128 bit you only have to worry about asymmetric crypto.

Xcelerate 7y ago

Has Google officially announced QS yet, or is this all based off of leaks?

MiroF 7y ago
Leaks but it's probably true leaks

septafree 7y ago

Almost mandatory link for any informed quatuom computation discussion: https://www.scottaaronson.com/blog/ https://www.scottaaronson.com/blog/

api 7y ago

Somewhat of a tangent but: a big driver for QC investment is breaking encryption for military purposes. We already have encryption that is not believed to be vulnerable to QC, and there is a ton of crypto R&D to make it faster and more practical (e.g. smaller keys and signatures). I wonder if that won't kill some QC investment.

darkmighty 7y ago

https://www.scottaaronson.com/blog/?p=4317 https://www.scottaaronson.com/blog/?p=4317 Scott's Quantum Supremacy FAQ

neonate 7y ago

The FT piece the article refers to is here: http://archive.is/ZLiUp http://archive.is/ZLiUp