1.7 Computation: deterministic, probabilistic, and quantum
Take one physical bit or a qubit.
It has two logical 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 directed16 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 (

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:
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.↩︎