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

Physical Review A

Quantum search heuristics

Tad Hogg

Published Apr 14, 2000• 76 citations
Publisher

Abstract

An alternative quantum algorithm for combinatorial search, adjusting amplitudes based on number of conflicts in search states, performs well, on average, for hard random satisfiability problems near a phase transition in search difficulty. The algorithm exploits correlations among problem properties more effectively than some current heuristics, and improves on prior quantum algorithms that ignore these correlations.

DOI
10.1103/physreva.61.052311

Related papers

Solving Random Satisfiability Problems with Quantum Computers

Tad Hogg

Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.

arXiv:quant-ph/0104048•Apr 9, 2001•5 citations

A Framework for Quantum Search Heuristics

Tad Hogg

A quantum algorithm for combinatorial search is presented that provides a simple framework for utilizing search heuristics. The algorithm is evaluated in a new case that is an unstructured version of the graph coloring problem. It performs significantly better than the direct use of quantum parallelism, on average, in cases corresponding to previously identified phase transitions in search difficulty. The conditions underlying this improvement are described. Much of the algorithm is independent of particular problem instances, making it suitable for implementation as a special purpose device.

arXiv:quant-ph/9611004•Nov 4, 1996•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

Graph coloring with quantum heuristics

Alex Fabrikant, Tad Hogg

We present a quantum computer heuristic search algorithm for graph coloring. This algorithm uses a new quantum operator, appropriate for nonbinary-valued constraint satis-faction problems, and information available in partial col-orings. We evaluate the algorithm empirically with small graphs near a phase transition in search performance. It im-proves on two prior quantum algorithms: unstructured search and a heuristic applied to the satisfiability (SAT) encoding of graph coloring. An approximate asymptotic analysis sug-gests polynomial-time cost for hard graph coloring problems, on average.

National Conference on Artificial Intelligence•Jul 28, 2002•10 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

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
An alternative quantum algorithm for combinatorial search, adjusting amplitudes based on number of conflicts in search states, performs well, on average, for hard random satisfiability problems near a phase transition in search difficulty. The algorithm exploits correlations among problem properties more effectively than some current heuristics, and improves on prior quantum algorithms that ignore these correlations.
Quantum computer algorithms can exploit the structure of random satisfiability problems. This paper extends a previous empirical evaluation of such an algorithm and gives an approximate asymptotic analysis accounting for both the average and variation of amplitudes among search states with the same costs. The analysis predicts good performance, on average, for a variety of problems including those near a phase transition associated with a high concentration of hard cases. Based on empirical evaluation for small problems, modifying the algorithm in light of this analysis improves its performance. The algorithm improves on both GSAT, a commonly used conventional heuristic, and quantum algorithms ignoring problem structure.
A quantum algorithm for combinatorial search is presented that provides a simple framework for utilizing search heuristics. The algorithm is evaluated in a new case that is an unstructured version of the graph coloring problem. It performs significantly better than the direct use of quantum parallelism, on average, in cases corresponding to previously identified phase transitions in search difficulty. The conditions underlying this improvement are described. Much of the algorithm is independent of particular problem instances, making it suitable for implementation as a special purpose device.
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 quantum computer heuristic search algorithm for graph coloring. This algorithm uses a new quantum operator, appropriate for nonbinary-valued constraint satis-faction problems, and information available in partial col-orings. We evaluate the algorithm empirically with small graphs near a phase transition in search performance. It im-proves on two prior quantum algorithms: unstructured search and a heuristic applied to the satisfiability (SAT) encoding of graph coloring. An approximate asymptotic analysis sug-gests polynomial-time cost for hard graph coloring problems, on average.
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.
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.