Grover Adaptive Search with Problem-Specific State Preparation

• URL: http://arxiv.org/abs/2602.08418v1
• Date: Mon, 09 Feb 2026 09:21:04 GMT
• Title: Grover Adaptive Search with Problem-Specific State Preparation
• Authors: Maximilian Hess, Lilly Palackal, Abhishek Awasthi, Peter J. Eder, Manuel Schnaus, Laurin Demmler, Karen Wintersperger, Joseph Doetsch,
• Abstract summary: We build upon previous work by Baertschi and Eidenbenz to construct a state preparation routine for the Traveling Salesperson Problem.<n>With our iterations, we aim to achieve a reasonable approximation ratio with only a number of iterations.
• Score: 0.0345923194452408
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: 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.

Related papers

• Reducing Circuit Resources in Grover's Algorithm via Constraint-Aware Initialization [3.7738353997936973]
  Grover's search algorithm provides a quadratic speedup over classical brute-force search in terms of query complexity.<n>We present a systematic framework with a simple preprocessing procedure for constraint-aware initializes in Grover's algorithm.<n>Our results indicate that this approach serves as a practical baseline for achieving more resource-efficient implementations of Grover's algorithm.
  arXiv  Detail & Related papers  (2026-01-25T07:31:06Z)
• Exponential convergence dynamics in Grover's search algorithm [0.0]
  Grover's search algorithm is the cornerstone of many applications of quantum computing.<n>We modify Grover's algorithm to eliminate the oscillatory dynamics, such that the search proceeds as an exponential decay into the solution states.<n>The basic idea is to convert the solution states into a reservoir by using ancilla qubits such that the initial state is nonreflectively absorbed.
  arXiv  Detail & Related papers  (2025-12-17T05:43:07Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Complement Grover's Search Algorithm: An Amplitude Suppression Implementation [0.5352699766206808]
  Grover's search algorithm was a groundbreaking advancement in quantum algorithms. An extension of Grover's search algorithm is derived where the focus of the query is on the undesirable items. Results are compared against QAOA.
  arXiv  Detail & Related papers  (2022-09-21T16:38:36Z)
• Reflection-Based Adiabatic State Preparation [0.0]
  Our algorithm deploys a sequence of reflections determined from eigenspaces of instantaneous Hamiltonians defined along an adiabatic schedule. We provide numerical evidence suggesting that, for search problems, our algorithm can find a solution faster, on average, than Grover's search.
  arXiv  Detail & Related papers  (2021-11-10T00:03:00Z)
• Machine Learning for Online Algorithm Selection under Censored Feedback [71.6879432974126]
  In online algorithm selection (OAS), instances of an algorithmic problem class are presented to an agent one after another, and the agent has to quickly select a presumably best algorithm from a fixed set of candidate algorithms. For decision problems such as satisfiability (SAT), quality typically refers to the algorithm's runtime. In this work, we revisit multi-armed bandit algorithms for OAS and discuss their capability of dealing with the problem. We adapt them towards runtime-oriented losses, allowing for partially censored data while keeping a space- and time-complexity independent of the time horizon.
  arXiv  Detail & Related papers  (2021-09-13T18:10:52Z)
• Determinantal Beam Search [75.84501052642361]
  Beam search is a go-to strategy for decoding neural sequence models. In use-cases that call for multiple solutions, a diverse or representative set is often desired. By posing iterations in beam search as a series of subdeterminant problems, we can turn the algorithm into a diverse subset selection process.
  arXiv  Detail & Related papers  (2021-06-14T13:01:46Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Quantum Search with Prior Knowledge [15.384459603233978]
  We propose a new generalization of Grover's search algorithm which performs better than the standard Grover algorithm in average under this setting. We prove that our new algorithm achieves the optimal expected success probability of finding the solution if the number of queries is fixed.
  arXiv  Detail & Related papers  (2020-09-18T09:50:33Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  We propose unified algorithms for the important cases of first-order expectations and second-order expectations in edge-factored, non-projective spanning-tree models. Our algorithms exploit a fundamental connection between gradients and expectations, which allows us to derive efficient algorithms.
  arXiv  Detail & Related papers  (2020-08-29T14:58:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.