TUTORIAL - The Computer Science Perspective on Quantum Information Processing and Communication

Saturday, March 25 by Philippe Jorrand

8:30 to 13:00, Location: EI 3A

About Quantum Information Processing and Communication

Research in quantum information processing and communication was born some twenty years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication based upon the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory, algorithmics and, more recently, in abstract computational models, programming languages and semantics frameworks, have shown that this transplantation of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science.

About the Tutorial

The aim of this tutorial is to give a survey of the motivations, principles, main results and long term perspectives of the currently very active research in quantum information processing and communication, from a computer science point of view. No prior knowledge in quantum mechanics is required to follow this tutorial. There will be four lectures of 45' each:
  1. Basic principles for quantum computation and communication: quantum resources and operations, classically controlled quantum computation, state of the art for the physical implementation of quantum computers;
  2. Communication, the quantum way: quantum key distribution, quantum state teleportation;
  3. Computing with quantum resources: Grover's and Shor's quantum algorithms, generalizations and other principles in quantum algorithmics;
  4. Foundational structures for quantum computation: measurement-based quantum computation, abstract quantum machines, quantum lambda calculi, quantum process calculi, quantum type systems, issues in semantics, open problems.

Who Should Attend

Computer scientists from universities and research centers, from academia and industry, with an interest in long term orientations, perspectives, challenging issues and open problems in information processing and communication, especially in areas like programming, semantics, algorithms and other foundational issues in computer science. A reasonable culture in computer science will be assumed from the part of the audience, but no strong expertise is required in any specific area of computer science. It must be stressed that absolutely no prior knowledge in quantum mechanics will be assumed from the audience. Basic notions in linear algebra at the undergraduate level (vectors and matrix products) will be helpful at some points in the lectures.

Instructor

Philippe Jorrand
Quantum Computation Group
Leibniz Laboratory
46 avenue Felix Viallet
38000 Grenoble France

Phone: +33 4 76 57 46 47
Fax: +33 4 76 57 46 02
E-mail: Philippe.Jorrand@imag.fr

Dr. Philippe Jorrand currently is Director of Research at CNRS (Centre National de la Recherche Scientifique)

Research experience:

Schedule

08:30 - 10:30: Lectures 1 and 2, and discussion
10:30 - 11:00: Coffee break
11:00 - 13:00: Lectures 3 and 4, and discussion

Detailed Presentation

Introduction

Information is physical: the laws which govern its encoding, processing and communication are bound by those of its unavoidably physical incarnation. In today's informatics, information obeys the laws of Newton's and Maxwell's classical physics: this assertion holds all the way from commercial computers down to (up to?) their most abstracted models, e.g. Turing machines and lambda-calculus. Today's computation is classical. Research in quantum information processing and communication was born some twenty years ago, as a child of two major scientific achievements of the 20th century, namely quantum physics and information sciences. The driving force of this interdisciplinary research is that of looking for the consequences of having information encoding, computation and communication based upon the laws of quantum physics, i.e. the ultimate knowledge that we have, today, of the foreign world of elementary particles, as described by quantum mechanics. Breakthroughs in cryptography, communications, information theory, algorithmics and, more recently, in abstract computational models, programming languages and semantics frameworks, have shown that this transplantation of information from classical to quantum has far reaching consequences, both quantitative and qualitative, and opens new avenues for research within the foundations of computer science. The aim of this tutorial is to give a survey of the motivations, principles, main results and long term perspectives of the currently very active research in quantum information processing and communication, from a computer science point of view. No prior knowledge in quantum mechanics is required to follow this tutorial. There will be four lectures of 45' each.

Lecture 1: Basic Principles for Quantum Computation and Communication

The basic ingredients and principles of quantum information and quantum computation will be introduced in the first lecture, and their fundamental differences with their classical counterparts will be stressed: quantum bits (qubits), deterministic unitary operations on one and two qubits, probabilistic measurement on one and two qubits, entangled quantum states, no-cloning theorem, combinations of these operations and properties into computations on quantum registers of arbitrary sizes, quantum massive parallelism. The simplest architecture for a quantum computer will be briefly explained, which implements the principles of classically controlled quantum computation, and a state of the art will be sketched about the current status, perspectives and difficulties of physically implementing the quantum side of such a computer.

Lecture 2: Communication, the Quantum Way

The second lecture will be devoted to quantum breakthroughs in the domain of communication, which show evidence that relying upon quantum resources allows qualitative performances beyond the reach of classical information. Two major results will be presented and explained: quantum key distribution, also called quantum cryptography, and quantum state teleportation. Rather than relying upon the difficulty of breaking a code, the quantum cryptographic protocol of Bennett and Brassard (1984) takes advantage of the physical property that quantum measurement causes a probabilistic evolution of the observed quantum state. Undesirable observations thus become detectable, and the secrecy of cryptographic key distribution can be guaranteed. With the quantum state teleportation protocol of Bennett et al (1993), a piece of quantum data initially located at point A can be relocated at a distant point B, without any quantum object carrying that data being moved along a trajectory from A to B. Both of these theoretical results have been experimentally implemented since their initial publications, and quantum cryptography starts being available within commercial products.

Lecture 3: Computing with Quantum Resources

The third lecture will be mostly devoted to two major results in quantum algorithmics, which show evidence that using quantum resources for computing allows quantitative performances unfeasable by classical means. The quantum algorithm of Grover (1996), which achieves a quadratic speedup on a broad class of problems will be presented first. Using a quantum algorithmic technique of amplitude amplification, this algorithm needs exactly sqrt(n) queries to a boolean oracle f for retrieving an element satisfying f from an unordered data base of size n, whereas classical computing requires of the order of n queries to f in a similar situation. Then, the quantum algorithm of Shor (1994) will presented in some detail. It solves a class of problems (e.g. finding factors of very large integers, which is an instance of the hidden subgroup problem) exponentially faster than by any known classical algorithm. It will be explained by developing the example of integer factorization, for which no polynomial classical algorithm is known. With an appropriate reduction of factorization to order finding, Shor has used a polynomial quantum Fourier transform to find the prime factors of an integer with bounded probability in polynomial time. In addition to amplitude amplification and order finding, other, more recent, quantum algorithmic techniques will also be sketched.

Lecture 4: Foundational Structures for Quantum Computation

Much of the quantum informatics research in the last ten to fifteen years has focused on a quest for new quantum algorithms and new kinds of quantum protocols, and great advances have been made, as described in the first three lectures. It is only in the last 5 years or so, that the exploration of other questions which are fundamental to the whole quantum informatics endeavor, has started. They address foundational structures which have long been recognized as essential to the understanding of classical computing but, strangely enough, were left aside until recently in the quantum setting. The current state of the art on these issues will be presented in the fourth lecture. Among them are the minimal resources required for universality, with an emphasis on measurement-based quantum computing, which is considered one of the most promising ways of organizing quantum computations and of designing quantum computers. Then, several families of abstract quantum computation models will be presented: pure quantum Turing machines, measurement-based and classically-controlled Turing machines, quantum cellular automata, quantum lambda calculi with quantum type systems, and quantum process calculi. It will be shwon how these abstract models of quantum computation give rise to the design of quantum programming languages, and a number of open problems for the design of adequate semantic frameworks will be explained. Concluding remarks will close this tutorial with an overview of the current hot topics in quantum information processing and communication.

Short Bibliography

Further ETAPS 2006 Programme Information:

ETAPS 2006 | Top | HTML 4.01 | Last Update: 2006-03-10