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/0304039 · Physical Review A

Adiabatic quantum search algorithm for structured problems

Jérémie Roland, Nicolas J. Cerf

Published Dec 15, 2003• 29 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physreva.68.062312

Related papers

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•104 citations

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•175 citations

Quantum search by measurement

Andrew M. Childs, E. Deotto, Edward Farhi +3 more

We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms.

arXiv:quant-ph/0204013•Physical Review A•Sep 23, 2002•81 citations

Optimality of Quantum Adiabatic Search Algorithm and Its Circuit Model

Jie Sun, Zhimin Zhang, Songfeng Lu

In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.

Quantum Reports•Mar 26, 2026•2 citations

Adiabatic quantum unstructured search in parallel

Sean A. Adamson, Petros Wallden

We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least $p$ in time of order $\sqrt{N}(1+p/\varepsilon)$, and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.

arXiv:2502.08594•Feb 12, 2025•0 citations

Speedup in Quantum Adiabatic Evolution Algorithm

Joonwoo Bae, Younghun Kwon

Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete

•Jan 1, 2002•0 citations
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.
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 authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
We propose a quantum algorithm for solving combinatorial search problems that uses only a sequence of measurements. The algorithm is similar to quantum computation by adiabatic evolution, in that the goal is to remain in the ground state of a time-varying Hamiltonian. Indeed, we show that the running times of the two algorithms are closely related. We also show how to achieve the quadratic speedup for Grover's unstructured search problem with only two measurements. Finally, we discuss some similarities and differences between the adiabatic and measurement algorithms.
In this paper, we study two aspects of quantum adiabatic evolution for a prototypical search problem: the optimality of the corresponding algorithm and its relation to the quantum circuit model. Firstly, we propose a general framework for proving the square-root speedup of the quantum adiabatic algorithm to be optimal over classical computation, which is readily applicable to the case of multiple targets. Through this framework, we also find that it is possible to further reduce the time complexity by increasing the physical energy of the system, encompassing results from previous works. Secondly, we find that, on the one hand, when the quantum adiabatic algorithm that achieves quadratic speedup is implemented on a quantum circuit, the time slice needed is always consistent with its time complexity, which also encompasses previous results; on the other hand, however, if a further algorithmic improvement is considered, the time slice always remains invariant. This phenomenon represents a significant observation with potential applications. We anticipate that the main results of this paper will interest the quantum adiabatic computation community and may help us to design efficient quantum algorithms for practical problems in the future.
We present an optimized adiabatic quantum schedule for unstructured search building on the original approach of Roland and Cerf [Phys. Rev. A 65, 042308 (2002)]. Our schedule adiabatically varies the Hamiltonian even more rapidly at the endpoints of its evolution, preserving Grover's well-known quadratic quantum speedup. In the errorless adiabatic limit, the probability of successfully obtaining the marked state from a measurement increases directly proportional to time, suggesting efficient parallelization. Numerical simulations of an appropriate reduced two-dimensional Schrödinger system confirm adiabaticity while demonstrating superior performance in terms of probability compared to existing adiabatic algorithms and Grover's algorithm, benefiting applications with possible premature termination. We introduce a protocol that ensures a marked-state probability at least ppp in time of order N(1+p/ε)\sqrt{N}(1+p/\varepsilon)N​(1+p/ε), and analyze its implications for realistic bounded-resource scenarios. Our findings suggest that quantum advantage may still be achievable under constrained coherence times (where other algorithms fail), provided the hardware allows for them to be sufficiently long.
Quantum adiabatic evolution algorithm suggested by Farhi et al. was effective in solving instances of NP-complete problems. The algorithm is governed by the adiabatic theorem. Therefore, in order to reduce the running time, it is essential to examine the minimum energy gap between the ground level and the next one through the evolution. In this letter, we show a way of speedup in quantum adiabatic evolution algorithm,using the extended Hamiltonian. We present the exact relation between the energy gap and the elements of the extended Hamiltonian, which provides the new point of view to reduce the running time. It is generally expected that quantum computation may solve the problems which are hard in classical context. Shor’s quantum factorization algorithm[1] and Grover’s quantum search algorithm[2] are the preludes to such expectation. Factorization problem, which is to factorize a large number, needs exponential time resource when a known classical algorithm is applied. However, Shor’s algorithm solves the problem with exponential speedup. Grover algorithm finds a target with quadratic speedup, compared to any known classical search algorithms. Quantum adiabatic evolution algorithm was proposed by Farhi et al. and applied to solve instances of NPcomplete