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• 58 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.

arXiv:1105.5459•Journal of Artificial Intelligence Research•Feb 1, 1999•9 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•Journal of Artificial Intelligence Research•Mar 2, 1996•30 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

Algorithms Based on Amplitude Amplification

Phillip Kaye, Raymond Laflamme, Michele Mosca

In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.

Oxford University Press eBooks•Nov 16, 2006•1 citation

Nested quantum search and structured problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d},$ where d is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d).$ It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.

arXiv:quant-ph/9806078•Physical Review A•Feb 9, 2000•117 citations

QUANTUM SEARCH ALGORITHM CAN BE IMPROVED

Lov K. Grover

Quantum search is a quantum mechanical technique for searching N possibilities in only [Formula: see text] steps. This has been proved to be the best possible algorithm for the exhaustive search problem in the sense that the number of queries it requires cannot be reduced. However, as this paper shows, the number of non-query operations can be reduced by a third without a single increase in the number of queries.

International Journal of Quantum Information•Dec 17, 2004•3 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.
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.
In this section, we discuss a broadly applicable quantum algorithm that provides a polynomial speed-up over the best-known classical algorithms for a wide class of important problems. The quantum search algorithm performs a generic search for a solution to a very wide range of problems. Consider any problem where one can efficiently recognize a good solution and wishes to search through a list of potential solutions in order to find a good one. For example, given a large integer N, one can efficiently recognize whether an integer p is a non-trivial factor of N, and thus one naive strategy for finding non-trivial factors of N is to simply search through the set {2, 3, 4, . . . , ⌊√N⌋} until a factor is found. The factoring algorithm we described in Chapter 7 is not such a naive algorithm, as it makes profound use of the structure of the problem. However, for many interesting problems, there are no known techniques that make much use of the structure of the problem, and the best-known algorithm for solving these problems is to naively search through the potential solutions until one is found. Typically the number of potential solutions is exponential in the size of the problem instance, and so the naive algorithm is not efficient. Often the best-known classical search makes some very limited use of the structure of the problem, perhaps to rule out some obviously impossible candidates, or to prioritize some more likely candidates, but the overall complexity of the search is still exponential. Quantum searching is a tool for speeding up these sorts of generic searches through a space of potential solutions. It is worth noting that having a means of recognizing a solution to a problem, and knowing the set of possible solutions, means that in some sense one ‘knows’ the solution. However, one cannot necessarily efficiently produce the solution. For example, it is easy to recognize the factors of a number, but finding those factors can take a long time. We give this problem a more general mathematical structure as follows.
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order d,\sqrt{d},d​, where d is the dimension of the search space, whereas any classical algorithm necessarily scales as O(d).O(d).O(d). It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.