The Argument Against Quantum Computers

About

We give a computational complexity argument against the feasibility of quantum computers. We identify a very low complexity class of probability distributions described by noisy intermediate-scale quantum computers, and explain why it will allow neither good-quality quantum error-correction (1) nor a demonstration of "quantum supremacy" (2). Some general principles governing the behavior of noisy quantum systems are derived. The argument crucially relies on the study by Kalai and Kindler (2014) of noise stability and sensitivity for systems of non-interacting bosons. This study is built on the theory of noise stability and noise sensitivity of Boolean functions developed by Benjamini, Kalai, and Schramm (1999). The argument, which is strictly within the framework of quantum mechanics, predicts the failure of near-term experimental goals of many groups around the world to demonstrate on NISQ computers quantum supremacy and good-quality quantum error-correcting codes. The lecture will be self contained and will start with a gentle explanation of some basic notions about computation, and quantum computers.

(1) Quantum error-correction codes are remarkable quantum states that are needed for large scale fault-tolerant quantum computers.

(2) Quantum supremacy refers to the ability of quantum computers to perform certain tasks that classical computers cannot perform. .

0:00:00 Slide 1

0:01:22 Slide 2

0:02:19 Slide 3

0:03:41 Slide 4

0:04:31 Slide 5

0:05:35 Slide 6

0:07:24 Slide 7

0:08:04 Slide 8

0:10:25 Slide 9