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

Error reduction of quantum algorithms

Debajyoti Bera, P. V. Tharrmashastha

Published Jul 19, 2019• 2 citations
arXivHTMLPDF

Abstract

We present a technique to reduce the error probability of quantum algorithms that determine whether its input has a specified property of interest. The standard process of reducing this error is statistical processing of the results of multiple independent executions of an algorithm. Denoting by $\ensuremath{\rho}$ an upper bound of this probability (wlog; assume $\ensuremath{\rho}\ensuremath{\le}\frac{1}{2}$), classical techniques require $O(\frac{\ensuremath{\rho}}{{[(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}]}^{2}})$ executions to reduce the error to a negligible constant. We investigate when and how quantum algorithmic techniques like amplitude amplification and estimation may reduce the number of executions. On one hand, the former idea does not directly benefit algorithms that can err on both yes and no answers and the number of executions in the latter approach is $O(\frac{1}{(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}})$. We propose a quantum approach called amplitude separation that combines both these approaches and achieves $O(\frac{1}{\sqrt{1\ensuremath{-}\ensuremath{\rho}}\ensuremath{-}\sqrt{\ensuremath{\rho}}})$ executions, which betters existing approaches when the errors are high. In the multiple-weight decision problem, the input is an $n$-bit Boolean function $f(\phantom{\rule{0.16em}{0ex}})$ given as a black box and the objective is to determine the number of $x$ for which $f(x)=1$, denoted $wt(f)$, given some possible values ${{w}_{1},...,{w}_{k}}$ for $wt(f)$. When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using $O({log}_{2}k\sqrt{{2}^{n}})$ calls to $f(\phantom{\rule{0.16em}{0ex}})$, which shows a quadratic speedup over classical approaches and currently known quantum algorithms.

DOI
10.1103/physreva.100.012331

Related papers

Quantum amplitude amplification and estimation

Gilles Brassard, Peter Høyer, Michele Mosca +1 more

Consider a Boolean function $χ: X \to \{0,1\}$ that partitions set $X$ between its good and bad elements, where $x$ is good if $χ(x)=1$ and bad otherwise. Consider also a quantum algorithm $\mathcal A$ such that $A |0\rangle= \sum_{x\in X} α_x |x\rangle$ is a quantum superposition of the elements of $X$, and let $a$ denote the probability that a good element is produced if $A |0\rangle$ is measured. If we repeat the process of running $A$, measuring the output, and using $χ$ to check the validity of the result, we shall expect to repeat $1/a$ times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good $x$ after an expected number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$, assuming algorithm $A$ makes no measurements. This is a generalization of Grover's searching algorithm in which $A$ was restricted to producing an equal superposition of all members of $X$ and we had a promise that a single $x$ existed such that $χ(x)=1$. Our algorithm works whether or not the value of $a$ is known ahead of time. In case the value of $a$ is known, we can find a good $x$ after a number of applications of $A$ and its inverse which is proportional to $1/\sqrt{a}$ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of $a$. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of $x\in X$ such that $χ(x)=1$. We obtain optimal quantum algorithms in a variety of settings.

arXiv:quant-ph/0005055•Contemporary mathematics - American Mathematical Society•Jan 1, 2002•2,286 citations

Quantum tests for the linearity and permutation invariance of Boolean functions

Mark S. Hillery, Erika Andersson

The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.

arXiv:1106.4831•Physical Review A•Dec 28, 2011•20 citations

New method for improving quantum-algorithm reliability

Коноплев Борис Георгиевич, A. V. Kovalev, В. В. Кальсков

A new method is proposed of reducing probability of error for quantum algorithms subject to physical constraints. It essentially involves preparation of qubits for computation. The method is tested on a part of a quantum algorithm employing the quantum gates NOT, SWAP, CNOT, CCNOT, and CSWAP.

Russian Microelectronics•Mar 1, 2007•0 citations

Evaluating Quantum Algorithms: Closing the Gap between Theory and Practice

Gabriel San Martín Silva, Lavínia Mendes Araújo, Isis Didier Lins +1 more

Motivated by its unique capabilities, quantum computation has gained significant attention over the last decade with numerous models and algorithms proposed for dealing with engineering challenges.The field of risk and reliability has also seen a growing interest in this area, with studies exploring Quantum Machine Learning for remaining useful life, Quantum Optimization for condition monitoring in civil structures, and Quantum Inference for enhancing Bayesian network models, to name a few.However, a common limitation across these works is the lack of thorough comparisons between the proposed quantum algorithms and their state-of-the-art classical counterparts.This critical gap must be addressed not only to evaluate the field's current state reliably but also to guide its development toward the most promising paths for achieving a quantum advantage.There are two key challenges to addressing this gap.First, quantum computation operates on fundamentally different principles than traditional computing, making direct comparisons -such as using the number of iterations -often infeasible.Second, large-scale, error-corrected quantum computers are not yet available, so machine-to-machine comparisons are also not yet possible.In this paper, we detail a novel methodology to evaluate quantum algorithms against their classical counterparts.Our technique is based on a simple observation: quantum computers do not extend the operations that a classical computer can perform.Instead, they have the potential to make them more efficient.As such, when large problems are considered, they ought to present a shorter runtime than classical algorithms to surpass, in any sense of the word, a classical algorithm.We validate the proposed methodology by applying it to an exciting application of quantum computation within the field of system reliability: the identification of minimal cut sets via the leverage of the Grover algorithm and Quantum Amplitude Amplification.

European Safety and Reliability Conference (ESREL)•Jan 1, 2025•0 citations

Quantum Computational Complexity Theory and Lower Bounds

Phillip Kaye, Raymond Laflamme, Michele Mosca

We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.

Oxford University Press eBooks•Nov 16, 2006•0 citations

D5.4 Evaluation of quantum algorithms for pricing and computation of VaR

Gonzalo A. Casanova Ferro, Alberto Manzano, Andrés Gómez +3 more

NEASQC Use Case 5 (UC5) works on the development and evaluation of quantum algorithms for financial applications. More specifically, the main line of research in UC5 focuses on Pricing and Value at Risk (VaR) problems. These two problems are computationally demanding tasks that are classically solved using Monte Carlo (MC) techniques. As Quantum Accelerated Monte Carlo (QAMC) techniques promise a quadratic speedup over Classical Monte Carlo (CMC) this roughly motivates why and how this field could benefit from the recent advances in Quantum Computing. This report summarises the development of a new pricing algorithm as well as its experimental assessment. In the first part of the report there is a brief summary of the classical and quantum techniques used to tackle both financial challenges. In the second part of the report the new method is explained in detail and evaluated. This new method includes two well defined parts: a new encoding for the quantum oracle and a new Amplitude Estimation (AE) technique. The new proposals are not yet applicable to current NISQ architectures although they represent a clear advance because: The new encoding algorithm allows pricing derivative products with negative payoffs. In particular, as illustrated in Section 3.1, it works in cases where other proposals fail as it is the case for a payoff of the form V (x) = x−K. The new AE algorithm, the so-called Real Quantum Amplitude Estimation (RQAE), allows pricing financial products with negative values (see Figure 9), which is an absolute novelty in the area. Current AE algorithms in the literature are concerned with the efficient estimation of the probability of finding a particular state, but they are not designed to be sensitive to the phases present in the underlying amplitudes. In contrast, RQAE is specifically tailored to be sensible to the sign of the amplitude. RQAE achieves a similar performance when compared with other previous well-known AE algorithms. In fact, in reference (Manzano et al., 2022), tighter bounds on the convergence of RQAE than any of the existing methods in the literature are proved. In this work, the experimental results show that although the performance is not the best one, it is on par with the cutting edge methods. However, there are some less positive results as: The new encoding algorithm gives a worse performance compared to the standard encoding algorithm. It depends on a factor (Npaths) that can overshadow or even kill the speedup depending on its specific setup. Nevertheless, NEASQC researchers who participate in the Use Case are actively working in new encoding methods to solve this issue. Two identified challenges have to be addressed in the near future. On the one hand, how to improve these algorithms to execute on current Quantum Processing Units (QPU), where deep circuits such as those required by the AE routines are not feasible without error correction techniques. On the other hand, previous works such as (Montanaro, 2015; Rebentrost et al., 2018) implicitly assume that the simulation of the Stochastic Differential Equation (SDE) to solve for these financial calculations can be directly done by translating the classical circuits into quantum circuits. However, this direct translation would require in practice a number of qubits too far from the current possibilities of the NISQ era.

•Sep 30, 2022•0 citations
We present a technique to reduce the error probability of quantum algorithms that determine whether its input has a specified property of interest. The standard process of reducing this error is statistical processing of the results of multiple independent executions of an algorithm. Denoting by \ensuremathρ\ensuremath{\rho}\ensuremathρ an upper bound of this probability (wlog; assume \ensuremathρ\ensuremath≤12\ensuremath{\rho}\ensuremath{\le}\frac{1}{2}\ensuremathρ\ensuremath≤21​), classical techniques require O(\ensuremathρ[(1\ensuremath−\ensuremathρ)\ensuremath−\ensuremathρ]2)O(\frac{\ensuremath{\rho}}{{[(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}]}^{2}})O([(1\ensuremath−\ensuremathρ)\ensuremath−\ensuremathρ]2\ensuremathρ​) executions to reduce the error to a negligible constant. We investigate when and how quantum algorithmic techniques like amplitude amplification and estimation may reduce the number of executions. On one hand, the former idea does not directly benefit algorithms that can err on both yes and no answers and the number of executions in the latter approach is O(1(1\ensuremath−\ensuremathρ)\ensuremath−\ensuremathρ)O(\frac{1}{(1\ensuremath{-}\ensuremath{\rho})\ensuremath{-}\ensuremath{\rho}})O((1\ensuremath−\ensuremathρ)\ensuremath−\ensuremathρ1​). We propose a quantum approach called amplitude separation that combines both these approaches and achieves O(11\ensuremath−\ensuremathρ\ensuremath−\ensuremathρ)O(\frac{1}{\sqrt{1\ensuremath{-}\ensuremath{\rho}}\ensuremath{-}\sqrt{\ensuremath{\rho}}})O(1\ensuremath−\ensuremathρ​\ensuremath−\ensuremathρ​1​) executions, which betters existing approaches when the errors are high. In the multiple-weight decision problem, the input is an nnn-bit Boolean function f()f(\phantom{\rule{0.16em}{0ex}})f() given as a black box and the objective is to determine the number of xxx for which f(x)=1f(x)=1f(x)=1, denoted wt(f)wt(f)wt(f), given some possible values w1,...,wk{{w}_{1},...,{w}_{k}}w1​,...,wk​ for wt(f)wt(f)wt(f). When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using O(log2k2n)O({log}_{2}k\sqrt{{2}^{n}})O(log2​k2n​) calls to f()f(\phantom{\rule{0.16em}{0ex}})f(), which shows a quadratic speedup over classical approaches and currently known quantum algorithms.
Consider a Boolean function χ:X→{0,1}χ: X \to \{0,1\}χ:X→{0,1} that partitions set XXX between its good and bad elements, where xxx is good if χ(x)=1χ(x)=1χ(x)=1 and bad otherwise. Consider also a quantum algorithm A\mathcal AA such that A∣0⟩=∑x∈Xαx∣x⟩A |0\rangle= \sum_{x\in X} α_x |x\rangleA∣0⟩=∑x∈X​αx​∣x⟩ is a quantum superposition of the elements of XXX, and let aaa denote the probability that a good element is produced if A∣0⟩A |0\rangleA∣0⟩ is measured. If we repeat the process of running AAA, measuring the output, and using χχχ to check the validity of the result, we shall expect to repeat 1/a1/a1/a times on the average before a solution is found. *Amplitude amplification* is a process that allows to find a good xxx after an expected number of applications of AAA and its inverse which is proportional to 1/a1/\sqrt{a}1/a​, assuming algorithm AAA makes no measurements. This is a generalization of Grover's searching algorithm in which AAA was restricted to producing an equal superposition of all members of XXX and we had a promise that a single xxx existed such that χ(x)=1χ(x)=1χ(x)=1. Our algorithm works whether or not the value of aaa is known ahead of time. In case the value of aaa is known, we can find a good xxx after a number of applications of AAA and its inverse which is proportional to 1/a1/\sqrt{a}1/a​ even in the worst case. We show that this quadratic speedup can also be obtained for a large family of search problems for which good classical heuristics exist. Finally, as our main result, we combine ideas from Grover's and Shor's quantum algorithms to perform amplitude estimation, a process that allows to estimate the value of aaa. We apply amplitude estimation to the problem of *approximate counting*, in which we wish to estimate the number of x∈Xx\in Xx∈X such that χ(x)=1χ(x)=1χ(x)=1. We obtain optimal quantum algorithms in a variety of settings.
The goal in function property testing is to determine whether a black-box Boolean function has a certain property or is $\ensuremath{\epsilon}$-far from having that property. The performance of the algorithm is judged by how many calls need to be made to the black box in order to determine, with high probability, which of the two alternatives is the case. Here we present two quantum algorithms, the first to determine whether the function is linear and the second to determine whether it is symmetric (invariant under permutations of the arguments). Both require order ${\ensuremath{\epsilon}}^{\ensuremath{-}2/3}$ calls to the oracle, which is better than known classical algorithms. In addition, in the case of linearity testing, if the function is linear, the quantum algorithm identifies which linear function it is. The linearity test combines the Bernstein-Vazirani algorithm and amplitude amplification, while the test to determine whether a function is symmetric uses projective measurements and amplitude amplification.
Motivated by its unique capabilities, quantum computation has gained significant attention over the last decade with numerous models and algorithms proposed for dealing with engineering challenges.The field of risk and reliability has also seen a growing interest in this area, with studies exploring Quantum Machine Learning for remaining useful life, Quantum Optimization for condition monitoring in civil structures, and Quantum Inference for enhancing Bayesian network models, to name a few.However, a common limitation across these works is the lack of thorough comparisons between the proposed quantum algorithms and their state-of-the-art classical counterparts.This critical gap must be addressed not only to evaluate the field's current state reliably but also to guide its development toward the most promising paths for achieving a quantum advantage.There are two key challenges to addressing this gap.First, quantum computation operates on fundamentally different principles than traditional computing, making direct comparisons -such as using the number of iterations -often infeasible.Second, large-scale, error-corrected quantum computers are not yet available, so machine-to-machine comparisons are also not yet possible.In this paper, we detail a novel methodology to evaluate quantum algorithms against their classical counterparts.Our technique is based on a simple observation: quantum computers do not extend the operations that a classical computer can perform.Instead, they have the potential to make them more efficient.As such, when large problems are considered, they ought to present a shorter runtime than classical algorithms to surpass, in any sense of the word, a classical algorithm.We validate the proposed methodology by applying it to an exciting application of quantum computation within the field of system reliability: the identification of minimal cut sets via the leverage of the Grover algorithm and Quantum Amplitude Amplification.
We have seen in the previous chapters that quantum computers seem to be more powerful than classical computers for certain problems. There are limits on the power of quantum computers, however. Since a classical computer can simulate a quantum computer, a quantum computer can only compute the same set of functions that a classical computer can. The advantage of using a quantum computer is that the amount of resources needed by a quantum algorithm might be much less than what is needed by the best classical algorithm. In Section 9.1 we briefly define some classical and quantum complexity classes and give some relationships between them. Most of the interesting questions relating classical and quantum complexity classes remain open. For example, we do not yet know if a quantum computer is capable of efficiently solving an NP-complete problem (defined later). One can prove upper bounds on the difficulty of a problem by providing an algorithm that solves that problem, and proving that it will work within in a given running time. But how does one prove a lower bound on the computational complexity of a problem? For example, if we wish to find the product of two n-bit numbers, computing the answer requires outputting roughly 2n bits and that requires Ω(n) steps (in any computing model with finite-sized gates). The best-known upper bound for integer multiplication is O(n log n log log n) steps. It has proved extremely difficult to derive non-trivial lower bounds on the computational complexity of a problem. Most of the known non-trivial lower bounds are in the ‘black-box’ model (for both classical and quantum computing), where we only query the input via a ‘black-box’ of a specific form. We discuss the black-box model in more detail in Section 9.2. We then sketch several approaches for proving black-box lower bounds. The first technique has been called the ‘hybrid method’ and was used to prove that quantum searching requires Ω(√n) queries to succeed with constant probability. The second technique is called the ‘polynomial method’. We then describe a technique based on ‘block sensitivity’, and conclude with a technique known as the ‘adversary method’.
NEASQC Use Case 5 (UC5) works on the development and evaluation of quantum algorithms for financial applications. More specifically, the main line of research in UC5 focuses on Pricing and Value at Risk (VaR) problems. These two problems are computationally demanding tasks that are classically solved using Monte Carlo (MC) techniques. As Quantum Accelerated Monte Carlo (QAMC) techniques promise a quadratic speedup over Classical Monte Carlo (CMC) this roughly motivates why and how this field could benefit from the recent advances in Quantum Computing. This report summarises the development of a new pricing algorithm as well as its experimental assessment. In the first part of the report there is a brief summary of the classical and quantum techniques used to tackle both financial challenges. In the second part of the report the new method is explained in detail and evaluated. This new method includes two well defined parts: a new encoding for the quantum oracle and a new Amplitude Estimation (AE) technique. The new proposals are not yet applicable to current NISQ architectures although they represent a clear advance because: The new encoding algorithm allows pricing derivative products with negative payoffs. In particular, as illustrated in Section 3.1, it works in cases where other proposals fail as it is the case for a payoff of the form V (x) = x−K. The new AE algorithm, the so-called Real Quantum Amplitude Estimation (RQAE), allows pricing financial products with negative values (see Figure 9), which is an absolute novelty in the area. Current AE algorithms in the literature are concerned with the efficient estimation of the probability of finding a particular state, but they are not designed to be sensitive to the phases present in the underlying amplitudes. In contrast, RQAE is specifically tailored to be sensible to the sign of the amplitude. RQAE achieves a similar performance when compared with other previous well-known AE algorithms. In fact, in reference (Manzano et al., 2022), tighter bounds on the convergence of RQAE than any of the existing methods in the literature are proved. In this work, the experimental results show that although the performance is not the best one, it is on par with the cutting edge methods. However, there are some less positive results as: The new encoding algorithm gives a worse performance compared to the standard encoding algorithm. It depends on a factor (Npaths) that can overshadow or even kill the speedup depending on its specific setup. Nevertheless, NEASQC researchers who participate in the Use Case are actively working in new encoding methods to solve this issue. Two identified challenges have to be addressed in the near future. On the one hand, how to improve these algorithms to execute on current Quantum Processing Units (QPU), where deep circuits such as those required by the AE routines are not feasible without error correction techniques. On the other hand, previous works such as (Montanaro, 2015; Rebentrost et al., 2018) implicitly assume that the simulation of the Stochastic Differential Equation (SDE) to solve for these financial calculations can be directly done by translating the classical circuits into quantum circuits. However, this direct translation would require in practice a number of qubits too far from the current possibilities of the NISQ era.