From the 1st till the 5th february 2010 — ENS Lyon
Intervenants :
Schedule: (Amphi B of ENS-Lyon)
- First part: Mon. 14:00-18:00, Tue. 14:00-18:00, Wed. 9:00-13:00.
- Second part: Wed. 14:00-17:00, Thu. 9:00-12:00 & 14:00-17:00, Fri. 9:00-12:00.
Course outline :
Our understanding of what a computer is (models of computation) and of the way one
may use it in order to solve mathematical problems(algorithmics) is under
constant evolution. Beyond the traditional approach, which is essentially based
upon deterministic discrete systems (automata of all sorts), a new vision is
emerging which considers that probabilistic phenomena (randomness, approximations)
and even quantum phenomena (interference, entanglement) should not be seen as just
added difficulties, but rather as novel tools awaiting to be exploited and offering
remarkable perspectives. What are the limits of the traditional approach which we
can overcome with these new tools? What more can we expect from them?
Lecture 1 (P.Arrighi) : Quantum information, causality and cellular automata
Lately quantum physical phenomena turned out to be extremely useful for speeding up
or securing a number of important information processing and communication tasks.
In the last 15 years, rather impressive theoretical results show that qualitative
and quantitative performances would then become possible, beyond reach of classical
computation. For instance it was proved that a quantum computer can factorise an
integer number in polynomial time, or search for an element within a unstructured
list of n elements, in time square root of n. These results are a threat to contemporary
cryptography, but what quantum physics takes on the one hand, it gives it back on
the other. Some quantum communication systems, already available in industry, warrant
provably unconditionnally secure communication channels.
This module provides background material from linear algebra, then from quantum
mechanics. Then main results relating to the particular, non-local nature of quantum
information are then given. The course is then oriented towads the quest for a model
of computation which is quantum and distributed at the same time, and that takes into
account several of the fundamental symmetries of physics (causality,
translation-invariance). This will bring us to the study of themes such as causality
in quantum mechanics, the definition of cellular automata in such a context, the
nature of the interplay between Physics and Computation.
Syllabus:
- Linear algebra
- Postulates of quantum theory
- Explorations on the nature of quantum information (Deutsch's algorithm,
No-distinguishing, No-cloning, Super-dense coding, Teleportation)
- Density matrices, quantum operators
- Entanglement (classification, non-local boxes)
- Causal operators and their structure
- Cellular Automata : three definitions and their equivalence
- Axiomatic definition of quantum cellular automata
- Structure theorems
- Universal quantum cellular automata
LECTURE 2 (F. Magniez) : Efficient algorithmics
This course aims at tackling those techniques which enable the construction of
efficient algorithms for a variety of contexts. These techniques rely on
tools stemming from probabilities and approximations. The contexts model the
sort of constraints that we are placing upon the machine in terms of
resources (time, space, randomness, query, comunication) and data access
(unconstrained (random access), or sequential (streaming)).
The themes we will hence cover:
- Random walks: k-SAT, (s,t)-CONNECTIVITY in RL
- Expander graphs: derandomizaton, (s,t)-CONNECTIVITY in L
- Approximation algorithms (approximation on the output)
- Property testing (approximation on the input)
- PCP Theorem (light version): application to inaproximability results
- Streaming algorithm
- One-way communication complexity: application to non existence of
streaming algorithms
Correspondant local
Français