{
  "id": "1910.11842",
  "version": "v1",
  "published": "2019-10-25T16:57:18.000Z",
  "updated": "2019-10-25T16:57:18.000Z",
  "title": "Computing partition functions in the one clean qubit model",
  "authors": [
    "Anirban N. Chowdhury",
    "Rolando D. Somma",
    "Yigit Subasi"
  ],
  "comment": "12 pages, 2 figures",
  "categories": [
    "quant-ph"
  ],
  "abstract": "We present a method to approximate partition functions of quantum systems using mixed-state quantum computation. For non-negative Hamiltonians, our method runs on average in time almost linear in $(M/(\\epsilon_{\\text{rel}} \\mathcal Z ))^2$, where $M$ is the dimension of the quantum system, $\\mathcal Z$ is the partition function, and $\\epsilon_{\\text{rel}}$ is the relative precision. It is based on approximations of the exponential operator as linear combinations of certain operations related to block-encoding of Hamiltonians or Hamiltonian evolutions. The trace of each operation is estimated using a standard algorithm in the one clean qubit model. For large values of $\\mathcal Z$, our method may run faster than exact classical methods, whose complexities are polynomial in $M$. We also prove that a version of the partition function estimation problem within additive error is complete for the so-called DQC1 complexity class, suggesting that our method provides an exponential speedup. To attain the desired relative precision, we develop a procedure based on a sequence of approximations within predetermined additive errors that may be of independent interest.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-10-25T16:57:18.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "clean qubit model",
      "computing partition functions",
      "quantum system",
      "partition function estimation problem",
      "relative precision"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}