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:
- 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;
- Communication, the quantum way: quantum key distribution, quantum state
teleportation;
- Computing with quantum resources: Grover's and Shor's quantum algorithms,
generalizations and other principles in quantum algorithmics;
- 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:
- Design of programming languages for NASA and NSA (USA) at the end of the sixties.
- R&D in programming languages with IBM France and with CNRS in the seventies.
- Research in process algebras with IBM Research California at the end of the seventies.
- Process algebras, term rewriting and parallel inferencing in Grenoble in the eighties.
- Head of large research laboratories in AI and fundamental computer science, at Grenoble
University, from the mid-eighties until the end of the nineties.
- Full time research and head of a research group in quantum information processing since
year 2000, Leibniz Laboratory, Grenoble.
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
- A concise introduction, easy to read and well written:
E. G. Rieffel and W. Polak. An introduction to quantum computing for non physicists. Los
Alamos e-print archive, http://arxiv.org/abs/quant-ph/9809016, 1998. Also published in ACM
Computing Surveys, Vol. 32(3), pp. 300-335, 2000.
- Two textbooks:
M. A. Nielsen and I. L. Chuang. Quantum Computation and Quantum Information. Cambridge
University Press, 2000.
A. Y. Kitaev, A. H. Shen and M. N. Vyalyi. Classical and Quantum Computation. American
Mathematical Society, Graduate Studies in Mathematics, Vol. 47, 2002.
- Two recent reports on the state of the art and on the perspectives:
ARDA Quantum Information Science and Technology Roadmapping Project. Quantum
Computation Roadmap. http://qist.lanl.gov/, ARDA document, version 2.0, 2004.
ERA Pilot Roadmap Quantum Information Sciences and Technologies. QIPC - Strategic
report on current status, visions and goals for research in Europe,
http://qist.ect.it/Reports/reports.htm, EU document, version 1.1,
Further ETAPS 2006 Programme Information:
- Programme Overview
- Main Conferences:
Complete Programme,
CC,
ESOP,
FASE,
FOSSACS,
TACAS
- Workshops:
ACCAT,
AVIS,
CMCS,
COCV,
DCC,
EAAI,
FESCA,
FRCSS,
GT-VMT,
LDTA,
MBT,
QAPL,
SC,
SLAP,
SPIN,
TERMGRAPH,
WITS,
WRLA
- Tutorials:
Phoenix
ETAPS 2006 |
Top |
HTML 4.01 |
Last Update: 2006-03-10