Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/9802043

Local Search Methods for Quantum Computers

Tad Hogg, Mehmet Fatih Yanik

Published Feb 16, 1998• 6 citations
arXivHTMLPDF

Abstract

Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard combinatorial search problems. This paper shows how quantum computers can also use these neighborhood relations. An example of such a local quantum search is evaluated empirically for the satisfiability (SAT) problem and shown to be particularly effective for highly constrained instances. For problems with an intermediate number of constraints, it is somewhat less effective at exploiting problem structure than incremental quantum methods, in spite of the much smaller search space used by the local method.

DOI
10.48550/arxiv.quant-ph/9802043

Related papers

Qubit‐Efficient Quantum Local Search for Combinatorial Optimization

Mikhail Podobrii, Viacheslav Kuzmin, Vladimir Voloshinov +2 more

ABSTRACT An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.

arXiv:2502.02245•Advanced Quantum Technologies•Mar 1, 2026•2 citations

SINGLE-STEP QUANTUM SEARCH USING PROBLEM STRUCTURE

Tad Hogg

The structure of satisfiability problems is used to improve search algorithms for quantum computers and to reduce their required coherence times by using only a single coherent evaluation of problem properties. The structure of random k-SAT allows the determination of the asymptotic average behavior of these algorithms, showing they improve on the quantum algorithms, such as amplitude amplification, that ignore detailed problem structure but remain exponential for hard problem instances. Compared to good classical methods, the algorithm performs better, on average, for weakly and highly constrained problems, but worse for hard cases. The analytic techniques introduced here apply also to other quantum algorithms, supplementing the limited evaluation possible with classical simulations, and showing how quantum computing can use the ensemble properties of NP search problems.

arXiv:quant-ph/9812049•International Journal of Modern Physics C•Jun 1, 2000•7 citations

Non-crossing neighborhood searching on quantum computer for a single machine scheduling problem

Wojciech Bożejko, Mariusz Uchroński, Mieczysław Wodecki

Many issues related to optimization practice belong to the class of NP-hard problems. Due to the large size of practical examples, metaheuristics are mainly used to solve them. However, calculations performed on classical computers, due to the computation time and values of the solutions determined, do not meet the expectations of many practitioners. In turn, quantum computers currently have too few qubits to solve even medium-sized examples. In this paper, we present a new approach to using neighborhoods with an exponential number of elements in local search algorithms. A hybrid CPU/QPU algorithm, in which the search of the neighborhood is performed on a quantum computer, allows for more efficient use of the currently available power of quantum computers.

IFAC-PapersOnLine•Jan 1, 2025•1 citation

Quantum Computing and Phase Transitions in Combinatorial Search

Tad Hogg

We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average. This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices. This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism. Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods. Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.

arXiv:cs/9603101•Journal of Artificial Intelligence Research•Mar 2, 1996•30 citations

Quantum Local Search with the Quantum Alternating Operator Ansatz

Teague Tomesh, Zain H. Saleem, Martin Suchara

We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.

arXiv:2107.04109•Quantum•Aug 22, 2022•22 citations

Exploiting the deep structure of constraint satisfaction problems with quantum computers

Tad Hogg

The deep structure of constraint satisfaction problems explains the association of hard search instances with a phase transition in problem solubility. This structure is also the basis of a quantum search algoritbm exhibiting the phase transition. In this paper, this algoritbm is modified to incorporate additional problem structure. This modification is an example of a general method for including heuristics in quantum search. The new algoritbm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.

National Conference on Artificial Intelligence•Jul 27, 1997•1 citation
Local search algorithms use the neighborhood relations among search states and often perform well for a variety of NP-hard combinatorial search problems. This paper shows how quantum computers can also use these neighborhood relations. An example of such a local quantum search is evaluated empirically for the satisfiability (SAT) problem and shown to be particularly effective for highly constrained instances. For problems with an intermediate number of constraints, it is somewhat less effective at exploiting problem structure than incremental quantum methods, in spite of the much smaller search space used by the local method.
ABSTRACT An essential component of many sophisticated metaheuristics for solving combinatorial optimization problems is some variation of a local search routine that iteratively searches for a better solution within a chosen set of immediate neighbors. The size of this set is limited due to the computational costs required to run the method on classical processing units. We present a qubit‐efficient variational quantum algorithm that implements a quantum version of local search with only qubits and, therefore, can potentially work with classically intractable neighborhood sizes. Increasing the amount of quantum resources employed in the algorithm allows for a larger neighborhood size, improving the quality of obtained solutions. This trade‐off is crucial for present and near‐term quantum devices characterized by a limited number of logical qubits. Numerically simulating our algorithm, we successfully solved the largest graph coloring instance that was tackled by a quantum method. This achievement highlights the algorithm's potential for solving large‐scale combinatorial optimization problems on near‐term quantum devices.
The structure of satisfiability problems is used to improve search algorithms for quantum computers and to reduce their required coherence times by using only a single coherent evaluation of problem properties. The structure of random k-SAT allows the determination of the asymptotic average behavior of these algorithms, showing they improve on the quantum algorithms, such as amplitude amplification, that ignore detailed problem structure but remain exponential for hard problem instances. Compared to good classical methods, the algorithm performs better, on average, for weakly and highly constrained problems, but worse for hard cases. The analytic techniques introduced here apply also to other quantum algorithms, supplementing the limited evaluation possible with classical simulations, and showing how quantum computing can use the ensemble properties of NP search problems.
Many issues related to optimization practice belong to the class of NP-hard problems. Due to the large size of practical examples, metaheuristics are mainly used to solve them. However, calculations performed on classical computers, due to the computation time and values of the solutions determined, do not meet the expectations of many practitioners. In turn, quantum computers currently have too few qubits to solve even medium-sized examples. In this paper, we present a new approach to using neighborhoods with an exponential number of elements in local search algorithms. A hybrid CPU/QPU algorithm, in which the search of the neighborhood is performed on a quantum computer, allows for more efficient use of the currently available power of quantum computers.
We introduce an algorithm for combinatorial search on quantum computers that is capable of significantly concentrating amplitude into solutions for some NP search problems, on average. This is done by exploiting the same aspects of problem structure as used by classical backtrack methods to avoid unproductive search choices. This quantum algorithm is much more likely to find solutions than the simple direct use of quantum parallelism. Furthermore, empirical evaluation on small problems shows this quantum algorithm displays the same phase transition behavior, and at the same location, as seen in many previously studied classical search methods. Specifically, difficult problem instances are concentrated near the abrupt change from underconstrained to overconstrained problems.
We present a new hybrid, local search algorithm for quantum approximate optimization of constrained combinatorial optimization problems. We focus on the Maximum Independent Set problem and demonstrate the ability of quantum local search to solve large problem instances on quantum devices with few qubits. This hybrid algorithm iteratively finds independent sets over carefully constructed neighborhoods and combines these solutions to obtain a global solution. We study the performance of this algorithm on 3-regular, Community, and Erdős-Rényi graphs with up to 100 nodes.
The deep structure of constraint satisfaction problems explains the association of hard search instances with a phase transition in problem solubility. This structure is also the basis of a quantum search algoritbm exhibiting the phase transition. In this paper, this algoritbm is modified to incorporate additional problem structure. This modification is an example of a general method for including heuristics in quantum search. The new algoritbm is evaluated empirically for random 3SAT, illustrating how quantum searches can benefit from using problem structure, on average.