4 ms·

I'm not pessimistic about them. I'm actually (weakly) pessimistic I'll see significant cryptographic breaks due to large scale quantum computers within thirty y

I'm not pessimistic about them. I'm actually (weakly) pessimistic I'll see significant cryptographic breaks due to large scale quantum computers within thirty years. We are very, very far off from quantum computers that can break RSA or even elliptic curve systems (which are a bit easier to break for quantum computers). Google's Bristlecone has 72 physical qubits but I don't recall seeing any published information about how many logical qubits they managed to achieve. Shor's algorithm requires O(n^3) time and 3n logical qubits to break an n-bit key. The state of the art in quantum error correction requires high tens of thousands to low hundreds of thousands of physical qubits to achieve the logical qubits needed to break a typical 2048-bit RSA semiprime. 4096-bit keys are even farther off. Research in post-quantum cryptography is really important, but I think you should take most of the non-scientific reporting about quantum computing and cryptography with a (large) grain of salt. The Economist is actually very level headed in its coverage here and it still neglects to mention that realistically we're far off, even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade. I also think you're being too uncharitable to post-quantum cryptography. You'll find that many of the lattice-based systems (particular the various flavors of LWE) are very fast (and getting faster) and perform reasonably well in real world experiments. I'm cautiously optimistic we'll have lattice-based schemes with keys smaller by an order of magnitude in a decade, and very optimistic we'll have achieved that before 2048-bit RSA can be broken on a quantum computer.

scottlocklin 8y ago
Quantum computers have been factoring the number 15 for 20 years now; seems like you're being kind of overly pessimistic. /sarcasm
lisper 8y ago
> even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade You seem to be ignoring the possibility of a technological breakthrough that will produce a major improvement in QEC in one fell swoop. Granted that is unlikely, but it's not impossible. And given what is at stake, I think it's a possibility that needs to be taken seriously despite the long odds.
- throwawaymath 8y ago
  I'm not ignoring that, I'm just treating it exactly as it is: very unlikely. All sorts of things could happen, but what could happen - independent of quantifiable likelihood - is not a realistic baseline for a risk modeling exercise.
  - lisper 8y ago
    > what could happen - independent of quantifiable likelihood - is not a realistic baseline for a risk modeling exercise. Except in the case where the result of a low-likelihood event is potentially catastrophic, c.f. Fukushima.
    - throwawaymath 8y ago
      That's not comparable. Fukushima's failure was due to fairly basic and straightforward precautions being in error or missing entirely. In other words they were avoidable, known knowns. In contrast we do not actually know how to achieve a breakthrough in quantum error correction except through the normal course of research. We don't just have known unknowns presenting obstacles to the path forward, we have unknown unknowns which must be resolved before further breakthroughs can be achieved. For that reason postulating when and how we'll have a giant leap forward in quantum error correction is closer to thinking about how to resolve the Riemann Hypothesis or Navier-Stokes, or when a deadly asteroid might finally be on a collision path with Earth. It's reasonable to be concerned about quantum computing's risk to cryptography, but it's infeasible to productively model whether or not we'll suddenly jump forwards by decades in research time. To state this another way: if the most informed thing you can state about the likelihood of an event is that it could happen, it's probably not feasible to model the likelihood of that event in a way that makes risk assessment productive.

scottlocklin 8y ago

Quantum computers have been factoring the number 15 for 20 years now; seems like you're being kind of overly pessimistic. /sarcasm

lisper 8y ago

> even if we can achieve 50% improvements in quantum error correction and stability year over year for over a decade You seem to be ignoring the possibility of a technological breakthrough that will produce a major improvement in QEC in one fell swoop. Granted that is unlikely, but it's not impossible. And given what is at stake, I think it's a possibility that needs to be taken seriously despite the long odds.

throwawaymath 8y ago
I'm not ignoring that, I'm just treating it exactly as it is: very unlikely. All sorts of things could happen, but what could happen - independent of quantifiable likelihood - is not a realistic baseline for a risk modeling exercise.
- lisper 8y ago
  > what could happen - independent of quantifiable likelihood - is not a realistic baseline for a risk modeling exercise. Except in the case where the result of a low-likelihood event is potentially catastrophic, c.f. Fukushima.
  - throwawaymath 8y ago
    That's not comparable. Fukushima's failure was due to fairly basic and straightforward precautions being in error or missing entirely. In other words they were avoidable, known knowns. In contrast we do not actually know how to achieve a breakthrough in quantum error correction except through the normal course of research. We don't just have known unknowns presenting obstacles to the path forward, we have unknown unknowns which must be resolved before further breakthroughs can be achieved. For that reason postulating when and how we'll have a giant leap forward in quantum error correction is closer to thinking about how to resolve the Riemann Hypothesis or Navier-Stokes, or when a deadly asteroid might finally be on a collision path with Earth. It's reasonable to be concerned about quantum computing's risk to cryptography, but it's infeasible to productively model whether or not we'll suddenly jump forwards by decades in research time. To state this another way: if the most informed thing you can state about the likelihood of an event is that it could happen, it's probably not feasible to model the likelihood of that event in a way that makes risk assessment productive.