Summer School in Quantum Information Processing
May 14 - 18, 2001
ABSTRACTS
Audio
of the Lectures
Charles Bennett (IBM)
Degrees of Knowledge of a Quantum State
It is possible to "know" or "possess" a quantum state in infinitely
many physically inequivalent ways, ranging from complete classical knowledge,
through possession of of a single specimen of the state, to weaker and
less compactly embodiable forms such as the ability to simulate the
outcome of a single measurement on the state. We study the transformations
of these degrees of knowledge, including "remote state preparation",
in which a sender with complete classical knowledge of a state enables
a receiver to create a single specimen of it in his lab.
Gilles Brassard ( Université de Montréal )
Quantum Cryptography
For ages, mathematicians have searched for a system that would allow
two people to exchange messages in absolute secrecy. Around the middle
of last century, Shannon proved that this dream is possible if and only
if the legitimate participants share a random secret key as long as
the message they wish to transmit. But Shannon's theorem did not take
account of the quantum world in which we live. When information is appropriately
encoded as quantum states, any attempt from an eavesdropper to access
it yields partial information at best and entails a probability of spoiling
it irreversibly. This unavoidable disturbance can be detected by the
legitimate users. This phenomenon can be exploited to implement a cryptographic
system that is unconditionally secure even against an eavesdropper with
unlimited computing power and technology, with no need for a long shared
secret key. This can be accomplished by the use of very faint pulses
of polarized light that consist on the average of less than one photon.
Alternatively, entanglement can be harnessed to the same cause. Sophisticated
prototypes have been built in several countries, including England,
Switzerland and the United States. In particular, the Swiss prototype
work over 23 kilometres of ordinary optical fibre deployed beneath Lake
Geneva. Another prototype, built at the Los Alamos National Laboratory,
implements quantum cryptography on a free line-of-sight optical path,
without any need for a waveguide. In the first lecture, I shall describe
the basics of quantum cryptography and discuss the (in)security of some
current prototypes. No prior knowledge of classical cryptography will
be assumed.
The second lecture will concentrate on more theoretical issues. What
advantages can there be to entanglement-based quantum cryptography?
How can entanglement purification and quantum error correcting codes
come to the rescue? But the main topic of the second lecture will concern
quantum cryptography beyond the transmission of confidential information.
Are there other tasks of a cryptographic nature that could benefit from
quantum mechanics? For many years, the chief candidate was bit commitment,
a primitive that would allow one person to commit to the value of a
bit in a way that this value remains concealed until that person wishes
to reveal it, at which time it is not possible to reveal a bit different
from what had been sealed in the commitment. In particular, this primitive
could be used to implement perfect zero-knowledge protocols and protect
private information while it is being used to reach public decisions.
It is obvious that unconditionally secure bit commitment cannot exist
according to the laws of classical physics. Yet, hopes were high that
a quantum version of this powerful primitive was possible, but they
were striken down five years ago. Despite this setback, quantum mechanics
does provide powerful tools for cryptography. For example, it allows
for a coin tossing protocol in which neither party can make the coin
fall on their chosen side with a probability better than 75%. Also,
it allows for the computationally-secure distributed computation of
functions on secret inputs under the only assumption that (quantum)
one-way functions exist. (This assumption is believed to be too weak
in a classical setting.) I shall discuss these results as well as other
more recent work on quantum authentication, the secret transmission
of quantum information, quantum digital signatures, etc.
We end with a speculation that the foundations of quantum mechanics
can be laid on the understanding of which information processing tasks
are possible (such as unconditionally secure confidential communication)
and which are not (such as unconditionally secure bit commitment). Could
it be that if God had wanted to provide His creatures with confidential
communication but not with the ability to compute on secret data, then
He had no choice but to invent quantum mechanics? Wouldn't that be a
nicer foundation for quantum mechanics than the current cumbersome axioms?
Richard Cleve (Calgary)
Bell's theorem and Communication Complexity
A distributed information processing task is one where two or more
physically separated parties each receive some input data and they are
required to compute some quantities based on this data. A simple two-party
example is where each party receives a binary string and their goal
is to determine whether or not the strings are identical. It is clear
that this particular task cannot be accomplished without some communication
occuring between the parties. In comunication complexity, the amount
of communication required to perform distributed information processing
tasks is quantified.
Bells Theorem concerns distributed information processing tasks that,
in terms of classical information, require communication, but which
can be performed without any communication in the presence of quantum
entanglement.
We explain Bell's Theorem and address the more general question of
when quantum information can be used to reduce the communication complexity
of distributed information processing tasks.
Peter Høyer (Calgary)
Introduction to Quantum Algorithms
This talk introduces to algorithms that are designed to run on quantum
computers. We refer to such algorithms as quantum algorithms. Most known
quantum algorithms share 2 characteristics: they are developed in the
so-called black box model, and they are based on amplitude amplification
and Fourier transforms. The black box model, which I introduce, will
be discussed in detail by Ronald de Wolf later this week. I discuss
and analyse some of the simplest quantum algorithms, most of which will
be extended and generalized by Michele Mosca and Alain Tapp on Tuesday
morning. No familiarity with quantum computation other than having actively
attended Michael Nielsen's lectures is assumed.
Emanuel Knill (Los Alamos)
Fault-tolerant Quantum Error Correction
Scalable quantum computation requires robustness against errors. Robustness
can be realized by using quantum error correction. I will give an elementary
introduction to quantum error correction based on the notions of subsystems
and error detection. The assumptions for scalable quantum computation
will be stated and techniques for establishing threshold accuracies
demonstrated.
1st
lecture slides, and
2nd
lecture slides ,
Please do not to print them! If you do, you'll get 40+ pages, most of
which are virtually the same.
Raymond Laflamme (Los Alamos)
NMR Quantum Information Processing (pdf-slides)
Nuclear magnetic resonance (NMR) provides an experimental setting
to explore physical implementations of quantum information processing
(QIP). I will introduce the basic background for understanding applications
of NMR to QIP and explain their current successes, limitations and potential.
NMR spectroscopy is well known for its wealth of diverse coherent manipulations
of spin dynamics. Ideas and instrumentation from liquid state NMR spectroscopy
have been used to experiment with QIP. This approach has carried the
field to a complexity of about 10 qubits, a small number for quantum
computation but large enough for observing and better understanding
the complexity of the quantum world. While liquid state NMR is the only
present-day technology about to reach this number of qubits, further
increases in complexity will require new methods. I will sketch one
direction leading towards a scalable quantum computer using spin 1/2
particles. The next step in this program is a solid state NMR-based
QIP capable of reaching 10-30 qubits.
Physical Implementations of Quantum
Information Processors (pdf slides)
Quantum Information Processing (QIP) has been an active area of research
bringing together many disciplines from the engineering to pure sciences.
In my talk I will describe how some of the ideas of quantum information
processing can be implemented using a variety of physical devices. Although
today's devices are a small step towards what is needed for useful (QIP)
they show that at least small quantum systems can reasonable controlled.
I will stress the importance for better quantum control, a necessary
requirement for scalability. I will also put forward the idea of common
benchmarking methods to compare the achievements of the various physical
devices. I will conclude with speculations of where the field might
go in the future.
Daniel Lidar (Toronto)
Ion Trap and Quantum Dot Implementations
Certain electronic states in a trapped ion can be used as a qubit,
and qubits can be coupled by collective vibrations of all ions. Ion
traps are currently the most advanced experimentally implemented quantum
computer systems, after NMR. Logic gates and decoherence avoidance has
been demonstrated using 2 ions, and entanglement has been achieved involving
4 ions. The first half of this lecture will be a theoretical introduction
to the Cirac-Zoller scheme for quantum computing using trapped ions,
and a survey of the latest experiments. The second half will be devoted
to a theoretical introduction to the quantum dots quantum computer proposal.
The spin states of an excess electron trapped in a quantum dot can serve
as a qubit, while qubits can be coupled through an exchange interaction
between neighboring dots. The quantum dots implementation is considered
to be one of the more promising scalable solid-state proposals for a
quantum computer.
Michele Mosca (Waterloo)
Quantum Algorithms (click
here for talk)
This talk will describe the most powerful known quantum algorithms.
I will use the approach in [CEMM] http://xxx.lanl.gov/abs/quant-ph/9708016
, much of which is based on the approach of Kitaev in http://xxx.lanl.gov/abs/quant-ph/9511026
.
The task of approximating a phase rotation can be formulated as a computational
problem; I will show how the quantum Fourier transform can be used to
perform this approximation. I will show how such phase rotations can
be produced as a result of an eigenvalue "kicked back" by a computation
involving an auxiliary register. Lastly I will show how efficient eigenvalue
estimation leads to efficient quantum factorization; this approach complements
the original approach of Shor, and when reformulated as done in CEMM
produces the same quantum network.
I will summarize the application of these methods to the Hidden Subgroup
Problem, and the Hidden Affine Function problem.
Michael Nielsen (Queensland)
Introduction to quantum mechanics and quantum information science
In these lectures I introduce the basic notions of quantum mechanics,
illustrated through simple examples drawn from quantum computation and
quantum information. The only prerequisite is a grasp of basic linear
algebra. No previous acquantaince with quantum mechanics is necessary.
1st Lecture slides in pdf format
or Postscript
2nd Lecture slides in pdf format or
Postscript
3rd Lecture slides in pdf format or
Postscript
Peter Shor (AT&T)
Quantum Computing
Quantum computers are hypothetical devices which use the principles
of quantum mechanics to perform computations. For some difficult computational
problems, including the cryptographically important problems of prime
factorization and finding discrete logarithms, the best algorithms known
for classical computers are exponentially slower than the algorithms
known for quantim computers. Although they have not yet been built,
quantum computers do not appear to violate any fundamental principles
of physics. I will explain how quantum mechanics provides this extra
computational power, and outline the factoring algorithm.
Capacities of Quantum Channels
The classical theorem of Shannon from 1948 gives a simple formula for
how much information can be sent through a communication channel. When
we try to extend this formula to the quantum regime, we find that there
is no longer a unique way to define channel capacity. We can define
one capacity of a channel for transmitting classical information, and
another for transmitting quantum information. To further complicate
the situation, these quantum channel capacities will sometimes be changed
by giving the sender and receiver additional capabilities which do not
change the classical capacity (e.g., shared entanglement or a back channel
from the receiver to the sender). However, there do seem to be a small
number of interesting quantum channel capacities, and many of them seem
to be quantifiable by analogs of Shannon's formula. We survey these
capacities, and give proven and conjectured analogs of Shannon's formula
for many of them.
Newsletter article
Aephraim Steinberg (Toronto)
Experiments with Entangled Photons
Much of the power of quantum mechanical systems for handling information
stems from the unusual sorts of correlations, or "entanglement," which
may exist between quantum particles. Entangled photons have long been
a topic of intense experimental investigation. At first, this was in
order to address foundational questions about locality and determinism,
through the famous Einstein-Podolsky-Rosen "paradox" and Bell's inequalities.
More recently, these states have been applied in a variety of quantum
information schemes. At the moment, photons appear to be ideal carriers
of information, for use in cryptography and teleportation, but have
certain weaknesses which make them less attractive for use in quantum
computers. Nevertheless, entangled photon states are likely to be important
in any future quantum- information technology. I will try to introduce
the basic quantum-mechanical concepts which govern the behaviour of
photons, by describing a number of important and surprising experiments
in the field. We will see some of the practical issues which arise in
this physical implementation of quantum information, and touch upon
the prospects for the direct application of photons in quantum computation.
Alain Tapp (Waterloo)
Quantum Searching and Generalizations
In 1996 Lov Grover gave the foundation of an exciting new algorithm
for quantum computers. One of the most important classes of problems
in computer science is the class NP. Roughly speaking it addresses all
the problems that can be stated the following way. We have a function
F:{0,1}^n -> {0,1} and an efficient classical algorithm that computes
it. The problem is to find x such that F(x)=1. Sometimes there is an
efficient solution to this problem but in general it is very hard.There
are literally hundreds of problems that can be put in this hard class,
from areas including optimization, scheduling, cryptography, theorem
proving, combinatorics, etc. The most efficient algorithms that can
solve this problem have a running time proportional to the number of
possible inputs x which is in O(2^n). Grover sketched an algorithm that
solves the general problem in a time proportional to the square root
of the number of inputs x, which is in O(2^(n/2)). In this talk I will
discuss the generalization of Grover's algorithm discussed by Boyer,
Brassard, Hoyer and Tapp. I will also present the algorithm proposed
by Brassard, Hoyer, Mosca and Tapp that probabilistically counts the
number of solution.
Barbara Terhal (IBM)
Simulating
Physical Systems of a Quantum Computer
One of the greatest and earliest mentioned promises of a quantum computer
lies in its ability to simulate physical systems. In order to realize
this promise, one must analyze how the structure and the dynamics of
physical quantum systems can be mapped onto the architecture of a quantum
computer.
I will treat various types of quantum systems for which it has been
found that they can be efficiently simulated on a quantum computer.
These are tensorproduct systems with local degrees of freedom, some
continuous conjugate variable systems, some 'unphysical' Hamiltonians
and fermionic quantum systems.
References:
- M.A. Nielsen and I.L. Chuang, "Quantum Computation and Quantum
Information," Cambridge University Press (2000).
Simulating systems with small local degrees of freedom:
- R.P. Feynman, Simulating Physics with Computers, Int. J. Theor.
Phys. 21 (1982), 467-488.
- S. Lloyd, Universal Quantum Simulators, Science 273 (1996),
1073.
Simulating the Schrödinger equation for systems with conjugate variables:
- C. Zalka, Simulating quantum systems on a quantum computer, Proc.
R. Soc. London A 454 (1998), 313-322.
- S. Wiesner, Simulations of Many-Body Quantum Systems by a Quantum
Computer, quant-ph/9603028.
Simulating fermionic quantum systems:
- D.S. Abrams and S. Lloyd, Simulation of Many-Body Fermi Systems
on a Universal Quantum Computer, Phys. Rev. Lett. 79
(1997), 2586-2589.
- S. Bravyi and A. Kitaev, Fermionic qantum computation, quant-ph/0003137.
- G. Ortiz, J.E. Gubernatis, E. Knill and R. Laflamme, Quantum Algorithms
for Fermionic Simulations, quant-ph/0012334.
Further reading:
Simulating noisy systems, thermal equilibration and calculating correlations
functions:
- B.M. Terhal and D.P. DiVincenzo, The problem of equilibriation and
the computation of correlation functions on a quantum computer, Phys.
Rev. A. 61 (2000), 022301/1-22.
Umesh Vazirani (Berkeley)
How Powerful is Adiabatic Quantum Computation?
Recently, Farhi et al. have proposed a novel paradigm for the design
of quantum algorithms - via quantum adiabatic evolution. We analyze
the computational power and limitations of such adiabatic quantum algorithms.
Joint work with Wim van Dam and Mike Mosca.
John Watrous (Calgary)
Quantum Interactive Proof Systems
Interactive proof systems were first introduced in 1985, both as a
natural extension of the class NP and as a model for various cryptographic
situations. An interactive proof system consists of two interacting
parties: a computationally unbounded prover and a polynomial-time verifier.
The prover attempts to prove to the verifier that a given input string
satisfies some property, while the verifier tries to determine the validity
of this proof.
Quantum interactive proof systems are interactive proof systems in
which the prover and verifier may perform quantum computations and exchange
quantum messages. In this talk I will survey some of the known facts
about quantum interactive proof systems, and discuss some of the tools
that are helpful for analyzing their properties.
Ronald de Wolf (CWI and University of Amsterdam)
Quantum
Lower Bounds
Few quantum algorithms are known to date, and virtually all of them
make use of "queries" in some form or other. In the query or "black-box"
model of computation, an N-bit input x is given as a black-box that
returns the i-th bit of the input x when queried on i. The aim is then
to compute some function f(x) of the input, using as few queries as
possible. A quantum computer has the advantage that it can query many
i-s in superposition. The quantum algorithms of Deutsch and Jozsa, Simon,
Grover, and Shor's period-finding can all be cast in this model and
provably require far fewer queries than their classical counterparts.
It thus appears that the notion of query complexity captures a significant
part of the power of quantum computing, and it makes sense to look at
the limits of quantum computers in this model. In the last 3 years,
significant progress has been made with respect to lower bounds on query
complexity of quantum algorithms (in contrast to proving lower bounds
on circuit complexity of quantum algorithms, which immediately runs
into P vs NP type problems). In this talk we will survey the main lower
bounds on quantum query complexity that have been obtained. We focus
on two general methods: (1) the "polynomial method" of Beals, Buhrman,
Cleve, Mosca, de Wolf, which in particular implies that exponential
quantum-classical separations only occur for "promise problems", and
(2) the "quantum adversary method" of Ambainis.
