4 ms·

Are there any real Quantum Computers yet?

tromp 4y ago
None that can reliably factor numbers bigger than 21. https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers https://en.wikipedia.org/wiki/Integer_factorization_records#...
- kadoban 4y ago
  That we know of. Machines that can would quickly become important to national security though.
  - api 4y ago
    Not for long: https://csrc.nist.gov/Projects/post-quantum-cryptography https://csrc.nist.gov/Projects/post-quantum-cryptography The cryptographic implications of QC are absurdly exaggerated. QC has no practical impact on symmetric (AES, ChaCha) or hash (SHA2, SHA3, Blake) algorithms. Impact is isolated to number-theoretic asymmetric ciphers of certain types (DH, ECDH, ECDSA, EDDSA, etc.) and even there practical attacks would require very large, fast, low-noise quantum computers. The link I posted above is to a project to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack, rendering the whole thing pretty much moot.
    - pseudo0 4y ago
      Yeah, the hype has been extremely excessive. Putting some investment into quantum-resistant public key cryptography now is a reasonable hedge against the possibility of an surprise breakthrough in the next 10-30 years, but that should be about all we need to future-proof things. Unfortunately "quantum" is still a hot buzzword for managers and non-technical leadership, so it will be diverting resources and attention for the foreseeable future.
    - kadoban 4y ago
      > The cryptographic implications of QC are absurdly exaggerated. Every(?) current TLS session is vulnerable. _Many many_ auth sessions of other types are vulnerable. At least petabytes of stored sessions can be decoded (though not all). It's hard to say how it's exaggerated at all. It's pretty much the device from Sneakers, but real. That it won't break every possible thing for all time is true, but it's still about as huge as any practical thing can be.
    - tromp 4y ago
      > QC has no practical impact on symmetric or hash algorithms It would require a doubling of key lengths to maintain security against quantum Grover search attacks. > to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack That will likely lead to much more than a doubling of key sizes; perhaps two orders of magnitude bigger. It will severely impact resource constrained cryptographic devices such as credit card chips.
      - api 4y ago
        > It would require a doubling of key lengths to maintain security against quantum Grover search attacks. Grover could in theory reduce a 256-bit cipher like AES-256 or ChaCha to a 128-bit cipher. 128 bits is still far beyond what can be brute forced with any sane or practical amount of resources or time. It would mean 128-bit keys would be unsafe, but 256-bit or higher has been recommended for years anyway for reasons beyond QC like birthday attacks. Also keep in mind that this is a theoretical (as in big-O notation) speedup. Real world performance would depend a ton on the speed of the quantum computer. If a QC running Grover's algorithm isn't at least as fast as e.g. a conventional CPU then it might not be much faster in practice than a custom ASIC brute forcing a full strength key. That would make it pretty much an academic demo, not even useful in practice against 128-bit keys.
- dspillett 4y ago
  How reliably can they factor large numbers? Once false positive and complete failure rates are low enough, using one of them to do most of the legwork with traditional electronics to check the result and rerun as needed becomes a potentially useful combination.
- upofadown 4y ago
  ... and without having the answer baked in to the implementation...
- baby 4y ago
  I think even the factorization of 21 was somewhat cheating no? It seems like we’re really a long way off being able to use a QC for anything practical, if ever. And that’s not even talking about cracking crypto.
  - tromp 4y ago
    I agree that a proper demonstration should be of factoring any product of an m-bit prime by an n-bit prime. So if it only worked for 3*7 and not (with the exact same setup) for 3*5 then it shouldn't count. It's sad that no-one has demonstrated a factorization of 4+4 bits (which should include factorizing 55,65,77,91, and 143). That would be an important milestone I think.
    - tengwar2 4y ago
      That's a possible demonstration, but bear in mind that they are also used for more analogue problems such as predicting chemical bond angles, where there is no discrete pass/fail, but rather a measure of how close they got to reality.
      - tromp 4y ago
        True; but those other useful applications of quantum computers are much messier to define and qualify, so factoring is still the ideal application for setting a milestone to be achieved.
simias 4y ago
Sure(1) 1/ Definition of "real", "quantum" and "computer" may vary. More seriously I don't think there's a real bar to what constitutes a "real" quantum computer, so it's in the eye of the beholder at this point I think. As far as I know from publicly available info, there's nothing resembling a practically usable quantum computer yet (as in, a computer that would outperform a conventional one at some practical task).
layer8 4y ago
No practical ones, not by a long stretch. It’s not clear at all if and when there will be ones achieving any measure of quantum supremacy.
mikewave 4y ago
There are real, usable, near-realtime Quantum Annealers, which are different from gate model quantum computers, but have proven to be much more amenable to physical implementation. These are more geared towards optimization functions, which can have practical use for logistics, physics simulations, and more. Gate model computers interest everyone because of the potential to factor large numbers; this could potentially render a lot of existing and past cryptography open to decryption that otherwise will be locked up for aeons, especially considering the apparently decaying effect of Moore's Law of late. However, it probably takes millions or billions of gate qubits to do that, whereas thousands of annealing qubits are enough to solve some interesting problems, and to contribute to finding better solutions when combined with classical compute in a hybrid setup.

None that can reliably factor numbers bigger than 21. https://en.wikipedia.org/wiki/Integer_factorization_records#Records_for_efforts_by_quantum_computers https://en.wikipedia.org/wiki/Integer_factorization_records#...

kadoban 4y ago
That we know of. Machines that can would quickly become important to national security though.
- api 4y ago
  Not for long: https://csrc.nist.gov/Projects/post-quantum-cryptography https://csrc.nist.gov/Projects/post-quantum-cryptography The cryptographic implications of QC are absurdly exaggerated. QC has no practical impact on symmetric (AES, ChaCha) or hash (SHA2, SHA3, Blake) algorithms. Impact is isolated to number-theoretic asymmetric ciphers of certain types (DH, ECDH, ECDSA, EDDSA, etc.) and even there practical attacks would require very large, fast, low-noise quantum computers. The link I posted above is to a project to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack, rendering the whole thing pretty much moot.
  - pseudo0 4y ago
    Yeah, the hype has been extremely excessive. Putting some investment into quantum-resistant public key cryptography now is a reasonable hedge against the possibility of an surprise breakthrough in the next 10-30 years, but that should be about all we need to future-proof things. Unfortunately "quantum" is still a hot buzzword for managers and non-technical leadership, so it will be diverting resources and attention for the foreseeable future.
  - kadoban 4y ago
    > The cryptographic implications of QC are absurdly exaggerated. Every(?) current TLS session is vulnerable. _Many many_ auth sessions of other types are vulnerable. At least petabytes of stored sessions can be decoded (though not all). It's hard to say how it's exaggerated at all. It's pretty much the device from Sneakers, but real. That it won't break every possible thing for all time is true, but it's still about as huge as any practical thing can be.
  - tromp 4y ago
    > QC has no practical impact on symmetric or hash algorithms It would require a doubling of key lengths to maintain security against quantum Grover search attacks. > to create the first NIST-certified asymmetric algorithms believed to not be vulnerable to quantum attack That will likely lead to much more than a doubling of key sizes; perhaps two orders of magnitude bigger. It will severely impact resource constrained cryptographic devices such as credit card chips.
    - api 4y ago
      > It would require a doubling of key lengths to maintain security against quantum Grover search attacks. Grover could in theory reduce a 256-bit cipher like AES-256 or ChaCha to a 128-bit cipher. 128 bits is still far beyond what can be brute forced with any sane or practical amount of resources or time. It would mean 128-bit keys would be unsafe, but 256-bit or higher has been recommended for years anyway for reasons beyond QC like birthday attacks. Also keep in mind that this is a theoretical (as in big-O notation) speedup. Real world performance would depend a ton on the speed of the quantum computer. If a QC running Grover's algorithm isn't at least as fast as e.g. a conventional CPU then it might not be much faster in practice than a custom ASIC brute forcing a full strength key. That would make it pretty much an academic demo, not even useful in practice against 128-bit keys.
dspillett 4y ago
How reliably can they factor large numbers? Once false positive and complete failure rates are low enough, using one of them to do most of the legwork with traditional electronics to check the result and rerun as needed becomes a potentially useful combination.
upofadown 4y ago
... and without having the answer baked in to the implementation...
baby 4y ago
I think even the factorization of 21 was somewhat cheating no? It seems like we’re really a long way off being able to use a QC for anything practical, if ever. And that’s not even talking about cracking crypto.
- tromp 4y ago
  I agree that a proper demonstration should be of factoring any product of an m-bit prime by an n-bit prime. So if it only worked for 3*7 and not (with the exact same setup) for 3*5 then it shouldn't count. It's sad that no-one has demonstrated a factorization of 4+4 bits (which should include factorizing 55,65,77,91, and 143). That would be an important milestone I think.
  - tengwar2 4y ago
    That's a possible demonstration, but bear in mind that they are also used for more analogue problems such as predicting chemical bond angles, where there is no discrete pass/fail, but rather a measure of how close they got to reality.
    - tromp 4y ago
      True; but those other useful applications of quantum computers are much messier to define and qualify, so factoring is still the ideal application for setting a milestone to be achieved.

simias 4y ago

Sure(1) 1/ Definition of "real", "quantum" and "computer" may vary. More seriously I don't think there's a real bar to what constitutes a "real" quantum computer, so it's in the eye of the beholder at this point I think. As far as I know from publicly available info, there's nothing resembling a practically usable quantum computer yet (as in, a computer that would outperform a conventional one at some practical task).

layer8 4y ago

No practical ones, not by a long stretch. It’s not clear at all if and when there will be ones achieving any measure of quantum supremacy.

mikewave 4y ago

There are real, usable, near-realtime Quantum Annealers, which are different from gate model quantum computers, but have proven to be much more amenable to physical implementation. These are more geared towards optimization functions, which can have practical use for logistics, physics simulations, and more. Gate model computers interest everyone because of the potential to factor large numbers; this could potentially render a lot of existing and past cryptography open to decryption that otherwise will be locked up for aeons, especially considering the apparently decaying effect of Moore's Law of late. However, it probably takes millions or billions of gate qubits to do that, whereas thousands of annealing qubits are enough to solve some interesting problems, and to contribute to finding better solutions when combined with classical compute in a hybrid setup.