4 ms·

Is prime factoring (e.g. Shor's algorithm) not a clear example of where quantum computers would clearly outperform classical ones? Why the skepticism?

gaugefield 2y ago
Are you talking about the skepticism from Kalai or more general skepticism (from wider group people, which is more about its application to optimization problem, not prime factoring)?
foota 2y ago
I think the goal here is to find more useful algorithms that benefit from quantum computing. Being able to factor primes efficiently is only useful for the sake of the cryptographers' job security :-)
whysosadge 2y ago
I’m exaggerating a lot here, but one concern people have with quantum computing is what if it breaks all cryptography, but doesn’t help us solve “useful” problems. The what if is pulling a lot of weight here but I hope it makes my point.
- zelphirkalt 2y ago
  I guess that would be about asymmetrical encryption. Which is today indispensable for a lot of infrastructure. Still, there's symmetrical encryption, which is mostly untouched by Shor's algorithm.
  - jfengel 2y ago
    Symmetrical encryption requires key distribution, which presents new areas of attack. Though there is also quantum key distribution, which will probably be solved as soon as quantum algorithms can break classical encryption.
    - pclmulqdq 2y ago
      QKD is essentially a layer 1 protocol. It's not in the same realm as symmetric key establishment. That said, there are quantum-resistant key establishment algorithms out there, and more likely one of them will be selected.
    - fsh 2y ago
      QKD also needs key distribution to prevent MITM attacks. It behaves almost exactly like a classical stream cypher, except that it cannot be package-routed, is many orders of magnitude slower, and is prone to side-channel attacks.
  - whysosadge 2y ago
    Depending on the use case. Symmetric crypto varies. For example, if your source only has 100 bits of classical entropy. For example, fuzzy extractors. It becomes manageable to break it now with a QC.
- adastra22 2y ago
  Quantum computing is extremely useful for accurate computational chemistry, which impacts everything from materials science to medicine.
  - gaugefield 2y ago
    That statement alone does not paint the whole picture. It also has to be better in terms of some metric (e.g. accuracy, computation time, size of molecules simulatable) when compared to classical ones.
    - adastra22 2y ago
      It makes accurate simulation of quantum mechanical systems of relevance (e.g. molecules) even possible. DFT simulations are full of approximations just to get them to be able to run on classical supercomputers. Nobody does a full solution of Schrödinger's equation. With a sufficiently sized quantum computer, you could.
stared 2y ago
The issue is that, apart from the Shor’s algorithm, it is hard to find a quantum algorithm, substantially faster than a classical one. Moreover, since cost of qubits scale exponentially, a slight reduction in the power of a polynomial-time algorithm is not enough to offer a practical benefit.
- kvathupo 2y ago
  Ah, walking across glued trees [1]! Not sure of its practical merits however, aha... [1] - https://arxiv.org/abs/quant-ph/0209131 https://arxiv.org/abs/quant-ph/0209131
- HappMacDonald 2y ago
  Grover's?
  - adastra22 2y ago
    “Substantially better” is doing the heavy lifting there. Grover’s gets you a sqrt speedup. Double the size of your hash function (SHA512 instead of SHA256) and you’re protected.
    - AgentME 2y ago
      I believe 256 bit symmetric keys and hashes are currently recommended because it's double the classically-secure 128 bit.
      - adastra22 2y ago
        Because there is a different sqrt speedup concern regarding the birthday paradox / collision resistance. These combine with Grover's to get you a O(N^(1/3)) speedup when finding a collision, making a 256-bit hash have ~85 bits of security against a quantum adversary. You'd need to switch to a 384 bit hash function to keep a 128-bit security threshold. In practice, this means SHA-512.
- adastra22 2y ago
soganess 2y ago
Factoring hasn't been shown to be NP-complete. It maybe the case that it's in P (and we just don't have an algo yet) or it maybe the case that it is an NP intermediate problem.
hannob 2y ago
I think it's clear that factoring works if you can build a scalable quantum computer. But: 1. It's a very lonely example. 2. It's not clear how big the market is for "you can break encryption from the past, but not current encryption, because once QCs arrive, everyone will obviously move away from QC-breakable encryption". And I'm not aware of any other reasons why factoring large numbers would be useful beyond breaking encryptions.

gaugefield 2y ago

Are you talking about the skepticism from Kalai or more general skepticism (from wider group people, which is more about its application to optimization problem, not prime factoring)?

foota 2y ago

I think the goal here is to find more useful algorithms that benefit from quantum computing. Being able to factor primes efficiently is only useful for the sake of the cryptographers' job security :-)

whysosadge 2y ago

I’m exaggerating a lot here, but one concern people have with quantum computing is what if it breaks all cryptography, but doesn’t help us solve “useful” problems. The what if is pulling a lot of weight here but I hope it makes my point.

zelphirkalt 2y ago
I guess that would be about asymmetrical encryption. Which is today indispensable for a lot of infrastructure. Still, there's symmetrical encryption, which is mostly untouched by Shor's algorithm.
- jfengel 2y ago
  Symmetrical encryption requires key distribution, which presents new areas of attack. Though there is also quantum key distribution, which will probably be solved as soon as quantum algorithms can break classical encryption.
  - pclmulqdq 2y ago
    QKD is essentially a layer 1 protocol. It's not in the same realm as symmetric key establishment. That said, there are quantum-resistant key establishment algorithms out there, and more likely one of them will be selected.
  - fsh 2y ago
    QKD also needs key distribution to prevent MITM attacks. It behaves almost exactly like a classical stream cypher, except that it cannot be package-routed, is many orders of magnitude slower, and is prone to side-channel attacks.
- whysosadge 2y ago
  Depending on the use case. Symmetric crypto varies. For example, if your source only has 100 bits of classical entropy. For example, fuzzy extractors. It becomes manageable to break it now with a QC.
adastra22 2y ago
Quantum computing is extremely useful for accurate computational chemistry, which impacts everything from materials science to medicine.
- gaugefield 2y ago
  That statement alone does not paint the whole picture. It also has to be better in terms of some metric (e.g. accuracy, computation time, size of molecules simulatable) when compared to classical ones.
  - adastra22 2y ago
    It makes accurate simulation of quantum mechanical systems of relevance (e.g. molecules) even possible. DFT simulations are full of approximations just to get them to be able to run on classical supercomputers. Nobody does a full solution of Schrödinger's equation. With a sufficiently sized quantum computer, you could.

stared 2y ago

The issue is that, apart from the Shor’s algorithm, it is hard to find a quantum algorithm, substantially faster than a classical one. Moreover, since cost of qubits scale exponentially, a slight reduction in the power of a polynomial-time algorithm is not enough to offer a practical benefit.

kvathupo 2y ago
Ah, walking across glued trees [1]! Not sure of its practical merits however, aha... [1] - https://arxiv.org/abs/quant-ph/0209131 https://arxiv.org/abs/quant-ph/0209131
HappMacDonald 2y ago
Grover's?
- adastra22 2y ago
  “Substantially better” is doing the heavy lifting there. Grover’s gets you a sqrt speedup. Double the size of your hash function (SHA512 instead of SHA256) and you’re protected.
  - AgentME 2y ago
    I believe 256 bit symmetric keys and hashes are currently recommended because it's double the classically-secure 128 bit.
    - adastra22 2y ago
      Because there is a different sqrt speedup concern regarding the birthday paradox / collision resistance. These combine with Grover's to get you a O(N^(1/3)) speedup when finding a collision, making a 256-bit hash have ~85 bits of security against a quantum adversary. You'd need to switch to a 384 bit hash function to keep a 128-bit security threshold. In practice, this means SHA-512.
adastra22 2y ago

soganess 2y ago

Factoring hasn't been shown to be NP-complete. It maybe the case that it's in P (and we just don't have an algo yet) or it maybe the case that it is an NP intermediate problem.

hannob 2y ago

I think it's clear that factoring works if you can build a scalable quantum computer. But: 1. It's a very lonely example. 2. It's not clear how big the market is for "you can break encryption from the past, but not current encryption, because once QCs arrive, everyone will obviously move away from QC-breakable encryption". And I'm not aware of any other reasons why factoring large numbers would be useful beyond breaking encryptions.