Grover Adaptive Search with Problem-Specific State Preparation
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917259876761600 |
|---|---|
| author | Hess, Maximilian Palackal, Lilly Awasthi, Abhishek Eder, Peter J. Schnaus, Manuel Demmler, Laurin Wintersperger, Karen Doetsch, Joseph |
| author_facet | Hess, Maximilian Palackal, Lilly Awasthi, Abhishek Eder, Peter J. Schnaus, Manuel Demmler, Laurin Wintersperger, Karen Doetsch, Joseph |
| contents | Grover's search algorithm is one of the basic building block in the world of quantum algorithms. Successfully applying it to combinatorial optimization problems is a subtle challenge. As a quadratic speedup is not enough to naively search an exponentially large space, the search has to be complemented with a state preparation routine which increases the amplitudes of promising states by exploiting the problem structure. In this paper, we build upon previous work by Baertschi and Eidenbenz to construct heuristic state preparation routines for the Traveling Salesperson Problem (TSP), mimicking the well-known classical Lin-Kernighan heuristic. With our heuristic, we aim to achieve a reasonable approximation ratio with only a polynomial number of Grover iterations. Further, we compare several algorithmic settings relating to termination criteria and the choice of Grover iterations when the number of marked solutions is unknown. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_08418 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Grover Adaptive Search with Problem-Specific State Preparation Hess, Maximilian Palackal, Lilly Awasthi, Abhishek Eder, Peter J. Schnaus, Manuel Demmler, Laurin Wintersperger, Karen Doetsch, Joseph Quantum Physics Grover's search algorithm is one of the basic building block in the world of quantum algorithms. Successfully applying it to combinatorial optimization problems is a subtle challenge. As a quadratic speedup is not enough to naively search an exponentially large space, the search has to be complemented with a state preparation routine which increases the amplitudes of promising states by exploiting the problem structure. In this paper, we build upon previous work by Baertschi and Eidenbenz to construct heuristic state preparation routines for the Traveling Salesperson Problem (TSP), mimicking the well-known classical Lin-Kernighan heuristic. With our heuristic, we aim to achieve a reasonable approximation ratio with only a polynomial number of Grover iterations. Further, we compare several algorithmic settings relating to termination criteria and the choice of Grover iterations when the number of marked solutions is unknown. |
| title | Grover Adaptive Search with Problem-Specific State Preparation |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2602.08418 |