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.
- 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

  • Pablo Arrighi