1.7 Computation: deterministic, probabilistic, and quantum

Take one physical bit or a qubit. It has two logical 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, for operating on at most n qubits we can reach any of the 2^n states of the composed system. Now, let the qubits interact in a controllable fashion. 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.

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 directed¹⁶ 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

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.

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 of a particular path to be followed is the product of amplitudes pertaining to 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 quantum interference, through a sequence of computational steps, enhancing probabilities of correct outputs and suppressing probabilities of the wrong ones.

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