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

81–90 of 146 posts

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

#81

Post by fractionalhare »

bdamm wrote: post #49
oldgradstudent wrote: post #45

Earlier quoted context omitted.

So magic computer could be more effective with more magic memory than with more magic processing power, right?

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.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved.

It might not look that way because there's a lot of (relatively) mainstream investment in quantum computing. However it's pretty common for speculative physics research to be pursued for years without ever coming to fruition. Especially when there are promising early results before it's shown that scaling the work reduces to an intractable problem.

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

#82

Post by thesz »

Strilanc wrote: post #76
tbabej wrote: post #12

This paper basically explores a hypothetical scenario where scaling quantum memory ends up being cheaper than scaling computational qubits. The title (or abstract) unfortunately does not mention the quantum memory requirements at n=2048 explicitly. For factoring 2048 RSA integers, the technique proposed in the paper would require ~430 million memory qubits (see the table at top of page 16).

It's an interesting question whether, over the long term, quantum hardware will match the feature of classical hardware where memory is significantly cheaper than compute-capable bits in the CPU. Hard drives are 100x cheaper per bit than RAM which is 100x cheaper (I think?) per bit than a CPU register. How expensive is quantum memory relative to quantum compute, over the long term? Expectations about the answer to th…

You are off by orders of magnitude. The difference in memory density between DRAM and SRAM (register file) is not 100 times, more like 10x. Standalone "registers" - memory elements of pipelines, state machines etc, - are again not more than ten times less denser than SRAM.

After DRAM goes SSD and after SSD goes disk. The difference in price per GB for SSD and disk is about four (4x) times, I looked for that numbers recently. The difference between tape and disk is, again, about 4-10 times (from memory).

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

#83

Post by reikonomusha »

fractionalhare wrote: post #81
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.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved. It might not look that way because there's a lot of (relatively) m…

I think it’s reasonable to be more optimistic than you put it. Qubit counts and qubit fidelity have been increasing at a remarkable rate. Just five years ago we could barely eek out a handful of qubits, and when we did, they’d be bad. Google’s quantum supremacy result is a testament to that. (At this stage, whether they actually demonstrated the “supreme” part of supremacy is, imho, irrelevant. They’ve demonstrated a much larger, controllable, programmable quantum computer and measured its quality characteristics accurately.)

Of course, I’m saying it’s reasonable to be more optimistic, not that we have a proof we will certainly be able to scale to enormous machine sizes. But it’s definitely more than “speculative physics”: real machines have been built and demonstrated to exhibit truly measurable quantum effects that allow for programmable computation.

(To be sure, there is hype, there is a lot of cash sloshing around, and there are totally bogus claims some companies are publicly making.)

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

#85

Post by reikonomusha »

kjrose wrote: post #23

It's an interesting theory but like most items in quantum computing it is purely theoretical. Not sure how much it would cost to build. I hope someone gets a grant to work out the engineering difficulties in this.

I would say most items in quantum computing are not theoretical. They’ve been demonstrated. Moreover, quantum physics is by far our most accurate theory of physics we have

What is still hypothesized is whether these elements, which have been demonstrated to work in small numbers (<100), will work in large numbers.

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

#86

Post by bollu »

syrrim wrote: post #79
_hl_ wrote: post #66

Earlier quoted context omitted.

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 measureme…

>which will allow us to solve some NP hard problems No it won't

> No it won't

We don't know either way. relationship between BPP, BQP, P, NP are all open.

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

#87

Post by [deleted] »

reikonomusha wrote: post #83
fractionalhare wrote: post #81

Earlier quoted context omitted.

The research in this field proceeds under the umbrella and framework of physics, yes. But it's not clear that it's possible to scale up to the number qubits required do anything nontrivial. It's plausible there are hard engineering limits on error correction which make it asymptotically more difficult with each order of magnitude more qubits involved. It might not look that way because there's a lot of (relatively) m…

I think it’s reasonable to be more optimistic than you put it. Qubit counts and qubit fidelity have been increasing at a remarkable rate. Just five years ago we could barely eek out a handful of qubits, and when we did, they’d be bad. Google’s quantum supremacy result is a testament to that. (At this stage, whether they actually demonstrated the “supreme” part of supremacy is, imho, irrelevant. They’ve demonstrated a…

[deleted]

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

#88

Post by Strilanc »

thesz wrote: post #82
Strilanc wrote: post #76

Earlier quoted context omitted.

It's an interesting question whether, over the long term, quantum hardware will match the feature of classical hardware where memory is significantly cheaper than compute-capable bits in the CPU. Hard drives are 100x cheaper per bit than RAM which is 100x cheaper (I think?) per bit than a CPU register. How expensive is quantum memory relative to quantum compute, over the long term? Expectations about the answer to th…

You are off by orders of magnitude. The difference in memory density between DRAM and SRAM (register file) is not 100 times, more like 10x. Standalone "registers" - memory elements of pipelines, state machines etc, - are again not more than ten times less denser than SRAM. After DRAM goes SSD and after SSD goes disk. The difference in price per GB for SSD and disk is about four (4x) times, I looked for that numbers r…

Are you sure? I was just going off a quick search of Amazon, where 1 GB of ram cost ~30$, 1 TB of disk cost ~50$, and a CPU with ~1MB of L2 cache cost ~200$. Based on that I actually thought 100x was a comfortable underestimate, not an overestimate.

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

#89

Post by vbezhenar »

umvi wrote: post #73
unilynx wrote: post #71

Earlier quoted context omitted.

Cashing out and actually getting $50B may be as much of a challenge as finding the private key

Why, do people actively monitor that wallet for activity? I'm assuming if any BTC at all moves out of that wallet it'll cause a massive correction to BTC price as people can no longer assume that those bitcoins are off the market.

I'm sure that enough geeks have all kinds of triggers to spot that kind of activity.

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

#90

Post by PeterisP »

hannob wrote: post #36
PeterisP wrote: post #33

Earlier quoted context omitted.

In common practice RSA keys/certificates are used for TLS and similar protocols where it does not allow to decrypt past recorded communications, as those are encrypted with an ephemeral session keys that can not be determined from observing the handshake even if you have the keys. Obtaining a private key would allow you to MITM future sessions and decrypt them, but it would not break confidentiality of past messages.…

That's not how this works. An attacker can record the key exchange. That is not using RSA, today it's usually some variation of elliptic curve diffie hellman. But that is just as vulnerable to quantum attacks as RSA. So you're attacking the key exchange, not the RSA signature. What you're probably alluding to here is the forward secrecy property of TLS. But that is only true under the assumption that the key exchange…

Interesting, I had assumed that the whole purpose of Diffie-Hellman and the like is to ensure that the ephemeral keys which are generated during the process can't be recovered from recorded traffic even if you later find out the private keys used by the parties. Or is it the case that it's secure from just knowing the private keys, but efficient factorization e.g. Shor's algorithm can break the whole process?
Post reply on HN