Mathematics Colloquium

Noise sensitivity, Fourier, and the quantum computer puzzle

Speaker: Gil Kalai, Hebrew University of Jerusalem, Reichman University and NYU

Location: Warren Weaver Hall 1302

Date: Monday, November 8, 2021, 3:45 p.m.

Synopsis:

I will start with the analysis of Boolean functions and the related theory of noise stability and noise sensitivity. Next, I will discuss the sensitivity of noisy intermediate scale quantum (NISQ) computers, and explain why NISQ computers are computationally primitive and incapable of demonstrating neither "quantum computational advantage" nor the harder task of quantum error-correction. Finally, I will briefly discuss recent papers claiming a huge quantum computational advantage for NISQ systems which appears to be in sharp contrast with my theory.