5 ms·

Unfortunately I work in cryptography, and breaking our algorithms is one of the tasks that requires the least number of qubits. And that doesn't depend on havin

Unfortunately I work in cryptography, and breaking our algorithms is one of the tasks that requires the least number of qubits. And that doesn't depend on having a desktop quantum computer either, but only that a single state actor anywhere has a sufficiently large quantum computer. I'm a bit bitter that physics handed us this magical tool, and the best we managed so far is using it to invalidate decades of security research.

lupire 4y ago
How many qubits vs larger keys?
- BoppreH 4y ago
  I'm afraid the number of qubits doesn't grow fast enough. Here's[1] a tongue in cheek "Post-Quantum RSA" with 2 Terabit keys. [1] https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf
JanisErdmanis 4y ago
It's rather easy to produce qubits and place them in a box. The hard part is to make them interact with each other in a controlled fashion thus, adding one qubit to a large system is substantially harder than adding it to a small one. The only true benchmark is a factorisation of numbers. Number 21 has been factorised with nudging. Let's wait for a number 45 in the coming next decade.
hannob 4y ago
> Unfortunately I work in cryptography, and breaking our algorithms is one of the tasks that requires the least number of qubits I don't think that is true (or maybe I'm underestimating how many qbits other uses of QCs take). Estimates are still in the many millions: https://cacm.acm.org/news/237303-how-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/fulltext https://cacm.acm.org/news/237303-how-quantum-computer-could-...
- BoppreH 4y ago
  That's from three years ago, and for error-corrected RSA breaking. ECC has keys an order of magnitude smaller, and minimizing the number of quits to run Shor's is a hot area. And compared to other uses (quantum AI anyone?), it's surprisingly compact.
- tromp 4y ago
  You only need a few thousand error-free qubits to implement Shor's algorithm for 256-bit Elliptic Curve Discrete Log, that will for instance break nearly all crypto. The "millions" is trying to account for the several orders of magnitude error correcting overhead.
  - naasking 4y ago
    Error-free qubits are a fantasy, error correction is a must. I'm not particularly worried about quantum computers breaking crypto anytime soon.
  - tsimionescu 4y ago
    The difficulty of adding qubits increases super-linearly with the number of qubits (especially because of communication delay vs time to decoherence) , so "only" a few thousand is already very optimistic. Worse, the idea of "error-free qubits" is essentially like cold fusion - you can say the words and we understand what you mean by them, but they don't describe anything that can exist in practice.
    - billti 4y ago
      > The difficulty of adding qubits increases super-linearly with the number of qubits Is that true? Hardware from the likes of IBM and IonQ has already gone from < 10 to >= 20 “algorithmic qubits” [1] in the space of a few year. [1] https://ionq.com/quantum-systems/aria https://ionq.com/quantum-systems/aria
  - hannob 4y ago
    Sure, I just don't think error-free qubits are a thing (or will be in the future). I don't think anyone seriously expects quantum computing to work without error correction.

lupire 4y ago

How many qubits vs larger keys?

BoppreH 4y ago
I'm afraid the number of qubits doesn't grow fast enough. Here's[1] a tongue in cheek "Post-Quantum RSA" with 2 Terabit keys. [1] https://cr.yp.to/papers/pqrsa-20170419.pdf https://cr.yp.to/papers/pqrsa-20170419.pdf

JanisErdmanis 4y ago

It's rather easy to produce qubits and place them in a box. The hard part is to make them interact with each other in a controlled fashion thus, adding one qubit to a large system is substantially harder than adding it to a small one. The only true benchmark is a factorisation of numbers. Number 21 has been factorised with nudging. Let's wait for a number 45 in the coming next decade.

hannob 4y ago

> Unfortunately I work in cryptography, and breaking our algorithms is one of the tasks that requires the least number of qubits I don't think that is true (or maybe I'm underestimating how many qbits other uses of QCs take). Estimates are still in the many millions: https://cacm.acm.org/news/237303-how-quantum-computer-could-break-2048-bit-rsa-encryption-in-8-hours/fulltext https://cacm.acm.org/news/237303-how-quantum-computer-could-...

BoppreH 4y ago
That's from three years ago, and for error-corrected RSA breaking. ECC has keys an order of magnitude smaller, and minimizing the number of quits to run Shor's is a hot area. And compared to other uses (quantum AI anyone?), it's surprisingly compact.
tromp 4y ago
You only need a few thousand error-free qubits to implement Shor's algorithm for 256-bit Elliptic Curve Discrete Log, that will for instance break nearly all crypto. The "millions" is trying to account for the several orders of magnitude error correcting overhead.
- naasking 4y ago
  Error-free qubits are a fantasy, error correction is a must. I'm not particularly worried about quantum computers breaking crypto anytime soon.
- tsimionescu 4y ago
  The difficulty of adding qubits increases super-linearly with the number of qubits (especially because of communication delay vs time to decoherence) , so "only" a few thousand is already very optimistic. Worse, the idea of "error-free qubits" is essentially like cold fusion - you can say the words and we understand what you mean by them, but they don't describe anything that can exist in practice.
  - billti 4y ago
    > The difficulty of adding qubits increases super-linearly with the number of qubits Is that true? Hardware from the likes of IBM and IonQ has already gone from < 10 to >= 20 “algorithmic qubits” [1] in the space of a few year. [1] https://ionq.com/quantum-systems/aria https://ionq.com/quantum-systems/aria
- hannob 4y ago
  Sure, I just don't think error-free qubits are a thing (or will be in the future). I don't think anyone seriously expects quantum computing to work without error correction.