The Complexity of NISQ

The recent proliferation of NISQ devices has made it imperative to understand their computational power. In this work, we define and study the complexity class textsfNISQ , which is intended to encapsulate problems that can be efficiently solved by a classical computer with access to a NISQ device. To model existing devices, we assume the device can (1) noisily initialize all qubits, (2) apply many noisy quantum gates, and (3) perform a noisy measurement on all qubits. We first give evidence that textsfBPPsubsetneq textsfNISQsubsetneq textsfBQP, by demonstrating super-polynomial oracle separations among the three classes, based on modifications of Simon's problem. We then consider the power of textsfNISQ for three well-studied problems. For unstructured search, we prove that textsfNISQ cannot achieve a Grover-like quadratic speedup over textsfBPP. For the Bernstein-Vazirani problem, we show that textsfNISQ only needs a number of queries logarithmic in what is required for textsfBPP. Finally, for a quantum state learning problem, we prove that textsfNISQ is exponentially weaker than classical computation with access to noiseless constant-depth quantum circuits.