{
  "id": "2008.06478",
  "version": "v1",
  "published": "2020-08-14T17:31:12.000Z",
  "updated": "2020-08-14T17:31:12.000Z",
  "title": "Quantum advantage for computations with limited space",
  "authors": [
    "Dmitri Maslov",
    "Jin-Sung Kim",
    "Sergey Bravyi",
    "Theodore J. Yoder",
    "Sarah Sheldon"
  ],
  "comment": "10 pages, 5 figures",
  "categories": [
    "quant-ph",
    "cs.ET"
  ],
  "abstract": "Quantum computations promise the ability to solve problems intractable in the classical setting. Restricting the types of computations considered often allows to establish a provable theoretical advantage by quantum computations, and later demonstrate it experimentally. In this paper, we consider space-restricted computations, where input is a read-only memory and only one (qu)bit can be computed on. We show that $n$-bit symmetric Boolean functions can be implemented exactly through the use of quantum signal processing as restricted space quantum computations using $O(n^2)$ gates, but some of them may only be evaluated with probability $\\frac{1}{2} {+} \\tilde{O}(\\frac{1}{\\sqrt{n}})$ by analogously defined classical computations. We experimentally demonstrate computations of $3$- and a $4$-bit symmetric Boolean functions by quantum circuits, leveraging custom two-qubit gates, with algorithmic success probability exceeding the best possible classically. This establishes and experimentally verifies a different kind of quantum advantage -- one where a quantum bit stores more useful information for the purpose of computation than a classical bit. This suggests that in computations, quantum scrap space is more valuable than analogous classical space and calls for an in-depth exploration of space-time tradeoffs in quantum circuits.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-08-14T17:31:12.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum advantage",
      "bit symmetric boolean functions",
      "limited space",
      "quantum circuits",
      "restricted space quantum computations"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 10,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}