3 ms·

I think this is a likely outcome, and it's a reason why we should be continuing research into so-called "post-quantum" cryptosystems. Where there exists a low-c

I think this is a likely outcome, and it's a reason why we should be continuing research into so-called "post-quantum" cryptosystems. Where there exists a low-cost quantum computing algorithm, it seems possible that there is a similarly low-cost probablistic algorithm. Randomized and probablistic algorithms are in my opinion the most important area for future development in computer science. One hope is that the vocabulary and syntax of quantum computing can be used to create classical probablistic simulations directly that will result in solving all but the most combinatorially explosive cases of various problems.

krastanov 4y ago
No, it really does not seem like a likely outcome. There are way too many small "coincidences" that point to a substantial separation between complexity classes like BQP and BPP. On the other hand, it is indeed incredibly exciting to see all the progress in derandomization of classical probabilistic algorithms and de-quantization of some quantum algorithms (in particular, all the initial ideas in quantum machine learning). Also, it seems most computational complexity theorists do not believe probabilistic algorithms (BPP) are more powerful than deterministic ones (P), and the details of this process of de-randomization are absolutely fascinating. E.g. how we found a deterministic prime-testing algorithm after decades of relying on the random ones. Or deterministic algorithms for creation of expander graphs. There is no equivalent to such derandomization techniques in the quantum case. Quantum and classical probabilities are just too different. Also, post-quantum cryptosystems have very little to do with finding classical counterparts of quantum algorithms.