1.7 Computation: deterministic, probabilistic, and quantum
One single qubit has two logical (i.e. non-superposition) states:
Think about computation as a physical process that evolves a prescribed initial configuration of a computing machine, called

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

Figure 1.5: Probabilistic computation.
The computation starts from some initial state (
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 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:
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.
So we read left to right, and omit the arrowheads.↩︎