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:1409.3305 · Physical Review Letters

Fixed-Point Quantum Search with an Optimal Number of Queries

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

Published Nov 18, 2014• 275 citations
arXivHTMLPDF

Abstract

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 λ.

DOI
10.1103/physrevlett.113.210501

Related papers

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

Fixed-point adiabatic quantum search

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

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.

arXiv:1609.03603•Physical Review A•Jan 11, 2017•26 citations

Ancilla-mediated fixed-point quantum search using Grover iterations

Yash Prabhat, Snigdha Thakur, Ankur Raina

Grover's quantum search algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from $\mathcal{O}(N)$ to $\mathcal{O}(\sqrt{N})$. However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, $M$, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least $92.6\%$ with a query complexity of approximately $\mathcal{O}(\sqrt{N/M})$, effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.

quant-pharXiv:2608.29839•APS Open Science•Sep 1, 2026•0 citations

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

Deterministic quantum search with adjustable parameters: Implementations and applications

Guanzhong Li, Lvzhou Li

Abstract Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. When it is known beforehand there are M marked elements in N elements, there exist several schemes to achieve the exact version that returns a marked element with certainty, by using the generalized Grover's iteration G(α, β) := Sr(β) So(α), where the phase oracle So(α) multiplies a marked state by eiα, and the phase rotation Sr(β) multiplies the initial state |ψ0⟩ (an equal-superposition of all states) by e-iβ.However, in all the existing schemes the value range of α and β is limited; for instance, in the three early schemes α and β are determined by M/N. Thus, a natural question arises: Given the phase oracle So(α) with an arbitrary angle α, or the phase rotation Sr(β) with an arbitrary angle β, can we always construct an exact search algorithm without sacrificing the quadratic speedup advantage? The significance of this problem lies not only in the expansion of mathematical form, but also in its application value. We answer the question affirmatively, by presenting a search framework with adjustable parameters. Technically, we propose the fixed-axis-rotation (FXR) method where each iteration of the search algorithm can be geometrically seen as rotating about a fixed axis on the Bloch sphere. Furthermore, two applications of the proposed search framework are developed: the first is to learn exactly the secret string hidden by the Hamming distance oracle, and the other to solve the element distinctness promise problem deterministically. The two applications correspond to the two different cases where α or β is fixed respectively.

arXiv:2210.12644•Information and Computation•Apr 24, 2023•24 citations

Exact and Fixed-Point Grover Search with Qudits

Tanay Roy

Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.

quant-pharXiv:2607.24658•Jul 28, 2026•1 citation
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 λ.
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λ.
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 algorithm provides a fundamental quadratic speedup for unstructured datasets, reducing query complexity from O(N)\mathcal{O}(N)O(N) to O(N)\mathcal{O}(\sqrt{N})O(N​). However, the algorithm's reliance on precise iteration counts leads to the ``soufflé problem,'' where over-rotation results in a sharp decline in success probability. This limitation is particularly restrictive when the number of solution states, MMM, is unknown. In this work, we present an ancilla-mediated fixed-point quantum search algorithm that achieves robust convergence by mapping the solution amplitude to a dedicated ancilla qubit. Unlike existing phase-matching fixed-point methods, our approach utilizes Grover's real-plane reflections, thereby maintaining the intuitive geometric architecture of the original algorithm. We demonstrate that this method achieves a success probability of at least 92.6%92.6\%92.6% with a query complexity of approximately O(N/M)\mathcal{O}(\sqrt{N/M})O(N/M​), effectively bridging the gap between standard amplitude amplification and robust fixed-point convergence.
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.
Abstract Grover's algorithm provides a quadratic speedup over classical algorithms to search for marked elements in an unstructured database. The original algorithm is probabilistic, returning a marked element with bounded error. When it is known beforehand there are M marked elements in N elements, there exist several schemes to achieve the exact version that returns a marked element with certainty, by using the generalized Grover's iteration G(α, β) := Sr(β) So(α), where the phase oracle So(α) multiplies a marked state by eiα, and the phase rotation Sr(β) multiplies the initial state |ψ0⟩ (an equal-superposition of all states) by e-iβ.However, in all the existing schemes the value range of α and β is limited; for instance, in the three early schemes α and β are determined by M/N. Thus, a natural question arises: Given the phase oracle So(α) with an arbitrary angle α, or the phase rotation Sr(β) with an arbitrary angle β, can we always construct an exact search algorithm without sacrificing the quadratic speedup advantage? The significance of this problem lies not only in the expansion of mathematical form, but also in its application value. We answer the question affirmatively, by presenting a search framework with adjustable parameters. Technically, we propose the fixed-axis-rotation (FXR) method where each iteration of the search algorithm can be geometrically seen as rotating about a fixed axis on the Bloch sphere. Furthermore, two applications of the proposed search framework are developed: the first is to learn exactly the secret string hidden by the Hamming distance oracle, and the other to solve the element distinctness promise problem deterministically. The two applications correspond to the two different cases where α or β is fixed respectively.
Grover's algorithm provides a quadratic speedup for searching unstructured databases and is traditionally implemented with qubits in Hilbert spaces whose dimensions are powers of two. With the advent of quantum platforms utilizing qudits---quantum systems with more than two levels---there is a need to generalize Grover search to these architectures, including heterogeneous systems with qudits of varying dimensions. Here, we present a unified framework for qudit-based Grover search, detailing the construction of oracles and diffusion operators with and without ancilla qubits and generalizing deterministic and fixed-point search variants that ensure exact or bounded success probabilities. We analyze phase-matching techniques and provide explicit circuit decompositions suitable for diverse hardware platforms. We also compare the corresponding trajectories on the Bloch sphere to provide an intuitive visualization of how the different phase choices amplify the target state. These results facilitate flexible, hardware-oriented protocols for implementing Grover search on qudit processors, potentially reducing circuit depth and enhancing success probabilities, thereby offering a practical toolkit for quantum computation and sensing applications leveraging multilevel quantum systems.