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/9802035 · Chaos Solitons & Fractals

Quantum Search on Structured Problems

Lov K. Grover

Published Sep 1, 1999• 33 citations
arXivHTMLPDF
DOI
10.1016/s0960-0779(98)00217-3

Related papers

Quantum Search on Structured Problems

Lov K. Grover

Lecture notes in computer science•Jan 1, 1999•15 citations

Quantum Algorithms for Highly Structured Search Problems

Markus Hunziker, David Meyer

Quantum Information Processing•Jun 1, 2002•12 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

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

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.

arXiv:quant-ph/0304039•Physical Review A•Dec 15, 2003•31 citations

A framework for structured quantum search

Tad Hogg

arXiv:quant-ph/9701013•Physica D Nonlinear Phenomena•Sep 1, 1998•27 citations
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.
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.
The study of quantum computation has been motivated by the hope of finding efficient quantum algorithms for solving classically hard problems. In this context, quantum algorithms by local adiabatic evolution have been shown to solve an unstructured search problem with a quadratic speedup over a classical search, just as Grover's algorithm. In this paper, we study how the structure of the search problem may be exploited to further improve the efficiency of these quantum adiabatic algorithms. We show that by nesting a partial search over a reduced set of variables into a global search, it is possible to devise quantum adiabatic algorithms with a complexity that, although still exponential, grows with a reduced order in the problem size.