{
  "id": "1511.02306",
  "version": "v1",
  "published": "2015-11-07T05:42:01.000Z",
  "updated": "2015-11-07T05:42:01.000Z",
  "title": "Quantum linear systems algorithm with exponentially improved dependence on precision",
  "authors": [
    "Andrew M. Childs",
    "Robin Kothari",
    "Rolando D. Somma"
  ],
  "comment": "28 pages",
  "categories": [
    "quant-ph"
  ],
  "abstract": "Harrow, Hassidim, and Lloyd showed that for a suitably specified $N \\times N$ matrix $A$ and $N$-dimensional vector $\\vec{b}$, there is a quantum algorithm that outputs a quantum state proportional to the solution of the linear system of equations $A\\vec{x}=\\vec{b}$. If $A$ is sparse and well-conditioned, their algorithm runs in time $\\mathrm{poly}(\\log N, 1/\\epsilon)$, where $\\epsilon$ is the desired precision in the output state. We improve this to an algorithm whose running time is polynomial in $\\log(1/\\epsilon)$, exponentially improving the dependence on precision while keeping essentially the same dependence on other parameters. Our algorithm is based on a general technique for implementing any operator with a suitable Fourier or Chebyshev series representation. This allows us to bypass the quantum phase estimation algorithm, whose dependence on $\\epsilon$ is prohibitive.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-11-07T05:42:01.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quantum linear systems algorithm",
      "dependence",
      "quantum phase estimation algorithm",
      "quantum state proportional",
      "chebyshev series representation"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 28,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151102306C"
    }
  }
}