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 Letters

Highly Structured Searches with Quantum Computers

Tad Hogg

Published Mar 16, 1998• 59 citations
Publisher

Abstract

A quantum algorithm for a class of highly structured combinatorial search problems is introduced. This algorithm finds a solution in a single step, contrasting with the linear growth in the number of steps required by the best classical algorithms as the problem size increases, and the exponential growth required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems, in fact, have no solutions, unlike previously proposed quantum search algorithms.

DOI
10.1103/physrevlett.80.2473

Related papers

Solving Highly Constrained Search Problems with Quantum Computers

Tad Hogg

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms. 1. Introduction Quantum computers (Benioff, 1982; Bernstein & Vazirani, 1993; Deutsch, 1985, 1989; DiVincenzo, 1995; Feynman, 1986; Lloyd, 1993) offer a new approach to combinatorial search problems (Garey & Johnson, 1979) with quantum parallelism, i.e., the abilit...

•Jan 1, 1998•9 citations

Solving Highly Constrained Search Problems with Quantum Computers

Tad Hogg

A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.

arXiv:1105.5459•Journal of Artificial Intelligence Research•Feb 1, 1999•5 citations

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.

Journal of Artificial Intelligence Research•Mar 2, 1996•30 citations

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•Mar 1, 1996•0 citations

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:quant-ph/9508012•Aug 16, 1995•0 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•5 citations
A quantum algorithm for a class of highly structured combinatorial search problems is introduced. This algorithm finds a solution in a single step, contrasting with the linear growth in the number of steps required by the best classical algorithms as the problem size increases, and the exponential growth required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems, in fact, have no solutions, unlike previously proposed quantum search algorithms.
A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms. 1. Introduction Quantum computers (Benioff, 1982; Bernstein & Vazirani, 1993; Deutsch, 1985, 1989; DiVincenzo, 1995; Feynman, 1986; Lloyd, 1993) offer a new approach to combinatorial search problems (Garey & Johnson, 1979) with quantum parallelism, i.e., the abilit...
A previously developed quantum search algorithm for solving 1-SAT problems in a single step is generalized to apply to a range of highly constrained k-SAT problems. We identify a bound on the number of clauses in satisfiability problems for which the generalized algorithm can find a solution in a constant number of steps as the number of variables increases. This performance contrasts with the linear growth in the number of steps required by the best classical algorithms, and the exponential number required by classical and quantum methods that ignore the problem structure. In some cases, the algorithm can also guarantee that insoluble problems in fact have no solutions, unlike previously proposed quantum search algorithms.
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 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 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.
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.