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

Leibniz international proceedings in informatics

Variable time amplitude amplification and quantum algorithms for linear algebra problems

Andris Ambainis

Published Jan 1, 2012• 97 citations
Publisher

Abstract

Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far from singular, faster then the previously known algorithms.

DOI
10.4230/lipics.stacs.2012.636

Related papers

Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations

Andris Ambainis

We present two new quantum algorithms. Our first algorithm is a generalization of amplitude amplification to the case when parts of the quantum algorithm that is being amplified stop at different times. Our second algorithm uses the first algorithm to improve the running time of Harrow et al. algorithm for solving systems of linear equations from O(kappa^2 log N) to O(kappa log^3 kappa log N) where κis the condition number of the system of equations.

arXiv:1010.4458•Oct 21, 2010•55 citations

O(logN) Algorithm for Amplitude Amplification and O(logN) Algorithms for Amplitude Transfer in Grover’s Algorithm

Ying Liu

Grover’s algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grover’s algorithm is T = O( N ). This paper introduces two new algorithms for Amplitude Amplification in Grover’s algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grover’s algorithm and our first algorithm is that the Amplitude Amplification ratio in Grover’s algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.

American Journal of Computational Mathematics•Jan 1, 2024•1 citation

Quantum linear systems algorithms: a primer

Danial Dervovic, Mark Herbster, Peter Mountney +3 more

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

arXiv:1802.08227•Feb 22, 2018•62 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

Superlinear Amplitude Amplification

Lov K. Grover

Quantum search/amplitude amplification algorithms are designed to be able to amplify the amplitude in the target state linearly with the number of operations. Since the probability is the square of the amplitude, this results in the success probability rising quadratically with the number of operations. This paper presents a new kind of quantum search algorithm in which the amplitude of the target state, itself increases quadratically with the number of operations. However, the domain of applications of this is much more limited than standard amplitude amplification.

arXiv:0806.0154•Jun 2, 2008•3 citations

Amplifying Block Encoded Quantum Operations with Grover Iterations

Nishitha Reddy Venkannagari, Varun Puram, J. Thomas

Block encoding allows quantum computers to simulate non-unitary matrices by embedding them into larger unitary operations [1]. This approach plays a critical role in many quantum algorithms that require matrix-vector multiplication such as quantum linear solvers, quantum machine learning models, and quantum reservoir computing. However, recovering the desired output state using block encoding is inherently probabilistic. The correct result is obtained only when the ancilla qubits collapse to the zero state during measurement, and the probability of this happening can be very low. As a result, repeated trials are often needed, which increases resource usage and reduces efficiency. In this work, we present a Grover-style amplitude amplification technique that significantly boosts the success probability without altering the final output state. By applying a series of unitary reflections, the method amplifies the amplitude of the successful outcome, reducing the number of repetitions required to obtain the correct result. This results in a quadratic improvement in efficiency compared to repeated sampling. Our results show that the success probability improved significantly from as low as 15 % to over 85 % after applying the amplification method. This improvement could help quantum programs run more efficiently in noisy environments and makes it easier to use block-encoded matrices in real applications.

International Conference on AI-ML Systems (AIMLSystems)•Oct 8, 2025•0 citations
Quantum amplitude amplification is a method of increasing a success probability of an algorithm from a small epsilon>0 to Theta(1) with less repetitions than classically. In this paper, we generalize quantum amplitude amplification to the case when parts of the algorithm that is being amplified stop at different times. We then apply the new variable time amplitude amplification to give two new quantum algorithms for linear algebra problems. Our first algorithm is an improvement of Harrow et al. algorithm for solving systems of linear equations. We improve the running time of the algorithm from O(k^2 log N) to O(k log^3 k log N) where k is the condition number of the system of equations. Our second algorithm tests whether a matrix A is singular or far from singular, faster then the previously known algorithms.
Grover’s algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grover’s algorithm is T = O( N ). This paper introduces two new algorithms for Amplitude Amplification in Grover’s algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grover’s algorithm and our first algorithm is that the Amplitude Amplification ratio in Grover’s algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.
The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.
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.
Quantum search/amplitude amplification algorithms are designed to be able to amplify the amplitude in the target state linearly with the number of operations. Since the probability is the square of the amplitude, this results in the success probability rising quadratically with the number of operations. This paper presents a new kind of quantum search algorithm in which the amplitude of the target state, itself increases quadratically with the number of operations. However, the domain of applications of this is much more limited than standard amplitude amplification.
Block encoding allows quantum computers to simulate non-unitary matrices by embedding them into larger unitary operations [1]. This approach plays a critical role in many quantum algorithms that require matrix-vector multiplication such as quantum linear solvers, quantum machine learning models, and quantum reservoir computing. However, recovering the desired output state using block encoding is inherently probabilistic. The correct result is obtained only when the ancilla qubits collapse to the zero state during measurement, and the probability of this happening can be very low. As a result, repeated trials are often needed, which increases resource usage and reduces efficiency. In this work, we present a Grover-style amplitude amplification technique that significantly boosts the success probability without altering the final output state. By applying a series of unitary reflections, the method amplifies the amplitude of the successful outcome, reducing the number of repetitions required to obtain the correct result. This results in a quadratic improvement in efficiency compared to repeated sampling. Our results show that the success probability improved significantly from as low as 15 % to over 85 % after applying the amplification method. This improvement could help quantum programs run more efficiently in noisy environments and makes it easier to use block-encoded matrices in real applications.