Interference versus success probability in quantum algorithms with imperfections

We study the importance of interference for the performance of Shor’s factoring algorithm and Grover’s search algorithm using a recently proposed interference measure. To this aim we introduce systematic unitary errors, random unitary errors, and decoherence processes in these algorithms. We show that unitary errors which destroy the interference destroy the efficiency of the algorithm, too. However, unitary errors may also create useless additional interference. In such a case the total amount of interference can increase, while the efficiency of the quantum computation decreases. For decoherence due to phase flip errors, interference is destroyed for small error probabilities, and converted into destructive interference for error probabilities approaching 1, leading to success probabilities which can even drop below the classical value. Our results show that in general, interference is necessary in order for a quantum algorithm to outperform classical computation, but large amounts of interference are not sufficient and can even lead to destructive interference with worse than classical success rates.

Figure 1

(Color online) Potentially available interference in the Grover algorithm with systematic unitary errors in the Hadamard gates, parametrized by the angle $\theta$, Eq. (4) (a); success probability $S$ of the algorithm (b); and success probability as function of interference (c). Black circles mean $n=4$, red squares $n=5$, green diamonds $n=6$, blue triangles up $n=7$, gray triangles left $n=8$. All curves are averaged over all values of the searched item $\alpha$.

Figure 2

(Color online) Same as Fig. 1, but for actually used interference.

Figure 3

(Color online) Potentially available interference in the Shor algorithm with systematic unitary errors in the Hadamard gates, parametrized by the angle $\theta$, Eq. (4) (a); success probability $S$ of the algorithm (b); and success probability as a function of interference (c). Black circles mean $n=6$ $\left[f\left(x\right)=2^x\left(\text{mod}3\right)\right]$, red squares $n=9$ $\left[f\left(x\right)=3^x\left(\text{mod}7\right)\right]$, green diamonds $n=12$ $\left[f\left(x\right)=7^x\left(\text{mod}15\right)\right]$. The inset is a closeup of the case $n=12$ close to the maximum.

Figure 4

(Color online) Same as Fig. 3, but for actually used interference.

Figure 5

(Color online) Potentially available interference in the Grover algorithm with random unitary errors in the Hadamard gates, parametrized by the interval $ϵ$, Eq. (4) (a); success probability $S$ of the algorithm (b); and success probability as function of interference (c) for $n=4$ to $n=7$. Same symbols as in Fig. 1.

Figure 6

(Color online) Actually used interference in the Grover algorithm with random unitary errors in the Hadamard gates, parametrized by the interval $ϵ$, Eq. (4) (a), and success probability $S$ as a function of interference (b). Same symbols as in Fig. 1. The success probability as a function of $ϵ$ is the same as in Fig. 5.

Figure 7

(Color online) Potentially available interference in Shor’s algorithm with random unitary errors in the Hadamard gates, parametrized by the interval $ϵ$, Eq. (4) (a); success probability of the algorithm (b); and success probability as a function of interference (c). Symbols as in Fig. 3. The inset shows a closeup of the curve for $n=12$.

Figure 8

(Color online) Actually used interference in Shor’s algorithm with random unitary errors in the Hadamard gates, parametrized by the interval $ϵ$, Eq. (4) (a), and success probability as a function of interference (b). Same symbols as in Fig. 3. The inset shows a closeup of the curve for $n=12$. The success probability as a function of $ϵ$ is the same as in Fig. 7.

Figure 9

(Color online) Potentially available interference in the Grover algorithm with decoherence through bit flips during the first Walsh-Hadamard transformation, as a function of the bit flip probability $p$ after each Hadamard gate (a). Same but for actually used interference (b). Success probability as a function of $p$ (c). All curves are for $n=4,\alpha =2$; $n_f=1$ black circles, $n_f=2$ red squares, $n_f=3$ green diamonds, $n_f=4$ blue triangles.

Figure 10

(Color online) Same as Fig. 9, but for phase flip errors.

Figure 11

(Color online) Potentially available interference in the Shor algorithm with decoherence through bit flips during the first Walsh-Hadamard transformation, as a function of the bit flip probability $p$ after each Hadamard gate, for $n=12$ (a), $n=9$ (b), $n=6$ (c). The symbols are $n_f=1$ black circles, $n_f=2$ red squares, $n_f=3$ green diamonds, $n_f=4$ blue up triangles, $n_f=5$ cyan down triangles, $n_f=6$ brown stars, $n_f=7$ gray $\times$, $n_f=8$ violet $+$. The corresponding success probability $S$ is a constant equal to $p=1$ for all values of $p$ (data not shown). Here and in the following figures all quantities are averaged over all possible choices of the $n_f$ qubits in the first register.

Figure 12

(Color online) Actually used interference in the Shor algorithm with decoherence through bit flips during the first Walsh-Hadamard transformation, as a function of the bit flip probability $p$ for $n=12$ (a), $n=9$ (b), $n=6$ (c). The corresponding success probability $S$ is a constant equal to $S=1$ for all values of $p$ (data not shown); symbols as in Fig. 11.

Figure 13

(Color online) Interference and success probability in the Shor algorithm with decoherence through bit flips during the first Walsh-Hadamard transformation, as a function of the bit flip probability $p$ after each Hadamard gate, with all $n$ qubits flipped, for $n=6$: potentially available interference (a), actually used interference (b), success probability (c). The inset is a closeup close to the minimum; symbols as in Fig. 11.

Figure 14

(Color online) Potentially available interference in the Shor algorithm with decoherence through phase flips during the first Walsh-Hadamard transformation, as a function of the phase flip probability $p$ after each Hadamard gate, for $n=12$ (a), $n=9$ (b), $n=6$ (c). The inset is a closeup of the case $n=12$ close to the minimum; symbols as in Fig. 11.

Figure 15

(Color online) Actually used interference in the Shor algorithm with decoherence through phase flips during the first Walsh-Hadamard transformation, as a function of the phase flip probability $p$ after each Hadamard gate for $n=12$ (a), $n=9$ (b), $n=6$ (c). The inset is a closeup of the case $n=12$ close to the minimum, showing that the value $\mathcal{I}=0$ is indeed reached for $p=0.5$.

Figure 16

(Color online) Success probability in the Shor algorithm with decoherence through phase flips during the first Walsh-Hadamard transformation, as a function of the phase flip probability $p$ after each Hadamard gate for $n=12$ (a), $n=9$, $a=3$ (b), $n=9$, $a=6$ (c), $n=6$ (d); symbols as in Fig. 11.