10 ms·
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
by 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.