## 1.7 Computation: deterministic, probabilistic, and quantum

Take one physical bit or a qubit.
It has two logical states: ** \texttt{INPUT}**, into some final configuration, called

**. We shall refer to the configurations as**\texttt{OUTPUT}

**states**. Figure 1.4 shows five consecutive computational steps performed on four distinct states.

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^{16} 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

The computation starts from some initial state (

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