1.7 Computation: deterministic, probabilistic, and quantum

One single qubit has two logical (i.e. non-superposition) states: |0\rangle and |1\rangle. Bring another qubit and the combined systems has four logical states: |00\rangle, |01\rangle,|10\rangle, and |11\rangle. In general n qubits will give us 2^n states, representing all possible binary strings of length n. It is important to use subsystems — here qubits — rather than one chunk of matter, since, by operating on at most n qubits, we can reach any of the 2^n states of the composed system. Now, if we let the qubits interact in a controllable fashion, then we are computing!

Think about computation as a physical process that evolves a prescribed initial configuration of a computing machine, called \texttt{INPUT}, into some final configuration, called \texttt{OUTPUT}. We shall refer to the configurations as states. Figure 1.4 shows five consecutive computational steps performed on four distinct states.

Deterministic computation.

Figure 1.4: Deterministic computation.

That computation was deterministic: every time you run it with the same input, you get the same output.

But a computation does not have to be deterministic — we can augment a computing machine by allowing it to “toss an unbiased coin” and to choose its steps randomly. It can then be viewed as a directed30 tree-like graph where each node corresponds to a state of the machine, and each edge represents one step of the computation, as shown in Figure 1.5

Probabilistic computation.

Figure 1.5: Probabilistic computation.

The computation starts from some initial state (\texttt{INPUT}) and it subsequently branches into other nodes representing states reachable with non-zero probability from the initial state. The probability of a particular final state (\texttt{OUTPUT}) being reached is equal to the sum of the probabilities along all mutually exclusive paths which connect the initial state with that particular state. Figure 1.5 shows only two computational paths, but, in general, there could be many more paths (here, up to 256) contributing to the final probability.

Quantum computation can be represented by a similar graph, as in 1.6.

Quantum computation.

Figure 1.6: Quantum computation.

For quantum computations, we associate with each edge in the graph the probability amplitude that the computation follows that edge. The probability amplitude that a particular path to be followed is the product of amplitudes pertaining to the transitions in each step. The probability amplitude of a particular final state being reached is equal to the sum of the amplitudes along all mutually exclusive paths which connect the initial state with that particular state: z = \sum_{\mathrm{all\,paths}\,k} z_k. The resulting probability, as we have just seen, is the sum of the probabilities pertaining to each computational path p_k modified by the interference terms: \begin{aligned} p &= |z|^2 \\&= \sum_{k,j} z_j^\star z_k \\&= \sum_k p_k + \sum_{k\ne j} \sqrt{p_k p_j}\cos(\varphi_k-\varphi_j). \end{aligned}

Quantum computation can be viewed as a complex multi-particle quantum interference involving many computational paths through a computing device. The art of quantum computation is to shape the quantum interference through a sequence of computational steps, enhancing probabilities of the “correct” outputs and suppressing probabilities of the “wrong” ones.

  1. So we read left to right, and omit the arrowheads.↩︎