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 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•19 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

Mitigating errors by quantum verification and postselection

Rawad Mezher, James K. Mills, Elham Kashefi

Correcting errors due to noise in quantum circuits run on current and near-term quantum hardware is essential for any convincing demonstration of quantum advantage. Indeed, in many cases it has been shown that noise renders quantum circuits efficiently classically simulable, thereby destroying any quantum advantage potentially offered by an ideal (noiseless) implementation of these circuits. Although the technique of quantum error correction (QEC) allows correcting these errors very accurately, QEC usually requires a large overhead of physical qubits which is not reachable with currently available quantum hardware. This has been the motivation behind the field of quantum error mitigation, which aims at developing techniques to correct an important part of the errors in quantum circuits, while also being compatible with current and near-term quantum hardware. In this work, we present a technique for quantum error mitigation which is based on a technique from quantum verification, the so-called accreditation protocol, together with postselection. Our technique allows for correcting the expectation value of an observable $O$, which is the output of multiple runs of noisy quantum circuits, where the noise in these circuits is at the level of preparations, gates, and measurements. We discuss the sample complexity of our procedure and provide rigorous guarantees of errors being mitigated under some realistic assumptions on the noise. Our technique is tailored to time-dependent behaviors, as we allow for the output states to be different between different runs of the accreditation protocol. We validate our findings by running our technique on currently available quantum hardware.

arXiv:2109.14329•Physical Review A•May 27, 2022•14 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

Modelling for Quantum Error Mitigation

Tom Weber, Matthias Riebisch, K. Borras +2 more

While we expect quantum computers to surpass their classical counterparts in the future, current devices are prone to high error rates and techniques to minimise the impact of these errors are indispensable. There already exists a variety of error mitigation methods addressing this quantum noise that differ in effectiveness, and scalability. But for a more systematic and comprehensible approach we propose the introduction of modelling, in particular for representing cause-effect relations as well as for evaluating methods or combinations thereof with respect to a selection of relevant criteria.

arXiv:2104.07320•IEEE International Conference on Software Architecture Companion (ICSA-C)•Mar 1, 2021•2 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.
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.
Correcting errors due to noise in quantum circuits run on current and near-term quantum hardware is essential for any convincing demonstration of quantum advantage. Indeed, in many cases it has been shown that noise renders quantum circuits efficiently classically simulable, thereby destroying any quantum advantage potentially offered by an ideal (noiseless) implementation of these circuits. Although the technique of quantum error correction (QEC) allows correcting these errors very accurately, QEC usually requires a large overhead of physical qubits which is not reachable with currently available quantum hardware. This has been the motivation behind the field of quantum error mitigation, which aims at developing techniques to correct an important part of the errors in quantum circuits, while also being compatible with current and near-term quantum hardware. In this work, we present a technique for quantum error mitigation which is based on a technique from quantum verification, the so-called accreditation protocol, together with postselection. Our technique allows for correcting the expectation value of an observable OOO, which is the output of multiple runs of noisy quantum circuits, where the noise in these circuits is at the level of preparations, gates, and measurements. We discuss the sample complexity of our procedure and provide rigorous guarantees of errors being mitigated under some realistic assumptions on the noise. Our technique is tailored to time-dependent behaviors, as we allow for the output states to be different between different runs of the accreditation protocol. We validate our findings by running our technique on currently available quantum hardware.
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’.
While we expect quantum computers to surpass their classical counterparts in the future, current devices are prone to high error rates and techniques to minimise the impact of these errors are indispensable. There already exists a variety of error mitigation methods addressing this quantum noise that differ in effectiveness, and scalability. But for a more systematic and comprehensible approach we propose the introduction of modelling, in particular for representing cause-effect relations as well as for evaluating methods or combinations thereof with respect to a selection of relevant criteria.
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.