Symmetrizing dynamics: from classical to quantum applications

Among the issues regarding networked systems, the “consensus problem” and the related algorithms have received a significant share of attention during the last ten years. In this problem the network agents asymptotically have to attain agreement on the value of some objective variable under local communication constraints. A number of algorithms have been developed to address this problem, among which the celebrated gossip algorithm. The latter relays on switching dynamics and, under rather weak assumptions, exhibits robust convergence under variations in the interaction constraints, i.e. the network topology. In this dissertation we reinterpret the goal of the consensus problem as a symmetrisation problem, and we address it by a switching-type dynamics based on convex combinations of actions of a finite group. In order to study the convergence of our class of algorithms we lift the dynamics to an abstract, group-theoretic level that allow us to derive general conditions for convergence. Such conditions, in fact, are independent of the particular group action, and focus only on the group itself and the way the iterations are selected. Convergence is guaranteed provided that some mild assumptions on the selection rule for the iterations are fulfilled. Furthermore, this class of algorithms retains the robustness features and unsupervised character of the consensus algorithm. Our reformulation allow to devise algorithms for application as diverse as randomized discrete Fourier transform and random state generation. We pose a special emphasis on the extension of the consensus problem to the quantum domain. In this setting we highlight how, due to the richer mathematical structure over which the internal state is encoded, the definition of the consensus goal admits various extensions, each of them exhibiting different features. We also propose a suitable dissipative dynamics enacting the symmetrising gossip interactions and then use our general result on convergence to prove it ensures asymptotic convergence. Beside the technical results, one of the main contributions of our work is a new, generalized view point on consensus, which allows us to extend the robustness of consensus-inspired algorithms to new problems in apparently unrelated fields. This reinforces the role of consensus algorithms as fundamental tools for distributed computing, both in the classical and the quantum setting