News for hackers. Stuff that matters.
Re:2025 Turing Award given for Quantum Information Science by bawolff on Wednesday March 18, 2026 @02:11PM (#47429223)
> Bennett and Brassard, with Ethan Bernstein and Umesh Vazirani, showed that in black-box setting, quantum computers would require big-omega(sqrt(n)) queries to search n entries, matching Grover's algorithm. For some reason, the popular press rarely covers these results that limit the power of quantum computing.

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.

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.