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:1609.03603 · Physical Review A

Fixed-point adiabatic quantum search

Alexander M. Dalzell, Theodore J. Yoder, Isaac L. Chuang

Published Jan 11, 2017• 26 citations
arXivHTMLPDF

Abstract

Fixed-point quantum search algorithms succeed at finding one of $M$ target items among $N$ total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.

DOI
10.1103/physreva.95.012311

Related papers

Fixed-Point Quantum Search with an Optimal Number of Queries

Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang

Grover's quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ.

arXiv:1409.3305•Physical Review Letters•Nov 18, 2014•275 citations

Nonadiabatic quantum search algorithms

Armando Pérez, A. Romanelli

We present two continuous-time quantum search algorithms similar to the adiabatic search algorithm, but now without the requirement of adiabatic evolution. Both algorithms can find the marked state in a time proportional to $\sqrt{N}$. The behavior of the first algorithm is, essentially, similar to Grover's algorithm, but the second model possesses the important property that one does not need to single out a given time in order to find the searched state. After a well-defined transition time, this second algorithm will converge towards the marked state with a high probability, provided the parameters of the Hamiltonian are chosen appropriately. This convergence shows a resemblance to quantum search algorithms with a fixed point [L. K. Grover, Phys. Rev. Lett. 95, 150501 (2005)].

arXiv:0706.1139•Physical Review A•Nov 20, 2007•14 citations

Optimal fixed-point quantum amplitude amplification using Chebyshev polynomials

Theodore J. Yoder, Guang Hao Low, Isaac L. Chuang

Grover's quantum search and its generalization, quantum amplitude amplification, provide quadratic advantage over classical algorithms for a diverse set of tasks, but are tricky to use without knowing beforehand what fraction $\lambda$ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction, but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability, and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of $\lambda$.

•Sep 11, 2014•1 citation

Performance Analysis and Parameter Optimization of the Optimal Fixed-Point Quantum Search

Tian-Yi Bao, Duan Huang

The optimal fixed-point quantum search (OFPQS) algorithm [Phys. Rev. Lett. 113, 210501 (2014)] achieves both the fixed-point property and quadratic speedup over classical algorithms, which gives a sufficient condition on the number of iterations to ensure the success probability is no less than a given lower bound (denoted by 1 − δ 2 ). However, this condition is approximate and not exact. In this paper, we derive the sufficient and necessary condition on the number of feasible iterations, based on which the exact least number of iterations can be obtained. For example, when δ = 0 . 8 , iterations can be saved by almost 25%. Moreover, to find a target item certainly, setting directly 1 − δ 2 = 100 % , the quadratic advantage of the OFPQS algorithm will be lost, then, applying the OFPQS algorithm with 1 − δ 2 < 100 % requires multiple executions, which leads to a natural problem of choosing the optimal parameter δ . For this, we analyze the extreme and minimum properties of the success probability and further analytically derive the optimal δ which minimizes the query complexity. Our study can be a guideline for both the theoretical and application research on the fixed-point quantum search algorithms.

Applied Sciences•Sep 2, 2019•0 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•3 citations

Continuous-time Quantum Algorithms: Searching and Adiabatic Computation

Lawrence M. Ioannou

One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.

•Jan 1, 2002•4 citations
Fixed-point quantum search algorithms succeed at finding one of MMM target items among NNN total items even when the run time of the algorithm is longer than necessary. While the famous Grover's algorithm can search quadratically faster than a classical computer, it lacks the fixed-point property---the fraction of target items must be known precisely to know when to terminate the algorithm. Recently, Yoder, Low, and Chuang [Phys. Rev. Lett. 113, 210501 (2014)] gave an optimal gate-model search algorithm with the fixed-point property. Previously, it had been discovered by Roland and Cerf [Phys. Rev. A 65, 042308 (2002)] that an adiabatic quantum algorithm, operating by continuously varying a Hamiltonian, can reproduce the quadratic speedup of gate-model Grover search. We ask, can an adiabatic algorithm also reproduce the fixed-point property? We show that the answer depends on what interpolation schedule is used, so as in the gate model, there are both fixed-point and non-fixed-point versions of adiabatic search, only some of which attain the quadratic quantum speedup. Guided by geometric intuition on the Bloch sphere, we rigorously justify our claims with an explicit upper bound on the error in the adiabatic approximation. We also show that the fixed-point adiabatic search algorithm can be simulated in the gate model with neither loss of the quadratic Grover speedup nor of the fixed-point property. Finally, we discuss natural uses of fixed-point algorithms such as preparation of a relatively prime state and oblivious amplitude amplification.
Grover's quantum search and its generalization, quantum amplitude amplification, provide a quadratic advantage over classical algorithms for a diverse set of tasks but are tricky to use without knowing beforehand what fraction λ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ.
We present two continuous-time quantum search algorithms similar to the adiabatic search algorithm, but now without the requirement of adiabatic evolution. Both algorithms can find the marked state in a time proportional to N\sqrt{N}N​. The behavior of the first algorithm is, essentially, similar to Grover's algorithm, but the second model possesses the important property that one does not need to single out a given time in order to find the searched state. After a well-defined transition time, this second algorithm will converge towards the marked state with a high probability, provided the parameters of the Hamiltonian are chosen appropriately. This convergence shows a resemblance to quantum search algorithms with a fixed point [L. K. Grover, Phys. Rev. Lett. 95, 150501 (2005)].
Grover's quantum search and its generalization, quantum amplitude amplification, provide quadratic advantage over classical algorithms for a diverse set of tasks, but are tricky to use without knowing beforehand what fraction λ\lambdaλ of the initial state is comprised of the target states. In contrast, fixed-point search algorithms need only a reliable lower bound on this fraction, but, as a consequence, lose the very quadratic advantage that makes Grover's algorithm so appealing. Here we provide the first version of amplitude amplification that achieves fixed-point behavior without sacrificing the quantum speedup. Our result incorporates an adjustable bound on the failure probability, and, for a given number of oracle queries, guarantees that this bound is satisfied over the broadest possible range of λ\lambdaλ.
The optimal fixed-point quantum search (OFPQS) algorithm [Phys. Rev. Lett. 113, 210501 (2014)] achieves both the fixed-point property and quadratic speedup over classical algorithms, which gives a sufficient condition on the number of iterations to ensure the success probability is no less than a given lower bound (denoted by 1 − δ 2 ). However, this condition is approximate and not exact. In this paper, we derive the sufficient and necessary condition on the number of feasible iterations, based on which the exact least number of iterations can be obtained. For example, when δ = 0 . 8 , iterations can be saved by almost 25%. Moreover, to find a target item certainly, setting directly 1 − δ 2 = 100 % , the quadratic advantage of the OFPQS algorithm will be lost, then, applying the OFPQS algorithm with 1 − δ 2 < 100 % requires multiple executions, which leads to a natural problem of choosing the optimal parameter δ . For this, we analyze the extreme and minimum properties of the success probability and further analytically derive the optimal δ which minimizes the query complexity. Our study can be a guideline for both the theoretical and application research on the fixed-point quantum search algorithms.
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.
One of the most important quantum algorithms is Grover's search algorithm [G96]. Quantum searching can be used to speed up the search for solutions to NP-complete problems e. g. 3SAT. Even so, the best known quantum algorithms for 3SAT are considered inefficient. \nSoon after Grover's discovery, Farhi and Gutmann [FG96] devised a "continuous-time analogue" of quantum searching. More recently Farhi et. al. [FGGS00] proposed a continuous-time 3SAT algorithm which invokes the adiabatic approximation [M76]. Their algorithm is difficult to analyze, hence we do not know whether it can solve typical 3SAT instances faster than Grover's search algorithm can. \nI begin with a review of the discrete- and continuous-time models of quantum computation. I then make precise the notion of "efficient quantum algorithms", motivating sufficient conditions for discrete- and continuous-time algorithms to be considered efficient via discussion of standard techniques for discrete-time simulation of continuous-time algorithms. After reviewing three quantum search algorithms [F00,FG96,G96], I develop the adiabatic 3SAT algorithm as a natural extension of Farhi and Gutmann's search algorithm. Along the way, I present the adiabatic search algorithm [vDMV01] and remark on its discrete-time simulation. Finally I devise a generalization of the adiabatic algorithm and prove some lower bounds for various cases of this general framework. \nUPDATE (February 2003): Please see article http://arxiv. org/abs/quant-ph/0302138 for a resolution to the problem of simulating the continuous-time adiabatic search algorithm with a quantum circuit using only O(sqrt(N)) resources.