A quantum computer is a new type of computer based on quantum physics. When it comes to certain computational objectives, the computational ability of quantum computers is much stronger than that of the familiar digital computers, and their construction will enable us to factor large integers and to break most of the current cryptosystems.
The question of whether quantum computation is possible is one of the fascinating clear-cut open scientific questions of our time. In my lecture I will explain theoretical discoveries from the 1990s that suggested that quantum computation is possible and present my theory as to why quantum computation is nevertheless impossible.
At the crux of the matter is the study of noisy intermediate scale quantum (NISQ) computers. Based on the mathematical notions of "noise sensitivity vs noise stability" (Benjamini, Kalai, and Schramm 1999, Kalai and Kindler 2014), we identify the inherent noise sensitivity of probability distributions arising from NISQ computers. This leads to a very low complexity class of probability distributions that can be robustly described by such quantum computers; consequently, NISQ computers will not allow good-quality quantum error-correction which are the necessary building blocks for larger quantum computers.
The lecture will be self-contained and will start with a gentle explanation of some basic notions about computation, and quantum computers.
Zoom link: https://pitp.zoom.us/j/93847236670?pwd=T2Z2emZ5ZExaZTVYcTNCdU1FNkxOdz09