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.

Negli ultimi decenni l’approfondito studio delle dinamiche su network è stato al centro dell’indagine in molti discipline tra cui, biologia, matematica applicata, scienze sociali, ingegneria dei sistemi e non ultima la fisica. Una delle caratteristiche più interessanti, sia da un punto di vista teorico che applicativo, è l’emergere di dinamiche collettive indotte dalle interazioni tra i costituenti del network nonostante i vincoli imposti dalla struttura topologica dello stesso. Spinti dai potenziali vantaggi promessi dalla quantum computation nella soluzione di certi problemi, i recenti avanzamenti nella capacitá di descrivere e controllare sistemi complessi, come per esempio i miglioramenti nella generazione e manipolazione correnti di sistemi singoli, hanno aperto nuove direzioni di ricerca verso applicazioni di quantum information “distribuita”. In campi differenti sono stati sviluppati molteplici approcci per descrivere sistemi complessi. Tuttavia, per il campo dell’information processing è particolarmente adeguata la cosiddetta prospettiva multi-agente. In questa visuale, il sistema è descritto come un insieme di componenti, dette agenti, ognuna delle quali possiede uno stato interno, il cui valore evolve come risultato dello scambio di informazione ed energia tra gli agenti stessi. A causa della topologia del network, la capacità di interazione degli agenti è vincolata ad essere locale: per esempio, assumiamo che la comunicazione possa avvenire solo tra agenti prossimi. Le leggi di evoluzione dell’intero sistema ereditano tale vincolo di località. Per queste classi di modelli un tipico problema di interesse è caratterizzarne il comportamento asintotico. Tra gli aspetti di interesse riguardanti i network, il “problema di consensus” a i relativi algoritmi hanno ricevuto grande attenzione nell’ultimo decennio. In questo problema gli agenti del network devono asintoticamente accordarsi sul valore di una qualche variabile di interesse sotto il vincolo di comunicazioni locali. Un grande numero di algoritmi sono stati sviluppati per affrontare tale problema, tra i quali il celebrato algoritmo di gossip. Quest’ultimo si basa su una dinamica di tipo switching ed esibisce una convergenza robusta rispetto alla variazione dei vincoli di interazione quali ad esempio la topologia del network. In questa tesi reinterpretiamo gli obiettivi del problema di consensus come un problema di simmetrizzazione che affrontiamo mediante dinamiche di tipo switching basate sulla combinazione convessa di azioni di un gruppo finito. Per descrivere la convergenza di tali algoritmi proponiamo una descrizione più astratta di stampo gruppale. Tale descrizione ci permette di formulare criteri generali per la convergenza, indipendenti dalla particolare azione, che si focalizzano solo sul gruppo in quesitone e sul modo in cui le iterazioni sono generate. La convergenza viene garantita a patto che i meccanismi di selezione delle iterazioni rispettino alcuni criteri poco stringenti. Inoltre, la nostra classe di algoritmi mantiene le caratteristiche di robustezza degli algoritmi di gossip. La nostra riformulazione ci permette di considerare algoritmi per diverse applicazioni quali ad esempio la trasformata di Fourier distribuita e la generazione di stati casuali. Inoltre, descriviamo approfonditamente l’estensione quantistica del problema del consensus. In quest’ambito mostriamo come, a causa della ricchezza delle strutture matematiche con cui gli stati interni sono descritti, la definizione dell’obiettivo di consensus ammetta diverse estensioni ognuna recanti diverse caratteristiche. Proponiamo, inoltre una dinamica dissipativa che asintoticamente realizza tale simmetrizzazione. Oltre a risultati di tipo tecnico, uno dei contributi centrali del lavoro è un nuovo e generalizzato punto di vista sul consensus che permette di estendere la robustezza di tali algoritmi a problemi a prima vista scollegati, rinforzando così il ruolo di tali algoritmi come strumento per il calcolo distribuito sia in ambito classico che quantistico.