{
  "id": "0805.0007",
  "version": "v2",
  "published": "2008-04-30T20:16:20.000Z",
  "updated": "2008-05-02T01:31:16.000Z",
  "title": "Superpolynomial speedups based on almost any quantum circuit",
  "authors": [
    "Sean Hallgren",
    "Aram W. Harrow"
  ],
  "comment": "16 pages, 1 figure, to appear in ICALP '08. v2 includes references and acknowledgments",
  "journal": "Proc. of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS 5125, pp. 782-795",
  "doi": "10.1007/978-3-540-70575-8_64",
  "categories": [
    "quant-ph"
  ],
  "abstract": "The first separation between quantum polynomial time and classical bounded-error polynomial time was due to Bernstein and Vazirani in 1993. They first showed a O(1) vs. Omega(n) quantum-classical oracle separation based on the quantum Hadamard transform, and then showed how to amplify this into a n^{O(1)} time quantum algorithm and a n^{Omega(log n)} classical query lower bound. We generalize both aspects of this speedup. We show that a wide class of unitary circuits (which we call dispersing circuits) can be used in place of Hadamards to obtain a O(1) vs. Omega(n) separation. The class of dispersing circuits includes all quantum Fourier transforms (including over nonabelian groups) as well as nearly all sufficiently long random circuits. Second, we give a general method for amplifying quantum-classical separations that allows us to achieve a n^{O(1)} vs. n^{Omega(log n)} separation from any dispersing circuit.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2008-05-02T01:31:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum circuit",
      "superpolynomial speedups",
      "dispersing circuit",
      "sufficiently long random circuits",
      "quantum polynomial time"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2008arXiv0805.0007H"
    }
  }
}