4 ms·

Fair point, but breaking crypto will require quantum computers with millions of qubits. Currently I’m not convinced that we’ve built a decent general quantum c

Fair point, but breaking crypto will require quantum computers with millions of qubits. Currently I’m not convinced that we’ve built a decent general quantum computer with more than five. Long way to go.

xucheng 8y ago
> breaking crypto will require quantum computers with millions of qubits I don’t think this is true. It is estimated that breaking 2048bits RSA only requires 4000 logical qubits (though the number of physical qubits would be much higher). Ref: https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer https://security.stackexchange.com/questions/87345/how-many-...
- throwawaymath 8y ago
  It is true, the parent is talking about physical qubits. By the most recent 2019 estimate (specifically the National Academies report, which was on HN recently, we'll need to increase our current qubit achievements by a factor of at least 10^5. That equates to millions of qubits, because we've currently achieved tens of qubits.
MzxgckZtNqX5i 8y ago
Where does that estimate come from? My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount of qubits (let call it q) such that N^2 =< 2^q =< 2N^2. Right now RSA is at most at 4096 bits, so q=8192 could be enough.
- abdullahkhalids 8y ago
  For building a quantum computer a distinction is made between logical qubits and physical qubits. The physical qubits correspond 1-to-1 with the underlying physical media i.e. each electron spin makes one physical qubit. The physical qubits have a lot of noise, so can't be used directly to do computation. Instead you do error correction on many (3 to millions or more) physical qubits to make one logical qubit that is noise free. These logical qubits are then used to do the actual computation. Your estimate of q=8192 is for logical qubits. The actual physical qubits will realistically go to millions, unless some really fundamental breakthroughs are made.
- throwawaymath 8y ago
  If you'd like a specific, authoritative citation confirming what the other responder is saying, read the National Academies 2019 report on QC.

xucheng 8y ago

> breaking crypto will require quantum computers with millions of qubits I don’t think this is true. It is estimated that breaking 2048bits RSA only requires 4000 logical qubits (though the number of physical qubits would be much higher). Ref: https://security.stackexchange.com/questions/87345/how-many-qubits-are-needed-to-factor-2048-bit-rsa-keys-on-a-quantum-computer https://security.stackexchange.com/questions/87345/how-many-...

throwawaymath 8y ago
It is true, the parent is talking about physical qubits. By the most recent 2019 estimate (specifically the National Academies report, which was on HN recently, we'll need to increase our current qubit achievements by a factor of at least 10^5. That equates to millions of qubits, because we've currently achieved tens of qubits.

MzxgckZtNqX5i 8y ago

Where does that estimate come from? My (basic) understanding is that, in order to find the factorization of a composite N, Shor's algorithm requires an amount of qubits (let call it q) such that N^2 =< 2^q =< 2N^2. Right now RSA is at most at 4096 bits, so q=8192 could be enough.

abdullahkhalids 8y ago
For building a quantum computer a distinction is made between logical qubits and physical qubits. The physical qubits correspond 1-to-1 with the underlying physical media i.e. each electron spin makes one physical qubit. The physical qubits have a lot of noise, so can't be used directly to do computation. Instead you do error correction on many (3 to millions or more) physical qubits to make one logical qubit that is noise free. These logical qubits are then used to do the actual computation. Your estimate of q=8192 is for logical qubits. The actual physical qubits will realistically go to millions, unless some really fundamental breakthroughs are made.
throwawaymath 8y ago
If you'd like a specific, authoritative citation confirming what the other responder is saying, read the National Academies 2019 report on QC.