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

Scientific Reports

Fixed-point oblivious quantum amplitude-amplification algorithm

Bao Yan, Shijie Wei, Haocong Jiang, Hong Wang, Qianheng Duan, Zhi Ma, Gui‐Lu Long

Published Aug 22, 2022• 10 citations
Publisher

Abstract

The quantum amplitude amplification algorithms based on Grover's rotation operator need to perform phase flips for both the initial state and the target state. When the initial state is oblivious, the phase flips will be intractable, and we need to adopt oblivious amplitude amplification algorithm to handle. Without knowing exactly how many target items there are, oblivious amplitude amplification also suffers the "soufflé problem", in which iterating too little "undercooks" the state and too much "overcooks" the state, both resulting in a mostly non-target final state. In this work, we present a fixed-point oblivious quantum amplitude-amplification (FOQA) algorithm by introducing damping based on methods proposed by A. Mizel. Moreover, we construct the quantum circuit to implement our algorithm under the framework of duality quantum computing. Our algorithm can avoid the "soufflé problem", meanwhile keep the square speedup of quantum search, serving as a subroutine to improve the performance of quantum algorithms containing oblivious amplitude amplification procedure.

DOI
10.1038/s41598-022-15093-x

Related papers

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•Sep 1, 2026•0 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

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

Grover search revisited: Application to image pattern matching

Hiroyuki Tezuka, Kouhei Nakaji, Takahiko Satoh +1 more

The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various types of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there has been no proposal to realize the original motivating application of the algorithm, i.e., the database search or more broadly the pattern matching in a practical setting, mainly due to the technical difficulty in efficiently implementing the data loading and amplitude amplification processes. In this paper, we propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit, together with the easily implementable inversion-test operation for realizing the projected quantum state having similarity to the query data, followed by the amplitude amplification operation that is independent to the target data index. We provide a thorough demonstration of the algorithm in the problem of image pattern matching.

arXiv:2108.10854•Physical Review A•Mar 24, 2022•35 citations

Quantum amplitude amplification operators: exact quantum search

Hyeokjea Kwon, Joonwoo Bae

Quantum search algorithms show quadratic speedups over their classical counterparts, and the speedup also turns out to be optimal. They share the common structure that an iteration contains two inversions, one with respect to a target state and the other to an initial state, and such iterations are applied O( √ N) times for an unsorted database of N items. In this work, we present the characterization to an iteration that leads to exact quantum search with a quadratic speedup. We show that the fixed-point quantum search algorithm with a quadratic speedup contains iterations that are not QAAOs whereas exact quantum algorithms are sequences of QAAOs. We also demonstrate 3-qubit QAAOs in cloud-based quantum computing services, IBMQ and IonQ.

Quantum Communications and Quantum Imaging•Oct 4, 2022•0 citations

Amplitude Amplification Algorithms

Mithilesh Kumar, Yusuf Tahir, Daiya, Varun

This survey traces the evolution of quantum amplitude amplification from its geometric origins in Grover’s algorithm to its algebraic formulation within the Quantum Singular Value Transformation (QSVT) framework. We develop a unified mathematical formalism intended to reduce the historical fragmentation of these algorithms. By establishing a consistent notational foundation early on, framing unstructured search as rotation within an invariant two-dimensional subspace, and following the progression through oblivious, fixed-point, and distributed amplification schemes, we aim to clarify how these methods can be interpreted within the broader language of singular-value polynomial synthesis. We additionally introduce a variational template for amplitude amplification based on parameterized phase rotations, connecting amplification primitives to hybrid quantum-classical algorithms suitable for near-term quantum architectures. To support the pedagogical objectives of this survey, we provide a companion website hosting interactive visualizations and implementation details at QuantumAmplitudeAmplification.

•May 6, 2026•0 citations
The quantum amplitude amplification algorithms based on Grover's rotation operator need to perform phase flips for both the initial state and the target state. When the initial state is oblivious, the phase flips will be intractable, and we need to adopt oblivious amplitude amplification algorithm to handle. Without knowing exactly how many target items there are, oblivious amplitude amplification also suffers the "soufflé problem", in which iterating too little "undercooks" the state and too much "overcooks" the state, both resulting in a mostly non-target final state. In this work, we present a fixed-point oblivious quantum amplitude-amplification (FOQA) algorithm by introducing damping based on methods proposed by A. Mizel. Moreover, we construct the quantum circuit to implement our algorithm under the framework of duality quantum computing. Our algorithm can avoid the "soufflé problem", meanwhile keep the square speedup of quantum search, serving as a subroutine to improve the performance of quantum algorithms containing oblivious amplitude amplification procedure.
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.
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λ.
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 λ.
The landmark Grover algorithm for amplitude amplification serves as an essential subroutine in various types of quantum algorithms, with guaranteed quantum speedup in query complexity. However, there has been no proposal to realize the original motivating application of the algorithm, i.e., the database search or more broadly the pattern matching in a practical setting, mainly due to the technical difficulty in efficiently implementing the data loading and amplitude amplification processes. In this paper, we propose a quantum algorithm that approximately executes the entire Grover database search or pattern matching algorithm. The key idea is to use the recently proposed approximate amplitude encoding method on a shallow quantum circuit, together with the easily implementable inversion-test operation for realizing the projected quantum state having similarity to the query data, followed by the amplitude amplification operation that is independent to the target data index. We provide a thorough demonstration of the algorithm in the problem of image pattern matching.
Quantum search algorithms show quadratic speedups over their classical counterparts, and the speedup also turns out to be optimal. They share the common structure that an iteration contains two inversions, one with respect to a target state and the other to an initial state, and such iterations are applied O( √ N) times for an unsorted database of N items. In this work, we present the characterization to an iteration that leads to exact quantum search with a quadratic speedup. We show that the fixed-point quantum search algorithm with a quadratic speedup contains iterations that are not QAAOs whereas exact quantum algorithms are sequences of QAAOs. We also demonstrate 3-qubit QAAOs in cloud-based quantum computing services, IBMQ and IonQ.
This survey traces the evolution of quantum amplitude amplification from its geometric origins in Grover’s algorithm to its algebraic formulation within the Quantum Singular Value Transformation (QSVT) framework. We develop a unified mathematical formalism intended to reduce the historical fragmentation of these algorithms. By establishing a consistent notational foundation early on, framing unstructured search as rotation within an invariant two-dimensional subspace, and following the progression through oblivious, fixed-point, and distributed amplification schemes, we aim to clarify how these methods can be interpreted within the broader language of singular-value polynomial synthesis. We additionally introduce a variational template for amplitude amplification based on parameterized phase rotations, connecting amplification primitives to hybrid quantum-classical algorithms suitable for near-term quantum architectures. To support the pedagogical objectives of this survey, we provide a companion website hosting interactive visualizations and implementation details at QuantumAmplitudeAmplification.