Quantitative measure of interference

We introduce an interference measure which allows to quantify the amount of interference present in any physical process that maps an initial density matrix to a final density matrix. In particular, the interference measure enables one to monitor the amount of interference generated in each step of a quantum algorithm. We show that a Hadamard gate acting on a single qubit is a basic building block for interference generation and realizes one bit of interference, an “ibit.” We use the interference measure to quantify interference for various examples, including Grover’s search algorithm and Shor’s factorization algorithm. We distinguish between “potentially available” and “actually used” interference, and show that for both algorithms the potentially available interference is exponentially large. However, the amount of interference actually used in Grover’s algorithm is only about $3\mathrm{ibits}$ and asymptotically independent of the number of qubits, while Shor’s algorithm indeed uses an exponential amount of interference.

Figure 1

(Color online) Amount of interference $\mathcal{I}$ (dimensionless) generated by a beam splitter as function of the angle $\theta$ (in radians) and $N=1,\dots ,20$ photons (top). The amount of entanglement at $\theta =\pi ∕4$ increases approximately linearly with $N$ (bottom). The full line is $\mathcal{I}=N$.

Figure 2

(Color online) Accumulated interference generated in a Mach-Zehnder interferometer as function of the angles $\theta$ and $\varphi$ (in radians) for 1 photon (top) and 20 photons (bottom). Note the different scale.

Figure 3

(Color online) Accumulated interference during the quantum teleportation protocol [7]. On the $t$ axis is the step number (see text). The interference is plotted for the entire propagator up to and including step number $t$. Interference only arises during the application of the two Hadamard gates and is conserved during all other steps, including the measurement (step 5). A maximum amount of interference of about $2.58\mathrm{ibits}$ $(\mathcal{I}=6)$ is generated.

Figure 4

(Color online) Accumulated interference generated during Shor’s algorithm for factorization of $R=15$ ($L=\left[{\log }_{2}R\right]+1=4$ and in total $n=3L=12\text{qubits}$). On the $t$ axis is the step number (see text). The interference is plotted for the entire propagator up to and including step number $t$. Values of $a$ are $a=13$ (circles, full red line), $a=7$ (squares, dashed green line), $a=11$ (diamonds, full blue line), $a=8$ (triangles up, full black line), $a=14$ (triangles down, full cyan line), $a=4$ (crosses, full orange line), $a=2$ (stars, dashed violet line). Data for different values of $a$ differ only for the last two time steps. Data from $a=13$ and $a=7$ are the same, as are data from $a=8$ and $a=2$. The horizontal dashed red line is the maximum possible value of interference for an untouched second register, $\mathcal{I}=2^n-2^L=4080$. The inset shows the same curves for the last steps on a different scale. Lines are there to guide the eye only. Massive interference $\mathcal{I}=2^n-2^L$ (or almost $n$ ibits) is generated during the application of the Walsh-Hadamard transform (part 1, first eight points). Interference is unchanged in part 2 (next eight points), and decreases during the last part (QFT) (last eight points).

Figure 5

Accumulated interference up to and including step number $t$ generated during Shor’s algorithm, excluding the initial Walsh-Hadamard transform for factorization of $R=15$ ($n=12\text{qubits}$). The step number on the $t$-axis is the same as in Fig. 4 but shifted by 8. Horizontal dashed red line is maximum possible value of interference for transformations of the first register alone $\mathcal{I}=4080$. The accumulated interference is changed only during the final quantum Fourier transform, and does not depend on the value of $a$. The actually used interference shown here is comparable with the potentially available interference shown in Fig. 4.

Figure 6

(Color online) Accumulated interference in Grover’s algorithm $U_G$ [16] for $n=8\text{qubits}$. On the $t$-axis is the step number (see text). The interference is plotted for the entire propagator up to and including step number $t$. Massive maximum interference ${\mathcal{I}}_{\max }=2^n-1=255$ (or $n=8\mathrm{ibits}$) is generated during the application of the Walsh-Hadamard gate (step 1) and the accumulated interference decreases subsequently during the iteration of oracle and diffusion to the value $\mathcal{I}\simeq 2^n-2$, at which point virtually all probability corresponding to the initial state ∣0⋯0⟩ is concentrated on the searched state.

Figure 7

(Color online) Accumulated interference up to and including step number $t$ generated during Grover’s algorithm ${\tilde{U}}_G$, excluding the initial Walsh-Hadamard transform [16] for $n=7\text{qubits}$. The step number on the $t$ axis is shifted by one compared to Fig. 6, i.e., step 1 is now the first application of the oracle $R_1$, which does not lead to interference. The accumulated interference is changed only during the diffusion steps $D=W{R}_{2}W$. The “actually used” interference shown here is much smaller than the “potentially available” interference shown in Fig. 6, and the maximum value $\mathcal{I}\simeq 8$ after the first application of $D$ is asymptotically independent of the number of qubits. This is quite different from what happens in Shor’s algorithm (compare with Fig. 5).