Nilanjana Datta (Cambridge): Data compression limit for an information source of interacting qubits

A system of interacting qubits can be viewed as a non-i.i.d quantum information source. A possible model of such a source is provided by a quantum spin system, in which spin-1/2 particles located at sites of a lattice interact with each other. We establish the limit for the compression of information from such a source and show that asymptotically it is given by the von Neumann entropy rate. Our result can be viewed as a quantum analogue of Shannon's noiseless coding theorem and an extension of Schumacher's coding theorem.

Benoît Douçot (Paris): Systems topologically protected against decoherence

One of the most serious problem raised by attempts to build devices based on qubits is the decoherence induced by the residual couplings between these small systems and their environment. Instead of trying to eliminate this quantum noise, an alternative strategy has been proposed some years ago by Kitaev, namely to build quantum circuits which would be to a large extent insensitive to external perturbations. This is achieved by a deeply non-local coding of the information. A key example for this paradigm is a class of bidimensionnal lattice gauge theories whose ground state acquires a "topological" degeneracy when the system exhibits macroscopic holes. Recent proposals to implement these ideas using Josephson junction arrays will then be presented.

Bertrand Georgeot (Toulouse): Quantum computers facing chaotic dynamics

Quantum computers hold great promises, since the massive parallelism due to the superposition principle of quantum mechanics may enormously increase the speed of a computational process. Still, they are prone to errors due to disorder and decoherence. The effects of disorder and static imperfections leading to quantum chaos on the operability of a quantum computer will be assessed. Methods for the efficient simulation of classical and quantum chaotic systems on such a quantum processor will also be presented, and the effects of errors on such algorithms discussed.

Philippe Grangier (Orsay): Quantum cryptography : from basic principles to practical implementations

We will review the basic principles of quantum key distribution (also called quantum cryptography), and present some recent experimental implementations.

Elham Kashefi (London): Quantum one-way permutations

The study of states and operators complexity is an important way to find the relationship between physical complexity and computational complexity. I show in this talk, the relationship between the complexity of preparing a state and the complexity of performing the operator of reflection about that state has a close connection with the question of the existence of one-way functions. Moreover by revisiting the Grover's algorithm I present a characterization theorem for quantum one-way permutations.

Julia Kempe (Orsay): Quantum Random Walks

Quantum computing has emerged recently as a new theoretically and technologically fascinating alternative to "classical" computation. Using the laws of quantum mechanics it has been shown, for instance, that factoring large numbers can be done in polynomial time and unconditionally secure key distribution is possible.
In the last few years computer scientist have tried to find new algorithms and algorithmic tools to exploit the power of quantum mechanics. After giving a crash-introduction to quantum computation we will present a framework to generalise classical random walks and Markov chains to the quantum regime and to compare classical and quantum mixing and hitting times. We show that the quantum random walk on the cycle mixes quadratically faster than its classical counterpart. We also provide a notion of quantum hitting time, and show that under certain conditions the hitting time of the random walk on the hypercube is exponentially smaller than the classical one.

John Schliemann (Basel): Entanglement-analogous quantum correlations in systems of indistinguishable particles

I will report on recent results on the question of "entanglement" when the participants involved are actually indistinguishable such as electrons etc. These studies are motivated by and will be illustrated on the example of quantum dot electron spin qubits. In this solid state proposal for quantum information processing qubits are formed by the spins of electrons residing in neighboring semiconductor quantum dots. Special emphasis is given to the dynamics and generation of entanglement between spin qubits in the course of gate operations.

Andreas Winter (Bristol): Probabilistic, geometric and combinatorial methods for quantum coding problems

I discuss some of the fundamental coding problems of quantum information theory. These capture an operational approach to a quantitative theory of quantum information, by identifying the optimal rates of conversion between resources, including the establishement of their units (qubits, ebits, etc.).
The talk will present the problems of quantum data compression (Schumacher), entanglement concentration, distillation and dilution (Bennett et al.), quantum channel coding of classical and quantum information (Holevo-Schumacher-Westmoreland and Schumacher-Shor), and their "reverse" problems.
The emphasis is on the mathematical structures, in particular the techniques used to prove coding theorems which draw from probabilistic (random coding), geometric (packing and covering) and combinatorial (counting; greedy algorithms) methods.