The Complexity of NISQ

The opportunities provided by contemporary quantum devices and the challenges they engender have invigorated theorists and experimentalists alike, ushering in a new age of research into quantum computation referred to as the NISQ (noisy intermediate-scale quantum) era. Computation in the NISQ era is facilitated by hybrid quantum-classical algorithms: a classical computer repeatedly runs a noisy quantum device with various gate sequences to obtain different classical output bitstrings, and then performs classical post-processing on those strings. This state of affairs suggests fundamental questions: How powerful are these NISQ algorithms compared to classical algorithms? Are NISQ algorithms inherently weaker than fault-tolerant quantum algorithms? In this talk we formalize and study these questions through the lens of computational complexity theory. Our findings suggest that NISQ algorithms can be super-polynomially more powerful than classical algorithms, but super-polynomially weaker than fault-tolerant quantum computation. We further analyze the power of NISQ algorithms for three well-studied problems: unstructured search, the Bernstein-Vazirani problem, and quantum state learning. Our proof techniques leverage and extend recent advances in quantum learning theory.