Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1512.03551

Optimizing the Gossip Algorithm with Non-Uniform Clock Distribution over Classical & Quantum Networks

Saber Jafarizadeh

Published Dec 11, 2015• 1 citation
arXivHTMLPDF

Abstract

Distributed gossip algorithm has been studied in literature for practical implementation of the distributed consensus algorithm as a fundamental algorithm for the purpose of in-network collaborative processing. This paper focuses on optimizing the convergence rate of the gossip algorithm for both classical and quantum networks. A novel model of the gossip algorithm with non-uniform clock distribution is proposed which can reach the optimal convergence rate of the continuous-time consensus algorithm. It is described that how the non-uniform clock distribution is achievable by modifying the rate of the Poisson process modeling the clock of the gossip algorithm. The minimization problem for optimizing the asymptotic convergence rate of the proposed gossip algorithm and its corresponding semidefinite programming formulation is addressed analytically. It is shown that the optimal results obtained for uniform clock distribution are suboptimal compared to those of the non-uniform one and for non-uniform distribution the optimal answer is not unique i.e. there is more than one set of probabilities that can achieve the optimal convergence rate. Based on the optimal continuous-time consensus algorithm and the detailed balance property, an effective method of obtaining one of these optimal answers is proposed. Regarding quantum gossip algorithm, by expanding the density matrix in terms of the generalized Gell-Mann matrices, the evolution equation of the quantum gossip algorithm is transformed to the state update equation of the classical gossip algorithm. By defining the quantum gossip operator, the original optimization problem is formulated as a convex optimization problem, which can be addressed by semidefinite programming.

DOI
10.48550/arxiv.1512.03551

Related papers

Optimizing the Convergence Rate of the Continuous-Time Quantum Consensus

Saber Jafarizadeh

Inspired by the recent developments in the field of distributed quantum computing, distributed quantum systems are analyzed as networks of quantum systems. This gives rise to the distributed quantum consensus algorithms. Focus of this paper is on optimizing the convergence rate of the continuous-time quantum consensus algorithm over a quantum network with N qudits. It is shown that the optimal convergence rate is independent of the value of d in qudits. By classifying the induced graphs as the Schreier graphs, they are categorized in terms of the partitions of integer N. The intertwining relation is established between one-level dominant partitions in the Hasse Diagram of integer N. Based on this result, the proof of the Aldous' conjecture is extended to all possible induced graphs, and the original optimization problem is reduced to optimizing algebraic connectivity of the smallest induced graph. Utilizing the generalization of Aldous' conjecture, it is shown that the convergence rates of the algorithm to both the consensus state and the reduced quantum state consensus are the same. By providing the analytical solution to semidefinite programming formulation of the obtained problem, closed-form expressions for the optimal results are provided for a range of topologies.

arXiv:1509.05823•IEEE Transactions on Automatic Control•Apr 24, 2017•18 citations

Consensus for Quantum Networks: Symmetry From Gossip Interactions

Luca Mazzarella, Alain Sarlette, Francesco Ticozzi

This paper extends the consensus framework, widely studied in the literature on distributed computing and control algorithms, to networks of quantum systems. We define consensus situations on the basis of invariance and symmetry properties, finding four different generalizations of classical consensus states. This new viewpoint can be directly used to study consensus for probability distributions, as these can be seen as a particular case of quantum statistical states: in this light, our analysis is also relevant for classical problems. We then extend the gossip consensus algorithm to the quantum setting and prove it converges to symmetric states while preserving the expectation of permutation-invariant global observables. Applications of the framework and the algorithms to estimation and control problems on quantum networks are discussed.

arXiv:1303.4077•IEEE Transactions on Automatic Control•Sep 25, 2014•68 citations

A new perspective on gossip iterations: From Symmetrization to quantum consensus

Luca Mazzarella, Alain Sarlette, Francesco Ticozzi

This paper extends the gossip algorithm, widely studied in the literature on distributed computing and control algorithms, to networks of quantum systems. In doing so, we reinterpret the classical algorithm and the average consensus task as a symmetrization problem with respect to the action of the permutation group. This allows us to extend in a natural way the gossip consensus algorithm to the quantum setting and prove its convergence properties to symmetric states while preserving the expectation of permutation-invariant global observables.

IEEE Conference on Decision and Control (CDC)•Dec 1, 2013•7 citations

Reaching Consensus in Quantum Networks with Continuous-time Markovian Dynamics

Guodong Shi, Daoyi Dong, Ian R. Petersen +1 more

In this paper, we investigate the convergence of the state of a quantum network to a consensus (symmetric) state. The state evolution of the quantum network with continuous-time swapping operators can be described by a Lindblad master equation, which also introduce an underlying interaction graph for the network. For a fixed quantum interaction graph, we prove that the state of a quantum network with continuous-time Markovian dynamics converges to a consensus state, with convergence rate given by the smallest nonzero eigenvalue of a matrix serving as the Laplacian of the quantum interaction graph. We show that this convergence rate can be optimized via standard convex programming given a fixed amount of edge weights. For switching quantum interaction graphs, we establish necessary and sufficient conditions for exponential quantum consensus and asymptotic quantum consensus, respectively. The convergence analysis is based on a bridge built between the proposed quantum consensus scheme and classical consensus dynamics, in that quantum consensus of n qubits naturally defines a consensus process on an induced classical graph with 2 nodes. Existing consensus results on classical networks can thus be adopted to establish the quantum consensus convergence.

•Mar 25, 2014•1 citation

Continuous time quantum consensus & quantum synchronisation

Saber Jafarizadeh

Distributed consensus algorithm over networks of quantum systems has been the focus of recent studies in the context of quantum computing and distributed control. Most of the progress in this category have been on the convergence conditions and optimizing the convergence rate of the algorithm, for quantum networks with undirected underlying topology. This paper aims to address the extension of this problem over quantum networks with directed underlying graphs. In doing so, the convergence to two different stable states namely, consensus and synchronous states have been studied. Based on the intertwining relation between the eigenvalues, it is shown that for determining the convergence rate to the consensus state, all induced graphs should be considered while for the synchronous state only the underlying graph suffices. Furthermore, it is illustrated that for the range of weights that the Aldouss conjecture holds true, the convergence rate to both states are equal. Using the Pareto region for convergence rates of the algorithm, the global and Pareto optimal points for several topologies have been provided.

arXiv:1605.06976•Australian Control Conference•Nov 1, 2016•3 citations

Agreeing over quantum hybrid networks: Centralized and distributed solutions

Guodong Shi, Bo Li, Zibo Miao +2 more

Quantum hybrid networks where classical and quantum components coexist play a fundamental role in quantum communications. We consider a basic quantum hybrid network model consisting of a number of nodes each holding a qubit, for which the aim is to drive the network to a consensus in the sense that all qubits reach a common state. Projective measurements are applied serving as control means, and the measurement results are exchanged among the nodes via classical communication channels. We show how to carry out centralized optimal path planning for the network with all-to-all classical communications, in which case the problem becomes a stochastic optimal control problem with a continuous action space. To overcome the computation and communication obstacles facing the centralized solutions, we also develop a distributed Pairwise Qubit Projection (PQP) algorithm, where pairs of nodes meet at a given time and respectively perform measurements at their geometric average. We show that the qubit states are driven to a consensus almost surely along the proposed PQP algorithm, and that the expected qubit density operators converge to the average of the network's initial values.

Australian Control Conference•Nov 1, 2016•1 citation
Distributed gossip algorithm has been studied in literature for practical implementation of the distributed consensus algorithm as a fundamental algorithm for the purpose of in-network collaborative processing. This paper focuses on optimizing the convergence rate of the gossip algorithm for both classical and quantum networks. A novel model of the gossip algorithm with non-uniform clock distribution is proposed which can reach the optimal convergence rate of the continuous-time consensus algorithm. It is described that how the non-uniform clock distribution is achievable by modifying the rate of the Poisson process modeling the clock of the gossip algorithm. The minimization problem for optimizing the asymptotic convergence rate of the proposed gossip algorithm and its corresponding semidefinite programming formulation is addressed analytically. It is shown that the optimal results obtained for uniform clock distribution are suboptimal compared to those of the non-uniform one and for non-uniform distribution the optimal answer is not unique i.e. there is more than one set of probabilities that can achieve the optimal convergence rate. Based on the optimal continuous-time consensus algorithm and the detailed balance property, an effective method of obtaining one of these optimal answers is proposed. Regarding quantum gossip algorithm, by expanding the density matrix in terms of the generalized Gell-Mann matrices, the evolution equation of the quantum gossip algorithm is transformed to the state update equation of the classical gossip algorithm. By defining the quantum gossip operator, the original optimization problem is formulated as a convex optimization problem, which can be addressed by semidefinite programming.
Inspired by the recent developments in the field of distributed quantum computing, distributed quantum systems are analyzed as networks of quantum systems. This gives rise to the distributed quantum consensus algorithms. Focus of this paper is on optimizing the convergence rate of the continuous-time quantum consensus algorithm over a quantum network with N qudits. It is shown that the optimal convergence rate is independent of the value of d in qudits. By classifying the induced graphs as the Schreier graphs, they are categorized in terms of the partitions of integer N. The intertwining relation is established between one-level dominant partitions in the Hasse Diagram of integer N. Based on this result, the proof of the Aldous' conjecture is extended to all possible induced graphs, and the original optimization problem is reduced to optimizing algebraic connectivity of the smallest induced graph. Utilizing the generalization of Aldous' conjecture, it is shown that the convergence rates of the algorithm to both the consensus state and the reduced quantum state consensus are the same. By providing the analytical solution to semidefinite programming formulation of the obtained problem, closed-form expressions for the optimal results are provided for a range of topologies.
This paper extends the consensus framework, widely studied in the literature on distributed computing and control algorithms, to networks of quantum systems. We define consensus situations on the basis of invariance and symmetry properties, finding four different generalizations of classical consensus states. This new viewpoint can be directly used to study consensus for probability distributions, as these can be seen as a particular case of quantum statistical states: in this light, our analysis is also relevant for classical problems. We then extend the gossip consensus algorithm to the quantum setting and prove it converges to symmetric states while preserving the expectation of permutation-invariant global observables. Applications of the framework and the algorithms to estimation and control problems on quantum networks are discussed.
This paper extends the gossip algorithm, widely studied in the literature on distributed computing and control algorithms, to networks of quantum systems. In doing so, we reinterpret the classical algorithm and the average consensus task as a symmetrization problem with respect to the action of the permutation group. This allows us to extend in a natural way the gossip consensus algorithm to the quantum setting and prove its convergence properties to symmetric states while preserving the expectation of permutation-invariant global observables.
In this paper, we investigate the convergence of the state of a quantum network to a consensus (symmetric) state. The state evolution of the quantum network with continuous-time swapping operators can be described by a Lindblad master equation, which also introduce an underlying interaction graph for the network. For a fixed quantum interaction graph, we prove that the state of a quantum network with continuous-time Markovian dynamics converges to a consensus state, with convergence rate given by the smallest nonzero eigenvalue of a matrix serving as the Laplacian of the quantum interaction graph. We show that this convergence rate can be optimized via standard convex programming given a fixed amount of edge weights. For switching quantum interaction graphs, we establish necessary and sufficient conditions for exponential quantum consensus and asymptotic quantum consensus, respectively. The convergence analysis is based on a bridge built between the proposed quantum consensus scheme and classical consensus dynamics, in that quantum consensus of n qubits naturally defines a consensus process on an induced classical graph with 2 nodes. Existing consensus results on classical networks can thus be adopted to establish the quantum consensus convergence.
Distributed consensus algorithm over networks of quantum systems has been the focus of recent studies in the context of quantum computing and distributed control. Most of the progress in this category have been on the convergence conditions and optimizing the convergence rate of the algorithm, for quantum networks with undirected underlying topology. This paper aims to address the extension of this problem over quantum networks with directed underlying graphs. In doing so, the convergence to two different stable states namely, consensus and synchronous states have been studied. Based on the intertwining relation between the eigenvalues, it is shown that for determining the convergence rate to the consensus state, all induced graphs should be considered while for the synchronous state only the underlying graph suffices. Furthermore, it is illustrated that for the range of weights that the Aldouss conjecture holds true, the convergence rate to both states are equal. Using the Pareto region for convergence rates of the algorithm, the global and Pareto optimal points for several topologies have been provided.
Quantum hybrid networks where classical and quantum components coexist play a fundamental role in quantum communications. We consider a basic quantum hybrid network model consisting of a number of nodes each holding a qubit, for which the aim is to drive the network to a consensus in the sense that all qubits reach a common state. Projective measurements are applied serving as control means, and the measurement results are exchanged among the nodes via classical communication channels. We show how to carry out centralized optimal path planning for the network with all-to-all classical communications, in which case the problem becomes a stochastic optimal control problem with a continuous action space. To overcome the computation and communication obstacles facing the centralized solutions, we also develop a distributed Pairwise Qubit Projection (PQP) algorithm, where pairs of nodes meet at a given time and respectively perform measurements at their geometric average. We show that the qubit states are driven to a consensus almost surely along the proposed PQP algorithm, and that the expected qubit density operators converge to the average of the network's initial values.