{
  "id": "2402.02585",
  "version": "v1",
  "published": "2024-02-04T19:01:27.000Z",
  "updated": "2024-02-04T19:01:27.000Z",
  "title": "Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering",
  "authors": [
    "Zewen Zhang",
    "Roger Paredes",
    "Bhuvanesh Sundar",
    "David Quiroga",
    "Anastasios Kyrillidis",
    "Leonardo Duenas-Osorio",
    "Guido Pagano",
    "Kaden R. A. Hazzard"
  ],
  "doi": "10.1088/2058-9565/ad895c",
  "categories": [
    "quant-ph",
    "physics.comp-ph"
  ],
  "abstract": "The SAT problem is a prototypical NP-complete problem of fundamental importance in computational complexity theory with many applications in science and engineering; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study shows numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over random sampling for finding all solutions to 3-SAT problems (All-SAT). G-QAOA is less resource-intensive and more adaptable for 3-SAT and Max-SAT than Grover's algorithm, and it surpasses conventional QAOA in its ability to sample all solutions. We show these benefits by classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. Interestingly, a single-angle-pair constraint that uses the same pair of angles at each G-QAOA round greatly reduces the classical computational overhead of optimizing the G-QAOA angles while preserving its quadratic speedup. We also find parameter clustering of the angles. The single-angle-pair protocol and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-02-04T19:01:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "quadratic speedup",
      "parameter clustering",
      "clustering significantly reduce obstacles",
      "grover quantum approximate optimization algorithm",
      "g-qaoa angles"
    ],
    "tags": [
      "journal article"
    ],
    "publication": {
      "publisher": "IOP"
    },
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}