When a quantum computer interacts and becomes entangled with its environment, it impacts the environment in such a way that the environment maintains a physical record of how the computer arrived at the desired output.
Here, in our simplistic diagram, we consider only two computational paths.
With decoherence present, quantum computation spills out the environment and results in not one, but two output states:
∣O1⟩∣O2⟩:=∣O⟩∣e1⟩=“computer shows output O, environment knows that path 1 was taken”:=∣O⟩∣e2⟩=“computer shows output O, environment knows that path 2 was taken”
The two final states O1 and O2 are identical if and only if ∣⟨e1∣e1⟩∣=1.
In this case, the environment does not know anything about what happened during the computation — there is quantum interference — and we add probability amplitudes corresponding to the two computational paths.
In contrast, the two final states O1 and O2 are completely different if and only if ∣⟨e1∣e2⟩∣=0.
Then there is only one path to the output — there is no quantum interference — and there is nothing to add.
Of course, there are also midway cases 0<∣⟨e1∣e2⟩∣<1 corresponding to partial distinguishability of the final states.
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 ∣ψ⟩⟨ψ∣ to a mixed state, which can be obtained by tracing over the environment.
We know that the state vector ∣ψ⟩=α∣0⟩+β∣1⟩ evolves as
(α∣0⟩+β∣1⟩)∣e⟩⟼α∣0⟩∣e00⟩+β∣1⟩∣e11⟩
and we can write this as the evolution of the projector ∣ψ⟩⟨ψ∣, and then trace over the environment to obtain
∣ψ⟩⟨ψ∣⟼+∣α∣2∣0⟩⟨0∣⟨e00∣e00⟩+αβ⋆∣0⟩⟨1∣⟨e11∣e00⟩α⋆β∣1⟩⟨0∣⟨e00∣e11⟩+∣β∣2∣1⟩⟨1∣⟨e11∣e11⟩.
Written in matrix form, this is
[∣α∣2α∗βαβ∗∣β∣2]⟼[∣α∣2α∗β⟨e00∣e11⟩αβ∗⟨e11∣e00⟩∣β∣2].
The off-diagonal elements (originally called coherences) vanish as ⟨e00∣e11⟩ approaches zero.
This is why this particular interaction is called decoherence.
Notice that
∣ψ⟩∣e⟩⟼1∣ψ⟩∣e1⟩+Z∣ψ⟩∣eZ⟩,
implies
∣ψ⟩⟨ψ∣⟼1∣ψ⟩⟨ψ∣1⟨e1∣e1⟩+Z∣ψ⟩⟨ψ∣Z⟨eZ∣eZ⟩,only if⟨e1∣eZ⟩=0, since otherwise we would have additional cross terms 1∣ψ⟩⟨ψ∣Z and Z∣ψ⟩⟨ψ∣1.
In this case (i.e. when ⟨e1∣eZ⟩=0) we can indeed say that, with probability ⟨e1∣e1⟩, nothing happens, and, with probability ⟨eZ∣eZ⟩, the qubit undergoes the phase-flip Z.
We can also represent this with the Kraus operators
E0E1=∣e1⟩⟨e1∣1=∣eZ⟩⟨eZ∣Z
which can be shown to satisfy E0†E0+E1†E1=1.
The process of decoherence is continuous.
It involves the environment gradually acquiring information about computational paths and the associated relative environmental states (∣e0⟩ and ∣e1⟩ in our example above), which evolve over time to become increasingly orthogonal to one another.
Despite this, we can perceive the influence of the environment on our system of interest — a collection of qubits in a quantum computer — in terms of discrete operations.
In essence, we can digitise quantum errors.