Decoherence and interference
Suppose a qubit undergoes the usual single-qubit interference evolution, but, between the phase gate and the second Hadamard gate, it is affected by decoherence:
\begin{aligned}
\times\colon
|0\rangle|e\rangle
&\longmapsto |0\rangle|e_{00}\rangle
\\|1\rangle|e\rangle
&\longmapsto |1\rangle|e_{11}\rangle
\end{aligned}
as described by Figure 13.1.
Let us step through the circuit in Figure 13.1, keeping track of the state of the environment:
\begin{aligned}
|0\rangle|e\rangle
& \overset{H}{\longmapsto} \Big( |0\rangle + |1\rangle \Big) |e\rangle
\\& \overset{\phi}{\longmapsto} \Big( |0\rangle + e^{i\phi}|1\rangle \Big) |e\rangle
\\& \overset{\times}{\longmapsto} |0\rangle|e_{00}\rangle + e^{i\phi}|1\rangle|e_{11}\rangle
\\& \overset{H}{\longmapsto} |0\rangle\Big( |e_{00}\rangle + e^{i\phi}|e_{11}\rangle \Big) + |1\rangle\Big( |e_{00}\rangle - e^{i\phi}|e_{11}\rangle \Big).
\end{aligned}
Writing \langle e_{00}|e_{11}\rangle=ve^{i\alpha} for v\in\mathbb{R}_{\geqslant 0} and \alpha\in[0,2\pi), the final probability P_k of measuring the output to be in state |k\rangle oscillates with \phi as
\begin{aligned}
P_{0}(\phi) &= \frac{1}{2}\big(1 + v\cos(\phi + \alpha)\big),
\\P_{1}(\phi) &= \frac{1}{2}\big(1 - v\cos(\phi + \alpha)\big).
\end{aligned}
As we can see in Figure 13.2, the interference pattern is suppressed by a factor v, which we call the visibility.
As v=|\langle e_{00}|e_{11}\rangle| gets closer and closer to 0, we lose all the advantages of quantum interference.
For example, in Deutsch’s algorithm (Section 10.4) we would obtain the correct answer with probability at most \frac{1}{2}(1+v).
For \langle e_{00}|e_{11}\rangle = 0, the case of perfect decoherence, the network outputs 0 or 1 with equal probabilities, i.e. it is useless as a computing device.
It is clear that we want to avoid decoherence, or at least diminish its impact on our computing device.
For this we need quantum error correction: we encode the state of a single (logical) qubit across several (physical) qubits.
If we wish to study the evolution of the qubit alone, then we can do so in terms of density operators: it evolves from the pure state |\psi\rangle\langle\psi| to a mixed state, which can be obtained by tracing over the environment.
We know that the state vector |\psi\rangle=\alpha|0\rangle+\beta|1\rangle evolves as
\left( \alpha|0\rangle +\beta |1\rangle\right)|e\rangle \longmapsto
\alpha |0\rangle|e_{00}\rangle +\beta |1\rangle |e_{11}\rangle
and we can write this as the evolution of the projector |\psi\rangle\langle\psi|, and then trace over the environment to obtain
\begin{aligned}
|\psi\rangle\langle\psi| \longmapsto & |\alpha|^2|0\rangle\langle 0| \langle e_{00}|e_{00}\rangle+ \alpha\beta^\star |0\rangle\langle 1|\langle e_{11}|e_{00}\rangle
\\+ &\alpha^\star\beta |1\rangle\langle 0|\langle e_{00}|e_{11}\rangle + |\beta|^2|1\rangle\langle 1|\langle e_{11}|e_{11}\rangle.
\end{aligned}
Written in matrix form, this is
\begin{bmatrix}
|\alpha|^2 & \alpha\beta^\ast
\\\alpha^\ast\beta & |\beta|^2
\end{bmatrix}
\longmapsto
\begin{bmatrix}
|\alpha|^2 & \alpha\beta^\ast \langle e_{11}|e_{00}\rangle
\\\alpha^\ast\beta \langle e_{00}|e_{11}\rangle & |\beta|^2
\end{bmatrix}.
The off-diagonal elements (originally called coherences) vanish as \langle e_{00}|e_{11}\rangle approaches zero.
This is why this particular interaction is called decoherence.
Notice that
|\psi\rangle|e\rangle \longmapsto \mathbf{1}|\psi\rangle|e_{\mathbf{1}}\rangle+Z|\psi\rangle|e_Z\rangle,
implies
|\psi\rangle\langle\psi|\longmapsto \mathbf{1}|\psi\rangle\langle\psi| \mathbf{1}\langle e_{\mathbf{1}}|e_{\mathbf{1}}\rangle +Z|\psi\rangle\langle\psi| Z\langle e_Z|e_Z\rangle,
only if \langle e_{\mathbf{1}}|e_Z\rangle=0, since otherwise we would have additional cross terms \mathbf{1}|\psi\rangle\langle\psi|Z and Z|\psi\rangle\langle\psi|\mathbf{1}.
In this case (i.e. when \langle e_{\mathbf{1}}|e_Z\rangle=0) we can indeed say that, with probability \langle e_{\mathbf{1}}|e_{\mathbf{1}}\rangle, nothing happens, and, with probability \langle e_Z|e_Z\rangle, the qubit undergoes the phase-flip Z.