  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 $\textsf{NISQ} $, 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 $\textsf{BPP}\subsetneq
\textsf{NISQ}\subsetneq \textsf{BQP}$, by demonstrating super-polynomial oracle
separations among the three classes, based on modifications of Simon's problem.
We then consider the power of $\textsf{NISQ}$ for three well-studied problems.
For unstructured search, we prove that $\textsf{NISQ}$ cannot achieve a
Grover-like quadratic speedup over $\textsf{BPP}$. For the Bernstein-Vazirani
problem, we show that $\textsf{NISQ}$ only needs a number of queries
logarithmic in what is required for $\textsf{BPP}$. Finally, for a quantum
state learning problem, we prove that $\textsf{NISQ}$ is exponentially weaker
than classical computation with access to noiseless constant-depth quantum
circuits.
