Re:2025 Turing Award given for Quantum Information Science
by shorden on Wednesday March 18, 2026 @03:50PM
(#47430582)
Worth noting that this is a bound on arbitrary search, but there exist some problems with structure (e.g. integer factorization) for which quantum algorithms are exponentially faster than known classical algorithms (a problem believed to be in NP and BQP but not P).
Re:2025 Turing Award given for Quantum Information Science
by shemnon42 on Wednesday March 18, 2026 @03:07PM
(#47430073)
QKD can be sold today.
The quantum computers are not quite large enough to search at an `n` such that O(n)` is not viable but `O(sqrt(n))` is, that's where there's money to be made, especially if viability is defined by small time horizons. So it's a footnote for the future.
Re:2025 Turing Award given for Quantum Information Science
by bawolff on Wednesday March 18, 2026 @03:16PM
(#47430189)
> QKD can be sold today.
It can, but it isn't largely because the classical solutions solve the problem better and you usually have to resort to classical solutions to solve MITM anyways afaik. However my point is less about practicality and more QKD seems more like a physics or engineering thing and not a computer science thing.
After all, this is supposed to be a computer science prize not a make money prize, so which is more sellable should be besides the point.
This is mentioned almost as a footnote, but to (layman) me seems much more important than QKD, especially from a comp sci perspective instead of a physics perspective.