{
  "id": "2210.07234",
  "version": "v1",
  "published": "2022-10-13T17:58:32.000Z",
  "updated": "2022-10-13T17:58:32.000Z",
  "title": "The Complexity of NISQ",
  "authors": [
    "Sitan Chen",
    "Jordan Cotler",
    "Hsin-Yuan Huang",
    "Jerry Li"
  ],
  "comment": "15+37 pages, 3 figures",
  "categories": [
    "quant-ph",
    "cs.CC",
    "cs.IT",
    "cs.LG",
    "math.IT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-10-13T17:58:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "complexity",
      "nisq device",
      "demonstrating super-polynomial oracle separations",
      "noiseless constant-depth quantum circuits",
      "quantum state learning problem"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 37,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}