Evènement pour le groupe Algorithmique Distribuée


Date 2009-05-04  14:00-15:00
TitreWhat Can be Observed Locally? Round-based Models for Quantum Distributed Computing 
RésuméIt is a well-established fact that, by resorting to quantum processing in addition to manipulating classical information, it is possible to reduce the time complexity of some centralized algorithms, and also to decrease the bit size of messages exchanged in tasks requiring communication among several agents. This talk focuses on the impact of quantum information on ``locality'' in distributed computing. Specifically, the object of the study is the round-complexity of quantum distributed algorithms, when no bounds are imposed on local computational power or on the message size. We consider Linial's LOCAL model of a distributed system, augmented through two types of quantum extensions: (1) initialization of the system in a quantum entangled state, and/or (2) application of quantum communication channels. For both types of extensions, we put forward valid proof-of-concept examples of distributed problems whose round complexity is in fact reduced through genuinely quantum effects, in contexts which do not depend on the anonymity of nodes or the appearance of faults. Finally, we show that even the quantum variants of the LOCAL model have non-trivial limitations, captured by a very simple (purely probabilistic) notion which we call ``physical locality''. While this is strictly weaker than the ``computational locality'' of the classical LOCAL model, it nevertheless implies that for many distributed combinatorial optimization problems, such as Maximal Independent Set, the best currently known lower time bounds cannot be broken by applying quantum processing, in any conceivable way. This is joint work with Cyril Gavoille. 
LieuSalle 178 
OrateurAdrian Kosowski 
UrlLaBRI 



Aucun document lié à cet événement.

Retour
Retour à l'index