Error reduction of quantum algorithms

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 $\rho$ an upper bound of this probability (wlog; assume $\rho \le \frac{1}{2}$), classical techniques require $O\left(\frac{\rho }{{[(1-\rho )-\rho ]}^2}\right)$ 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\left(\frac{1}{(1-\rho )-\rho }\right)$. We propose a quantum approach called amplitude separation that combines both these approaches and achieves $O\left(\frac{1}{\sqrt{1-\rho }-\sqrt{\rho }}\right)$ 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\left(\right)$ given as a black box and the objective is to determine the number of $x$ for which $f\left(x\right)=1$, denoted $wt\left(f\right)$, given some possible values $\{w_1,...,w_k\}$ for $wt\left(f\right)$. When our technique is applied to this problem, we obtain the correct answer, maybe with a negligible error, using $O\left({log}_{2}k\sqrt{2^n}\right)$ calls to $f\left(\right)$, which shows a quadratic speedup over classical approaches and currently known quantum algorithms.

Figure 1

Comparison of the dominant terms in the query complexity of the classical, amplitude-estimation-based and amplitude-separation-based error reduction algorithms; the Y axis shows the values of the dominant terms and the X axis shows ${\rho }_n$. The plot for ${\rho }_y=0.5$ (not shown) is identical to that for ${\rho }_y=0.7$, indicating that amplitude separation works best for high values of ${\rho }_y$ and is reasonably good for lower values.

Figure 2

The case $sin\theta \ge sin\tau$ (left) and the case $sin\theta \le \beta sin\tau$ (right) of Algorithm lg1, before and after amplification. The Y axis represents the probability $p$ of observing $|1\rangle$ and the X axis represents the probability of observing $|0\rangle$.

Figure 3

Quantum circuit for the WDP with bounded error.

Figure 4

Proof of the fact that $sin\theta \le asint\Rightarrow \theta \le at$.