## 2.1 Composing quantum operations

In order to understand something in its full complexity it is always good to start with the simplest case. Let us take a closer look at quantum interference in the simplest possible computing machine: the one that has only two distinguishable configurations — two quantum states — which we label as |0\rangle and |1\rangle. We prepare the machine in some input state, usually |0\rangle, and let it evolve: the machine undergoes a prescribed sequence of computational steps, each of which induces transitions between the two “computational states”, |0\rangle and |1\rangle. The machine then ends in the output state |\psi\rangle=\alpha_0|0\rangle+\alpha_1|1\rangle, meaning the two outputs, |0\rangle and |1\rangle, are reached with probability amplitudes \alpha_0 and \alpha_1, respectively. In the process of computation each computational step U (also referred to as an operation) sends state |k\rangle to state |l\rangle, where k,l=0,1, but only with some amplitude U_{lk}. We write this as |k\rangle \longmapsto \sum_l U_{lk} |l\rangle. (watch out for the order of the indices).

Thus any computational step U of this machine can be described by a matrix which tabulates all the transition amplitudes: U = \begin{bmatrix} U_{00} & U_{01} \\U_{10} & U_{11} \end{bmatrix}. The matrix element U_{lk} represents the amplitude of transition from state |k\rangle to state |l\rangle (again, watch the order of indices). To be clear, the entries in this matrix are not any random complex numbers: their moduli squared represent transition probabilities, which in turn implies that such matrices must be unitary.28

We can also describe U by drawing a diagram, which contains exactly the same information as the matrix representation, but just in a different form:

Now how can we find some quantum interference to study? Consider two computational steps, U and V. What is the amplitude that input |k\rangle will generate output |m\rangle? We have to check all computational paths leading from input |k\rangle to output |m\rangle and add the corresponding amplitudes. For example, as you can see in Figure 2.1, input |0\rangle and output |1\rangle are connected by the two computational paths: |0\rangle\mapsto|0\rangle\mapsto|1\rangle (amplitude V_{10}U_{00}) and |0\rangle\mapsto|1\rangle\mapsto|1\rangle (amplitude V_{11}U_{10}). Thus the total amplitude that input |0\rangle gives output |1\rangle is the sum V_{10}U_{00}+V_{11}U_{10}, and when we take the modulus squared of this expression we will see the interference term.

In general, given U and V \begin{aligned} |k\rangle &\longmapsto \sum_l U_{lk}|l\rangle \\|l\rangle &\longmapsto \sum_m V_{ml}|m\rangle \end{aligned} we can compose the two operations: we first apply U, and then V, to obtain \begin{aligned} |k\rangle &\longmapsto \sum_l U_{lk} \left( \sum_m V_{ml}|m\rangle \right) \\&= \sum_m \left( \sum_l V_{ml}U_{lk} \right) |m\rangle \\&= \sum_m (VU)_{mk} |m\rangle. \end{aligned}

If you want to hone your quantum intuition think about it the following way. The amplitude that input |k\rangle evolves to |m\rangle via a specific intermediate state |l\rangle is given by V_{ml}U_{lk} (evolutions are independent so the amplitudes are multiplied). This done, we have to sum over all possible values of l (the transition can occur in several mutually exclusive ways so the amplitudes are added) to obtain \sum_l V_{ml}U_{lk}. Thus the matrix multiplication VU (watch the order of matrices) in one swoop takes care of multiplication and addition of amplitudes corresponding to different computational paths.

1. Recall that matrix U is called unitary if U^\dagger U = UU^\dagger = \mathbf{1} where the adjoint or Hermitian conjugate U^\dagger of any matrix U with complex entries U_{ij} is obtained by taking the complex conjugate of every element in the matrix and then interchanging rows and columns (U^\dagger_{kl}= U^\star_{lk}).↩︎