## 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 ** \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^{30} 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 (

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

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