{
  "id": "1509.09271",
  "version": "v1",
  "published": "2015-09-30T17:47:39.000Z",
  "updated": "2015-09-30T17:47:39.000Z",
  "title": "Optimal quantum algorithm for polynomial interpolation",
  "authors": [
    "Andrew M. Childs",
    "Wim van Dam",
    "Shih-Han Hung",
    "Igor E. Shparlinski"
  ],
  "comment": "16 pages",
  "categories": [
    "quant-ph",
    "cs.CR",
    "cs.DS"
  ],
  "abstract": "We consider the number of quantum queries required to determine the coefficients of a degree-d polynomial over GF(q). A lower bound shown independently by Kane and Kutin and by Meyer and Pommersheim shows that d/2+1/2 quantum queries are needed to solve this problem with bounded error, whereas an algorithm of Boneh and Zhandry shows that d quantum queries are sufficient. We show that the lower bound is achievable: d/2+1/2 quantum queries suffice to determine the polynomial with bounded error. Furthermore, we show that d/2+1 queries suffice to achieve probability approaching 1 for large q. These upper bounds improve results of Boneh and Zhandry on the insecurity of cryptographic protocols against quantum attacks. We also show that our algorithm's success probability as a function of the number of queries is precisely optimal. Furthermore, the algorithm can be implemented with gate complexity poly(log q) with negligible decrease in the success probability.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-09-30T17:47:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "optimal quantum algorithm",
      "polynomial interpolation",
      "lower bound",
      "bounded error",
      "quantum queries suffice"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}