{
  "id": "2408.03864",
  "version": "v1",
  "published": "2024-08-07T16:12:32.000Z",
  "updated": "2024-08-07T16:12:32.000Z",
  "title": "Parameterized Quantum Query Algorithms for Graph Problems",
  "authors": [
    "Tatsuya Terao",
    "Ryuhei Mori"
  ],
  "comment": "32 pages, 4 figures, abstract shortened to meet arXiv requirement; to appear in ESA'24",
  "categories": [
    "quant-ph",
    "cs.DS"
  ],
  "abstract": "In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for $k$-vertex cover and $k$-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-08-07T16:12:32.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "graph problems",
      "parameterized quantum query complexity",
      "design parameterized quantum query algorithms",
      "vertex cover",
      "lower bounds"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}