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).
replyQKD can be sold today.
replyThe 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.
> QKD can be sold today.
replyIt 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.