INDIAN INSTITUTE OF TECHNOLOGY ROORKEE

IPH-305: Quantum Computing

An introduction

P. Arumugam ()

Department of Physics
[email protected]
Phone: 5712, 8979890366
 Refer class notes for
introductory topics

The rest of the lectures are based on

Quantum Computation and Quantum Information

Michael A. Nielsen & Isaac L. Chuang

2
Notations

3
Linear independence and Bases
A spanning set for a vector space is a set of vectors |1 , . . . , |
Such that any vector | in the vector space can be written as a linear
combination of vectors as | = |
1 0
Eg.: A spanning set for the vector space 2 is |1 = ; |2 =
0 1
1
Any vector | = in 2 can be written as | = 1 |1 + 2 |2
2
|1 and |2 SPAN the vector space 2
Generally, a vector space may have many different spanning sets
1 1 1 1
Eg.: |1 = ; |2 =
2 1 2 1
+
| = 1 2 |1 + 1 2 |2
2 2
A set of non-zero vectors |1 , , | are linearly dependent if there exists
a set of complex numbers 1 , , with 0 for at least one value of ,
such that 1 |1 + 2 |2 + + | = 0.
A set of vectors is linearly independent if it is NOT linearly dependent.
We call such a set a basis for .
4
Linear operators & matrix representation
A linear operator between vector spaces and is :
is linear in its inputs: | = (| ) .
(|) |
is defined on :
Identity operator: | | |
Zero operator: 0| 0
If we have : and : , | (|)

=
An complex matrix with entries is a linear operator :

matrices can be regarded as linear operators

If |1 , , | is a basis for & |1 , , | is a basis for , then for

each in the range 1, , , there exist 1 through such that | =
| .
forms a matrix representation of the operator
operators can be regarded as matrices 5
The Pauli matrices
0 1
1 =
1 0
0
2 =
0
1 0
3 =
0 1
1 0
0 =
0 1

det = 1
Tr = 0
Recap: Trace of a matrix is the sum of eigenvalues.
Each of the Pauli matrices has two eigenvalues, +1 and 1.
= , form a basis for the vector space of 2 2 Hermitian matrices.

In quantum information, single-qubit quantum gates are 2 2 unitary

matrices.
6
Inner product & Hilbert space
= (|, | )
An inner product is a function which takes as input two vectors | and
| from a vector space and produces a complex number as output.
A function (,) or | from to is an inner product if it satisfies the
requirements that:
1) | is linear in the second argument = .
2) = .
3) 0 with = 0 if and only if | = 0.
Eg. has an inner product: 1 , , 1 , , =
1
[1 , , ]

We call a vector space equipped with an inner product an inner product
space.
Hilbert space is the same thing as an inner product space.
For the finite dimensional complex vector spaces that come up in
quantum computation, the above statement is exact.
7
Orthonormal basis
= 0 | and | are orthogonal
The norm of a vector |: | =
| = 1 | is a unit vector; | is normalized
Remember = = 2

|
| is not normalized, is normalized
|
A set | of vectors with index is orthonormal if each vector is a unit
vector, and distinct vectors in the set are orthogonal
i.e. = , where and are both chosen from the same index set
Gram-Schmidt procedure:
|1 , , | is a basis for with an inner product
An orthonormal basis set |1 , , | for can be constructed
|1 |+1
+1
|1 = ; |+1 = =1
for 1 1
|1 |+1
=1
+1
Thus, any finite dimensional vector space of dimension has an
orthonormal basis |1 , , |
8
Inner & outer products on a Hilbert space
Let | = | & | = | with =
= |, | = =
1
= = [1 , , ] ; Note: | = |

The inner product of two vectors is equal to the vector inner product
between two matrix representations of those vectors, provided the
representations are written with respect to the same orthonormal basis.

Outer product: : (| | )| = | = |
| = | || = | | = |
| = |Completeness relation

For : |1, , | (orthonormal) with a subspace : |1, , |

(orthonormal)
The projector onto subspace is =1| |
The orthogonal complement of is spanning | + 1, , |
9
Definitions
| = |
Diagonal representation for an operator = | |where the
vectors | form an orthonormal set of eigenvectors for , with
corresponding eigenvalues .
Eg. = 1 0
=
1 0

0 0
=
1
1 0
0
0 1 = |00| |11|
0 1 0 0 0 1 0 1
Diagonal representations orthonormal decompositions.
When an eigenspace is more than 1d, we say that it is degenerate.
2 0 0
Eg. 0 2 0 , eigenvectors (1,0,0) and (0,1,0) for the eigenvalue 2.
0 0 0
Hermitian or self-adjoint: = Normal: =
Projector is hermitian Positive: = real & positive
Unitary: = 1 Positive definite: as above but | 0
= exp is unitary , if Hermitian
Spectral decomposition: Any normal operator is diagonalizable (has a
orthornormal basis). Converse is also true.
10
Tensor product
The tensor product is a way of putting vector spaces together to form
larger vector spaces.
Suppose and are Hilbert spaces of dimension and respectively,
The tensor product (Read tensor ) is of dimension .
if | and | are orthonormal bases for the spaces and then | |
is a basis for .
=
If is an by matrix, and is a by matrix,

11 12 1
22 2
21

1 2
Terms like 11 denote by submatrices

11
Tensor product: examples
2 12 2
1
1 2 3
= = 13 = 3
2 3 2 22 4
2
3 23 6

The tensor product of the Pauli matrices

0 0 0
0 1 0 0 1
= = = 0 0 0
1 0 0 1 0 0 0 0
0 0 0
| means | is tensored with itself times
Eg. |2 = | |

Operators distribute over tensor product: =
=
=

12
More definitions
tr
Cyclic, tr = tr , and linear, tr + = tr + tr
tr = tr where is a complex number
tr = sum of eigenvalues of
Trace is invariant under the unitary similarity transformation
tr = tr = tr

Commutator: , = , = 2
If , = 0, commutes with , = 2
, = 2

Anti-commutator: , = +
, = 0 where
If {, } = 0, anti-commutes with

If and are Hermitian, , = 0 if and only if if there exists an

orthonormal basis such that both and are diagonal with respect to
that basis. and are simultaneously diagonalizable in this case.
13
Postulate 1 & qubit
Postulate 1: Associated to any isolated physical system is a complex
vector space with inner product (that is, a Hilbert space) known as the
state space of the system. The system is completely described by its
state vector, which is a unit vector in the systems state space.
(For every observable there is an operator)

A qubit has a two-dimensional state space.

1 0
0 = and 1 = form an orthonormal basis for that state space.
0 1
| = 0 + |1
Normalization: = 1 2 + 2 = 1
A qubits state is a unit vector in a 2D complex vector space
The way a qubit differs from a bit is that superpositions of the two states,
of the form 0 + |1, can also exist
1 1 1 1
Eg. A state 0 1 has amplitudes and for the basis states
2 2 2 2
0 and 1 , respectively

14
Postulate 2 & choice of
Postulate 2: The evolution of a closed quantum system is described by a
unitary transformation. That is, the state | of the system at time 1 is
related to the state | of the system at time 2 by a unitary operator
such that |(2 ) = (1 , 2 )|(1 )
Pauli matrices could be those unitary operators for qubit systems
0 1 1 0
Eg. |0 = = = |1
1 0 0 1
|1 = |0; quantum NOT gate
|0 = |0; |1 = |1 phase flip

Closed system: not interacting in any way with other systems.

In reality, of course, all systems (except the Universe as a whole) interact
at least somewhat with other systems. Nevertheless, there are interesting
systems which can be described to a good approximation as being
closed, and which are described by unitary evolution to some good
approximation.
Open quantum systems: more exciting!
15
Postulate 2 & choice of
Postulate 2:The time evolution of the state of a closed quantum system
is described by the Schrdinger equation
|
= |

is Hermitian it has a spectral decomposition
= | |

The lowest energy ground state energy

Corresponding energy eigenstate (or eigenspace) ground state.

| stationary state because their only change in time is to acquire an

overall numerical factor | exp(/)|

16
A single cubit system
=

0 1
The eigenstates of this Hamiltonian are those of =
1 0
1 1 1 1
i.e. 0 + 1 and 0 1
2 2 2 2

With eigenvalues and

1 1
Ground state is 0 1 with energy
2 2

Postulate 2: |(2 ) = 1 , 2 |(1 )

is Hermitian exp() is Unitary

|(2 ) = exp (2 1 )/ |(1 )

1 , 2 exp (2 1 )/

17
Qubits: What can be measured?
A qubit can exist in a continuum of states between |0 and |1 until it is
observed
When a qubit is measured, it only ever gives 0 or 1 as the
measurement result probabilistically
Eg. a qubit can be in the state
1 1
+: 0 + 1
2 2
1 2
When measured, gives the result 0 fifty percent of the time, and
2
the result 1 fifty percent of the time.
Despite this strangeness, qubits are decidedly real
Many different physical systems can be used to realize qubits
two different polarizations of a photon
alignment of a nuclear spin in a uniform magnetic field
two states of an electron orbiting a single atom

18
Qubit: Atom model
The electron can exist in either the ground 0 or excited 1 states

1
+ 0 1
0

By shining light on the atom, with appropriate energy and for an

appropriate length of time, it is possible to move the electron from the 0
state to the 1 state and vice versa.
By reducing the time we shine the light, an electron initially in the state
0 can be moved halfway, into the + state.
meaning or interpretation that might be attached to superposition
states, and of the inherently probabilistic nature of observations on
quantum systems Complicated

19
Bloch sphere
2 2
| = 0 + |1; + =1

| = cos 2 |0 + sin 2 |1
, and are real numbers
has no observable effects & ignored

| = cos |0 + sin |1
2 2
and define a point on the unit three-
dimensional sphere
Bloch sphere: useful means of visualizing
the state of a single qubit
Infinite number of points on BS?
Measurement of a qubit 0 or 1 only
Measurement changes the state of a qubit
A single measurement a single bit of information
Only if infinitely many identically prepared qubits were measured
would one be able to determine and
20
Quantum information
Infinite information can be stored in a cubit? Yes but not exactly.
How much information is represented by a qubit if we do not measure it?
This is a trick question
How can one quantify information if it cannot be measured?

Nature evolves a closed quantum system of qubits, not performing any

measurements, keeping in track all (variables and ) states.
In the state of a qubit, there is a great deal of hidden information.
The potential amount of this extra information grows exponentially with
the number of qubits.
Classical system of bits 2 combinations of 0 and 1
Quantum system of qubits 2 amplitudes

Understanding this hidden quantum information is our quest

This lies at the heart of what makes quantum mechanics a powerful tool
for information processing
21
Two cubit system
For two classical bits, there are four possible states, 00, 01, 10, and 11
For two qubits: computational basis states are 00 , 01 , 10 and 11
= 00 00 + 01 01 + 10 10 + 11 |11
Similar to the case for a single qubit, the measurement result (= 00, 01,
10 or 11) occurs with probability 2 , with the state of the qubits after
the measurement being .
Normalization condition: 0,1 2 2 = 1 where 0,1 2 means the set of
strings of length two with each letter being either zero or one.
We could measure just a subset of the qubits
Measuring the first qubit alone gives 0 with probability 00 2 + 01 2 ,
leaving the post-measurement state
00 00 + 01 01
=
00 2 + 01 2
is renormalized by the factor 00 2 + 01 2 and hence is a
legitimate quantum state.

22
Bell state or EPR pair
00 + 11
=
2
Upon measuring the first qubit, one obtains two possible results:
0 with probability 1/2, leaving the post-measurement state = 00
1 with probability 1/2, leaving the post-measurement state = 11
Measurement of the second qubit always gives the same result as the
measurement of the first qubit
The measurement outcomes are correlated
Einstein, Podolsky and Rosen, first pointed out such strange properties
EPRs insights were taken up and greatly improved by John Bell
The measurement correlations in the Bell state are stronger than could
ever exist between classical systems
Quantum mechanics allows information processing beyond what is
possible in the classical world
Bell state is the key ingredient in quantum teleportation and superdense
coding, and the prototype for many other interesting quantum states.

23
Quantum computation
Changes occurring to a quantum state can be described using the
language of quantum computation.
Quantum computer Quantum circuits with wires & quantum gates
We will discuss the following
Single qubit gates
Multiple qubit gates
Measurements in bases other than the computational basis
Quantum circuits

24
Single qubit gates

Quantum not gate:

| = 0 + |1;
0 1 0 1
Pauli matrix = , | = =
1 0 1 0
0

| = =
0
1 0

| = =
0 1
1 1 1
Hadamard gate = 2
1 1
1 1 1 1 + +
= 2 = = 0 + |1
1 1 2 2 2
0+1 01
= + = + +
2 2
0 = +; 1 =

25
Visualization of the Hadamard gate

26
Single qubit gates

= ( + )/ 2
=
=
=

27
More single cubit gates
1 1 0
Phase gate =
2 0


exp 8
0 1 0
/8 gate = exp =
8
0 exp
0 exp 4
8
= 2
Recall | = 0 + 1 is a point (, ) on the unit (Bloch) sphere where

= cos and = cos
2 2
Exponentiated Pauli matrices give arise to rotational operators


cos sin
2 2
exp = cos sin =
2 2 2
sin cos
2 2

exp 2
; exp 2

28
Decompositions for a single cubit
An arbitrary unitary operator on a single qubit can be written in many
ways as a combination of rotations, together with global phase shifts on
the qubit.
decomposition: Theorem: If is unitary, there exist real numbers
, , and such that = exp()

Suppose is a unitary gate on a single qubit. Then there exist unitary

operators , , on a single qubit such that
= and
= exp
where is some overall phase factor.

29
General form of single qubit gates
There are infinitely many two by two unitary matrices, and thus infinitely
many single qubit gates.
An arbitrary 2x2 unitary matrix may be decomposed as

We dont need to be able to do these gates for arbitrary , , and , but

can build arbitrarily good approximations to such gates using only certain
special fixed values of , , and .
An arbitrary quantum computation on any number of qubits can be
generated by a finite set of gates that is said to be universal for quantum
computation.

Excercises 4.1 to 4.15

30
Classical 2 bit gates

Any function on bits can be computed from the composition of gates

alone, which is thus known as a universal gate.

31
Controlled NOT gate
The prototypical multi-qubit quantum logic gate is the controlled-NOT or
CNOT gate.
This gate has two input qubits: the control qubit and the target qubit
This can be regarded as a type of generalized-XOR gate

The XOR and NAND gates are essentially irreversible or non-invertible.

Unitary quantum gates are always invertible
Understanding how to do classical logic in this reversible or invertible
sense will be a crucial step
Any multiple qubit logic gate may be composed from CNOT and single
qubit gates.
32
Controlled operations
If A is true, then do B. This type of controlled operation is one of the
most useful in computing, both classical and quantum.

Eg. CNOT:

A controlled operation:

Exercises 4.16 to 4.20

CNOT basis transformations:
+ + : + + = 0 0 0 0 : + +

In this basis, the target and control have essentially interchanged roles!
33
Controlled operation
Goal: implement C using single qubit operations and the CNOT gate.
Strategy: = exp
A controlled operation:
Phase shift: exp

34
 in multiple cubits:
A controlled in single cubit:
If we have + qubits, and is a qubit unitary operator
1 2 = 1 2 1 2
1 2 means the product of the qubits 1 , 2 , ,
Operator is applied to the last qubits if the first qubits are all equal
to one, and otherwise, nothing is done

35
Ex. 4.2.
Q: Let be a real number and a matrix such that 2 = 1. Show that
exp = cos + sin
A: Both sides satisfy the same differential equation and have the same
initial conditions, so they agree.

let = exp &

let = cos + sin

= exp , = exp =
= sin + cos , = cos sin =

0 = 0 =
0 = 0 =

Therefore .

36
Toffoli gate

For c = 1, we get a For a = 1 & c = 0, we get a

NAND gate: FANOUT gate:

NAND &
FANOUT gates
form a
UNIVERSAL gate

37
Fredkin gate (universal)
The bits a and b are
swapped if c = 1

38
Generalization: 2 () gate

Suppose is a unitary operator chosen so that 2 = .

Special case: (1 )( + )/2 corresponds to the Toffoli gate.

39
Implementation of
In terms of Toffoli gate for e.g.

40
Control bit being 0

41
Another possible representation

42
Measurements in other bases

Provided the states are orthonormal, it is possible to perform a

measurement with respect to the new basis

43