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

Quantum amplitude-amplification operators

Hyeokjea Kwon, Joonwoo Bae

Published Dec 27, 2021• 16 citations
arXivHTMLPDF

Abstract

Quantum search algorithms have been shown to deliver quadratic speedups over classical ones. The authors propose a generalized form of such algorithms through the use of ``quantum amplitude-amplification operators'' (QAAOs), with a goal of implementing them on near-term quantum devices. They demonstrate three-qubit examples on cloud-based quantum computing services, and use their framework to distinguish between exact and fixed-point quantum search algorithms.

DOI
10.1103/physreva.104.062438

Related papers

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

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

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

Chapter 4: Amplitude amplification and estimation

Giacomo Nannicini

In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.

Society for Industrial and Applied Mathematics eBooks•Dec 17, 2025•0 citations

Amplitude amplification and estimation

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.

Cambridge University Press eBooks•Apr 24, 2025•0 citations
Quantum search algorithms have been shown to deliver quadratic speedups over classical ones. The authors propose a generalized form of such algorithms through the use of ``quantum amplitude-amplification operators'' (QAAOs), with a goal of implementing them on near-term quantum devices. They demonstrate three-qubit examples on cloud-based quantum computing services, and use their framework to distinguish between exact and fixed-point quantum search algorithms.
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.
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 λ.
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.
In Chs. 2 and 3 we described several quantum algorithms that are exponentially faster than classical algorithms for the same problem, under some measure of complexity. Unfortunately, the algorithms of Ch. 2 apply to rather contrived problems that do not have known direct applications. We now describe a quantum algorithm that gives only a polynomial—more specifically, quadratic—speedup with respect to classical algorithms, but it applies to a large class of problems and finds many useful applications, both directly and as an algorithmic design tool. The algorithm is known as Grover’s search [89], and its generalization is known as amplitude amplification [43]. Amplitude amplification is widely used as part of many quantum algorithms. It also serves as the basis for amplitude estimation, a way of estimating probabilities quadratically faster than with classical Monte Carlo, and for quantum minimum finding. All these topics are discussed in this chapter.
This chapter covers the quantum algorithmic primitives of amplitude amplification and amplitude estimation. Amplitude amplification is a generalization of Grover’s quantum algorithm for the unstructured search problem. Amplitude estimation can be understood in a similar framework, where it utilizes quantum phase estimation to estimate the value of the amplitude or probability associated with a quantum state. Both amplitude amplification and amplitude estimation provide a quadratic speedup over their classical counterparts, and feature prominently as an ingredient in many end-to-end algorithms.