Module 4: Classical and Quantum

Systems

1
 The Leap from Classical to Quantum

• Computer scientists feel comfortable with graphs and matrices.

• We shall cast quantum mechanical ideas in graph and matrix form.

• We will study three systems

1. Classical Deterministic System - the graphs are without weights.
2. Classical Probabilistic System - the graphs are weighted with real numbers.
3. Quantum Systems - the graphs are weighted with complex numbers.

Throughout this chapter, we first present an idea in terms of a toy model, then
generalize it to an abstract point, and finally discuss its connection with quantum
mechanics.
2
 Classical Deterministic System
We begin with a simple system described by a graph together with some toy
marbles. Imagine the identical marbles as being placed on the vertices of a graph. The
state of a system is described by how many marbles are on each vertex.
Let there be 6 vertices in a graph and a total of 27 marbles. We might place 6
marbles on vertex 0, 2 marbles on vertex 1, and the rest as described by this picture.

We shall denote this state as X = [6, 2, 1, 5, 3, 10]T.

3
We are concerned not only with the states of the system, but also with the way the
states change. How they change – or the dynamics of the system – can be
represented by a graph with directed edges.

An example of the dynamics might be described by the following directed graph:

The idea is that if an arrow exists from vertex i to vertex j , then in one time
click, all the marbles on vertex i will shift to vertex j .
4
This graph is easy to store in a computer as a Boolean adjacency matrix, M (for “marbles”):

where M[i, j ] = 1 if and only if there is an arrow from vertex j to vertex i. The requirement
that every vertex has exactly one outgoing edge corresponds to the fact that every column of
the Boolean adjacency matrix contains exactly one 1.
5
Let’s say that we multiply M by a state of the system X = [6, 2, 1, 5, 3, 10]T. Then we have

This means: If X describes the state of the system at time t, then Y is the state of the
system at time t + 1 , i.e., after one time click.
Notice that the top two entries of Y are 0. This corresponds to the fact that there are no
arrows going to vertex 0 or vertex 1.
Exercise : Using the dynamics given in slide 4, determine what the state of the system
would be if you start with the state [5, 5, 0, 2, 0, 15]T. 6
As we shall soon see, (finite-dimensional) quantum mechanics works the same way.
States of a system are represented by column vectors, and the way in which the system
changes in one time click is represented by matrices. Multiplying a matrix with a
column vector yields a subsequent state of the system.

• In quantum mechanics, if there are two or more matrices that manipulate states, the
action of one followed by another is described by their product.
• We shall take different states of systems and multiply the states by various matrices
(of the appropriate type) to obtain other ones.
• These new states will again be multiplied by other matrices until we attain the
desired end state.
• In quantum computing, we shall start with an initial state, described by a vector of
numbers. The initial state will essentially be the input to the system. Operations in a
quantum computer will correspond to multiplying the vector with matrices. The
output will be the state of the system when we are finished carrying out all the
operations.
7
Summing up, we have learned the following:

• The states of a system correspond to column vectors (state vectors).

• The dynamics of a system correspond to matrices.
• To progress from one state to another in one time step, one must multiply the
• state vector by a matrix.
• Multiple step dynamics are obtained via matrix multiplication.

8
 Classical Probabilistic System
In quantum mechanics, change in the state is governed by probabilistic law. This
means the change of state is defined by likelihood.

In order to capture these probabilistic scenarios, let us modify what we did in the last
section. Instead of dealing with a bunch of marbles moving about, we shall work with a
single marble.
• The state of the system will tell us the probabilities of the marble being on each vertex.
• For a three-vertex graph, a typical state might look like
X = [1/5, 3/10, 1/2]T.
• This will correspond to the fact that there is a one-fifth chance that the marble is on
vertex 0, a three-tenths chance that the marble is on vertex 1; and a half chance that the
marble is on vertex 2.
• Because the marble must be somewhere on the graph, the sum of the probabilities is 1.
9
 An example of such a graph is

The adjacency matrix for this graph is

The adjacency matrices for our graphs will have real entries between 0 and 1 where the sums of
the rows and the sums of the columns are all 1. Such matrices are called doubly stochastic. 10
Let us see how the states interact with the dynamics. Suppose we have a state
X = [1/6, 1/6, 2/3]T
that expresses an indeterminacy about the position of a marble: the probability is 1/6 that the marble
is on vertex 0, the probability is 1/6 that the marble is on vertex 1, and the probability is 2/3 that the
marble is on vertex 2.
With this interpretation, we will calculate how a state changes:

Notice that the sum of the entries of Y is 1. We might express this by saying
If the marble’s position is 1/6 chance on vertex 0, 1/6 chance on vertex 1, and 2/3 chance on vertex 2,
then, after following the arrows, the probability of the marble’s position is
21/36 chance on vertex 0, 9/36 chance on vertex 1, and 6/36 chance on vertex 2. 11
We shall multiply vectors not only on the right of a matrix, but on the left as well. We
shall posit that a row vector will also correspond to a state of a system.
Take a row vector where the sum of the entries is 1. Multiply it on the left of M.
W = [1/3, 0, 2/3]. Then we have

Notice that the sum of the entries of Z is 1.

12
The transpose of M

corresponds to our directed graph with the arrows reversed:

Reversing the arrows is like traveling back in time or having the marble roll backward.
13
A simple calculation shows that

i.e.,

So if multiplying on the right of M takes states from time t to time t + 1, then multiplying
on the left of M takes states from time t to time t − 1.
This time symmetry is one of the fundamental concepts of quantum mechanics and
quantum computation. Our description of system dynamics is entirely symmetric: by
replacing column vectors with row vectors, and forward evolution in time with backward
evolution, the laws of dynamics still hold. 14
Example : Let us tackle a real example: the stochastic billiard ball.
Consider the graph

Corresponding to this graph is the matrix

15
Notice that A is a doubly stochastic matrix. Let us start with a single marble on vertex
0; that is, we shall start in state [1, 0, 0, 0]T. After one time click, the system will be in
state

A quick calculation shows that in another time click, the system will be in state

Continuing in this fashion, we find that the marble acts like a billiard ball and continues
to bounce back and forth between vertices 1,2 and 0,3.
We shall meet a quantum version of this example in the next section.
16