Complexity foundations for noisy intermediate scale quantum (NISQ) computers

The defining features of quantum systems today are noise and limited system sizes. A fundamental question in this era of noisy intermediate-scale quantum computers (NISQ) is whether these limitations render any demonstration of quantum advantage with these systems useless, or whether some advantage is still salvageable for specific tasks. In this talk, I will give a broad overview of the state-of-the-art of NISQ computation, from the perspective of a complexity theorist. 

I will touch upon complexity theoretic hardness and easiness results for random circuit sampling and optimization tasks—which are two popular paradigms to demonstrate quantum advantage with NISQ devices—under different noise and hardware models. I will also cover the challenges to benchmark and verify any quantum advantage demonstration. My talk aims to inform the audience of the advances and disappointments in the ongoing quest to conclusively demonstrate that quantum computers, even with their many present limitations, beat their classical counterparts.

About the Speaker:
Soumik Ghosh is a third-year Ph.D. student at the Department of Computer Science, University of Chicago, where he is advised by Professor Bill Fefferman. His main topics of research include quantum complexity theory, quantum cryptography, and near-term quantum computation. Previously, he obtained his master’s degree in Computer Science at the University of Waterloo in 2020, where he was advised by Professor John Watrous. He obtained his bachelor’s degree in Electronics and Telecommunication Engineering at Jadavpur University in 2018.