{
  "id": "2007.10885",
  "version": "v1",
  "published": "2020-07-21T15:16:28.000Z",
  "updated": "2020-07-21T15:16:28.000Z",
  "title": "Epsilon-nets, unitary designs and random quantum circuits",
  "authors": [
    "Michał\\ Oszmaniec",
    "Adam Sawicki",
    "Michał\\ Horodecki"
  ],
  "comment": "21.5 pages + 13 pages of appendix, 2 figures, comments and suggestions are welcome",
  "categories": [
    "quant-ph",
    "math-ph",
    "math.MP"
  ],
  "abstract": "Epsilon-nets and approximate unitary $t$-designs are natural notions that capture properties of unitary operations relevant for numerous applications in quantum information and quantum computing. The former constitute subsets of unitary channels that are epsilon-close to any unitary channel. The latter are ensembles of unitaries that (approximately) recover Haar averages of polynomials in entries of unitary channels up to order $t$. In this work we establish quantitative connections between these two seemingly different notions. Specifically, we prove that, for a fixed dimension $d$ of the Hilbert space, unitaries constituting $\\delta$-approximate $t$-expanders form $\\epsilon$-nets in the set of unitary channels for $t\\simeq\\frac{d^{5/2}}{\\epsilon}$ and $\\delta\\simeq(\\epsilon/C)^{\\frac{d^2}{2}}$, where $C$ is a numerical constant. Conversely, we show that $\\epsilon$-nets with respect to this metric can be used to construct $\\delta$-approximate unitary $t$-expanders for $\\delta\\simeq\\epsilon t$. We further apply our findings in conjunction with the recent results of [Varju, 2013] in the context of quantum computing. First, we show that that approximate t-designs can be generated by shallow random circuits formed from a set of universal two-qudit gates in the parallel and sequential local architectures considered in [Brandao-Harrow-Horodecki, 2016]. Importantly, our gate sets need not to be symmetric (i.e. contains gates together with their inverses) or consist of gates with algebraic entries. Second, we consider a problem of compilation of quantum gates and prove a non-constructive version of the Solovay-Kitaev theorem for general universal gate sets. Our main technical contribution is a new construction of efficient polynomial approximations to the Dirac delta in the space of quantum channels, which can be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-07-21T15:16:28.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "random quantum circuits",
      "unitary designs",
      "unitary channel",
      "epsilon-nets",
      "approximate unitary"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 5,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}