Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

arxiv.org

Post reply on HN
Print view View original

61–70 of 146 posts

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#61

Post by freeone3000 »

azatris wrote: post #56
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

I do not know much about quantum computing. But could you explain what makes these computers quantum? Is it the configuration of these transistors to invoke some quantum phenomena?

They're built off fundamentally different basic units. Contemporary computers use transistors, which occupy traditional physics and do logic with voltage thresholds. Quantum computers use a quantum phenomenon -- one easy-to-understand (and fairly easy to construct) quantum computer substrate uses the spin of electrons in superconducting loops. Electron spin is a quantum phenomenon, in that the spin isn't deterministically positive or negative, it's a probability distribution -- initially, equally likely to be positive or negative, but you can't tell what it is until you actually read it. It's not 0.0, it's either -0.5 or 0.5, both with a 50% chance. Equally importantly, you can perform (physical) operations on electrons singly or in pairs in order to manipulate these probabilities. Quantum computing is turning these probability fields and operations into useful computational results.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#62

Post by CodesInChaos »

marcosdumay wrote: post #27
dzdt wrote: post #9

Quantum computers of this scale are probably 5-15 years out. Basically this is a warning that if you have secrets that should still be kept secret over that timeframe, you should not be using RSA today.

> you should not be using RSA today Also, always remember that ECC is believed to be just as weak against quantum computers as RCA. So you'll probably want some fusion of pre and post-quantum algorithms. Or, anyway, get your perfect forward secrecy working and don't rely on asymmetric crypto for confidentiality. Yeah, PFS is very hard to get on some use cases, but it's really the best way to solve this problem.

Forward secrecy relies on asymmetric crypto, it merely uses short lived/one-time keys instead of long lived keys. The most popular algorithm for ephemeral key exchange is (Elliptic curve) Diffie-Hellman which is just as weak against quantum attacks as RSA. So adding a post-quantum algorithm is just as important for PFS as for plain RSA.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#63

Post by antepodius »

azatris wrote: post #56
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

I do not know much about quantum computing. But could you explain what makes these computers quantum? Is it the configuration of these transistors to invoke some quantum phenomena?

In a classical computer, every bit of information in the system is in a definite state- 1 or 0. In a quantum system with such definite possible states, what you actually have most of the time of the system in some interpolation of the possible states- so in the quantum computer case each bit is usually in a state a1 + b0, where a and b are complex numbers such that |a^2|+|b^2| = 1.

Most of the time, the 'weight' flows back and forth between a and b according to certain equations over time. When you measure the system- that is, when the bit interacts with the outside world, hopefully your measuring apparatus- you see a 1 or a 0, with probabilities |a^2| and |b^2| respectively.

So what you can do is get a whole bunch of these quantum bits- qubits together, and set things up so that the time-evolution of their quantum state is correlated and probabilistically moves towards something you're interested in. Say you can set things up so the bit array- which, at first, will give you a mere perfectly random bit string on measurement- becomes more and more likely to give you, say, a prime factor, or the answer to some other question.

So yes, the quantum phenomenon is that the bits of the computer are quantum objects as opposed to classical.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#64

Post by _hl_ »

azatris wrote: post #56
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

I do not know much about quantum computing. But could you explain what makes these computers quantum? Is it the configuration of these transistors to invoke some quantum phenomena?

A quantum computer is defined as a machine that can implement an arbitrary "unitary evolution" (up to arbitrary precision). If you don't know enough math to understand what a unitary evolution is, think of it as a quantum computer doing basically any possible thing that you can do with a given number of qubits. As another comment said, the idea is to (ab)use this to do some operations on qubits such that they end up in a state where measuring it will give you an answer to something you're interested in. It has very little to do with classical programming.

The math on quantum computers checks out, it's "just" an engineering challenge at this point, and many are doubtful whether these challenges will ever be overcome to build a quantum computer of sufficient complexity.

Essentially, some "unitary evolutions" are complex to implement, as in requiring a lot of quantum "gates". This causes an accumulation of error and a whole lot of other problems, which limits the complexity of the calculations that can currently be performed.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#65

Post by DebtDeflation »

elephantum wrote: post #5
stirlo wrote: post #2

Just to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.

Do I understand correctly, that largest quantum computer that exists today contains less than 100 qubits? Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers... . They hit the wall in 2017. We should be safe for now :)

>largest quantum computer that exists today contains less than 100 qubits

The numbers reported in the press are physical qubits not logical qubits. You need multiple physical qubits + error correction to create a single logical qubit. The main type of error correction used today is something called "surface codes". With this type of error correction it's estimated that MILLIONS of physical qubits will be required to create a SINGLE fully error corrected logical qubit.

https://www.ncbi.nlm.nih.gov/books/NBK538709/

We do not have actual quantum computers today and we don't seem to be much closer to having them than we were a decade ago. What we have are really interesting quantum science experiments that get misrepresented by the press (and a handful of companies with a commercial interest in doing so).

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#66

Post by _hl_ »

gallerdude wrote: post #53
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

...would be like bringing mathematics to Mesopotamia. Can you expound on this? What sort of breakthroughs are bottlenecked by developments in quantum computing?

The hope is that quantum computers will give us an exponential speed up on some problems, which could (again, hopefully) allow us to solve some NP hard problems. This can be extremely useful for scientific computing (e.g. protein folding) and engineering, where computers have to solve complex NP-hard optimisation problems.

It could also be possible to use the technology developed for the precise control and measurement of qubits to "rebuild" natural phenomena like the interaction of chemical molecules, something which is currently extremely hard to simulate.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#67

Post by Gene_Parmesan »

lallysingh wrote: post #48
isolli wrote: post #44

Earlier quoted context omitted.

Thanks. I don't understand your last paragraph. Can you provide a bit more context? Just a starting point for an Internet search :)

I think they're saying that we know nobody's using quantum computing to break crypto yet, because nobody's been draining bitcoin wallets.

Maybe, but if a state actor has achieved this ability, I doubt they would make its existence public knowledge by stealing a few billion US$ in btc. That's chump change compared to the value of being able to surreptitiously crack the cryptographically secure messages of everybody in the world.

Note I'm not saying that I actually think someone has achieved this, I just don't think "no one is stealing btc" is a good non-existence test.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#68

Post by RIMR »

rnestler wrote: post #60
bdamm wrote: post #49

Earlier quoted context omitted.

Quantum computers exist today, they're just very low power, low gate counts, and extremely expensive. Don't discount it as magic just because of the claims. Scaling up QC would be like bringing mathematics to Mesopotamia. But it isn't "magic", it's physics.

> they're just very low power, I guess you meant to write high power as in high electrical power consumption? Or low power in the sense of low processing power? Anyway: Performance per Watt is probably pretty bad for current quantum computers ;)

"Processing power" is colloquially the term most people I know use to describe computers of varying capabilities.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#69

Post by _hl_ »

CodesInChaos wrote: post #46
graderjs wrote: post #28

Earlier quoted context omitted.

Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factoriz…

> Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.

"Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.

Re: Factoring 2048 RSA integers in 177 days with 13436 qubits and a multimode memory

#70

Post by jakozaur »

One day you can start calculating private keys based on public keys.

This is the biggest crypto puzzle: find private key of Sathoshi Bitcoin wallet with 1 mln bitcoins. Over $50 Bln prize for one crypto puzzle.

This would be AlphaGo moment of quantum computing if you could make that one attack successful even while paying huge price (e.g. years of quantum datacenter work).

Post reply on HN