Sixth Canadian Summer School on Quantum Information Processing

University of Calgary, Canada, 7-11 August 2006

home page  |  goals  |  schedule  |  lecturers  |  registration  |  accommodation  |  travel  |  all schools

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 no-cloning 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 so-called 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 group-theoretical 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 coin-flipping 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 control-not 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 post-selection 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 real-world 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 two-qubit 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 speed-up 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 speed-up 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 non-local 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 polynomial-time bounded quantum computer. This notion gives rise to a quantum complexity class, known as QMA, that represents a quantum computational analogue to the well-known complexity class NP. A problem known as the Group Non-Membership 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 bit-rate 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 well-know quantum algorithms on a small number of ions. The technical challenges for ion-trap 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 ion-trappers 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