
Introduction to quantum information processing
[PowerPoint,
PDF]

by Richard Cleve:
These lectures provide an introduction to the basic quantum information
framework in terms of qubits and the elementary operations that can be
performed on them. Protocols for superdense coding and teleportation are
examined as examples of constructs within this framework. Additional topics
are: the nocloning theorem, simulations of classical computers by quantum
computers (and vice versa, with exponential overhead), and density matrices
and admissible operations (just very briefly discussed).

Quantum algorithms
[PowerPoint,
PDF]

by Peter Høyer:
In this introductionary talk to quantum algorithms, we introduce the socalled
black box model. We discuss how to compare the complexity of quantum
algorithms to that of classical algorithms. We give and analyze a set of
simple quantum algorithms. We then give an efficient quantum algorithm for a
grouptheoretical problem called Simon's problem, ideas from which lead to an
efficient quantum algorithm for Integer Factorization. We finally show how to
implement the quantum fourier transform efficiently.

Applications of quantum information theory
[PDF,
additional material]

by Ashwin Nayak:
Quantum information theory is a quantitative study of resources required to
store or transmit information, in the form of quantum (and classical)
states. Its influence extends to many aspects of quantum computing, and even
beyond. These lectures are aimed at introducing basic concepts from quantum
information theory on a rigorous mathematical footing, in tandem with
applications. We will follow the outline below:
1. Beginning with the notion of mixed states we will show the impossibility of
superluminal signalling using only shared entanglement and without further
communication.
2. We will then study purifications of mixed states, and _local transitions_
between them. Using this, we will show the impossiblity of ideal bit
commitment.
3. Next, we will encounter the most general form of physically allowed
measurement: POVM. Using the formalism of density matrices and POVMs, we will
establish a bound on the length of classical messages that can be encoded into
quantum states of fixed dimension.
4. This will naturally lead us to the notion of distinguishability. We will
learn about trace distance and fidelity. Using these concepts, we can, for
example, analyze a quantum coinflipping protocol.
5. Finally, we will learn about von Neumann entropy and quantum mutual
information. This will enable us to state the Holevo bound, and reduce its
proof to properties of von Neumann entropy. We will conclude with a sketch of
a lower bound for the communication complexity of Set Disjointness.

Optical implementations of quantum information
processing
[PDF (6 MB)]

by Gregor Weihs:
Among the potential implementations of quantum computing optical techniques
have a somewhat special status. Quantum optics was, to a large degree, the
field out of which quantum information developed, spearheaded by quantum
commmunication techniques such as quantum cryptography and teleportation.
Since it was clear early on that two qubit gates are needed for universal
computation optics seemed to have been ruled out as a way to a quantum
computer because the interactions between photons, even in the most advanced
materials are orders of magnitude too weak to inplement, for example, a
controlnot gate. However, when Knill, Laflamme and Milburn tried to prove
that an optical quantum computer wasn't viable they failed and at the same
time showed that teleportation and postselection by measurement can replace
stronger nonlinearities.
I will start my lecture by making the connection from abstract quantum
computing concepts to a physical implementation. I will introduce the
necessary terminology and talk about sources of error that occur in any
realworld experiment. Most of the time will then be spent on specializing
these concepts to the optical case. In particular we will learn how to encode
qubits into photons and how to manipulate the photons to perform certain gate
operations. I will discuss experiments that demonstrate various parts of
optical quantum information processing, focussing on linear optical twoqubit
gates and advanced quantum communication protocols such as entanglement
purification.

Grover's algorithm
[PowerPoint,
PDF]

by Peter Høyer:
One of the most famous quantum algorithms is Grover's search algorithm that
achieves a quadratic speedup over any classical algorithm. A simple way of
understanding Grover's algorithm is in terms of amplitude amplification, which
is a technique for manipulating the amplitudes of quantum states. It shows
that the benefits of Grover's algorithm carry over to arbitrary search
processes and settings, and that a quadratic speedup can be achieved for many
problems.

Lower bounds for quantum algorithms
[PowerPoint,
PDF]

by Andris Ambainis:
I will describe the two main methods for proving lower bounds on quantum
algorithms in the query (black box) model: adversary method and polynomials
method, together with their applications to various problems.

Nonlocality and quantum communication complexity
[PowerPoint]

by Alain Tapp:
According to quantum mechanics, distant experiments made on entangled quantum
systems can exhibit correlations stronger than anything achievable
classically. In a classical world, those correlations could only be obtained
through communication. Therefore we conclude that quantum mechanics is a
nonlocal theory. In my talk, I will study this phenomenon by describing
games (or thought experiments) where only quantum players can win
consistently. I will also present useful distributed computation tasks where
entangled players can obtain the desired outcome using much less communication
that would be necessary for classical players. Finally I will investigate the
consequences of having stronger correlations than those predicted by quantum
mechanics.

Quantum proofs
[PDF]

by John Watrous:
This talk will introduce the notion of quantum proofs, which are quantum
states that certify the validity of a given statement to someone with a
polynomialtime bounded quantum computer. This notion gives rise to a quantum
complexity class, known as QMA, that represents a quantum computational
analogue to the wellknown complexity class NP. A problem known as the Group
NonMembership problem that illustrates how quantum information can be
exploited in this context will be discussed.

Practical quantum cryptography and communication
[PDF]

by Wolfgang Tittel:
Quantum cryptography has seen tremendous progress during the last years and is
now on the verge of becoming an industrial application. After a general
introduction into quantum cryptography, I will present several implementations
and address current limits in terms of bitrate and distance. I will then
discuss recent developments, i.e. more efficient protocols, quantum relays and
quantum repeater, that promise to overcome these problems.

Distinguishing quantum states and operations
[PDF]

by John Watrous:
This talk will survey various results that are centered around the following
basic problem: to distinguish the elements of some known collection of quantum
states or quantum operations. Many variations on this sort of problem have
been considered, such as the case where multiple parties must perform a
distributed variant of the problem without exchanging quantum information.
The talk will include a discussion of some very basic aspects of these
problems as well as some of the interesting variants.

Implementations of quantum information processing in ion traps
[PowerPoint 1st lecture (8 MB),
PowerPoint 2nd lecture (14 MB)]

by Paul Haljan:
These lectures will introduce the concepts and practicalities of quantum
information processing in ion traps. In particular, I will cover how to
implement the basic requirements for quantum computing with ion qubits,
including measurement and quantum logic gates. In the past few years,
prototype experiments have tested many of these techniques at a basic level
and have demonstrated, to some degree, several of the wellknow quantum
algorithms on a small number of ions. The technical challenges for iontrap
quantum computing are shifting towards the development of robust quantum
operations, and the development of microfabricated devices that can support
large arrays of ions on a single chip. With these directions in mind, I will
briefly outline some of the experimental difficulties that iontrappers are
currently facing today and where the field is heading for solutions.

Graphs in quantum information theory
[PDF]

by David Feder:
I will discuss some of the relationships between quantum information and graph
theory that have been developed over the past few years. There are two main
points of contact between these seemingly disparate fields. One of these is to
consider a graph as a collection of vertices in either real or configuration
space, connected by edges. A major effort in this case is to construct quantum
algorithms that can efficiently determine properties of the graph, and I will
describe in detail one such approach which is based on quantum walks. The
other point of contact is to consider each vertex as a qudit, with edges
representing an entangling operation. In this picture, each graph is uniquely
associated with a highly entangled quantum state known as a graph state or
stabilizer state. I will discuss the relationship between stabilizers and the
theory of quantum error correction. I will also show that certain graph
states, known as cluster states, are a resource for universal quantum
computation based only on measurements.

Quantum Visualization
[QViz website]
 by Maria Lantin
at the Banff New Media Institute, The Banff Centre