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:quant-ph/9708016 · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences

Quantum algorithms revisited

Richard Cleve, ARTUR K. EKERT, Chiara Macchiavello, Michele Mosca

Published Jan 8, 1998• 1,300 citations
arXivHTMLPDF

Abstract

Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. A common pattern underpinning quantum algorithms can be identified when quantum computation is viewed as multiparticle interference. We use this approach to review (and improve) some of the existing quantum algorithms and to show how they are related to different instances of quantum phase estimation. We provide an explicit algorithm for generating any prescribed interference pattern with an arbitrary precision.

DOI
10.1098/rspa.1998.0164

Related papers

Quantum Interferometers as Quantum Computers

ARTUR K. EKERT

Quantum computers which use quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations can be viewed as multiparticle interferometers. I discuss this approach to quantum computation and argue that it provides additional insights into the nature of quantum algorithms.

Physica Scripta•Jan 1, 1998•15 citations

On Quantum Algorithms

Richard Cleve, ARTUR K. EKERT, Henderson, L +2 more

Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical paradigm as (multi-particle) interferometers. We show how most known quantum algorithms, including quantum algorithms for factorising and counting, may be cast in this manner. Quantum searching is described as inducing a desired relative phase between two eigenvectors to yield constructive interference on the sought elements and destructive interference on the remaining terms.

•Jan 1, 1998•21 citations

On Quantum Algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical paradigm as (multi-particle) interferometers. We show how most known quantum algorithms, including quantum algorithms for factorising and counting, may be cast in this manner. Quantum searching is described as inducing a desired relative phase between two eigenvectors to yield constructive interference on the sought elements and destructive interference on the remaining terms.

arXiv:quant-ph/9903061•Mar 17, 1999•0 citations

Optimal quantum phase estimation algorithms

Joseph T. Smith

It is suggested that computers exploiting quantum phenomena can solve tasks with an efficiency surpassing that achievable by classical computers. One example of this quantum advantage arises in the task of phase estimation. Here, an unknown eigenvalue of a unitary evolution is estimated, a critical subroutine for many quantum algorithms and quantum metrology protocols. For a fixed amount of resources, the utilisation of quantum coherence and entanglement can lead to a quadratic increase in precision of the final estimate compared to classical statistical limits. In systems affected by depolarising noise, including current quantum hardware, this improvement becomes a constant factor. While numerous phase estimation algorithms have been proposed claiming to achieve these theoretical limits, the lack of well-defined criteria for both precision and resource utilisation casts doubt on these results. Further issues arise due to a lack of point identification (the existence of multiple equally likely estimates) that some algorithms have. I aim to address these issues in this thesis. I employ statistical inference, the theoretical foundation for interpreting any quantum measurement, in order to find rigorous definitions for precision and resource use. By combining these definitions with previous work in the field of quantum metrology, I am able to derive theoretical precision limits that one can hope to achieve. I then outline several phase estimation algorithms that can achieve these limits in different contexts. These algorithms that I describe are split into three major groups. Algorithms in the first group focus on the process of point identification; one set of measurements provides a precise estimate of the unknown phase before an additional set of measurements removes any ambiguities present. This second set of measurements can be either decided before any measurement is taken or during measurements in an iterative fashion. I show that the balancing of resources used in each set of measurements can lead to optimally scaling precision both with and without depolarising noise. These algorithms are based upon two of my peer-reviewed articles, [Phys. Rev. A 106, 062615 (2022)] and [Phys. Rev. A 109, 042412 (2024)]. The second group of algorithms that I introduce use the principles of Bayesian experimental design. Here, previous measurement outcomes are used to select future measurements recursively. These algorithms require large classical computing times to select each measurement but boast high precision in certain metrics. The final group of algorithms exploit the oscillating nature of phases by using a discrete Fourier transform (DFT). The DFT can be implemented using either classical or quantum hardware, the latter of which leads to the famous quantum phase estimation algorithm (QPEA). In this thesis, I show that the QPEA performs worse than some classical precision limits. However, I also suggest some modifications to the QPEA circuit that can lead to optimal precision scaling. These results and modifications are described in one of my articles awaiting publication [arXiv:2505.00764].

•Sep 12, 2025•0 citations

Quantum signal processing and the quantum singular value transformation

Steven Herbert

Abstract The quantum algorithms presented in the previous chapters are underpinned by three fundamental features of quantum computation. First, it is possible to construct Grover iterates that amplify amplitude and concentrate probability mass on desired outcomes quadratically faster than their classical counterparts; second, quantum phase estimation is a subroutine that uses the quantum Fourier transform to interfere a quantum state such that wrong answers cancel out, leaving a state from which the solution to the problem can be extracted; and finally, using a digital quantum computer, Hamiltonian evolution can be simulated. Remarkably, these three phenomena can be seen to be instances of the same underlying computational effect: the quantum singular value transformation – a breakthrough that has been dubbed ‘the grand unification of quantum algorithms’, and which is introduced and analysed in this chapter.

•Dec 8, 2025•0 citations

A Precise Error Bound for Quantum Phase Estimation

James M. Chappell, Max A. Lohe, Lorenz von Smekal +2 more

Quantum phase estimation is one of the key algorithms in the field of quantum computing, but up until now, only approximate expressions have been derived for the probability of error. We revisit these derivations, and find that by ensuring symmetry in the error definitions, an exact formula can be found. This new approach may also have value in solving other related problems in quantum computing, where an expected error is calculated. Expressions for two special cases of the formula are also developed, in the limit as the number of qubits in the quantum computer approaches infinity and in the limit as the extra added qubits to improve reliability goes to infinity. It is found that this formula is useful in validating computer simulations of the phase estimation procedure and in avoiding the overestimation of the number of qubits required in order to achieve a given reliability. This formula thus brings improved precision in the design of quantum computers.

arXiv:1102.0108•PLoS ONE•May 10, 2011•9 citations
Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. A common pattern underpinning quantum algorithms can be identified when quantum computation is viewed as multiparticle interference. We use this approach to review (and improve) some of the existing quantum algorithms and to show how they are related to different instances of quantum phase estimation. We provide an explicit algorithm for generating any prescribed interference pattern with an arbitrary precision.
Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical paradigm as (multi-particle) interferometers. We show how most known quantum algorithms, including quantum algorithms for factorising and counting, may be cast in this manner. Quantum searching is described as inducing a desired relative phase between two eigenvectors to yield constructive interference on the sought elements and destructive interference on the remaining terms.
Quantum computers use the quantum interference of different computational paths to enhance correct outcomes and suppress erroneous outcomes of computations. In effect, they follow the same logical paradigm as (multi-particle) interferometers. We show how most known quantum algorithms, including quantum algorithms for factorising and counting, may be cast in this manner. Quantum searching is described as inducing a desired relative phase between two eigenvectors to yield constructive interference on the sought elements and destructive interference on the remaining terms.
It is suggested that computers exploiting quantum phenomena can solve tasks with an efficiency surpassing that achievable by classical computers. One example of this quantum advantage arises in the task of phase estimation. Here, an unknown eigenvalue of a unitary evolution is estimated, a critical subroutine for many quantum algorithms and quantum metrology protocols. For a fixed amount of resources, the utilisation of quantum coherence and entanglement can lead to a quadratic increase in precision of the final estimate compared to classical statistical limits. In systems affected by depolarising noise, including current quantum hardware, this improvement becomes a constant factor. While numerous phase estimation algorithms have been proposed claiming to achieve these theoretical limits, the lack of well-defined criteria for both precision and resource utilisation casts doubt on these results. Further issues arise due to a lack of point identification (the existence of multiple equally likely estimates) that some algorithms have. I aim to address these issues in this thesis. I employ statistical inference, the theoretical foundation for interpreting any quantum measurement, in order to find rigorous definitions for precision and resource use. By combining these definitions with previous work in the field of quantum metrology, I am able to derive theoretical precision limits that one can hope to achieve. I then outline several phase estimation algorithms that can achieve these limits in different contexts. These algorithms that I describe are split into three major groups. Algorithms in the first group focus on the process of point identification; one set of measurements provides a precise estimate of the unknown phase before an additional set of measurements removes any ambiguities present. This second set of measurements can be either decided before any measurement is taken or during measurements in an iterative fashion. I show that the balancing of resources used in each set of measurements can lead to optimally scaling precision both with and without depolarising noise. These algorithms are based upon two of my peer-reviewed articles, [Phys. Rev. A 106, 062615 (2022)] and [Phys. Rev. A 109, 042412 (2024)]. The second group of algorithms that I introduce use the principles of Bayesian experimental design. Here, previous measurement outcomes are used to select future measurements recursively. These algorithms require large classical computing times to select each measurement but boast high precision in certain metrics. The final group of algorithms exploit the oscillating nature of phases by using a discrete Fourier transform (DFT). The DFT can be implemented using either classical or quantum hardware, the latter of which leads to the famous quantum phase estimation algorithm (QPEA). In this thesis, I show that the QPEA performs worse than some classical precision limits. However, I also suggest some modifications to the QPEA circuit that can lead to optimal precision scaling. These results and modifications are described in one of my articles awaiting publication [arXiv:2505.00764].
Abstract The quantum algorithms presented in the previous chapters are underpinned by three fundamental features of quantum computation. First, it is possible to construct Grover iterates that amplify amplitude and concentrate probability mass on desired outcomes quadratically faster than their classical counterparts; second, quantum phase estimation is a subroutine that uses the quantum Fourier transform to interfere a quantum state such that wrong answers cancel out, leaving a state from which the solution to the problem can be extracted; and finally, using a digital quantum computer, Hamiltonian evolution can be simulated. Remarkably, these three phenomena can be seen to be instances of the same underlying computational effect: the quantum singular value transformation – a breakthrough that has been dubbed ‘the grand unification of quantum algorithms’, and which is introduced and analysed in this chapter.
Quantum phase estimation is one of the key algorithms in the field of quantum computing, but up until now, only approximate expressions have been derived for the probability of error. We revisit these derivations, and find that by ensuring symmetry in the error definitions, an exact formula can be found. This new approach may also have value in solving other related problems in quantum computing, where an expected error is calculated. Expressions for two special cases of the formula are also developed, in the limit as the number of qubits in the quantum computer approaches infinity and in the limit as the extra added qubits to improve reliability goes to infinity. It is found that this formula is useful in validating computer simulations of the phase estimation procedure and in avoiding the overestimation of the number of qubits required in order to achieve a given reliability. This formula thus brings improved precision in the design of quantum computers.