Script QI

Quantum Computations
&
Quantum Information Theory:
An Introduction
https://wiki.oulu.fi/display/766647S/Home
(lecture notes and additional material)
Stephan Fritzsche
2
Contents
0. Preconsiderations 11
0.1. Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.2. Literature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1. Introduction and motivation 13

1.1. Need and promises of quantum computations . . . . . . . . . . . . . . . . . . . . . . 13
1.2. Qubits and quantum information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.3. Different realization of qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.4. Young’s double slit experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.5. Mach-Zehnder interferometer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6. Quantum simulators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1.7. Summary & reminder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
5
Contents
2. A short account on classical information and computations 39

2.1. Computational complexity and the Church-Turing thesis . . . . . . . . . . . . . . . . 40
2.2. Classical computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.a. Classical logic operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2.b. Universal classical computations . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.2.c. Reversible computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
2.3. Classical information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.a. Content of classical information . . . . . . . . . . . . . . . . . . . . . . . . . . 55
2.3.b. Classical communication channels . . . . . . . . . . . . . . . . . . . . . . . . 57
2.3.c. Shannon’s entropy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
3. Basic quantum mechanics and Dirac notation 65

3.1. Linear vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
3.2. State vectors and operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.a. Linear Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
3.2.b. Pauli matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.2.c. Scalar product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
3.2.d. Cauchy-Schwartz and triangle inequalities . . . . . . . . . . . . . . . . . . . . 72
3.2.e. Orthogonality and norm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
6
Contents
3.2.f. Outer product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.2.g. Expectation value of an operator . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.3. Properties of linear operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
3.3.a. Adjoint and hermitean operators . . . . . . . . . . . . . . . . . . . . . . . . . 80
3.3.b. Projection operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
3.3.c. Normal operators and spectral decomposition . . . . . . . . . . . . . . . . . . 83
3.3.d. Unitary operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
3.3.e. Positive operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
3.4. Products and functions of linear operators . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.a. Product spaces (tensor spaces) . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.4.b. Tensor product of linear operators . . . . . . . . . . . . . . . . . . . . . . . . 88
3.4.c. Trace of an operator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
3.4.d. Operator functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
3.4.e. Scalar product of operators (Hilbert-Schmidt product) . . . . . . . . . . . . . 98
3.4.f. Commutators and anticommutators . . . . . . . . . . . . . . . . . . . . . . . 99
3.4.g. Decomposition of linear operators . . . . . . . . . . . . . . . . . . . . . . . . 101
3.5. Postulates of quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
3.5.a. Postulate I (State space & state vectors) . . . . . . . . . . . . . . . . . . . . . 102
3.5.b. Postulate II (Time evolution of closed systems): . . . . . . . . . . . . . . . . . 102
3.5.c. Postulate III (Quantum measurements and measurement operators): . . . . . 105
7
Contents
3.5.d. Postulate IV (Composite systems and entanglement): . . . . . . . . . . . . . 106

3.6. Measurements in quantum mechanics . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.6.a. Indistinguisable quantum states . . . . . . . . . . . . . . . . . . . . . . . . . . 108
3.6.b. Projective measurements (von Neumann measurements) . . . . . . . . . . . . 109
3.6.c. POVM measurements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
3.6.d. Mach-Zehnder interferometer . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
3.7. Density matrices and operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.7.a. Ensemble of quantum systems . . . . . . . . . . . . . . . . . . . . . . . . . . 123
3.7.b. Properties of density operators . . . . . . . . . . . . . . . . . . . . . . . . . . 126
3.7.c. Postulates of quantum mechanics for density operators . . . . . . . . . . . . . 129
3.7.d. Uniqueness of the density operator . . . . . . . . . . . . . . . . . . . . . . . . 131
3.7.e. Blochdarstellung eines Qubits . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3.7.f. Stokes parameters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
3.7.g. Reduced density operators and partial trace . . . . . . . . . . . . . . . . . . . 140
3.7.h. Schmidt decomposition of pure states . . . . . . . . . . . . . . . . . . . . . . 143
3.7.i. Purification of reduced density operators . . . . . . . . . . . . . . . . . . . . . 145
3.8. The EPR paradoxon and Bell’s inequality . . . . . . . . . . . . . . . . . . . . . . . . 147
3.8.a. Bohr–Einstein debate (1926–35) . . . . . . . . . . . . . . . . . . . . . . . . . 147
3.8.b. EPR ‘gedanken’ experiment . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
3.8.c. Bell’ inequalities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
8
Contents
3.8.d. Quantum mechancical ‘anticorrelations’ in the EPR experiment . . . . . . . . 152

3.8.e. Bipartite systems and the Bell basis . . . . . . . . . . . . . . . . . . . . . . . 154
3.8.f. Bell state representation of a two-qubit density operator . . . . . . . . . . . . 156
4. Models for quantum computations 157

4.1. Di’Vincenzo’s criteria on physical requirements . . . . . . . . . . . . . . . . . . . . . 157
4.2. Different models: A short overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.3. Circuit model of quantum computations . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.3.a. Single-qubit operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.3.b. Conditional quantum operations . . . . . . . . . . . . . . . . . . . . . . . . . 168
4.3.c. Universal quantum gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
4.4. Adiabatic model of quantum computations . . . . . . . . . . . . . . . . . . . . . . . 173
4.5. One-way or cluster state computations . . . . . . . . . . . . . . . . . . . . . . . . . . 173
4.6. Holonomic quantum computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
4.7. Beyond the Di’Vincenzo’s criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174
5. Quantum information and communication 179

5.1. Information & physics. Non-cloning theorem . . . . . . . . . . . . . . . . . . . . . . 179
5.2. Quantum cloning (quantum copier) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182
9
Contents
5.3. Quantum cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

5.4. (Super-) dense coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5.5. Teleportation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
5.6. Entanglement swapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
5.7. No instantaneous transfer of information . . . . . . . . . . . . . . . . . . . . . . . . . 198
10
0. Preconsiderations
0.1. Schedule
General agreements:
➣ Lecture: Thuesday and Thursday (14:15 - 16:00)

➣ Tutorials: Wednesday, after agreement. Help ??
➣ Breaks ??
➣ Credit points: 6 op
➣ Who has already used Maple or Mathematica ??
➣ Names, email addresses, remarks ??
11
0. Preconsiderations
0.2. Literature
A few books for home work:
➣ M.A. Nielsen and I. L. Chang: Quantum Computation and Quantum Information
(Cambridge University Press, 2000 and later)
➣ G. Benenti, G. Casati and G. Strini: Principles of Quantum Computation and Infor-
mation; Volume I: Basic Concepts (World Scientific, 2004)
➣ V. Vedral: Introduction to Quantum Information Science (Oxford University Press,
2007)
➣ G. Jaeger: Quantum Information — An Overview (Springer, 2007)
➣ John Preskill’s physics notes at
http://www.theory.caltech.edu/people/preskill/ph229/
➣ Carnegie Mellon course at
http://quantum.phys.cmu.edu/QCQI/index1.html
12
1. Introduction and motivation
1.1. Need and promises of quantum computations
A computer is always a physical device that helps us process information by executing

algorithms. An algorithm is a finite procedure that realizes an information-processing task.
Computers allow an efficient storage, exchange and processing of information. An

information-processing task can always be translated into a physical task.
Moore’s law (1965): Number of transitors and speed grows exponentially; doubles every
18 months about.
13
Figure 1.1.: Classical (electronic) computers will reach fundamental limits

quite soon.
14
Remarks:
➤ Today: 50–100 nm ≈ 0.1 µm; 12 % reduction every year. Development towards 13.5
nm light sources.
➤ Quantum mechanical behaviour of electrons will become visible within the next few
years.
➤ Quantum effects: small voltage; capacities of only a few elementary charges.
➤ Dissipative versus reversible computations.
➤ The main difference between classical and quantum information arises from the dif-
ference between a bit and a qubit, i.e. the capability what can be represented by the
corresponding physical units that are utilized to store these (qu)bits.
➤ Quantum information processing hereby means that we use quantum systems and quan-
tum theory in order to see and understand which information processes tasks are pos-
sible (devices: quantum computers).
➤ Whatever do we understand as information ? It must be possible to stored this in some
physical medium and to manipulated it by means of physical processes.
15
Figure 1.2.: R. P.
Feynman.
➤ We must therefore study the laws of physics when we wish to study the theory of
information processing and, in particular, the theory of computation.
➤ In this lecture, we shall consider how quantum physics and quantum computers can
be utilized to solve certain problems more efficiently than can be done with classical
computers.
R. P. Feynman, Int. J. Theoret. Phys., 21 (1982) 467:

“Quantum Mechanics cannot be simulated efficiently on a classical PC !”
Quantum computers are universal quantum simulators.
16
Quantum algorithms:
➣ Deutsch (1985) or Deutsch-Jozsa (1992): Decision about simple ‘two-valued’ functions.
➣ Coppersmith (1994): Quantum Fourier Transformtion (QFT).

➣ Shor (1994): Factorization of large integers.
➣ Grover (1995): Search algorithm.
Search for efficient algorithms for which the computational effort (time, storage)
does not increase exponentially with N , the number of qubits.
Web link (Quantum Computers):

➣ A short CNN report on youtube; http://www.youtube.com/watch?v=DNatzhe4BoQ
➣ A short video explaining what quantum computers are, how they work, and what you’d
need to build one on youtube; http://www.youtube.com/watch?v=VyX8E4KUkWw
17
1.2. Qubits and quantum information
Classical versus quantum bits (qubits):
➣ Classical bit just takes values 0 or 1.

➣ Computational basis:
1 0
|0i ≡ |1i ≡
0 1
➣ A qubit system can be in one out of an infinite number of significant states:
|ψi = α |0i + β |1i
➣ A qubit is either in a pure state (vector) or a mixed state (density matrix).

➣ Another commonly used basis is the diagonal basis
1 1
|+i ≡ √ (|0i + |1i) , |−i ≡ √ (|0i − |1i)
2 2
18
Figure 1.3.: Bloch sphere representation of the qubit. The pure

qubit states lie on the periphery, known also as the
Poincare-Bloch sphere. The mixed qubit states lie in
the interior and are weighted convex combinations of
pure states.
19
Figure 1.4.: From: www.labs.nec.co.jp
➣ Qubits are realized by different ‘two-level’ systems: electron spin, photon polarization,
charges in a quantum dot, ...
20
Figure 1.5.: Quantum

parallelism.
Quantum registers:
➣ Classical: messages are stored and carried by sequences of bits.

➣ Quantum world: sequence of distinguishable qubits; such sequences are called
(n−qubit) quantum register.
➣ n−qubit systems are associated with a 2n −dimensional state space; in general, super-
positions of all 2n basis states are possible.
➣ Quantum parallelism: certain computations can be carried out in parallel for all 2n
input values. This follows directly from the superposition principle but is, by far, not
easy to utilize (see quantum algorithms).
➣ In quantum systems, therefore, an exponential increase in parallelism requires only a
linear increase in the amount of space needed [cf. Fig. 1.5].
21
➣ Diffuculties arise from measurements in quantum mechanics; state reduction is never

ideal.
➣ Quantum mechanics does not permit to generate an exact copy of an unknown state
(non-cloning theorem).
Quantum information processing (3 major ingredients):

➣ Initialization of a quantum register: |000....0i ;
this step in non-unitary and non-reversible, dissipative.
➣ Information processing:
|ψ0 i −→ |ψ1 i −→ |ψ2 i −→ . . .
• Quantum algorithms: special unitary transformation that is to be realized as a
sequence of (generalized) gate operations.
• Time development follows some Hamiltonian Ho : U (t0 , t) = exp(−iH0 t) ... in
the trivial case
• Separation of the total unitary transformation into elementary operations (sets of
universal gates).
➣ Measurement process and read out: projection upon the eigen states of some appro-
priate observable(s); need usually to be done separately for each qubit.
22
1.3. Different realization of qubits
1.3. Different realization of qubits
Experimental schemes:
➣ NMR (nuclear magnetic resonance) with suitable solutions; experiments with a large
number of the same system (∼ 1020 molecules; difficult to scale towards large N (Nmax ∼
7..10)).
➣ Ions in traps: Qubits are represented by the low-lying states of the corresponding
quantum oscillator.
➣ Neutral atoms in optical lattices; the dimenionality, form, depth and position of optical
lattices can be precisely controlled through the geometry, polarization and intensity of
the external laser beams.
➣ Quantum dots: Qubits represented by elementary charges in dots.
➣ Superconducting qubits: Use of Cooper pairs which may be controlled by some macro-
scopically defined conductances (L) and capacities (C). There are three types of super-
conducting qubits: charge qubits, flux qubits and phase qubits.
➣ Photons: Qubits are represented by the polarization state or in ‘dual rail’ or in ‘spatial
color’ modes.
23
➣ Other schemes: small polar molecules; hyperfine states of rare-earth ions in certain
crystals; single ballistic electrons in low-temperature semiconductor nanostructures.
Decoherence: all processes that lead to the loss of (quantum) information, for example,
loss in the quantum phases due to small fluctuations in the energy. Superpositions are easily
destroyed (fractile quantum states).
24
1.4. Young’s double slit experiment
Figure 1.6.: Experiments with

double slits: classical
particles vs. waves
25
Figure 1.7.: Experiments with double slits: Quantum particles behave differently.
26
Figure 1.8.: Double-slit experiment with electrons.
27
Figure 1.9.: The Mach-Zehnder inter-

ferometer. A photon is
sent through a beam split-
ter and bounced off at
two mirrors into another
beam splitter. Mysteri-
ously, only one of the de-
tectors registers a photon.
1.5. Mach-Zehnder interferometer

The Mach-Zehnder interferometer setup is another way out of many experimental set-ups
which have convinced the physicists that quantum mechanics cannot be described by classical
mechanics.
28
1.5. Mach-Zehnder interferometer
Set-up and properties:
➣ It is important that the fully-silvered and half-silvered surfaces of all mirrors face the
inbound beam. The last beam-splitter can be changed to change the detector which
records the photons.
➣ Outcome of such a set-up depends on the phase shifts due to material of the mirrors:
(i) Reflection or refraction at the surface of a medium with a lower refractive index
causes no phase shift.
(ii) Reflection at the surface of a medium with a higher refractive index causes a phase
shift of half of a wavelength.
➣ A 1/2 wavelength phase shift occurs upon reflection from the front of a mirror, since
the medium behind the mirror (glass) has a higher refractive index than the medium
the light is traveling in (air).
➣ If k is the constant phase shift incurred by passing through a glass plate on which a
mirror resides, a total of 2k phase shift occurs when reflecting off the rear of a mirror.
This is because light traveling toward the rear of a mirror will enter the glass plate,
incurring k phase shift, and then reflect off the mirror with no additional phase shift.
29
➣ If an absorber is placed into one of the beam lines, then half of the photons are absorbed
but the other half is detected with probability 1/2 at both detectors.
30
1.6. Quantum simulators

During the last decade, a number of (software) projects have been developed at various places
worldwide for simulating quantum computations and the manipulation of quantum registers.
These developement often refer to rather small projects which focus on some standard task
or the implementation of some algorithm, such as those by Shor, Grover or Deutsch-Josza.
FEYNMAN toolbox:
➣ A toolbox for simulating the behavior of n-qubit quantum systems (quantum registers)
within the framework of the computer algebra system Maple.
➣ Flexible framework that facilitates both, symbolic and/or numerical computations.
➣ First, the basic data structures for the simulation of n-qubit quantum systems were
implemented; two data structures qregister() and qoperator() are important building
blocks to perform most standard operations.
➣ Various separability criteria and entanglement measures.
➣ Support for quantum operations, i.e. completely positive and trace-preserving maps
(CPT maps); they an be utilized to describe general (unitary or nonunitary) transfor-
mation of quantum states as needed for describing decoherence effects.
31
Figure 1.10.: From DARPA QuIST Poster Session, Brian T.

Mitchell, Donald F. Brinkman, Jr.
32
➣ Various parametrizations of the quantum states and quantum transformations.

➣ Simulation of quantum measurements.
➣ See the short manual in: 1.6-Feynman-short-manual.pdf.
33
1.7. Summary & reminder
Remember:
➣ In quantum information (theory), we wish to exploit the laws of quantum physics for
data storage, transmission and processing.
➣ Most often, this concept is based on qubits and quantum registers.
➣ A qubit system can be in one out of an infinite number of significant states:
|ψi = α |0i + β |1i
➣ Quantum properties such as superposition, entanglement, uncertainty and interference

have led to new brand of theory, where computational and communication processes
are based on fundamental physics.
➣ Like lasers do not replace ‘light bulbs’, a quantum computer will not be a faster or
smaller version of an ordinary computer; instead, it will be a different kind of computer
to control coherent quantum mechanical waves for different applications.
34
Figure 1.11.: New paradigm for computing.
35
➣ In quantum systems, an exponential increase in parallelism requires only a linear in-

crease in the amount of space needed. ➥ Promise to solve efficiently difficult problems
in computational sciences such as simulation of quantum systems, integer factorization,
or database searching.
➣ Possible applications: Inherently secure quantum communication; efficient simulation
of quantum systems (Feynman’s 1982 proposal);
➣ Central challenge in building quantum computers: To keep the ability to control quan-
tum systems, measure them, and to preserve their strong isolation from undesired
interactions with the environment.
36
Task (28.01.2011)
Read the article “Whither the Future of Controlling Quantum Phenomena ?” by H. Rabitz
et al., Science 288 (2000) 824-828; DOI: 10.1126/science.288.5467.824.
Task (28.01.2011)
Web link (Introduction to Quantum Computing):

➣ Listen to the GoogleTechTalk:
http://www.youtube.com/watch?v=I56UugZ 8DI
Task (04.02.2011)
Read the review article “Quantum Computers” by T. D. Ladd et al., Nature 464 (2010)
45–53; DOI: 10.1038/nature08812.
37
2. A short account on classical information and
computations
Remarks:
➤ When designing complex algorithms and protocols for various information processing tasks, it helpful
and essential that one works with some idealized computing model.
➤ However, when we shall study the true limitations of a computing device, its important for practical
reasons to remember the close relationship between computing and physics.
➤ Quantum information theory has largely been considered as an extension of those methods that were
developed first for classical information and to extent them to analogous situations making use of
quantum systems ... but remind the ‘different physics’.
➤ Because measurements on quantum systems result in classical information, the traditional information-
theoretical methods still play an essential role in quantum communication and information.
39
2. A short account on classical information and computations
2.1. Computational complexity and the Church-Turing thesis
Computational complexity:
➣ Refers to the resources such as time and memory used.
➣ Coarse measure based on the order of resources, often the time: O(n3 ), O(n2 ), O(log n),
... This provides a ‘hierarchy’ of complexities; robust with regard to changes to the
‘computing model’ and how resources are counted.
➣ If an algorithm runs in O(n), it is called linear; similar
O(log n) ... logarithmic
O(nk ) for some k ... polynomial.
➣ Problems polynomial in n can be solved efficiently; they are also called easy, tractable,
feasible.
➣ Lower bounds are sometimes denoted by the Ω notation: Algorithms that use Ω(cn )
resources, for some constant c, are said to be exponential or superpolynomial. These
algorithms are considered to be not efficient.
The mathematical theories of computability and computational complexity theory deal with
the questions of computability and efficiency of computers in a general sense. This may
become quite ‘mathematical’ and goes well beyond the scope of this lecture.
40
Church-Turing Thesis: A computing problem can be solved on an computer if and only if

it can be solved on a simple Turing machine, named after the mathematician Alan Turing
who conceived this concept. A Turing machine is a mathematical abstraction and certainly
not a physical device.
Computable is of what can be computed by a Turing machine.

A Turing machine is a computing model that consists of a finite set of states, an
infinite ‘tape’ to which symbols from a finite alphabet can be written and read
from by using a moving head.
41
Figure 2.1.: Turing machine.
Turing machine:
➣ Tape for data storage; this tape is of unlimited length in one direction.
➣ Processor; this is the operative element of the computer with a finite set of internal
states.
➣ Finite instruction set; tells the machine what it has to do when a certain symbol is
read from the tape and when the processor is in a certain internal state.
42
➣ Tape manipulation device; recognizes, erases and re-writes a symbols being under this
device.
The original Church-Turing Thesis says nothing about the efficiency of some computation.
In order to extend the Church-Turing Thesis to say something useful about this efficiency, it
is useful and nessary to generalize the definition of a Turing machine slightly. A probabilistic
Turing machine is one capable of making a random binary choice at each step, where the
state transition rules are expanded to account for these random bits. We can say that a
probabilistic Turing machine is a Turing machine with a built-in ‘coin-flipper’.
If a Turing machine is always restricted to move in one direction only, they belong to a class
of devices called finite-state automatons. These automatons have attracted considerable
interest in information-processing contexts.
Strong Church-Turing Thesis: A probabilistic Turing machine can efficiently simulate
any realistic model of computation.
Remarks:
➤ The term ‘realistic model’ of computation in the statement of the strong Church-Turing
Thesis refers to a model of computation which is consistent with the laws of physics
43
and in which the available physical resources are properly taken into account into the
model.
➤ The fundamental problem with the classical strong Church-Turing Thesis is that it
appears that classical physics is not powerful enough to efficiently simulate quantum
physics. The basic principle is still believed to be true; however, we need a computing
model capable of simulating arbitrary ‘realistic’ physical devices, including quantum
devices.
44
2.2. Classical computations
Figure 2.2.: NOT gate.

Computations on standard computers are in general not ‘reversible’; this is closely related
to the way we use the ‘classical logic’ and its implementation in the (classical) circuit model.
2.2.a. Classical logic operations

Functions defined on the values 0, 1 are called logical functions, and the corresponding
algebra is called a Boolean algebra.
Three basic logical functions:
NOT : a ⇒ ā
45
Figure 2.3.: Truth table and circuit representation of the AND and OR gate.
OR : (a, b) ⇒ a ∨ b
AND : (a, b) ⇒ a ∧ b
They are sufficient to represent any logical operations but they are not independent of each
other. See Figures 2.2–2.3 for the truth table and circuit representation of the NOT, AND
and OR gates.
46
deMorgan’s rules:
a ∨ b = ā ∧ b̄, a ∧ b = ā ∨ b̄
In computations, we need one more logical function for addition ‘with carry’.
47
Figure 2.4.: deMorgan’s rules in terms

of Venn’s diagrams.
48
Figure 2.5.: Truth table and circuit representation of the XOR and NAND gate.
XOR : (a, b) ⇒ a ⊕ b = a + b (mod2)

NAND : (a, b) ⇒ a ↑ b = a ∧ b = ab = 1 − ab
Binary addition can be represented as:
⊕: (a, b) ⇒ {a ∧ b, XOR(a, b)}
49
Figure 2.6.: Truth table of XOR and

CNOT is the same.
(
b if a = 0
CNOT : (a, b) =⇒
b̄ if a = 1
(a, b) =⇒ (a, a ⊕ b)
50
Figure 2.7.: Circuit representation of the FANOUT

and CROSSOVER gates.
Two other important gates are the FANOUT (COPY) and the CROSSOVER (SWAP) gates:
FANOUT : a =⇒ (a, a)
CROSSOVER : (a, b) =⇒ (b, a)
51
2.2.b. Universal classical computations

Universal gates: Any function
f: {0, 1}n =⇒ {0, 1}m
can be constructed from the elementary gates AND, OR, NOT and FANOUT; these gates
are said to form a universal set of gates for classical computations.
2.2.c. Reversible computations
Application of two CNOT gates:

(a, b) =⇒ (a, a ⊕ b) −→ (a, a ⊕ (a ⊕ b)) =⇒ (a, b)
Therefore (CNOT)2 = I or, equivalently, (CNOT)−1 = CNOT .
Remarks:
➤ CNOT gate becomes the FANOUT gate if the target bit is set to 0; (a, 0) =⇒ (a, a).
➤ Two-bit reversible gates are not enough for universal classical computations (Preskill
1998).
52
Figure 2.8.: Truth table and circuit representation of the Toffoli and Fredkin gate.
➤ A universal gate is the controlled-controlled-NOT (CCNOT) or Toffoli-gate (three-bit

gate).
➤ Another universal reversible gate is the controlled-EXCHANGE or Fredkin-gate; this
three-bit gate swaps the bits b and c only of the bit a is set to 1.
➤ Both, the Toffoli and Fredkin gates are self-inverse.
Problem (Reversible logical functions): Show that the Toffoli and Fredkin gates are
self-inverse.
53
Blackboard example (Construct NOT, AND and OR from Toffoli gate):
Blackboard example (Fredkin gate is universal):
54
2.3. Classical information

2.3.a. Content of classical information
Remarks:
➤ Classical information theory is based to a large extent on the concept of information
as developed by Claude Shannon in the late 1940s; this concept uses the basic bit as
the unit of information.
➤ This approach to information is based on the entropy term from physics following Shan-
non’s idea that the amount of information is related to the improbability/unlikelyhood
that certain symbols occur in some memory or signal.
➤ The less probable an event with probability p is the more information is carried over,
i.e. the rarity or surprise value can be measured by p−1 .
➤ For a string of characters, the transmitted information via a classical communication
channel, the information content of some signal event x (i.e. the surprisal of obtaining
this particular message) is defined as
1
I(x) = log2 = − log2 p(x)
p(x)
55
with p(x) being the probability that the event x occurs.

➤ For single-symbol messages, p(x) is just probability that this symbol occurs.
➤ Today, Shannon’s theory is used in biology (especially genetics), sociology and eco-
nomics, to name just a few.
➤ A finite number of mutually exclusive events form, together with their probabilities, a
(so-called) finite scheme.
56
2.3.b. Classical communication channels

The fundamental task of communication is to send information from an initial source through
some channel to a remote location.
Examples:
➣ Ideal channels (without noise): Good for understanding the basic behaviour of a trans-
mission network but unrealistic in practice.
➣ Additive noise channel:
r(t) = s(t) + n(t)
The result r(t) of a originally transmitted signal s(t) is affected by some (additive)
noise n(t).
➣ Binary symmetric channel (BSC) provides a model for a discrete, memoryless noisy
channel.
57
Figure 2.9.: The additive noise channel.
Figure 2.10.: Schematic of the binary symmetric

channel (BSC). A transition between
values of any given bit occurs with
probability p, known as the symbol-
error probability. Initial bit values
appear at left, final bit values at
right. Bit values remain unchanged
with probability 1 − p.
58
2.3.c. Shannon’s entropy
How can information be quantified ?

➣ Shannon modeled information as events which occur with certain probabilities pi .
➣ Amount of information in an event x must depend only upon its probability p.
➣ If we select a set P
of symbols {ai } for communication and if these symbols occur with
probabilities {pi , i pi = 1}, then the Shannon entropy is defined as
X
H({pi }) ≡ H[p1 , p2 , ..., pn ] = − pi log2 pi
i
➣ Example: Message 001011...01

‘0’ with probability p0 and ‘1’ with probability p1 = 1 − p0 .
H(1 − bit) = −p0 log p0 − (1 − p0 ) log(1 − p0 )
p0 = 1 : −1 · 0 − 0 · log(0) = 0
p0 = 0 : 0 · log(0) − 1 · log(1) = 0
p0 = 1/2 : −1/2 · log(1/2) − 1/2 · log(1/2) = − log2 (1/2) = 1
59
That means, we have one bit/symbol in binary messages.

➣ Shannon’s entropy satisfies two requirements:
(i) invariance under permutations of the probabilities pi (clear from definition);
(ii) additivity

p1 p2
H[p1 , p2 , ..., pn ] = H[p1 + p2 , ..., pn ] + (p1 + p2 )H ,
p1 + p2 p1 + p2
.
➣ The Shannon entropy can be considered as the average information associated with the
set of events (in units of bits). It can also be thought of as the number of bits that are
needed on average in order to describe the random variable X.
➣ For a pair of random variables A, B, one can define also a so-called joint entropy of the
pair
X
H(A, B) = − p(a, b) log2 p(a, b)
a,b
where p(a, b) = PAB (A = a, B = b) are the joint probabilities that A = a and B = b

and where the sums have to be taken over the two sample spaces associated with both
A and B.
60
➣ The quantum generalization of the Shannon entropy is the von Neumann entropy
S(ρ) = −Tr(ρ log ρ)
where the density matrix takes the role of the probability distribution.
Theorem: Let {pi } and {qi } be two arbitrary normalized probability distributions; then
the inequality applies:
X X
pi log pi ≧ pi log qi
i i
since log x ≤ x − 1.
61
Some further interpretation of Shannon’s entropy:
➣ H(A) is the uncertainty we have about the value of A when no information has been
received.
➣ H(A) is the amount of information we can obtain if we get information about the value
of A and no other information is available.
➣ H(A) limits the average word length if we want to identify the value taken by A (i.e.,
the word length needed to encode the information carried by A).
➣ Like the entropy concept itself, all entropy concepts from information theory are closely
related to (Kolmogorov’s) mathematical theory of probability.
62
Remember:
➣ Computable is of what can be computed by a Turing machine.

➣ Classical computations are not reversible if based on classical logic.
➣ The logical functions And, Or, and Not are sufficient to represent any logical opera-
tion/combination of classical propositions but they are not independent (de Morgans’
rules).
➣ Shannon’s entropy: Amount of information which is given by some event/message and
which depends only on the probabilities that certain symbols occur in the message.
X
H({pi }) = − pi log pi
i
➣ The Shannon entropy can be considered as the average information associated with the
set of events (in units of bits). It can also be thought of as the number of bits that are
needed on average in order to describe the random variable X.
63
3. Basic quantum mechanics and Dirac notation
General agreement: If not stated otherwise, we consider the vector space Cn =
{(z1 , ..., zn ); zi ∈ C}, i.e. the vector space of the complex n−tupel.
3.1. Linear vector spaces
Elements of the vector space are called (ket) vectors:

 
z1
 z2 
 
|ψi =  .. 
 . 
zn
65
Properties:
➣ addition of vectors
➣ multiplication with complex numbers z ∈ C
   
z1 zz1
 z2   zz2 
   
z  ..  =  .. 
 .   . 
zn zzn
➣ null vector, null element: 0

|vi + 0 = |vi ∀ |vi
Remember: 0 = (0, 0, ..., 0) ∈ Cn
➣ associative and distributive
a (|vi + |wi) = a |vi + a |wi
(a + b) |vi = a |vi + b |vi
66
3.1. Linear vector spaces
Basis in Cn : Every set {|v1 i , |v2 i , ..., |vn i} so that we have

n
X
|vi = ai |vi i ∀ |vi
i
.
P
Linear indepedence of vectors: i ai |vi i = 0 is valid only if all ai = 0; otherwise
these vectors are called linear independent.
Problem (Linear independence): How can we determine the linear dependence or inde-
pendence of a given set of vectors ?
Many mathematical difficulties of ‘quantum mechanics’, that one encounters in dealing with
atoms, molecules, the solid state, etc., are associated with the need to treat ∞− dimensional
Hilbert spaces; this is not the case if we consider a finite number of distinguishable qubits
n
(C2 if n is the number of qubits).
67
3.2. State vectors and operators

3.2.a. Linear Operators
Linear maps: A : V → W or V → V ; ‘A acts in/on V ’.

!
X X
A ai |vi i = ai A |vi i ≡ A |vi
i i
Identity: I |vi = |vi ∀ |vi

Null operator: 0̂ |vi = 0 ∀ |vi
Apparently, the mapping/action of an operator is known if we know its action upon all the
basis states {|vi i}.
If A : V → W and B : W → X, then (BA) : V → X with
(BA) |vi = B (A |vi) .
68
Matrix representation of A : V → W : If V : {|v1 i , |v2 i , ..., |vm i} and W :

{|w1 i , |w2 i , ..., |vn i}, we can write also
n
X
A |vj i = Aij |wi i
i
with (Aij ) being a (n × m) matrix representation of A. The particular matrix depends of

course always on the choice of basis in V and W .
Task (02.02.2011)
Problem (Matrix in C2 ): Suppose V is a vector space with the basis vectors

1 0
|0i = , |1i =
0 1
and A : V → V is a linear operator such that A |0i = |1i and A |1i = |0i. Give the matrix
representation of A.
Solution: ??
69
3.2.b. Pauli matrices

There are many different notations for the Pauli matrices:

1 0
σ0 = I =
0 1

0 1
σ1 = σx = X =
1 0

0 −i
σ2 = σy = Y =
i 0

1 0
σ3 = σz = Z =
0 −1
Matrix representation of
4 linear
independent
operators C2 → C2 with regard to the com-
0 1
putational basis |0i = and |1i = .
1 0
70
3.2.c. Scalar product

Map of V × V → C or (|v1 i , |v2 i) → C:
hv1 | v2 i ≡ (|v1 i , |v2 i)
Properties of the scalar product:

P P
• linear in the second argument: hv | i ai w i i = i ai hv | wi i
• hv | wi = hw | vi∗
• hv | vi ≥ 0; =0 (only) if |vi ≡ 0
Scalar product in Cn :
X
h(y1 , y2 , ..., yn ) | (z1 , z2 , ..., zn )i = yi∗ zi
i
In Cn refer the terms ‘scalar product space’ and ‘Hilbert space’ to the same.
Blackboard example (Dual state and scalar product):
71
3.2.d. Cauchy-Schwartz and triangle inequalities

Two important identities in scalar product spaces are the Cauchy-Schwarz inequality
| hψ | φi |2 ≤ hψ | ψi hφ | φi
and the triangle inequality

p p p
hψ + φ | ψ + φi ≤ hψ | ψi + hφ | φi .
Blackboard example (Cauchy-Schwartz and triangle inequalities):
72
3.2.e. Orthogonality and norm
Orthogonality:
|vi and |wi are orthogonal ⇐⇒ hv | wi = 0
p
Norm: ||v|| = hv | vi
Unit vector: ||v|| = 1
Set of vectors {|ii , i = 1, ....n} is called orthogonal, if
hi | ji = δij ∀ i, j = 1, ..., n
Gram-Schmidt orthogonalization: Let {|w1 i , |w2 i , ..., |wd i} be an arbitrary basis in

V , then an orthonormal basis |v1 i , |v2 i , ..., |vd i is obtained by
|w1 i
|v1 i =
|| |w1 i ||
Pk
|wk+1 i − hvi | wk+1 i |vi i
|vk+1 i = Pik (1 ≤ k ≤ d − 1)
|| |wk+1 i − i hvi | wk+1 i |vi i ||
73
General agreement: Matrix representations of linear operators always refer to the use of some
orthonormal basis if not stated otherwise. For all maps A : V → V , the same basis is used
in the input and output space.
Blackboard example (Find an orthonormal state):
Task (02.02.2011)
Problem (Gram-Schmidt procedure): Construct an orthonormal basis from the three
vectors      
1 1 2
|v1 i =  
1 , |v2 i =  
3 , |v3 i =  2 ,
0 1 3
using the standard scalar product in R3 .
Solution: ??
74
3.2.f. Outer product

If we have |vi ∈ V and |wi ∈ W , then
(|wi hv|) |v ′ i ≡ |wi hv | v ′ i
defines a linear operator V → W and is known as the outer product (|wi hv|)).
! !
X X X
ai |wi i hv| bk |vk i = ai bk |wi i hv | vk i
i k ik
i.e. linear: V → W
Completeness:
P P Let’s {|v1 i , i = 1, .., n} be an orthonormal basis in V , i.e. |vi =
i |ii hi | vi = i vi |ii, then we have
!
X X
|ii hi| |vi = |ii hi | vi = |vi ∀ |vi
i i
X
|ii hi| = I
i
75
Matrix representation of operator A : V → W :

X
A = Iw A Iv = |wk i hwk |A| vi i hvi |
ik
X
= hwk |A| vi i |wk i hvi |
ik
X
= Aki |wk i hvi |
ik
Blackboard example (Z operator acting upon a qubit):
Blackboard example (Outer vector of two vectors):
76
3.2.g. Expectation value of an operator

The expectation value of an operator A is the mean or average value of that operator with
respect to a given quantum state |ψi :
< A > = hψ |A| ψi .
It tells us the average of the measurement if the state |ψi is prepared many times, and we
measure the given operator A each time.
Blackboard example (Operator in qutrit basis):
77
3.3. Properties of linear operators

A |vi = v |vi
... eigenvectors, eigenvalues (often useful to use the same symbol)
Determination of eigenvalues: use characteristic polynomal
p(λ) = det |A − λI| = 0
Eigen space associated with eigenvalue v: space spanned by all eigenvectors with
eigenvalue v.
P
Diagonal form of operator: A = i λi |ii hi|
if {|ii} form an orthonormal set of eigenvectors and λi the corresponding eigenvalues. A is
called diagonalizable if such a diagonal form exist.
Diagonal form is sometimes called orthonormal decomposition.
78
Blackboard example (Eigenvalues of a matrix):
Task (02.02.2011)
Problem (Eigenvalues and eigenvectors of the π/8−gate):
Find the eigenvalues and eigenvectors for the π/8−gate with the matrix representation

1 0
.
0 eiπ/4
Solution: ??
79
3.3.a. Adjoint and hermitean operators

hv | Awi = A+ v | w ∀ |vi , |wi ∈ V
Matrix representation: A+ ≡ (A∗ )T

• (AB)+ = B + A+
• (A |vi)+ = hv| A+
• (|wi hv|)+ = |vi hw|
In physics, A+ is called the adjoint or hermitian conjugate operator to A.
Hermitian (or self-adjoint) operator: A+ ≡ A
Blackboard example (Form and eigenvalues of a 2 × 2 hermitian matrix):
80
Task (02.02.2011)
Problem (Pauli matrices):
a) Find the eigenvalues, eigenvectors and the diagonal representation of the Pauli matrices
(definition see above).
b) Show that the Pauli matrices are hermitian and unitary.
c) Show that any 2 × 2 hermitian matrix A can always be expressed in terms of the unitary
matrix I and the three Pauli matrices as:
A = c 0 I + c 1 σx + c 2 σy + c 3 σz ,
where c0 , c1 , c2 and c3 are real numbers.
Solution: ??
81
3.3.b. Projection operators

If W denotes a m−dimensional subspace of V and {|1i , ..., |mi , m ≤ n} an orthonormal
basis in W , then
Xm
P = |ii hi|
i
is called the projection operator (projector) on W and is independent of the choice of the
basis.
Properties: P + ≡ P is always hermitian and P 2 = P .
Orthogonal complement: Q = I − P
... projector upon the (complementary) space {|m + 1i , ..., |ni}.
Blackboard example (Projection upon the diagonal states):
Blackboard example (Finding the i−th outcome in case of measurement):
Blackboard example (Outcome of a single-qubit measurement):
82
3.3.c. Normal operators and spectral decomposition

A is a normal operator ⇐⇒ AA+ = A+ A
Hermitian operators are normal operators.
Theorem (Spectral decomposition): Every normal operator A in V is diagonalizable

(with regard to some basis in V ) and vice versa every diagonalizable operator is normal.
Moreover, every normal operator can be written as
X
A = λi |ii hi|
i
where λi are the eigenvalues and |ii the pairwise orthonormal eigenvectors, hi | ji = δij .
Also: X X
A = λi Pi , Pi = I , Pi Pj = δij Pj
i i
where the Pi is the projector upon the eigenspace of λi .
Blackboard example (Spectral decomposition of a 3 × 3 matrix):
83
3.3.d. Unitary operators

U is a unitary operator ⇐⇒ U U + = U +U = I
Every unitary operator is normal and has a spectral decomposition.
Unitary operator ‘conserve’ the scalar product, i.e. distances and angles for all pairs of
vectors, since

hU v | U wi = v | U + U w = hv | wi
Notation: Unitary operators describe generalized rotations in Hilbert space.

Especially, if {|vi i} is an orthonormal basis in V , then {|wi i = U |vi i} is also orthonormal
in V .
Blackboard example (Basis change from the computational to diagonal basis):
Blackboard example (Unitary transform of hermitian operator):
84
3.3.e. Positive operators

A is called positive ⇐⇒ hv | Avi ≥ 0 , real ∀ |vi ∈ V
A is positive definite ⇐⇒ hv | Avi > 0 , real
All positive operators are hermitian and have a spectral decomposition

X
A = λi |ii hi| with λi ≥ 0 ∀ i .
i
POVM: A set of positive semi-definite operators

k
X
{E1 , E2 , ..., Em } with Ei = I
i
is called a positive operator-valued measure or short a POVM. Such POVM allow another
view and way of quantum measurements.
85
3.4. Products and functions of linear operators
3.4.a. Product spaces (tensor spaces)

If V and W are vector spaces with dimensions m and n, then V ⊗ W is called the product
space with dimension mn; the vectors (elements) of this space are:
|vi |wi ≡ |v, wi ≡ |vwi
with |vi ∈ V and |wi ∈ W
Important to describe composite systems (many-particle systems).
Especially, if {|ii} denotes an orthonormal basis in V and {|ji} an orthonormal basis in W ,

then
{ |ii ⊗ |ji ; i = 1, ..., m, j = 1, ..., n }
an orthonormal basis in V ⊗ W .
86
Properties of tensor products: Suppose, we have |v1 i , |v2 i ∈ V ,

|w1 i , |w2 i ∈ W and z ∈ C, then
• z (|vi ⊗ |wi) = (z |vi) ⊗ |wi = |vi ⊗ (z |wi)
• (|v1 i + |v2 i) ⊗ |wi = |v1 i ⊗ |wi + |v2 i ⊗ |wi
• |vi ⊗ (|w1 i + |w2 i) = |vi ⊗ |w1 i + |vi ⊗ |w2 i
Blackboard example (Product space of two qubits):
Blackboard example (Diagonal product basis):
87
3.4.b. Tensor product of linear operators
Definition: Suppose, we have the vectors |vi i ∈ V , |wi i ∈ W and the operators A : V → V
and B : W → W , then
(A ⊗ B) (|vi ⊗ |wi) ≡ A |vi ⊗ B |wi ∀ |vi , |wi
defines again a linear operator (A ⊗ B) : V ⊗ W → V ⊗ W .
Generalization: If A : V → V ′ and B : W → W ′ define two maps between different

vector spaces, then every operator
X
C = ci Ai ⊗ Bi
i
defines also a linear operator C : V ⊗ W → V ′ ⊗ W ′ with

!
X X
ci Ai ⊗ Bi (|vi ⊗ (|wi) = ci Ai |vi ⊗ Bi |wi
i i
88
Scalar product in V ⊗ W : can be naturally ‘defined/reduced to’ in terms of the scalar

products as defined in V and W . Moreover, since V ⊗ W also defines a Hilbert space, all
the other properties of operators, such as being adjoint, hermitian, normal, etc., can be also
utilized for the operators in the product space.
* +
X X X
ai |vi i ⊗ |wi i | bi |vk′ i ⊗ |wk′ i = a∗i bk hvi | vk′ i hwi | wk′ i
i k ik
Kronecker product (tensor product) of matrices: Suppose, we have an (m×n) matrix

A and a (p × q) matrix B, then
 
A11 B A12 B ... A1n B
 
A⊗B = 
 A21 B ... ... ... 

Am1 B ... ... Amn B
is a (mp × nq) matrix and is called the Kronecker product of A and B.
89
Example (Tensor product of the Pauli matrices X and Y ):

 
0 0 0 −i
0·Y 1·Y  0 0 i 0 
X ⊗Y = = 

1·Y 0·Y 0 −i 0 0 
i 0 0 0
Notations:
|ψi⊗ 2 = |ψi ⊗ |ψi

|ψi⊗ k = |ψi ⊗ |ψi ⊗ ... ⊗ |ψi k − times
and, similarly, A⊗ k or V ⊗ k .
Blackboard example (Eigenvalues of product eigenvectors):
Blackboard example (Action of (X ⊗ Z)):
90
Product of two operators A ⊗ B has the properties

• If A and B are hermitian, then A ⊗ B is also hermitian.
• If A and B are projection operators, then A ⊗ B is also a projection operator.
• If A and B are unitary, then A ⊗ B is also unitary.
• If A and B are positive, then A ⊗ B is also positive.
Blackboard example (Product of two projection operators):
Task (09.02.2011)
Problem (Two hermitian operators A, B): Suppose that A and B are hermitian. Show
that A ⊗ B is then also hermitian.
Solution: ??
Blackboard example (Hadamard operator):
91
3.4.c. Trace of an operator

P
Tr(A) = ii Aii
Properties:
➣ trace of an outer product |ψi hφ| is the inner product: Tr |ψi hφ| = hψ | φi.
➣ invariant under unitary (similarity) transformations:
Tr(U AU + ) = Tr(AU + U ) = Tr(A)
and, therefore, independent of the choice of the basis.
➣ trace is basis independent, i.e.
n
X n
X
TrA = hvi |A| vi i = hwi |A| wi i .
i i
Pn
➣ trace of an operator equals the sume of its eigenvalues: TrA = i λi .
92
If A, B, C are quadratic and of the same dimension, then the trace has the properties
• cyclic: Tr(ABC) = Tr(BCA) = Tr(CAB)
• linear: Tr(zA + B) = z Tr(A) + Tr(B)
If |ψi is a unit vector, then we have

X
Tr(A |ψi hψ|) = (hi |A| ψi hψ | ii) = hψ |A| ψi
i
This is often used to calculate trace of an operator.
Blackboard example (Trace of operator):
Blackboard example (Trace is equal to sum of eigenvalues):
93
3.4.d. Operator functions
The function of an operator can be found by calculating its Taylor expansion:

∞
X
f (A) = an An ,
i=0
for instance,
a2 2 a3 3
eaA = I + aA + A + A + ...
2! 3!
Definition: Suppose A is a normal operator with the spectral decomposition A

P =
i λi |ii hi|, then X
f (A) = f (λi ) |ii hi|
i
is a uniquely defined (operator) function and can be utilized in order to define/declare the
roots, logarithm, exponential, sin, ... functions of linear operators.
94
Example (Exponent of the Pauli matrix Z):

θ
θZ e 0
exp(θZ) ≡ e =
0 e−θ

1 0
since θZ has eigen values ±θ and the eigen vectors and .
0 1
Blackboard example (Infinitesimal unitary transformation):
95
Task (09.02.2011)
Problem (Single-qubit rotation): Let v = (v1 , v2 , v3 ) be any real, three-dimensional

unit vector and θ a real number. Prove that
exp(iθ v · σ) = cos θ I + i sin θ v · σ ,
where σ = (σ1 , σ2 , σ3 ) is the vector of Pauli matrices.
Solution: We first have to find the spectral decomposition of the operator

vz vx − ivy
v · σ = v x σx + v y σy + v z σz = .
vx + ivy −vz
The eigenvalues and eigenvectors of this operator are
r vx −ivy
1 − vz
λ = 1 =⇒ |uλ=+1 i = 1−vz
2 1
r
1 + vz − v1+v
x −ivy
λ = −1 =⇒ |uλ=−1 i = z
2 1
96
Therefore, the spectral decomposition is:

X
v·σ = λ |uλ i huλ |
λ=±1
and, thus, the operator functions

X
exp(iθ v · σ) = exp(iθ λ) |uλ i huλ |
λ=±1
 
2
vx +vy2 vx −ivy
1 − vz (vz −1)2 − vz −1
= eiθ  
2 v +iv
− vxz −1y 1
 
2
vx +vy2 vx −ivy
1 + vz (vz +1)2 − vz +1
+ e−iθ  
2 v +iv
− vxz +1y 1

1 2 0 i 2vz 2(vx − ivy )
= cos θ + sin θ
2 0 2 2 2(vx + ivy ) −2vz
= cos θ I + i sin θ v · σ ,
and were we made use that v is a unit vector, i.e. vx2 + vy2 + vz2 = 1.
Blackboard example (Exponential operator):
97
3.4.e. Scalar product of operators (Hilbert-Schmidt product)

All (linear) operators V → V ′ form a linear vector space LV and together with a suitable
scalar product also a Hilbert space by themself.
Hilbert-Schmidt product: (A, B) ≡ Tr(A+ B)

is a map LV × LV → C and fulfills all properties of the scalar product:
LV ⊕ Hilbert-Schmidt product ֒→ Hilbert space of lin. operators in V
If V has dimension n, the vector space LV has dimension n2 ; in general, we can choose any
set of n2 orthonormal hermitian matrices as a basis in LV .
Example (Pauli matrices): The matrices I, X, Y and Z form a basis in C2 × C2 .
98
3.4.f. Commutators and anticommutators
[A, B] = AB − BA [A, B] = 0 ⇐⇒ operators ‘commute′
{A, B} = AB + BA {A, B} = 0 ⇐⇒ operators ‘anticommute′
Many properties of operators can be understood by analyzing their commutators and anti-
commutators.
Simultaneous set of eigenfunctions:

[A, B] = 0 ⇐⇒ A and B have a common set of eigenfunctions;
diagonalizable in the same basis.
Distributivity of the commutator:
[A, BC] = [A, B]C + B[A, C] .
99
Example (Commutation relations of the Pauli matrices):
[X, Z] = 2i Z and cyclic

[σj , σk ] = 2i ǫjkl σl
{σj , σk } = 0 for j 6= k
σj2 = I for j = 1, 2, 3
σj σk = δjk I + iǫjkl σl
100
3.4.g. Decomposition of linear operators
Polar decomposition: If A : V → V is given, then we can always find a unitary operator

U and two positive operators J and K so that we have
A = UJ = KU.
These decompositions are called left-polar and right-polar decomposition, respectively.
Moreover, the operators J and K are unique and are given by
√ √
J = A+ A and J = AA+
If A−1 exist ⇐⇒ U is unique.
Singular-value decomposition: If A is a quadratic matrix, then there exist two unitary

matrices U and V (with the same dimension) and a diagonal matrix D with non-negative
eigenvalues
A = U DV
The diagonal elements of D are called singular values of A.
Blackboard example (Polar decomposition of single qubit operator):
101
3.5. Postulates of quantum mechanics
3.5.a. Postulate I (State space & state vectors)

For each quantum-mechanical systems, there is associated a scalar product space (Hilbert
space) whose unit vectors describe the system uniquely, i.e. all these states (superpositions)
represent possible states of the system.
3.5.b. Postulate II (Time evolution of closed systems):

The time evolution of the system is described by a unitary transformation
|ψ ′ (t2 )i = U (t2 , t1 ) |ψ(t1 )i
U ... time evolution operator;

discrete time evolution
102
Example (Pauli matrices):

• X : NOT gate, spin-flip (in analogy to the classical case).
|0i → |1i , |1i → |0i
• Z : phase-flip; |0i → |0i , |1i → − |1i

1 1 1
• Hadamard: H = √2 , H2 = I
1 −1
1 1
H |0i = √ (|0i + |1i) H |1i = √ (|0i − |1i)
2 2
A strict unitary time evolution applies only for closed systems; although this is an idealiza-
tion, it is often quite well fulfilled (discrete time evolution).
Schrödinger equation: alternative description with contineous time evolution

d |ψi
−i~ = H |ψi
dt
Hamilton operator: hermitian
103
The knowledge of the Hamilton operator typically requires physical intuition and experi-
mental information; in QI, the Hamiltonian is itself often less in the focus of interest but
assumed to be a known (and given by an) hermitian matrix.
P
Spectral decomposition: H = E E |Ei hE|
... eigenvalues and eigenvectors of H

Relation for H 6= H(t):

−iH(t2 − t1 )
|ψ(t2 )i = exp |ψ(t1 )i = U (t2 , t1 ) |ψ(t1 )i
~
K hermitian ⇐⇒ U = exp(iK) is unitary
Experiment: Interactions with external systems can often be described by means of a

time-dependent Hamiltonian, H = H(t).
Exceptions:
➣ Quantum measurements.
➣ Coupling to some bath or environement.
104
3.5.c. Postulate III (Quantum measurements and measurement operators):

Quantum measurements can be formally described by a set of measurement operators {Mm }
that act within the state space of the system and where m denotes one of the possible
outcomes of the measurement.
For a system in state |ψi (before the measurement), the probability for the outcome m is

+
p(m) = ψ Mm Mm ψ
and the state (just) after the measurement
M ψ Mm ψ
pm = p
p(m) hψ |Mm
+ M | ψi
m
Completeness relation:
X X

1 = p(m) = ψ Mm
+
Mm ψ ∀ |ψi
m m
X
+
I = Mm Mm
m
Blackboard example (Measurement of a qubit in the computational basis):
105
3.5.d. Postulate IV (Composite systems and entanglement):

For composite systems, the state space is given by the tensor product of the state space of
all subsystems. Especially for n systems in state {|ψi i , i = 1, ..., n}, the overall states is:
|ψ1 i ⊗ |ψ2 i ⊗ ... ⊗ |ψn i
interaction free case
In general, however, such systems will not reside in such a product state due to internal
interactions or interactions with some environement.
Notations: There are many different forms to describe many-particle/ multi-qubit systems;
in QI, one often uses an ‘index’ to denote the subsystem, for example, X2 , Z5 , ...
Entanglement: Composite systems can be in (superposition) states that cannot be written

as ‘product states’. This has been recognized also as an important resource in QI and can
lead to very unexpected results.
106
Task (16.02.2011)
Problem (Bell state): Prove that the entangled state |ψi = √12 (|01i + |10i) cannot be
represented in the form |ψi = |ai |bi where |ai and |bi are single-qubit states.
Solution: ??
Difficulties that remain with the framework of ‘QM’:

➣ State vector itself is not observable
➣ In classical physics, energy and momentum are the basic dynamical quantities that can
be observed directly; in QM, these quantities are derived and the possible measurement
outcome is determined by the state vector.
➣ Is there a ‘hidden world’ which we can understand only indirectly by using QM ? This
issue is closely related to the Bell inequalities.
➣ At present, it still looks that we will have to live and learn to go around with this ‘so
little intuitive quantum world’.
107
3.6. Measurements in quantum mechanics
3.6.a. Indistinguisable quantum states

In QM, nonorthogonal states cannot be distinguished with ‘certainty’.
Example (Determination of nonorthogonal states):

• Alice initialize a certain |ψk i out of a given {|ψi i}.
• Bob should figure out which |ψk i it is.
If all the |ψi i are pairwise orthogonal, then we may use
X
{Mi = |ψi i hψi | , i = 1, ..., n and M0 = I − |ψi i hψi | ,
i

and this choise gives for |ψk i : p(k) = ψk Mi+ Mi ψk = δik , that is this idenitifies |ψk i
with ‘certainty’.
If the {|ψi i} are nonorthogonal, then we cannot determine the state ‘with certainty’ since
other |ψj i also contain some component of |ψk i .
108
3.6.b. Projective measurements (von Neumann measurements)
Projective measurements usually refer to measuring some observable (hermitian operator)

M with the spectral decomposition
X
M = m Pm
m
where Pm denotes the projectors upon the eigenspace associated with eigenvalue m. The
probability to find this result and the state after the measurement are:
P |ψi
p(m) = hψ |Pm | ψi pm
p(m)
Follows immediately from postulate III, if we assume the measurement operators to be
+ ′
hermitian and orthogonal projectors, Mm = Mm and Mm Mm = δmm′ Mm , respectively.
Blackboard example (Action of P0 ⊗ I and I ⊗ P1 upon two-qubit state):
109
Task (16.02.2011)
Problem (Measurement of the three-qubit state): A three-qubit system is in the
state √ !
2+i 1 1 i
|ψi = √ |000i + √ |001i + √ |011i + |111i
20 2 10 2
a) Is this state normalized ?? What is the probability that the system is found in the state
|000i if all 3 qubits are measured ?
b) What is the probability that a measurement on the first qubit only gives 0 ? What is the
postmeasurement state of the system in this case ?
Solution: ??
Blackboard example (Y −gate operation and single-qubit measurement):
110
Properties of projective measurements:

➣ mean value:
X X
M̄ = m p(m) = m hψ |Pm | ψi
m m
X
= hψ |m Pm | ψi = hψ |M | ψi = hM i
m
mean value = (quantum mechanical) expectation value

➣ mean quadratic deviation:

[∆(M )]2 = (M − hM i)2 = M 2 − hM i2
The description of the measurement by means of hermitian operators (observables) also

implies Heisenberg’s uncertainty principle
1
∆(A) ∆(B) ≥ | hψ |[A, B]| ψi |
2
111
Instead of the observable

P M , one can start equivalently also from a set of orthonormal
projectors {PmP} with m Pm = I and Pm Pm′ = δmm′ Pm ; the corresponding observable is
then of course m Pm .
Other notions: Measurement in an (orthonormal) Basis {|mi} always refers to a projective

measurement with projector Pm = |mi hm|.
1
Example (Measurement of Z): Suppose we have |ψi = 2
(|0i + |1i), then
• eigenvalue +1 : hψ | 0i h0 | ψi = 1/2
• eigenvalue −1 : hψ | 1i h1 | ψi = 1/2
Blackboard example (Average value of a two-qubit operator):
112
Task (16.02.2011)
Problem (Projectors of v · σ):
a) Show that the operator v · σ = vx σx + vy σy + vz σz has eigenvalues ±1 and that the
projectors upon the corresponding eigenspaces are given by P± = (I ± v · σ) /2.
b) Apply the projector P± to calculate the probability that, for a measurement of the operator
v · σ, one obtains the result ±1, if the state prior to the measurement was |0i . What is the
state of the qubit just after the measurement if the outcome +1 was obtained ?
Solution: ??
113
3.6.c. POVM measurements

... positive operator-valued measure;
non-negative eigenvalues or positive operator norm
The POVM formalism provides a proper tool for analysing a measurement if the state (just)
after the measurement is not important.
+
Since the probability for the outcome of m is p(m) = hψ |Mm Mm | ψi is positive,
+
E m = Mm Mm
must be a positive operator, and we have

X
Em = I, p(m) = hψ |Em | ψi .
m
This means, however, that any set of positive operators {Em } is sufficient to characterize
uniquely the probabilities for some possible outcome of an experiment; the operators Em are
called the POVM elements and the set {Em } is called POVM.
114
P
Note: The projectors {Pm } with m Pm = I and Pm Pm′ = δmm′ Pm from a projective
measurement form a POVM (POVM elements = measurement operators), since
Em = Pm+ Pm = Pm .
P
If we have a set of √
positive operators {Em } with m Em = I, they also form a POVM
since, with Mm = Em , we can always write
X X
+
Mm Mm = Em = I .
m m
Alternative definition: A POVM is a set of operators {Em } that are

(i) positive, P
(ii) fulfill the completeness relation m Em = I.
The probability for measuring the outcome m is then given by
p(m) = hψ |Em | ψi.
Blackboard example (POVM for a single qubit):
Blackboard example (Transmission of non-orthogonal states):
115
Remarks:
➤ The example above shows how we can get insight into quantum measurements if we
are interested only in the outcome and probability distribution.
➤ In the past, POVM measurement have been mainly considered by mathematicians; the
POVM ‘view’ on quantum measurements has been re-activited by QI.
➤ It may help in certain cases in getting better control of a quantum system than what
is possible by projective measurements alone.
➤ Postulate III in its generalP
form has the advantage that the Mm need not to be or-
thornormal projectors, i.e. m Mm Mm′ 6= δmm′ Mm is also possible.
➤ In QI there exist problems which require the general formalism and not only projectiv
measurements.
➤ Projective measurements can, by definition, always be repeated; in Nature this is often
not the case, for example, if photons are absorbed. If measurement cannot be repeated
for a particular system/process, it can be useful to return to postulate III in its general
form.
116
Task (23.02.2011)
Problem (Construct a POVM): A given source produces a system either in one of two
nonorhtogonal states, either |ψi or |φi with scalar product | hψ | φi | = cos θ. — Construct
a POVM that help distinguish these states.
Solution: ??
Example (Weak measurements): POVM’s can be used to obtain information about a

state by means of a (so-called) weak measurement, i.e. a measurement that provides some
information about the state but without enforcing a ’collapse of the wave functions’. The
amount of information for such a mild disturbance is of course restricted.
Let’s consider a qubit in the state |ψi = a |0i + b |1i with |a|2 + |b|2 = 1. Moreover, let’s
suppose that we have a small positive parameter ε ≪ 1 and two measurement operators
√ √
M0 = |0 ih 0| + 1 − ε |1 ih 1| , M1 = ε |1 ih 1| .
From these measurement operators, we can construct a POVM by
E0 = M02 = |0 ih 0| + (1 − ε) |1 ih 1| , E1 = M12 = ε |1 ih 1| ,
117
which satisfies the completeness relation E0 + E1 = I. The eigenvalues of E0 are {1, 1 − ε}

and of E1 are {0, ε} and, thus, these POVM elements are positive semi-definite.
The probability for outcome E0 is
hψ |E0 | ψi = |a|2 + |b|2 (1 − ε) ≈ 1 ,
while the post-measurment state is

√
M0 |ψi a |0i + b 1 − ε |1i
p = p .
hψ |E0 | ψi |a|2 + |b|2 (1 − ε)
Although the state has been disturbed from the initial state of the wave function, a ’collapse
of the wave function’ to |0i or |1i did not occur but we still have a superposition.
The probability for outcome E1 is
√
2 M1 |ψi εb |1i
hψ |E1 | ψi = |b| ε ≈ 0, p = √ = |1i .
hψ |E1 | ψi ε|b|
Since ε ≪ 1, the probability of obtaining this measurement result is very small. Moreover
the wave function has collapsed in this case into the postmeasurement state |1i .
118
POVMs are more general and enable us to do things in quantum mechanics that are not
possible using ordinary projective measurements; they are often helpful if we do not need or
cannot know the postmeasurement state.
While every projective (and, hence, repeatable) measurement can be treated also as a POVM
measurement, POVM’s provide us with more freedom in that its elements need not to be
projectors and to describe especially measurements on the system without concern of the
postmeasurement state.
Task (23.02.2011)
Problem (Weak measurements): Do the operators
√ √
A0 = |0 ih 0| + 1 − ε |1 ih 1| , A1 = ε |1 ih 1|
form a POVM ??
Solution: ??
119
Figure 3.1.: The Mach-Zehnder inter-

ferometer. A photon is
sent through a beam split-
ter and bounced off at
two mirrors into another
beam splitter. Mysteri-
ously, only one of the de-
tectors registers a photon.
3.6.d. Mach-Zehnder interferometer
Set-up: A collimated beam is split by a half-silvered mirror. The two resulting beams (the
sample beam and the reference beam) are each reflected by a mirror. The two beams then
pass a second half-silvered mirror and enter two detectors (1 and 2).
It is important that the fully-silvered and half-silvered surfaces of all mirrors, except the
last, face the inbound beam, and that the half-silvered surface of the last mirror faces the
120
outbound beam exiting in the same orientation as the original collimated beam. That is, if
the original beam is horizontal, the half-silvered surface of the last mirror should face the
horizontally outbound beam.
In quantum mechanics, the Mach-Zehnder interferometer can be described by a two-

dimensional Hilbert space which is associated to the photon pathes. The state vectors
|0i and |1i can be considered as orthonormal wave packets that move along the arms of
the interferometer and where the mirrors, beam splitters and relative phases Up are given by
! ! !
0 1 1 1 1 eiφ 0
Um = , Ubs = √ , Up =
1 0 2 1 −1 0 1
For a given ρin , we need to calculate

+ + + +
ρout = Ubs Um Up Ubs ρin Ubs Up Um Ubs
For the density matrix

!
1 0
ρin = |0i h0| =
0 0
121
one obtains !
1 1 + cos φ i sin φ
ρout = .
2 −i sin φ 1 − cos φ
For the intensity along the path |0i (detector 2), we find
I ∝ 1 + cos φ ,
or in other words, the relative phase Up can be observed in the output signal of the interfer-
ometer. The intensity vanishes for a phase φ = π.
122
3.7. Density matrices and operators
3.7.a. Ensemble of quantum systems

The density operator formalism provides a suitable language if the state of a system is not
completely known, for example
{pi , |ψi i}
Ensemble of pure states: pi -th part of the Ensemble is in state |ψi i or
System is in one of the states {|ψi i} with probability pi .
The density operator is then given by:
X
ρ = pi |ψi i hψi | .
i
Time evolution of a closed quantum system:

|ψi i −→ U |ψi i
X X
ρ = pi |ψi i hψi | −→ pi U |ψi i hψi | U + = U ρU +
i i
123
Measurement with oprator Mm on state |ψi i :

+

p(m|i) = ψi Mm Mm ψi = Tr(Mm+
Mm |ψi i hψi |)
X X
+
P (m) = p(m|i)pi = pi Tr(Mm Mm |ψi i hψi |)
i i
+
= Tr(Mm Mm ρ)
and the state after the measurement:
Mm |ψi i
|ψim i = p
p(m|i)
X
ρm = p(i|m) |ψim i hψim |
i
X Mm |ψi i hψi | Mm+ +

Mm ρ Mm
= p(i|m) =
i
hψi |Mm
+M | ψ i
m i Tr(Mm
+ M ρ)
m
where use is made that p(i|m) = p(m|i)pi /p(m).
124
Notations:
pure states mixed states

X
ρ = |ψi hψ| ρ = pi |ψi i hψi |
i
Tr(ρ2 ) = 1 Tr(ρ2 ) < 1
Mixture of density operators: is again a valid density operator since with

X
ρi = qk |ψik i hψik |
k
X X X
p i ρi = pi qk |ψik i hψik | = pr |ψr i hψr |
i k k
In QI, the density matrix occurs especially in the description of composed systems and
decoherence processes that result from the (not controllable) interaction of some systems
with its environment.
125
3.7.b. Properties of density operators

Beside of the ensemble interpretation of the density matrix, there is an independent definition
that does not rely on the term of the state vector.
An operator ρ is a valid density operator, i.e. the density operator for ensemble {pi , |ψi i}, if
• Tr(ρ) = 1 (trace condition, normalization)
• ρ is any positive operator
P
Proof: If ρ = i pi |ψi i hψi |, then
X X
Tr(ρ) = pi Tr(|ψi i hψi |) = pi = 1
i i
X X
hφ |ρ| φi = pi hφ | ψi i hψi | φi = pi | hφ | ψi i |2 ≥ 0 .
i i
and vice versa: Since ρ is positive, there alway exist a spectral decomposition
X
ρ = λj |ji hj|
j
with {|ji} orthonormal and λj ≥ 0, real.
126
Moreover X X
Tr(ρ) = λj Tr(|ji hj|) = λj = 1 ,
j j
that is ensemble {pi , |ψi i} has density operator ρ.
Blackboard example (Density matrix of a pure state):
Blackboard example (Test for being a valid density operator):
Blackboard example (Expectation value of an operator):
Blackboard example (Probability for finding the |−i state):
Blackboard example (Completely mixed state):
Task (23.02.2011)
Problem (Mixed state density operators): Proof that Tr(ρ2 ) < 1 for mixed state !
Solution: ??
127
Task (23.02.2011)
Problem (Pure vs. mixed states): There are given the following density matrices:
! !
3/4 0 1/2 1/2
a) ρ = , b) ρ = ,
0 1/4 1/2 1/2
! !
1/2 1/4 1/2 −i/2
c) ρ = , d) ρ = ,
1/4 1/2 i/2 1/2
!
1−i
1/2 √
2 2
e) ρ = 1+i .
√
2 2
1/2
Which of these density operators represent pure and which one mixed states ? If the state
is pure, then determine the state vector, and find an ensemble representation otherwise.
Solution: ??
128
3.7.c. Postulates of quantum mechanics for density operators

Postulate I (State space & density operators):
A scalar product space (Hilbert space) is associated with each quantum-mechanical systems.
Every positive operator ρ with Trρ = 1, that acts in the state space, defines a possibleP state
of the system. Especially, if the system is in state ρi with probablility pi , then ρ = i p i ρi
Postulate II (Time evolution of closed systems):
Every (discrete) time evolution of a closed system can be described by a unitary transfor-
mation
ρ′ = U ρ U + = U (t2 , t1 ) ρ(t1 )U + (t2 , t1 )
Postulate III (Quantum measurements and measurement operators):
Quantum measurements are described by a set of measurement operators {Mm }, that act in
the state space and where m denotes the possible outcomes.
129
If, before the measurement, the system is in state ρ, then

+
• Probability for outcome m: p(m) = Tr(Mm Mm ρ)
• State after the measurement: +
Mm ρMm
Tr(Mm ρMm +)
P +
• Completeness: m Mm Mm = I
Postulate IV (Composite systems and entanglement):
The state space of a composed system is the product space of the state spaces of the
subsystems; if the n subsystems are in the state {ρi , i = 1, .., n}, then the total state is
ρ tot = ρ1 ⊗ ρ2 ⊗ ... ⊗ ρn .
Advantages of the density-matrix concept:
➣ Incomplete knowledge about the system
➣ Description of subsystems that should be considered independent of some total system.
Blackboard example (Post-measurement state):
Blackboard example (Expectation value for measuring X):
130
3.7.d. Uniqueness of the density operator
Different ensemble {pi , |ψi i} may have the same density operator,
P i.e. the behave uniquely
with regard to all measurements. The particular ensemble ρ = i λi |ii hi|, that is associ-
ated with the eigenvalues and eigenvectors, is physically not distinguished.
Notation: A set of (non-normalized) vectors {|ψ gi i} is said to ‘create’ the density operator
P gg
ρ = i |ψi ihψi |, then we refer to the ensemble
( )
g
|ψ ii
pi , √ ... normalized .
pi
g
Unitary freedom: Two set of vectors {|ψ g
i i} and {|φi i} create the same density operator,
if X
g
|ψ ii =
g
uij |φ ji
j
131
g
are related to each other via a unitary matrix, U = (uij ) If the number of {|ψ g
i i} and {|φi i}
vectors are different, then a corresponding number of ‘null vectors’ can be added.
If two ensemble {pi , |ψi i} and {qj , |φj i} are given, then they have the same density operator
if X
√ √
pi |ψi i = uij qj |φj i
j
is fulfilled for some unitary matrix
132
3.7.e. Blochdarstellung eines Qubits
Computational basis:
1 0
|0i = , |1i =
0 1
|ψi = a |0i + b |1i a, b ∈ C
|a|2 + |b|2 = 1
Conjugate basis: Two bases are called conjugate to each other if the corresponding pairs
of antipodal points on the Bloch sphere are 90o apart from each other. For two conjugated
bases |ai , |bi and |a′ i , |b′ i, the probability of a qubit in the state |ai or |bi to be found in
the state |a′ i or |b′ i is always 1/2 and vice versa.
Diagonal basis:
1 1
|րi ≡ |+i = √ (|0i + |1i), |ցi ≡ |−i = √ (|0i − |1i) .
2 2
This basis is conjugate to the computational basis. The computational and diagonal bases
are used together to provide the pairs of ‘signal states’ that are utilized in the BB84 quantum
key distribution (QKD) protocol.
133
Circular basis:
1 1
|Ri = √ (|0i + i |1i), |Li = √ (|0i − i |1i) .
2 2
This basis is conjugate to both, the computational and diagonal basis. It is also useful in
quantum cryptography and in many quantum-optical realizations and experiments.
Breitbart or ‘intermediate’ basis:

π π π π
cos |0i + sin |1i , − sin |0i + cos |1i .
8 8 8 8
This basis lies on the φ = 0 plane and is used in QKD for eavesdropping.
Bloch-sphere or spinor representation:

iγ θ iφ θ
|ψi = e cos |0i + e sin |1i
2 2
with (θ, φ) refereing to the polar angles on a unit sphere. If θ = 0 or π, then φ is taken
to be zero by convention. The effect of a general operation on a qubit can be viewed as a
(possibly stochastic) transformation within this (Bloch) ball.
134
Figure 3.2.: Statistical operators represented in the unit Bloch ball, a

real-valued representation of the space of qubit states via
the expectation values, Si , of Pauli operators σi , i = 1, 2, 3.
P (|xi) = |xi hx|. Orthogonal quantum states are antipodal
in this representation; the ‘conjugate bases’ correspond to
orthogonal axes. The pure qubit states |ψ(θ, φ)i lie on
the periphery, known as the (Poincare-) Bloch sphere. The
mixed qubit states, ρ(r, θ, φ), lie in the interior and are
weighted convex combinations of pure states. The maxi-
mally mixed state, 12 I, lies at the center of the ball, being
an evenly weighted linear combination of any two orthogo-
nal pure states. In the Poincare presentation that is often
used in polarization optics, the sphere is rotated counter-
clockwise about the diagonal-basis axis by 90o with respect
to the one here.
135
Unfortunately, there is no simple picture for several qubits.

General representation for mixed states:
I + r·σ
ρ =
2
where r = (rx , ry , rz ) is any 3−dimensional vector with |r| ≤ 1. For |r| = 1, ρ describes a
pure state.
Blackboard example (Stern-Gerlach filter):
Task (02.03.2011)
Problem (Stern-Gerlach filter): A beam of electrons, prepared as a 50:50 statistical

mixture with spin projections µz = ±1/2 (along the z−axis), is sent through a Stern-Gerlach
filter which admits only particles with spin projection +1/2 on the z−axis. Determine the
probability that an electron will penetrate the filter. Compare this result with the solution
from above. How can one distinguish the pure and mixed electron states by using the
Stern-Gerlach technique ?
Solution: ??
136
3.7.f. Stokes parameters

Instead to the three real parameters (rx , ry , rz ), often four Stokes parameters Pµ are utilized
that have the advantage of being more closely related to empirical quantities, such as photon-
counting rates in selective measurements. Three of these parameters (µ = 1, 2, 3) correspond
to measurements in the computational, diagonal and circular basis (which are all orthogonal
on the Bloch sphere).
Stokes parameters and density matrix: both representations are homomorphic to each
other, since the density matrix and the Stokes four-vector Pµ are related to each other via
the Pauli (and unit) matrices by
1 X
3
ρ = Pµ σµ
2 µ=0
with σ0 ≡ I. This representation of the density operator is known also as Pauli representa-
tion.
137
The Stokes parameters Pµ also enables one to directly visualize the qubit state geometrically
in the Bloch ball !
1 P0 + P3 P1 − iP2
ρ = .
2 P1 + iP2 P0 − P3
The Stokes parameter are often normalized to P0 = 1 ... the total quantum probability.
Stokes parameters are expressed in terms of the density matrix as
Pµ = Tr(ρσµ ) .
!
cos 2θ
If the state of a qubit is given in the spinor representation , then the Stokes
eiφ sin 2θ
are P0 = 1, P1 = sin θ cos φ, P2 = sin θ sin φ and P3 = cos θ.
The four-vectors formed by the Stokes parameters provide a basis in Minkowski space R41,3
in which the σµ are the generators of rotations and hyperbolic rotations in this space.
Blackboard example (Stoke’s parameters of a single-qubit state):
138
Example (Pauli representation for two qubits): is given by

1 X
ρ = cij σi ⊗ σj
4 ij
with cij = Tr(ρ(σi ⊗ σj )). It can be shown that the density operator ρ is separable, iff
|c11 | + |c22 | + |c33 | ≤ 1, while c00 ≡ 1 for a properly normalized state.
Task (02.03.2011)
Problem (Density matrix of spin-1/2 particle): Let a spin-1/2 particle be in the spin
state X
|ψi = aµ |χµ i .
µ=±1/2
a) Find the density matrix which describe the spin state of this particle.
b) Find the polarization vector P = hψ |σ| ψi in terms of the coefficients aµ .
Solution: ??
139
3.7.g. Reduced density operators and partial trace
Reduced density operator: Let ρAB be the density operator of a system that consists
out of two subsystems A and B. Then, the reduced density operator of system A
ρA = TrB (ρAB )
is given by the partial trace over system B.
Partial trace: Suppose the density matrix of a composed system is given by

nA X
X nB
ρAB = ρij,kl |iA i |jB i hkA | hlB |
ik jl
with respect to two orthonormal bases {|iA i} and {|jB i}, then the partial trace is defined as
nA nB
!
X X
TrB (ρAB ) = ρim,km |iA i hkA | .
ik m
The partial trace is independent of the basis {|jB i} and, thus, suitable to describe observa-
tions and measurements for subsystem A.
140
Example (Reduced density matrix of a product state):

Suppose ρAB = σ ⊗ τ = ρA ⊗ ρB , then
ρA = TrB (σ ⊗ τ ) = σ Tr(τ ) = σ since Tr(τ ) = 1 .
Example (Reduced density matrix of a Bell state):

Consider |Φ+ i = √12 (|00i + |11i) and, hence,
|00i h00| + |11i h00| + |00i h11| + |11i h11|

ρ = ,
2
and
1 I
ρ1 = Tr2 (ρ) = (|0i h0| + |1i h1|) = = ρ2
2 2
1
Tr(ρ21 ) = Tr(ρ22 ) = ≤ 1.
2
Although the total system is in a pure state, the reduced density matrix of any subsystem
represents in general a mixed state.
141
Task (02.03.2011)
Problem (Reduced density matrix of other Bell states): Find the reduced density
operators also for the Bell states |Ψ± i = 12 (|01i ± |10i).
Solution: ??
142
3.7.h. Schmidt decomposition of pure states
Schmidt decomposition: Suppose |ψi is a pure state of a bipartite system AB. Then,
there always exist orthonormal states {|iA i} and {|jB i} so that
X
|ψi = λi |iA i |iB i
i
P
with λi ≥ 0, real and i λi = 1. The λi are called the Schmidt coefficients.
The reduced density operators for the subsystems A and B are given by
X X
ρA = λ2i |iA i |iA i , ρB = λ2i |iB i |iB i ,
that is the ρA and ρB have the same eigenvalues {λ2i }. For a proof, see Nielsen & Chuang
(2002), section 2.5; applies the singular-value decomposition.
The bases {|iA i} and {|jB i} are called Schmidt bases.

Schmidt number: Number of non-zero eigenvalues λi > 0 measure for entanglement between
A and B.
143
For composed systems:

AB
ψ is product state ⇐⇒
2 2
Tr(ρA ) = Tr(ρB ) = 1
separable Schmidt number is 1.

ρA and ρB are pure.
Task (02.03.2011)
Problem (Schmidt decomposition of two-qubit states): Find the Schmidt decompo-

sition for the following two-qubit states:
√
a) (|00i + |11i)/ 2 and
b) (|00i + |01i + |10i + |11i)/2.
Solution: ??
144
3.7.i. Purification of reduced density operators

Given: ρA of a quantum system A.
Looking for: Pure state |ARi , so that
ρA = TrR (|ARi hAR|) .
This pure state is to be obtained by considering the ‘composed’ system A together with some
particularly chosen reference system R.
Indeed, P such a pure state exist for every valid density operator ρA . Suppose, we have
ρA = pi |iA i hiA | and a reference system in the same state space and with the basis
{|iR i}. Then, X√
|ARi = pi |iA i |iR i .
i
Obviously,
X√
TrR (|ARi hAR|) = pi pk |iA i hkA | |iR i Tr(|iR i hkR |)
ik
145
X
= pi |iA i hiA | = ρA .
i
Apparently, there is a close relation between the Schmidt decomposition and the purification
of states. Schmidt basis of A is the same basis in which ρA diagonal is.
However, pure state |ARi is not unique but pairs of such states are related to each other
by some unitary transformation
|AR1 i = (IA ⊗ UR ) |AR2 i .
146
3.8. The EPR paradoxon and Bell’s inequality

(Einstein, Rosen und Podolsky, 1935)
3.8.a. Bohr–Einstein debate (1926–35)

The Bohr-Einstein debate refers to a series of public disputes about quantum mechanics
between Albert Einstein and Niels Bohr who were two of its founders. Their debates are
remembered because of their importance to the philosophy of science. It was summarized by
Bohr in an article titled Discussions with Einstein on Epistemological Problems in Atomic
Physics.
Remarks:
➤ See, for example, wikipedia (Bohr-Einstein debate) for details.

➤ In 1925, remember, Werner Heisenberg introduced matrix equations that removed the
Newtonian elements of space and time from any underlying reality; in 1926, Max Born
then proposed that the mechanics was to be understood as a probability without any
causal explanation. — Einstein, in contrast, believed that the reasons for the ‘new’
mechanics still needed to be understood.
147
➤ Bohr himself accepted the ‘philosophical’ problems with quantum mechanics by propos-
ing a Principle of Complementarity that emphasized the role of the observer over the
observed.
➤ A first serious attack by Einstein took place during the Fifth Conference of Physics at
the Solvay Institute in 1927 where he argued from the viewpoint of the (universally
accepted) laws of conservation of energy and of impulse (momentum).
➤ Bohr’s replied quickly and showed the impossibility of using Einstein’s apparatus to
violate the principle of indeterminacy depends crucially on the fact that the macroscopic
system also obeys quantum laws.
➤ At the sixth Congress of Solvay in 1930, Einstein attacked again the indeterminacy
relation; he proposed an experimental apparatus which was subsequently re-designed
by Bohr to emphasize the essential elements and the key points which he would use in
his response.
➤ Finally, the discussion culminated in 1935 in the famous EPR paper which stated the
paradoxon of quantum-mechanically entangled states in a very clear way and which,
since then, has lead to numerous experiments to (dis-)prove the consequences of non-
locality.
148
3.8.b. EPR ‘gedanken’ experiment

The idea of the EPR paper was to show that quantum mechanics is not a ‘complete theory’
in the sense that it provides only an imcomplete description of Nature.
‘Elements of reality’ (local realism):
➣ every complete theory must be able to predict the physical properties of an object with
certainty.
➣ Physical events and measurements must be independent if they are causal unrelated to
each other.
Core value of EPR: was that the properties of physical systems have definite values (an
objective reality) whether you observe the system or not. That is, a given property of a
system has (should have) a defined value already before a measurement is made, or even
if no measurement is made. Quantum mechanics, however, tells a different story: Prior to
measurement, a property of the system does not have a definite or sharply defined value.
149
Classical experiment:
Alice Charlie Bob

PQ : Q = ±1 ←− source −→ PS : S = ±1
PR : R = ±1 produces equivalent pairs of particles PT : T = ±1
with PX property and X the outcome of a measurement.
The scenario drawn by EPR is difficult to test experimentally (for mainly technical reasons).
A simpler version of this seminal thought experiment was put forward by David Bohm in
1952 and involved particles with correlated spins; he considered a spin-0 particle that decays
into two spin-1/2 particles (like in the two-photon decay of an atom).
Blackboard example (Correlations of–entangled–Bell states):
150
3.8.c. Bell’ inequalities

Classical treatment of the outcomes Q, ..., T as random variables gives rise to equation:
QS + RS + RT − QT = (Q + R)S − (R − Q)T = ± 2 .
Suppose, p(q, r, s, t) is the probability to find Q = q, R = r, ..., then the classical expectation
value (average) is:
X
E(QS + RS + RT − QT ) = p(q, r, s, t) (qs + rs + rt − qt)
qrst
X
≤ 2 p(q, r, s, t) = 2 .
qrst
Therefore, since expectation values is linear, we obtain

E(QS) + E(RS) + E(RT ) + E(QT ) ≤ 2
Bell’s inequality: Classical expectation for any experiment has under the assumptions above
an ‘upper limit’.
151
3.8.d. Quantum mechancical ‘anticorrelations’ in the EPR experiment

Consider the two-qubit (Bell) state
|01i + |10i
|ψi = √ ,
2
i.e. an entangled singulet state. If we perform an indepedent spin measurment along some
axis w for both qubits, then outcome for the measurement w · σ = ±1.
Quantum experiment, for example with measurements of:

|01i + |10i
Alice |ψi = √
2
Bob
−Z2 − X2
PQ : Z1 ←− source −→ PS : √
2
Z2 − X 2
PR : X1 PT : √
2
then one finds (after the computation of the expectation values):
√
hQSi + hRSi + hRT i + hQT i = 2 2 = > 2
152
In other words, Bell’s inequality can be violated by an quantum mechanical experiment.

Nature: Suitable chosen experiments confirm QM and are in clear clear conflict with the
classical expectations.
Consequences:
➣ At least one of the assumptions above are not fulfilled by Nature;
either ‘physical reality’ of properties is wrong, i.e. the assumption that the properties
PQ , ..., PT exist independently from the observation or
➣ the ‘locality’ of events, i.e. that causal independent events cannot influence each
other.
➣ Apparently, the quantum world is not local-realistic.
➣ (Quantum-mechanical) entanglement and nonlocality is an additional resource that
is provided by quantum mechanics and which we do not have in the classical world.
Indeed, there are many applications of these resources in QI.
Many people belief that the ‘physical reality’ of properties does not exist independent of the
observations.
153
3.8.e. Bipartite systems and the Bell basis

A bipartite system consists of two subsystems, for example, if Alice and Bob each have one
member of an entangled pair of particles. The Hilbert space of the composite system is
HA ⊗ HB , and a basis for this systems is found by taking the tensor products |ai i ⊗ |bj i ≡
|ai bj i. Moreover, if the basis for Alice and Bob are both orthonormal, we have
hai bj | ak bl i = δik δjl
Pr(ai bj ) = | hai bj | ψi |2
X
A = hai bj | hai bj |A| ak bl i |ak bl i
ijkl
for the scalar product, probability and representation of an operator in this product basis.
A frequently considered alternative is the Bell basis which is formed by the four Bell states
|00i + |11i |01i + |10i |00i − |11i
|β00 i = √ , |β01 i = √ , |β10 i = √ (triplet state)
2 2 2
|10i − |01i
|β11 i = √ (singulet state)
2
154
The Bell states can be written more compactly in the form

|0yi + (−1)x |1ȳi
|βxy i = √ ,
2
where ȳ is ‘not”y; x is also called the phase bit and y the parity bit.
Blackboard example (Z ⊗ Z |βxy i):
Blackboard example (Is the state H ⊗ H |00i entangled ??):
155
3.8.f. Bell state representation of a two-qubit density operator

A two-qubit density operator that is diagonal with respect to the Bell states can be written
in the form
X
ρ = cij |βij ih βij |
ij
= c00 |β00 ih β00 | + c01 |β01 ih β01 | + c10 |β10 ih β10 | + c11 |β11 ih β11 | .
The outer products in this expansion can be expressed also in terms of the Pauli matrices
1
|β00 ih β00 | = (I ⊗ I + X ⊗ X − Y ⊗ Y + Z ⊗ Z)
4
1
|β01 ih β01 | = (I ⊗ I + X ⊗ X + Y ⊗ Y − Z ⊗ Z)
4
1
|β10 ih β10 | = (I ⊗ I − X ⊗ X + Y ⊗ Y + Z ⊗ Z)
4
1
|β11 ih β11 | = (I ⊗ I − X ⊗ X − Y ⊗ Y − Z ⊗ Z) .
4
When expressible in this form, a density operator ρ is separable if and only if
1
c00 ≤ .
2
156
4. Models for quantum computations
4.1. Di’Vincenzo’s criteria on physical requirements

In an important article in 2000, Di’Vincenzo proposed five criteria that any physical system
should satisify in order to represent a viable quantum computer. The discussion in this
section here follows closely some work by Salomaa and Nakahara (conference contribution,
World Scientific Publishing, 2005).
Five (+ two) criteria for a successful realization of a quantum computer:
➣ A scalable physical system with well characterized qubits.

+ The simplest way to realize a qubit physically is to use a two-level quantum system;
one can use also any other 2-dimensional subspace of some larger Hilbert space (for
157
example, atoms or molecules) ... but must avoid leakage into other parts of the corre-
sponding Hilbert space.
+ Each qubit must be separately addressable.
+ Scalable up to a large number of qubits.
+ The condition of two states may be relaxed to three states (qutrits) or, more gener-
ally, d states (qudits).
+ A given system may contain different kinds of qubits; trapped ions, for instance,
may employ (1) hyperfine/Zeeman sublevels in the electronic ground state of ions, (2)
the ground and excited states of weakly allowed optical transition, and (3) the normal
modes of ion oscillation, as qubits.
➣ Initializiation to a simple fiducial (and usually) pure state.

+ In many realizations, initialization may be done either by cooling or by means of
projective measurements.
+ If such a measurement results in a undesired state, some additional unitary trans-
formation may become necessary for initialization.
+ For some realizations (such as liquid state NMR), it can be impossible to cool the
system down to extremely low temperatures; one is then enforced to use a thermally
populated state as an initial state with additional complications.
+ Continuous fresh supply of qubits in a specified state, such as |0i , may also be an
important requirement for successful quantum error correction.
158
➣ Long decoherence times, much longer than the gate operation time.
+ Decoherence due to undesired interactions of the system with its environment is
probably the hardest obstacle to building a viable quantum computer.
+ What matters is the ratio decoherence time/gate operation time.
+ There are several ways to effectively elongate the decoherence time by either quantum
error correction (QEC) or decoherence-free subspaces (DFS). Both of these methods
require extra qubits to be implemented.
+ Time-optimal implementation of a quantum algorithm is regarded as a method to
fight against decoherence without any extra resouce.
➣ Universal set of quantum gates.
+ A well known theorem guarantees that any U (2n ) gate may be decomposed into
single-qubit gates U (2) and CNOT gates.
+ Therefore it suffices to find the control sequences to implement U (2) gates and a
CNOT gate to construct an arbitrary gate.
+ Implementation of a CNOT gate in any realization is considered to be a milestone
but other (entangling) two-qubit operations would be also sufficient.
+ Many quantum circuit implementations would requires less steps if multi-qubit gates
for n ≥ 3 qubits could be realized als ‘black boxes’.
159
➣ A qubit-specific measurement capability.

+ The state after an execution of a computation must be measured to extract the result
of the computation; for most realizations, projective measurements are the primary
method to extract the outcome of a computation.
+ Measurements have in general no 100 % efficiency due to decoherence, gate operation
error and many more reasons. If this is the case, one has to repeat the same computation
several times to achieve reasonably high reliability.
In practice, there are two more requirements to be considered:
➣ Ability to interconvert stationary and flying qubits.

+ A working quantum computer may involve several kinds of qubits, and one may be
enforced to introduce distributed quantum computing.
+ Such an interconverting ability is also important in long distant quantum teleporta-
tion using quantum repeaters.
➣ Ability to faithfully transmitting qubits between specified locations.
+ Important in distributed quantum computing.
160
There are numerous physical systems proposed as a possible candidate for a viable quantum
computer; they include
Physical realizations:
➣ Liquid-state/solid-state NMR
➣ Trapped ions
➣ Neutral atoms in optical lattice
➣ Cavity QED with atoms
➣ Linear optics
➣ Solid state (spin-based, charge-based)
➣ Josephson junctions (charge, flux, phase)
➣ Electrons on liquid helium surface
➣ Other “unique” realizations
ARDA QIST roadmap evaluates each of these realizations; see “A Quantum Information
Science and Technology (QIST) Roadmap, Part 1: Quantum Computation” compiled by
Advanced Research and Development Activity (ARDA), Los Alamos, USA. This article is
updated annually.
161
4.2. Different models: A short overview

There are many models of quantum computation. Historically, the first was the quantum
Turing machine, based on classical Turing machines. A more convenient model is the quan-
tum circuit model.
Promising models for quantum computing
➣ Quantum circuit model.

+ Adapts the ‘classical’ circuit model with reversable gates to the quantum case; usually
drawn in terms of wire diagrams.
+ A (single) quantum gate or quantum logic gate is a rudimentary quantum circuit
operating on a small number of qubits.
+ Quantum gates are the analogues for quantum computers to classical logic gates
for conventional digital computers. Quantum logic gates are reversible, unlike many
classical logic gates.
162
➣ “One-way” or measurement-based quantum computations (MBQC).

+ One way quantum computation (1WQC) uses an initially highly entangled state
(called a cluster state), together with single qubit measurements; it was introduced by
Raussendorf and Briegel in 2001.
+ Since the outcome of measurements is probabilitistic, this scheme must be combined
with a feed-forward based on the results, in order to drive a quantum computation.
+ The final result of the computation is obtained by measuring the last remaining
qubits in the computational basis.
+ Key feature of 1WQC is that the computation is not reversible since measurement
collapses the state of the measured qubit and, thus, disentangling it effectively from
the rest of the cluster state.
+ The essential concept underlying 1WQC is teleportation of quantum gates; it al-
lows scalable universal QC in systems which have a probabilistic entangling procedure
and single qubit measurements, but without a direct two-qubit interaction suitable for
implementing deterministic entangling gates.
➣ Adiabatic quantum computations (AQC).

+ Adiabatic computation encodes the solution of a problem in the (product) ground-
state of a specially crafted Hamiltonian.
163
+ One begins with a physical system in an easily generated ground state of some initial
Hamiltonian, and then changes the Hamiltonian slowly enough (in the so-called adia-
batic limit), so that the system always remains in the ground state of the instantaneous
Hamiltonian.
+ At the end of the process, the final Hamiltonian is made to have a ground-state
which encodes the solution of the problem.
+ Central questions of this model concern of how slowly does one need to change the
Hamiltonian in order to satisfy the adiabatic theorem; this depends on the energy gap
between the (non)degenerate ground state and the first excited state(s).
+ AQC was proved to be polynomially equivalent to the standard circuit model.
➣ Topological quantum computations (TQC)
+ TQC is an approach to quantum information processing that eliminates decoher-
ence at the hardware level by encoding quantum states and gates in global, delocalized
properties of the hardware medium.
+ TQC thus avoids perfect shielding from the environment.
+ TQC is considered as fundamental breakthroughs in eliminating decoherence; real-
izations of this scheme are not (yet) well understood.
+ Delocalized, or topological degrees of freedom are intrinsically immune to all forms
of noise which do not impact the entire medium at once and coherently.
164
➣ Quantum Programming Language

+ Not a model for practical realization.
+ Quantum Programming Language is a programming language, which can be used to
write programmes for quantum computer.
+ Since every quantum machine has to be controlled by classical device, existing quan-
tum programming languages incorporate classical control structures such as loops and
conditional execution and allow to operate on classical and quantum data.
165
4.3. Circuit model of quantum computations
Task (06.04.2011)
Read the section 3.2 The circuit model of quantum computations from the book of Benenti,
Casati & Strini, Volume I (2004), pages 105-130.
4.3.a. Single-qubit operations
Properties:
➣ Represented by 2 × 2 unitary matrices which cause ‘rotations’ (of some given state) on
the Bloch sphere.
➣ Typically, quite easy to implement in most realizations.
➣ Important single-qubit operations are: X, Y, Z, Rz (θ), S, T, ....
166
Task (13.04.2011)
Problem (Single-qubit gates):
a) Prove that an arbitrary single-qubit unitary operation can be written in the for
U = exp(iα)Rn (θ)
where α and θ are real parameters, and n is a real three-dimensional unit vector.
b) Find the values of α, θ and n for the following gates:
! ! !
0 1 1 1 1 1 0
σx = , H = √ , S = .
1 0 2 1 −1 0 i
Solution: ??
167
x1 H x1
Figure 4.1.: Examples of two-qubit quantum circuits.
x2 x2 H
4.3.b. Conditional quantum operations

Blackboard example (Matrix representation of multi-qubit gates):
168
Task (20.04.2011)
Problem (CNOT constructed from a controlled-Z gate): Construct a CNOT gate
from a controlled-Z gate  
1 0 0 0
 
 0 1 0 0 
 
 0 0 1 0 
 
0 0 0 −1
and two Hadamard gates. Specify the control and target qubits.
Solution: ??
Problem (Gate identities): Prove that H σz H = σx and make use of this

! result to show
1 0
that H T H = Rx (π/4), up to a global phase, if T = and Rx (θ) =
0 exp(iπ/4)

exp −iθ X2 .
Solution: ??
169
H H
Figure 4.2.: Equivalence of simple circuits.
H H
Example (CNOT basis transformation): Prove the equivalence of Figure 4.2.
The left-hand side is:
(H1 ⊗ H2 ) · CNOT · (H1 ⊗ H2 )

     
1 1 1 1 1 0 0 0 1 1 1 1
 1 −1 −1 
1  0 0   −1 
1    0 1  1  1 −1 1 
=  · ·  
2  1 1 −1 −1   0 0 0 1  2  1 1 −1 −1 
1 −1 −1 1 0 0 1 0 1 −1 −1 1
 
1 0 0 0
 0 0 0 1 
 
=  
 0 0 1 0 
0 1 0 0
170
Obviously, this transforms the basis states according to the rules:

   
1 1
 0   0 
   
U |00i = U   =   = |00i
 0   0 
0 0
and, similarly,
U |10i = |10i , U |01i = |11i , U |11i = |01i .
This is apparently the transformation of a CNOT gate where the first qubit is the target and the second is
the control-qubit.
171
4.3.c. Universal quantum gates

Blackboard example (Determine circuit from given gate):
Task (20.04.2011)
Problem (Design of small circuits):
a) Construct a two-qubit gate that realizes the transformation
|a, bi −→ |b, ai ∀ a, b, = |0i , |1i ,
by using only the CNOT and Hadamard gates.

!
1 0
b) Prove that U = can be written in the form U = eiθ A σx B σx C where
0 eiα
θ = α/2, A = Rz (α), B = C = Rz (−α/2) such that A B C = I.
Solution: ??
172
4.4. Adiabatic model of quantum computations
4.4. Adiabatic model of quantum computations
Task (13.04.2011)
Read the paper “Quantum Computation by Adiabatic Evolution” by E. Farhi et al., quant-
ph/0001106.
4.5. One-way or cluster state computations
Task (13.04.2011)
Read the Letter “A One-Way Quantum Computer” by R. Raussendorf and H. J. Briegel,
Phys. Rev. Lett. 86 (2002) 5188.
Moreover, read the chapter 15. Cluster-state computing from the book of D. McMahon,
Quantum Computing Explained (2008), pages 315-327.
173
4.6. Holonomic quantum computations

Read the article by E. Sjöquist: “A new phase in quantum computations”, Physics 1, 35
(2008).
4.7. Beyond the Di’Vincenzo’s criteria
Remember the 5+2 criteria:
➣ A scalable physical system with well characterized qubits.

➣ Initializiation to a simple fiducial (and usually) pure state.
➣ Long decoherence times, much longer than the gate operation time.
➣ Universal set of quantum gates.
➣ A qubit-specific measurement capability.
➣ Ability to interconvert stationary and flying qubits.

➣ Ability to faithfully transmitting qubits between specified locations.
174
4.7. Beyond the Di’Vincenzo’s criteria
Remarks:
➤ Some conditions can be relaxed; for example, in one-way quantum computing one make use of irre-
versible non-unitary gates.
➤ There has been a wide discussion of whether Di’Vincenzo’s criteria are sufficient; these questions refer
to topics such as:
+ Implementation of decoherence-free subsystems/subspaces.
+ Implementation of quantum error correction.
+ Fault-tolerant quantum computing.
+ Topologically protected qubits.
➤ Fault-tolerant quantum computing requires (Gottesman):
(1) Low gate error rates.
(2) Ability to perform operations in parallel.
(3) A way of remaining in, or returning to, the computational Hilbert space.
(4) A source of fresh initialized qubits during the computation.
(5) Proper error scaling: error rates that do not increase as the computer gets larger, and no large-scale
correlated errors.
Many of the above conditions are necessary for quantum error corrections to work reasonably well.
175
Remember:
➣ Quantum computers are no hypercomputers in the sense that they can do more than
what can be done classically; however, they can do it more efficient. In principle,
classical and quantum computers can emulate each other.
➣ What are easy and hard problems are different for classical and quantum computers.
Classically, hard problems are the traveling salesman problem, the graph isomorphism
problem, and the problem of factoring a number into primes.
➣ Quantum computers may first show up as quantum simulators since quantum sys-
tems can simulate efficiently with managable overhead the behaviour of other quantum
systems. Indeed, an important difference between quantum computers and quantum
simulators are that hundreds or thousands of qubits are needed for a competible Shor-
algorithm applications, while a few tens of qubits may already be useful for the simu-
lation of quantum systems.
➣ Another application refers to atomic clocks as needed for global positioning or the
synchronization of large telescopes: By generating quantum correlations between the
176
N relevant atoms in the atomic clock,√a quantum circuit can in principle reduce the
uncertainty of the clock by a factor of N .
➣ An important difference between classical and quantum computers concerns the read-
out process which can be done only probabilistically for quantum states: In practice,
this probabilistic nature of the read-out process on the one hand and the possibility of
exploiting quantum parallelism on the other hand are competing aspects in analyzing
the computational power of quantum and classical computers.
➣ Any generic two-qubit gate (together with the possibility of swapping the qubits) is
itself a universal set, similar as the NAND gate is for classical computing.
➣ Any quantum circuit that makes use of a certain universal set of quantum gates can
be simulated by some different quantum circuit based on another universal set of gates
with only polylogarithmic overhead.
➣ Gottesman-Knill theorem: Any quantum circuit that only consists of CNOT, H, phase
and Pauli gates can be simulated efficiently on a classical computer. — Thus, the
quantum representation alone does not ensure yet an increase in efficiency but requires
a careful use of quantum correlations.
➣ One of the crucial differences between classical and quantum circuits is that, in the
quantum case, the COPY operation is not possible (no-cloning theorem).
177
➣ Nielsen and Chuang showed that quantum computers cannot be universal gate arrays
that are simply to be programmed like a classical computer. Therefore, quantum com-
puters will not be the kind of all-purpose devices that classical computers are.
178
5. Quantum information and communication
5.1. Information & physics. Non-cloning theorem
Information is part of physics (Landauer):

➣ Although information is often considered as abstract quantity, it reaches us only through interaction
with the outside world and is processing by different devices, including the brain.
➣ Information is always encoded into a physical systems.
➣ Processed by using the dynamical laws of physics; they typically result in certain restrictions how
information can be transfered and manipulated (speed of transmission, capacity of channels, ...);
indeed, quantum laws of physics are fundamentally different from the classical laws.
➣ A striking difference between quantum and classical information storage is that we cannot clone an
‘unknown quantum state.
179
➣ Quantum mechanics is a more general concept than classical mechanics.

➣ QI provides much more general concept that allows information-processing protocols that have no
classical analogue; in this sense, Shannon’s classical theory of information is just a special case.
No-cloning theorem: Its impossible to produce two copies of an unknown quantum state
|ψi , that is (|ψi , |ψi), because of the linearity of quantum mechanics.
Suppose we have |ψi = α |0i + β |1i and a unitary (cloning) operator U : U |ψ ′ i = |ψ ′ i |ψ ′ i.

Then, we have:
U |0i = |00i , U |1i = |11i
giving rise to:
U |ψi = α |00i + β |11i
On the other hand, we also find:
U |ψi = |ψi |ψi = α2 |00i + αβ |01i = + βα |10i + β 2 |11i
the same still hold if we use anchillary systems.
Of course, it is possible to make imperfect copies. How can one quantify this imperfection ?
How close can the copies come to original copies to be cloned ?
180
5.1. Information & physics. Non-cloning theorem
No-cloning is a powerful concept:
➣ In QM we can have only a limited knowledge about an unknown state of a system.

Otherwise, we could produce an unlimited number of copies and make experiments on
them. In classical physics, measurements do not destroy the state of the system; they
are noninvasive.
➣ Supports secure transmission of information (quantum cryptography); it enables one
to transmit information with the “security of nature’s laws”.
➣ Prevents instantaneous communication via quantum entanglement.
➣ Does not allow to use classical error correction techniques
➣ If we choose a certain basis {|φia }, we can always design a transformation that clones
these basis states. But then, the operation acts as
UAB |ψiA |0iB ⇒ c1 |φ1 iA |φ1 iB + c2 |φ2 iA |φ2 iB
i.e. it copies only the individual components; this provide a tool to create strongly
entangled states.
181
5.2. Quantum cloning (quantum copier)

Although we are not able to copy quantum states exactly, one may ask how accurate can we
copy an arbitrary quantum state of a (given) system 1:
|φi1 = α |0i1 + β |1i1
in the computational basis. Our aim is to transfer this state as faithfully as possible to the
system 2, for which we also need a third system (3), called the anchilla. As usual, we have
|ai1 |bi2 |ci3 = |abci.
Let us consider the following transformation:

r
2 1
|0i1 |0i2 |0i3 ⇒ |000i − √ (|011i + |101i)
3 6
r
2 1
|1i1 |0i2 |0i3 ⇒ − |000i + √ (|010i + |100i)
3 6
This transformation maps orthogonal states upon orthogonal ones and can be realized by
unitary transformations; as seen from this map, we choose the systems 2 and 3 initially in
the state |0i2 |0i3 .
182
5.2. Quantum cloning (quantum copier)
The application of this transformation gives rise to:

r
2 α
|Ψi123 = (α |000i − β |111i) − √ (|011i + |101i)
3 6
β
+ √ (|010i + |100i) .
6
To understand, how well the transformation works, we need to analyze the reduced density
matrices
ρ1 = Tr23 (ρ) ρ2 = Tr13 (ρ) .
These traces can be written in the form

! !
1 1 0 2 αα∗ αβ ∗ 1 2
ρ1 = ρ2 = ρout = + = 1 + ρin ,
6 0 1 3 α∗ β ββ ∗ 6 3
and it turns out that they are equal for the subsystems 1 and 2. I.e. both systems 1 and 2
retain the same information about the original state.
183
The expectation value of the projector |φi hφ| is

5
hφ |ρout | φi = ,
6
independent of |φi. We have therefore obtained a procedure that retains the original state
with the probability of 83 %, and this holds for both subsystems 1 and 2. The expectation
value above between the input and output state is called the fidelity of the copying process.
It can be shown that this is the optimal value for a symmetric copying of a unknown state
Buzek-Hillary quantum copying machine (QCM).
184
5.3. Quantum cryptography
Figure 5.1.: Alice and Bob are try-

ing to communicate secretly
but there is an eavesdrop-
per called Eve who is at-
tempting to listen in on their
communications.
Quantum cryptography
➣ A process by which two parties, Alice and Bob, can communicate secretly.
➣ ‘No cloning’ is an important ingredient for quantum cryptography since it prevents an
eavesdropper from copying information.
➣ Main issue: to establish a secret key between Alice and Bob; i.e. a string of zeros and
ones that can be used to encode information.
➣ There have been several protocols suggested in the literature; many of them requiring
the entanglement of states.
185
Figure 5.2.: Alice can store the bit either

in the rectilinear basis or in
the diagonal basis.
BB84 quantum key exchange protocol
➣ Named after Bennett and Brassard (1984); it does not need entanglement.
➣ Alice uses one out of four nonorthogonal states to communicate a zero or a one to
Bob. Advantage of using nonorthogonal states is that an eavesdropper, Eve, cannot
discriminate between them perfectly. Neither can Bob, of course !
➣ For instance, Alice sends 0 or 1 in one of the states: |0i = 0, |1i = 1 or |+i = 0, |−i = 1
(randomly) in the computational or diagonal (Hadamard) basis, and Bob measures the
186
state in either basis which he chooses arbitrarely. Obviously, if Bob or Eves uses the
‘other’ bases, then they receive a 50:50 probability of getting the bit which was sent
originally.
➣ Alice sends an arbitrary string of x1 , x2 , ..., xn to Bob, choosing arbitrarely the basis
from above.
➣ Bob measures theses bit-states, also in any of these basis. Both make a list of the basis
which they used for sending/recording.
➣ Alice and Bob compare via ‘public channel’ the bases which they used for each xi and
discard all events if a different bases was choosen. For the remaining bits they therefore
know what was transfered — except if Eve was measuring and resending in between.
➣ For a few of the finally selected events, the also compare the value: An evesdropper
can be excluded if these events all ‘agree’; otherwise not. Only the remaining ‘bits’ can
be used as the ‘secret key’.
187
5.4. (Super-) dense coding
Entanglement
➣ A property of two or more quantum systems which exhibit correlations that cannot be
explained by classical physics.
➣ A key resource in quantum computation and quantum information theory.
➣ A pure state is generally entangled across two or more subsystems when it cannot be
expressed as a tensor product of states of these subsystems. Unfortunately, much more
complicated for ‘mixed states’.
|ψi 6= |ai ⊗ |bi = |ai |bi
➣ Entanglement can exist over large distances; its in fact independent of distance.
➣ Can be used to teleport a quantum state from Alice to Bob by only sending classical
bits.
➣ Sometimes results in intuitively ‘unexpected’ results (for example, collaps over large
distances).
188
➣ Raised a large deal of ‘philosophical discussions’.

➣ Mathematically, entanglement is closely related to the partial trace operation. The
physical motivation for this is that we wish or are enforced (because of complexity)
trace out from the overall state those degrees of freedom which we cannot handle
quantum mechanically (environment, other parts of an overall system, ...).
➣ Entanglement is a purely quantum phenomenon and none of the protocols we discuss
are possible classically.
➣ Typically, each communication protocols requires some classical communication and so
does not break the laws of relativity: That is, even if Alice and Bob are entangled,
Alice cannot communicate with Bob faster than the speed of light.
➣ If Alice and Bob share an entangled state, they can use it for dense coding, in which
Alice sends Bob just one qubit of an entangled pair and that delivers two bits of classical
information.
➣ Alice and Bob can also use an entangled state for teleportation, in which a qubit in
a unknown quantum state is teleported from Alice to Bob when Alice sends Bob two
classical bits.
189
Pure-state entanglement and Pauli operators:

Let us consider the four orthogonal entangled states
± 1 ± 1
Φ = √ (|00i ± |11i) , Ψ = √ (|01i ± |10i)
2 2
and the Pauli operators
σx ≡ X = |1i h0| + |0i h1|
σy ≡ Y = i |1i h0| − i |0i h1|
σz ≡ Z = |0i h0| − |1i h1|
Alice (or Bob) can apply one or more of the Pauli operators locally to change between any
of the Bell states

(σx ⊗ I) Φ± = Ψ±

(σx ⊗ I) Ψ± = Φ±

(σz ⊗ I) Φ± = Φ∓

(σz ⊗ I) Ψ± = Ψ∓
and similar for σy ∼ σx σz .
190
Dense coding
➣ Alice and Bob share the Bell state

+ 1
Φ = √ (|00i + |11i) .
2
➣ Alice also has two bits x and y of classical information which she likes to send to Bob.
➣ Alice and Bob have agreed in advance some unitary operations that Alice performs on
|Φ+ i in dependence of the values x and y; if x = 0, she is doing nothing, if x = 1, she
performs a swap operation σx on her qubit which transforms

(σx ⊗ I) Φ+ = Ψ+
➣ Similar for the second bit y; if y = 0, she is doing nothing, if y = 1, she performs a
phase shift σ3 on her qubit:

(σz ⊗ I) Φ+ = Φ−
191
➣ Depending on the values of x and y, Alice and Bob now share one of the four Bell
states, while the state that either Alice or Bob sees is a maximally mixed state. I.e.
Alice and Bob cannot deduce from measurements on their own systems which Bell state
they share.
➣ Alice can send Bob her qubit, in which case Bob has one of the four orthogonal Bell
states, which he can measure and can then deduce the values of x and y.
➣ ‘One qubit’ is enough to send two classical bits.
➣ Dense coding is a simple yet nontrivial example of how entanglement can be used in
quantum communication. By performing a communication that cannot be performed
classically (i.e. encoding two bits of classical information into one qubit), dense cod-
ing provides a convincing example that quantum information differs from any sort of
classical information.
192
5.5. Teleportation
5.5. Teleportation
Teleportation is a process by which Alice can send Bob one qubit in an unknown state |ψi
by sending Bob two classical bits if Alice and Bob initially share an entangled Bell state.
When classical bits are sent over a classical channel, it is possible for Alice to retain a copy.
However, the no-cloning theorem says that it is impossible for Alice to copy the unknown
state |ψi . When she sends |ψi to Bob, she retains no information about the state of |ψi
— it is simply ‘moved’ from Alice to Bob and, hence, the name: teleportation.
Teleportation protocol:
➣ Initially, Alice and Bob share an entangled Bell state

+ 1
Φ = √ (|00i + |11i) .
2
➣ Alice also has a qubit in an unknown state |ψi = α |0i + β |1i, and she wants to
teleport it to Bob. — Given that Alice does not know the state, she cannot measure it
to obtain all the information necessary to specify it.
193
➣ Initially, the state of all three qubits is

1
|ψA i Φ+
AB = √ (α |0A i + β |1A i) (|0A 0B i + |1A 1B i)
2
1 +
= ΦAA (α |0B i + β |1B i) + Φ−AA (α |0B i − β |1B i)
2
+ −
Ψ
AA (α |1B i + β |0B i) + ΨAA (α |1B i − β |0B i)
➣ Alice’s two qubits are now written in terms of the four Bell states, while Bob’s qubit
in all four cases ‘looks very similar to the original qubit’ of Alice before the process.
➣ Alice now measures her part of the system in the Bell basis. She randomly, obtains,
one of the Bell states and uses two bits to send Bob the result of the measurement.
➣ Bob now knows which of the four states from above he ‘got’ and can apply a unitary
operation to his system to obtain the original |ψi .
194
5.5. Teleportation
Figure 5.3.: An unknown quantum state

|ψi is teleported from Alice
to Bob. Initially, Alice has
the unknown state |ψi and
one half of an entangled pair
of photons.
Figure 5.4.: Bob’s operations afterwards.
195
Figure 5.5.: Entanglement swapping. Initially, entangled

pairs are shared between Alice and Bob, and be-
tween Bob and Charlie. There is no entanglement
between Alice and Charlie. However, Bob can
use his entanglement with Charlie to teleport his
entanglement with Alice to Charlie. Thus Alice
and Charlie become entangled even though they
have never directly communicated.
5.6. Entanglement swapping

Can systems that have never interacted become entangled ? The answer is, very surprisingly,
yes: and entanglement swapping is the method.
Entanglement swapping is an example of a tripartite communication protocol. If Alice and Bob share
entanglement, and Bob and Charlie share entanglement, entanglement swapping can be used to entangle
Alice and Charlie.
The purpose of entanglement swapping is to induce entanglement between systems that hitherto have shared
no entanglement. An entanglement resource is required for entanglement swapping to occur; indeed, the
nomenclature ‘entanglement swapping’ describes the transfer of entanglement from a priori entangled systems
to a priori separable systems.
196
5.6. Entanglement swapping
Swapping protocol:
−
➣ Alice and Bob share a Bell state such as Φ and Bob and Charlie share a Bell
AB
+
state such as ΦBC .

➣ Then, Bob can send his part of Φ+ BC to Alice by teleportation (this uses classical
communication).

➣ Finally, Alice and Charlie share the Bell state Φ− AB . The entanglement between Bob
and Charlie is destroyed in the teleportation process.
197
5.7. No instantaneous transfer of information
Remarks:
➤ No faster-than-light communication is possible. Of course, this would break the laws of relativity. In
the above protocols, classical bits were sent between Alice and Bob, preventing them from signaling
to one another faster than the speed of light.
➤ Overall, quantum mechanics is a local theory. Whatever Alice does, no faster-than-light communica-
tion is possible (strictly speaking, no instantaneous communication is possible — the speed of light
does not enter this argument in any way). There is no way of instantaneously influencing something
over there by acting over here.
➤ Typical quantum information-processing protocols involve entangled quantum systems, quantum mea-
surements on them, and–very importantly–classical communication. We emphasize that for protocols
such as teleportation and entanglement swapping, classical communication is absolutely crucial.
➤ But what is classical communication in the first place? — Classical communication is therefore a very
special type of communication, where we do not use the effects of superpositions.
➤ Its possible to present a more coherent view of teleportation where there is no division between
quantum and classical information and where everything is quantum mechanical—as it should be.
Suppose, that Alice shares with Bob a Bell state and that she, in addition, has an extra qubit in
an unknown state that needs to be teleported to Bob. Now, Alice makes a measurement in the Bell
basis on her two qubits. Suppose that this measurement is actually written into another (four-level)
quantum system. This four-level quantum system is then sent to Bob. Conditionally on the state
198
5.7. No instantaneous transfer of information
of the four-level system, Bob performs one (or none) of the Pauli operations. And this results in
teleportation. There are no measurements involved here, only conditional unitary operations (which
themselves are unitary by definition).
➤ We can consider classical information theory as a subset of quantum information theory where we are
restricted to orthogonal states.
199

Script QI

Uploaded by

Copyright:

Available Formats

Script QI

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Script QI

Uploaded by

Copyright:

Available Formats

Quantum Computations

(lecture notes and additional material)

1. Introduction and motivation 13

2. A short account on classical information and computations 39

3. Basic quantum mechanics and Dirac notation 65

3.2.f. Outer product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.5.d. Postulate IV (Composite systems and entanglement): . . . . . . . . . . . . . 106

3.8.d. Quantum mechancical ‘anticorrelations’ in the EPR experiment . . . . . . . . 152

4. Models for quantum computations 157

5. Quantum information and communication 179

5.3. Quantum cryptography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

➣ Lecture: Thuesday and Thursday (14:15 - 16:00)

1.1. Need and promises of quantum computations

A computer is always a physical device that helps us process information by executing

Computers allow an efficient storage, exchange and processing of information. An

Figure 1.1.: Classical (electronic) computers will reach fundamental limits

R. P. Feynman, Int. J. Theoret. Phys., 21 (1982) 467:

➣ Deutsch (1985) or Deutsch-Jozsa (1992): Decision about simple ‘two-valued’ functions.

➣ Coppersmith (1994): Quantum Fourier Transformtion (QFT).

Web link (Quantum Computers):

1.2. Qubits and quantum information

Classical versus quantum bits (qubits):

➣ Classical bit just takes values 0 or 1.

➣ A qubit system can be in one out of an infinite number of significant states:

|ψi = α |0i + β |1i

➣ A qubit is either in a pure state (vector) or a mixed state (density matrix).

Figure 1.3.: Bloch sphere representation of the qubit. The pure

Figure 1.4.: From: www.labs.nec.co.jp

Figure 1.5.: Quantum

➣ Classical: messages are stored and carried by sequences of bits.

➣ Diffuculties arise from measurements in quantum mechanics; state reduction is never

Quantum information processing (3 major ingredients):

1.3. Different realization of qubits

Figure 1.6.: Experiments with

1.4. Young’s double slit experiment

Figure 1.8.: Double-slit experiment with electrons.

Figure 1.9.: The Mach-Zehnder inter-

1.5. Mach-Zehnder interferometer

Set-up and properties:

1.6. Quantum simulators

Figure 1.10.: From DARPA QuIST Poster Session, Brian T.

➣ Various parametrizations of the quantum states and quantum transformations.

1.7. Summary & reminder

|ψi = α |0i + β |1i

➣ Quantum properties such as superposition, entanglement, uncertainty and interference

Figure 1.11.: New paradigm for computing.

➣ In quantum systems, an exponential increase in parallelism requires only a linear in-

Web link (Introduction to Quantum Computing):

2.1. Computational complexity and the Church-Turing thesis

Church-Turing Thesis: A computing problem can be solved on an computer if and only if

Computable is of what can be computed by a Turing machine.

Figure 2.1.: Turing machine.

Figure 2.2.: NOT gate.

2.2. Classical computations

2.2.a. Classical logic operations

Three basic logical functions:

Figure 2.4.: deMorgan’s rules in terms

XOR : (a, b) ⇒ a ⊕ b = a + b (mod2)

Binary addition can be represented as: