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