Summer School in Quantum Information Processing

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