{
  "id": "1409.7447",
  "version": "v1",
  "published": "2014-09-26T00:28:36.000Z",
  "updated": "2014-09-26T00:28:36.000Z",
  "title": "Near invariance of the hypercube",
  "authors": [
    "Scott Aaronson",
    "Hoi Nguyen"
  ],
  "comment": "28p",
  "categories": [
    "math.CO",
    "math.PR"
  ],
  "abstract": "We give an almost-complete description of orthogonal matrices $M$ of order $n$ that \"rotate a non-negligible fraction of the Boolean hypercube $C_n=\\{-1,1\\}^n$ onto itself,\" in the sense that $$P_{x\\in C_n}(Mx\\in C_n) \\ge n^{-C},\\mbox{ for some positive constant } C,$$ where $x$ is sampled uniformly over $C_n$. In particular, we show that such matrices $M$ must be very close to products of permutation and reflection matrices. This result is a step toward characterizing those orthogonal and unitary matrices with large permanents, a question with applications to linear-optical quantum computing.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-09-26T00:28:36.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "invariance",
      "almost-complete description",
      "orthogonal matrices",
      "boolean hypercube",
      "reflection matrices"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1409.7447A"
    }
  }
}