{
  "id": "2011.12277",
  "version": "v1",
  "published": "2020-11-24T18:44:57.000Z",
  "updated": "2020-11-24T18:44:57.000Z",
  "title": "Random quantum circuits anti-concentrate in log depth",
  "authors": [
    "Alexander M. Dalzell",
    "Nicholas Hunter-Jones",
    "Fernando G. S. L. Brandão"
  ],
  "comment": "44 pages, 6 figures",
  "categories": [
    "quant-ph",
    "cond-mat.stat-mech",
    "cond-mat.str-el"
  ],
  "abstract": "We consider quantum circuits consisting of randomly chosen two-local gates and study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated, roughly meaning that the probability mass is not too concentrated on a small number of measurement outcomes. Understanding the conditions for anti-concentration is important for determining which quantum circuits are difficult to simulate classically, as anti-concentration has been in some cases an ingredient of mathematical arguments that simulation is hard and in other cases a necessary condition for easy simulation. Our definition of anti-concentration is that the expected collision probability, that is, the probability that two independently drawn outcomes will agree, is only a constant factor larger than if the distribution were uniform. We show that when the 2-local gates are each drawn from the Haar measure (or any two-design), at least $\\Omega(n \\log(n))$ gates (and thus $\\Omega(\\log(n))$ circuit depth) are needed for this condition to be met on an $n$ qudit circuit. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n \\log(n))$ gates are also sufficient, and we precisely compute the optimal constant prefactor for the $n \\log(n)$. The technique we employ relies upon a mapping from the expected collision probability to the partition function of an Ising-like classical statistical mechanical model, which we manage to bound using stochastic and combinatorial techniques.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-11-24T18:44:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random quantum circuits anti-concentrate",
      "log depth",
      "expected collision probability",
      "classical statistical mechanical model",
      "measurement outcomes"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 44,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}