A personal view on quantum computation and cryptography and an interactive discussion

Abstract

Recently, there have been rapid and exciting developments in quantum computing technology with the promise to revolutionize our world in a not-to-distance future. However,? it is not yet clear that at what pace and in which ways quantum computation will start to impact our world. In this talk, I will share my (relatively conservative) view on the near-term impact of quantum computation from a theoretical computer science perspective. Instead of presenting my view in the whole talk, I will give a short presentation and be open to an interactive discussion. I hope it can lead to interesting discussions on what to expect for the applications of quantum computation. The presentation and the discussion are expected to be conceptual and non-technical. ?In the short presentation, I will classify algorithms into provable and heuristic types and discuss the role of provable and heuristic classical algorithms in modern (classical) computations. Based on it, I will discuss the potential role of provable and heuristic quantum algorithms in future quantum computation. Then I will discuss how current quantum computing technology facilitates the development of both types of algorithms and my personal view on what to expect for the first real-world applications of quantum computation.If time permits, I will also give a high-level presentation on how does quantum power impact the landscape of cryptography.