Hacker News Reader

Comment by colordrops | Hacker News Reader

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

View on HN

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.

Ah, walking across glued trees [1]! Not sure of its practical merits however, aha...

[1] - https://arxiv.org/abs/quant-ph/0209131

Grover's?

“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.

I believe 256 bit symmetric keys and hashes are currently recommended because it's double the classically-secure 128 bit.

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.

Cost of qubits does not scale exponentially if we have quantum error correction.

Do you know a proof for that?

I.e., that for n logical qubits, decoherence time goes down polynomially rather than e^(-a n)? AFAIK (and yes, I could be mistaken!) what we deal with is reducing a susbtantially.

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.

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.

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 :-)

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)?

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.

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.

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.

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.

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.

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.

Quantum computing is extremely useful for accurate computational chemistry, which impacts everything from materials science to medicine.

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.

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.

Reply on news.ycombinator.com