1

Continuous Time Quantum Consensus & Quantum
Synchronisation

arXiv:1605.06976v1 [] 23 May 2016

Saber Jafarizadeh, Member, IEEE,

Abstract
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.
Index Terms
Quantum Networks Synchronization, Distributed Consensus, Aldous’ Conjecture, Optimal Convergence Rate

I. I NTRODUCTION
In the context of distributed control, distributed consensus algorithms are employed as the building
block for implementing other distributed algorithms which rely on the individual decision of agents and
the local communication among them [2], [5]. The extension of this class of algorithms to the quantum
domain has been addressed in [7] where four different generalizations of classical consensus states have
been proposed. In [8], [9], [10] the necessary and sufficient conditions for asymptotic convergence of
the quantum consensus algorithm is studied. Optimizing the convergence rate of the algorithm to the
consensus state has been addressed in [11], [12]. The majority of the analysis regarding the convergence
e-mail: saber.jafarizadeh@sydney.edu.au

2

rate of the algorithm has been focused on quantum networks with an undirected underlying graph. In this
paper, we aim to study the convergence rate of the distributed consensus algorithm over a network of qudit
systems with general (i.e. either directed or undirected) underlying topologies. The convergence rates to
two different states of the network of quantum systems have been studied. These states are consensus
and synchronous states. Consensus state is the symmetric state which is invariant to all permutations
[7]. Synchronous state is the state where the reduced states of the quantum network are driven to a
common trajectory [9], [10]. Employing the intertwining relation [11] between the eigenvalues of the
Laplacian matrices of the induced graphs, we have shown that the convergence rate to the consensus
state is obtained from the spectrum of all induced graphs combined. On the contrary, the convergence
rate to the synchronous state is dictated by only the spectrum of the underlying graph of the network
and therefore it is independent of the dimension of the Hilbert space (d). By establishing the relation
between the convergence rates to consensus and synchronous states, we have shown that both convergence
rates are equal and independent of d if the Aldous’ conjecture holds true for all induced graphs of the
networks. Furthermore, we have proved that the synchronous state is reachable for any permutationinvariant system Hamiltonian (H0 ), while for the algorithm to converge to the consensus state, either the
system Hamiltonian should be zero (i.e. H0 = 0) or the analysis should be limited to the interaction
picture. For different network topologies, by plotting the Pareto region of the convergence rates to the
consensus and synchronous states, we have studied the Pareto optimal points and the global optimal points
regarding both convergence rates.
The rest of the paper is organized as follows. Preliminaries on graph theory are provided in section II.
Section III explains the evolution of the quantum network. In section IV, optimization of the convergence
rates of the algorithm have been addressed over different topologies and Section V concludes the paper.
II. P RELIMINARIES
In this section, we present the fundamental concepts on graph theory, Cayley and Schreier Coset Graphs.
A. Graph Theory
A directed graph (digraph) is defined as G = {V, E} with V = {1, . . . , N } as the set of vertices and E
as the set of edges. Each edge {i, j} ∈ E is an ordered pair of distinct vertices, denoting an directed edge
from vertex i to vertex j. Throughout this paper, we consider directed simple graphs with no self-loops
and at most one edge between any two different vertices. A weighted graph is a graph where a weight

3

is associated with every edge according to a proper map W : E → R, such that if {i, j} ∈ E, then
W ({i, j}) = wij ; otherwise W ({i, j}) = 0. The edge structure of the weighted graph G is described
through its weighted adjacency matrix (AG ). The weighted adjacency matrix AG is a N × N matrix with
{i, j}-th entry (AG (i, j)) defined as below

AG (i, j) =



wij

if

{i, j} ∈ E,


0 Otherwise.
The indegree (outdegree) of a vertex i is the sum of the weights on the edges heading in to (heading out
of) vertex i. A directed path (dipath) in a digraph is a sequence of vertices with directed edges pointing
from each vertex to its successor in the sequence. A simple dipath is the one with no repeated vertices
in the sequence. A directed graph is called strongly connected if there is a dipath between any pair of
vertices in the graph. The weighted Laplacian matrix of graph G is defined as below,

LG (i, j) =



DG (i, i)

if i = j,


−A (i, j) if
G

i 6= j,

where DG (i, i) is the indegree of the i-th vertex. This definition of the weighted Laplacian matrix can
be expressed in matrix form as LG = DG − AG , where DG and AG are the indegree and the adjacency
matrices of the graph G. The Laplacian matrix of a directed graph is not necessarily symmetric and its
eigenvalues can have imaginary parts. Defining 1 and 0 as vectors of length N with all elements equal
to one and zero, respectively, for the Laplacian matrix we have LG × 1 = 0. In directed graphs, the
eigenvalues of the the associated Laplacian can be arranged in non-decreasing order as below,
0 = λ1 (LG ) ≤ Re (λ2 (LG )) ≤ · · · ≤ Re (λN (LG )) .
Re (λi (LG )) denotes the real part of the i-th eigenvalue of the weighted Laplacian matrix of the digraph.
The digraph G is said to be strongly connected [4] iff Re (λ2 (LG )) > 0.

B. Cayley Graph & Schreier Coset Graph
Let H be a group and let S ⊆ H. The Cayley graph of H generated by S (referred to as the generator
set S), denoted by Cay(H, S), is the directed graph G = (V, E) where V = H and E = {(x, xs)|x ∈
H, s ∈ S}. If S = S −1 (i.e., S is closed under inverse), then Cay(H, S) is an undirected graph. If H acts

4

transitively on a finite set Ω, we may form a graph with vertex set V = Ω and edge set E = {(ν, νs)|ν ∈
Ω, s ∈ S}. Similarly, if Q is a subgroup in H, we may form a graph whose vertices are the right cosets
of Q , denoted (H : Q) and whose edges are of the form E = {(Qh, Qhs)|Qh ∈ (H : Q), s ∈ S}. These
two graphs are the same when Ω is the coset space (H : Q), or when Q is the stabilizer of a point of Ω
and is called the Schreier coset graph Sch(H, S, Q).

III. E VOLUTION OF THE Q UANTUM N ETWORK
Considering a quantum network as a composite (or multipartite) quantum system with N qudits, and
assuming H as the d-dimensional Hilbert space over C, then the state space of the quantum network is
within the Hilbert space H⊗N = H ⊗ . . . ⊗ H. The state of the quantum system is described by its density
matrix (ρ) (a positive Hermitian matrix with trace one). The network is associated with an underlying
graph G = {V, E}, where V = {1, . . . , N } is the set of indices for the N qudits, and each element in
E is an ordered pair of two distinct qudits, denoted as {j, k} ∈ E with j, k ∈ V. Permutation group SN
acts in a natural way on V by mapping V onto itself. For each permutation π ∈ SN we associate unitary
operator Uπ over H⊗N , as below
Uπ (Q1 ⊗ · · · ⊗ QN ) = Qπ(1) ⊗ · · · ⊗ Qπ(N ) ,
where Qi is an operator in H for all i = 1, . . . , N .
Employing the quantum gossip interaction introduced in [7], the evolution of the quantum network can
be described by the following master equation
X

i
dρ
= − [H0 , ρ] +
wπ Uπ × ρ × Uπ† − ρ
π∈B
dt
~

(1)

where B is a subset of the permutation group SN , H0 is the (time-independent) system Hamiltonian, i
is the imaginary unit, ~ is the reduced Planck constant and where wπ is a positive time-invariant weight
corresponding to the permutation π. These weights form the distribution of limited amount of weight up
to D, among edges of the underlying graph, i.e.
X
π∈B

lπ wπ ≤ D,

(2)

where lπ is the sum of the cycle length of cycles appearing in π except for trivial one-cycles. The generator
set B should be selected in a way that the underlying graph corresponding to GB (the group generated by

5

B which is a subset of SN ) is connected.

A. Consensus & Synchronous States
In [7], four different consensus states generalized to the quantum domain are exploited. Based on
these schemes, three different possible consensus states can be defined which are reachable by quantum
consensus algorithm.
Definition 1: Observable-Expectation Consensus
The observable-expectation consensus (ρ∗ ) is defined as the state where for any observable σ the
following holds,
tr(ρ∗ (t)σl ) = tr(ρ∗ (t)σk ) for

k, l = 1, · · · , N,

(3)

k

z}|{
where σk = I ⊗ I ⊗ · · · σ ⊗ · · · I).
Definition 2: Synchronous State
The synchronous state (ρ∗ ) is defined as the state where the following holds
ρ̄∗1 = ρ̄∗2 = · · · = ρ̄∗N ,

(4)

where ρ̄k is the reduced state of the subsystem k for an overall system state ρ i.e. ρ̄k = tr(⊗j6=k Hj ) (ρ).
In [7], equation (4) is defined as the reduced state consensus.
In [7] it is shown that the observable-expectation consensus and the synchronous state are equivalent.
Definition 3: Symmetric State
The symmetric state (ρ∗ ) is defined as the state where for each unitary permutation Uπ , with π ∈ GB ⊂
SN
ρ∗ =

1 X
Uπ ρ(t)Uπ†
|GB | π∈B

(5)

For the special case that the subset B is able to generate the permutation set SN (i.e. GB = SN ) the
symmetric state is referred to as the consensus state.

B. Master Equation in Interaction Picture
For the case of permutation-invariant H0 , i.e.
[H0 , Uπ ] = 0

for every π ∈ SN ,

(6)

6

we can eliminate the first term in Lindblad equation by writing it in interaction picture, i.e. ρ(t) =
e−iH0 t ρI (t)eiH0 t and then substituting the result in Lindblad equation which in turn results in the following,
X

dρI
=
wπ Uπ × ρI × Uπ† − ρI .
dt
π∈B

(7)

In [7], [8], it is shown that equation (7) can asymptotically reach the symmetric state given below,
ρ∗I (t) =

1 X
Uπ ρI (t)Uπ† .
|GB | π∈B

(8)

Substituting (8) in (7) and using the fact that ρ∗I (t) is permutation-invariant i.e.
Uπ ρ∗I (t)Uπ† = ρ∗I (t) for every
dρ∗I (t)
dt

it can be concluded that

(9)

π ∈ B,

= 0 and ρ∗I (t) = ρ∗I (0).

Theorem 1: For permutation-invariant H0 , the equation (1) can reach the symmetric state (5).
Proof: The following can be written for the symmetric state (5)
ρ∗ (t) =

1 X
1 X
Uπ ρ(t)Uπ† =
Uπ e−iH0 t ρI (t)eiH0 t Uπ† = e−iH0 t ρ∗I (t)eiH0 t = e−iH0 t ρ∗I (0)eiH0 t .
|GB | π∈B
|GB | π∈B
(10)

Therefore, the equation (1) will reach the symmetric state (5), as long as the equation (7) reaches the
symmetric state (8).

Theorem 2: Equation (1) can reach the synchronous state if the underlying graph corresponding to GB
is strongly connected and H0 is permutation-invariant.
Proof: Based on (10) we have
l

<i|

ρ∗l (t)

k

z }| {
z }| {
| j >= tr(ρ (t)I × I × · · · | j >< i | × · · · I) = tr(ρ∗ (t)Uπ (I × I × · · · | j >< i | × · · · I)Uπ† )
∗

k

k

z }| {
z }| {
=
× I × · · · | j >< i | × · · · I) = tr(ρ∗ (t)I × I × · · · | j >< i | × · · · I) =< i | ρ∗k (t) | j >,
(11)
l
k
z}|{
z}|{
where Uπ is the unitary representation of a permutation that maps 0 · · · 0 1 0 · · · 0 to 0 · · · 0 1 0 · · · 0.
tr(Uπ† ρ∗ (t)Uπ I

From equation (11), it can be concluded that the ρ∗l (t) = ρ∗k (t) i.e. the reduced states of the l-th and k-th
qudits in the equilibrium are the same, i.e synchronous state is obtained.

7

Also equation(11) implies the following,
tr(ρ∗ (t)σl ) = tr(ρ∗ (t)σk ) for

k, l = 1, · · · , N,

(12)

k

z}|{
where σk = I ⊗ I ⊗ · · · σ ⊗ · · · I). In [7], equation (12) is defined as the σ-Expectation Consensus.
Remark 1: Based on Theorem 2 and Definition 3, we can state that for permutation-invariant H0 and
a strongly connected underlying graph (B) which can generate the permutation group (i.e. GB = SN ),
the consensus state is reachable for ρI (t), and on the other hand the consensus state is reachable for ρ(t)
if H0 = 0.
Thus to have both consensus and synchronous states as feasible states, for the rest of the analysis
presented in this paper we have assumed that H0 = 0 and GB = SN .

C. Equivalent Classical Continuous-Time Consensus Algorithm
The density matrix (ρ) can be expanded in terms of the generalized Gell-Mann matrices [11, Appendix
A] as below,
1
ρ= N
d

2 −1
dX

ρµ1 ,µ2 ,...,µN · λµ1 ⊗ λµ2 ⊗ · · · ⊗ λµN ,

(13)

µ1 ,µ2 ,...,µN =0

where N is the number of particles in the network and ⊗ denotes the Cartesian product and λ matrices
are the generalized Gell-Mann matrices. Note that due to Hermity of density matrix, its coefficients of
expansion ρµ1 ,µ2 ,...,µN are real numbers and because of unit trace of ρ we have ρ0,0,...,0 = 1.
Substituting the density matrix ρ from (13) in Lindblad master equation (7) and considering the
independence of the matrices λµ1 ⊗ λµ2 ⊗ · · · λµN we can conclude the following for Lindblad master
equation (7),
X

d
ρµ1 ,··· ,µN =
wπ ρπ(µ1 ),··· ,π(µN ) − ρπ(µ1 ,··· ,µN )
dt
π∈B

(14)

for all µ1 , µ2 , · · · , µN = 0, · · · , d2 − 1, with the constraint (2) on the edge weights. The tensor component
of the quantum consensus state (8) can be written as below
ρ∗µ1 ,µ2 ,...,µN =

1 X
ρπ(µ1 ),π(µ2 ),...,π(µN ) (0)
π∈SN
N!

(15)

and for the strongly connected underlying graph, the QCME reaches quantum consensus, componentwise

8

as below
lim ρµ1 ,µ2 ,...,µN (t) = ρ∗µ1 ,µ2 ,...,µN ,

t→∞

Comparing the set of equations in (14) with those of the classical Continuous-Time Consensus (CTC)
problem [11] we can see that the Quantum Consensus Master Equation (7) is transformed into a classical
CTC problem with d2N − 1 tensor component ρµ1 ,··· ,µN as the agents’ states. Defining X Q as a column
vector of length d2N with components ρµ1 ,...,µN , the state update equation of the classical CTC can be
written as below,
dX Q
= −LQ X Q ,
dt

(16)

with the constraint (2) on the edge weights. LQ is the corresponding Laplacian matrix as below,
LQ =

X
π∈B

wπ (Id2N − Uπ ),

(17)

where Uπ is the swapping operator given in [11, Appendix A] provided that d is replaced with d2 which
in turn results in Gell-Mann matrices of size d2 × d2 .

D. Convergence Rate to Consensus State
It is obvious that the convergence rate of the obtained classical CTC problem (16) is dictated by
Re(λ2 (LQ )), where λ2 (LQ ) is the eigenvalue of LQ with second smallest real value. Thus, the corresponding optimization problem can be written as below,
max Re (λ2 (LQ ))
w
X
s.t.
lπ wπ ≤ D.

(18)

π∈B

This problem is known as the Fastest Continuous Time Quantum Consensus (FCTQC) problem [8], [11],
[9].
In [11], [8] it is shown that the underlying graph of the obtained classical CTC problem (16) is a
cluster of connected components. Similar result can be deduced for directed underlying graphs and it can
be shown that each strongly connected graph component corresponds to a given partition of N into K
integers, namely N = n1 + n2 + · · · + nK , where K ≤ d2 and nj for j = 1, . . . , K is the number of indices
in ρµ1 ,µ2 ,...,µN with equal values. For a given partition and its associated Young Tabloids, more than one
connected component can be obtained. Therefore for each partition we consider only one of them, and

9

we refer to this graph as the induced graph. These induced graphs are the same as those noted in [8].
Each Young tabloid tn (r1 , r2 , · · · , rN ) is equivalent to an agent in the induced graph of the CTC problem
and its corresponding coefficient (ρµr1 ,µr2 ,··· ,µrN ) is equivalent to the state of that agent. For more details
on Young Tabloids and their association with partitions of an integer, we refer the reader to [11]. Based
on the fact that the underlying graph of the CTC problem (14) is a cluster of connected components, in
[11] it is shown that the Laplacian matrix LQ is a block diagonal matrix where each block corresponds
to one of the connected components, with state vector X n . The state update equation (16) for the state
vector X n is as below,
dX n
= −Ln X n ,
dt

(19)

with Ln as the Laplacian matrix which is one of the blocks in LQ . Therefore, the convergence rate of
(7) to the fixed point (8) is equivalent to the convergence rate of the obtained classical CTC problem,
i.e. (Re(λ2 (LQ ))), which in turn is determined by the real part of the spectrum of the induced graphs’
Laplacian matrices. In other words we have Re (λ2 (LQ )) = min (Re (λ2 (Ln ))).
n

0

0

Let n and n be two given partitions of N , then n dominates n if we have
0

nDn

if and only if

i
X
j=1

nj ≥

i
X

0

nj

for all i ≥ 1.

j=1

In [11], it is shown that the spectrum of the induced graph corresponding to the dominant partition is
included in that of the less dominant partition. This is known as the intertwining relation [11]. Also, in
[11], it is shown that if the underlying graph of the quantum network is a connected and undirected graph
then the second smallest eigenvalues of all induced graphs are equal. This is known as the generalization
of Aldous’ conjecture. Using this result, in [11], the problem of optimizing the convergence rate of
quantum consensus algorithm is reduced to the problem of maximizing the second smallest eigenvalue
of the underlying graph of the quantum network. Thus, the convergence rate is independent of d (the
dimension of the Hilbert space). In general, Aldous’ conjecture does not hold true for the case of directed
underlying graphs. Therefore for optimizing Re (λ2 (LQ )), all induced graphs should be considered. Hence,
the convergence rate will depend on d (the dimension of the Hilbert space). In next section, for several
examples, we have shown that the Aldous’ conjecture is partially true.

10

E. Convergence Rate to the Synchronous State
Expanding ρ∗ in terms of Gell-Mann matrices (similar to (13)) and substituting λµ as σ in (12) we
have
ρ∗0,...,0, µ ,0,...0 = ρ∗0,...,0, µ ,0,...0 .
|{z}
|{z}
l

k

Since (12) can be concluded if the equation above holds true therefore (12) is the necessary and sufficient
condition for reaching the synchronous state. In other words, reaching consensus in the underlying
graph (not necessarily in the induced graphs) is the necessary and sufficient condition for reaching the
synchronous state.
Therefore, it can be concluded that for analyzing the convergence rate to the synchronous state, it
suffices to study the convergence rate of the classical consensus algorithm over only the underlying
digraph of the network. As a result the convergence rate to the synchronous state wold be independent
of d (the dimension of Hilbert space). For optimizing the convergence rate to the synchronous state, the
corresponding optimization problem can be written as below,
max Re (λ2 (LU ))
w
X
s.t.
lπ wπ ≤ D.

(20)

π∈B

where LU is the Laplacian matrix of the underlying graph. Note that as long as the Aldous conjecture
holds true, the convergence rate to both the synchronous and the consensus states are the same, otherwise
the convergence rate to the synchronous state is faster than that of the consensus state.
For the rest of this paper, we will study different underlying digraphs and we will investigate if the
Aldous’ conjecture holds true and also we will study the convergence rate to both the synchronous state
and the consensus states.
IV. O PTIMIZING THE C ONVERGENCE R ATES TO THE C ONSENSUS AND S YNCHRONOUS S TATES
In this section, we optimize the convergence rates of the distributed quantum consensus algorithm to
the consensus and the synchronous states, over different topologies with three and four qudits.
Topologies with 3 qudits have two induced graphs of sizes 3 and 6, where the smaller induced graph
is identical to the underlying graph of the topology. we denote the Laplacian matrices of the underlying
graph and the induced graphs by LU , L3 and L6 , respectively. Using the intertwining relation [11] between
laplacian matrices of the induced graphs, we can state that all eigenvalues of L3 are amongst those of

11

Fig. 1.

(a) Underlying graph of G1 (3) and (b) the resultant induced graph.

L6 . Therefore, the convergence rates to the synchronous and consensus states are dictated by the second
smallest eigenvalues of LU and L6 , respectively.
The first topology (G1 (3)) that we consider is a digraph with three qudits with one cycle of length three
and one transposition. The underlying and the induced (L6 ) graphs of this topology are depicted in figure
1. The weight on edges of the cycle and the transposition are denoted by w123 and w12 , respectively. The
Laplacian matrices for the underlying (LU ) and the induced graphs (L6 ) of this topology are as below,


w123 + w12

−w12


LU = 
 −w123 − w12 w123 + w12
0

−w123

−w123
0


,


w123



d1
0
−w123 −w12
0
0


 −w123
d1
0
0
0
−w12


 0
−w123
d1
0
−w12
0

L6 = 
 −w
0
0
d1
0
−w123
12



0
−w12 −w123
d1
0
 0

0
−w12
0
0
−w123
d1
√









,







B1 /2, where A1 = 23 w123 + w12
√
2
2
and B1 = −3w123
+ 4w12
. Thus the second smallest eigenvalue of LU is A1 − 21 B1 . In the case of
√
L6 the nontrivial eigenvalues are A1 − 21 B1 and 2w12 and the second smallest eigenvalue of L6 is
√ 
min 2w12 , A1 − 21 B1 . Hence the convergence rate to the synchronous state and the consensus state is
where d1 = w12 + w123 . The nontrivial eigenvalues of LU are A1 ±

12

dictated by the following,


p
λSynch = Re A1 − B1 /2 ,
λCons



(21)




p
= min 2w12 , Re A1 − B1 /2 .

(22)

In figure 2, we have plotted the Parieto region [1] for λSynch and λCons , with the constraint 3w123 +2w12 ≤
1. From figure 2, it is obvious that there is not any global optimal point for both λCons and λSynch . The
region is bounded by two lines, namely λSynch = 0.5 and λCons = λSynch and a convex curve, where all
three of them are obtained for the constraint 3w123 + 2w12 = 1. The line λSynch = 0.5 is obtained for

√
0 < w123 ≤ 51 where B1 ≤ 0 and thus Re A1 − B1 /2 = 23 w123 + w12 = 21 . The line λCons = λSynch

√
is obtained for 3+1√3 ≤ w123 ≤ 13 which results in 2w12 > Re A1 − B1 /2 . The convex curve between
two lines is obtained for

1
5

≤ w123 ≤

1√
.
3+ 3

Note that the points along the line λCons = λSynch are the

only set of convergence rates where the Aldous’ conjecture holds true. Regarding the consensus state, the
optimal convergence rate is the point λCons = 0.4 and λSynch = 0.4 in the pareto region which is obtained
for w123 = w12 = 1/5 and for synchronous state, the optimal convergence rate can be obtained for any
of the points along the line λSynch = 0.5. Although the points on the convex curve in figure 2 do not
result in any of the optimal convergence rates but these points act as maximal points which can be used
for trade-off between the convergence rates to the consensus states and the synchronous state.

The second topology (G2 (3)) that we consider is a digraph with three qudits, two cycles and one
transposition. The underlying and the induced (L6 ) graphs of this topology are depicted in figure 3. The
weight on edges of the cycles and the transposition are denoted by w123 , w321 and w12 , respectively. The
Laplacian matrices for the underlying (LU ) and the induced (L6 ) graphs of this topology are as below,



L3 = 


w123 + w321 + w12

−w321 − w12

−w123

−w123 − w12

w123 + w321 + w12

−w321

−w321

−w123

w123 + w321


,


13

Fig. 2.

Pareto region for λCons and λSynch of the graph (G1 (3)) depicted in figure 1 (a).

Fig. 3.

(a) Underlying graph G1 (3) and (b) the resultant induced graph.



d2
−w321 −w123 −w12
0
0


 −w123
d2
−w321
0
0
−w12


 −w321 −w123
d2
0
−w12
0

L6 = 
 −w
0
0
d2
−w321 −w123
12



0
−w12 −w123
d2
−w321
 0

0
−w12
0
−w321 −w123
d2









,







14

where d2 = w123 + w321 + w12 . The nontrivial eigenvalues of LU are A2 ±

√

B2 /2 where A2 = 32 w123 +

3
w
2 321

2
2
2
and the second smallest eigenvalue of LU
− 3w123
+ 6w321 w123 + 4w12
+ w12 and B2 = −3w321
√
√
is A2 − B2 /2. In the case of L6 , the nontrivial eigenvalues are A2 ± B2 /2 and 2w12 and the second

√
smallest eigenvalue of L6 is min 2w12 , A2 − B2 /2 . Hence the convergence rate to the synchronous

state and the consensus state is dictated by the following,
λSynch




p
= Re A2 − B2 /2 ,

(23)




p
λCons = min 2w12 , Re A2 − B2 /2 .

(24)

With constraint 3w123 + 3w321 + 2w12 ≤ 1, format of the pareto region for this topology is similar to that
of G1 (3), i.e. the pareto region is bounded by the vertical line λSynch = 0.5, the line λCons = λSynch and
a convex curve between these two lines. The boundaries of the pareto region are obtained for the case
that either one of w321 or w123 is zero. In this case, this topology reduces to G1 (3). In other words, the
second cycle is redundant as it is slowing down the convergence rates to both the consensus state and the
synchronous state. Interestingly, for the case w321 = w123 (where the underlying graph is an undirected
graph), the Aldous’s conjecture does not always hold true. As an example for w321 = w123 > 32 w12 , the
convergence rates are λSynch = 3w123 > λCons = 2w12 . Similar to G1 (3) topology, the points along the
line λCons = λSynch are the only set of convergence rates where the Aldous’ conjecture holds true.
The third topology (G3 (3)) that we have analyzed is a digraph with three qudits and two transpositions.
This topology is identical to an undirected path graph with three vertices. The weight on edges of the
transpositions are denoted by w12 and w23 . The Laplacian matrices for the underlying (LU ) of this topology
is as below,


w12

−w12

0





,
LU = 
−w
w
+
w
−w
12
12
23
23


0

−w23

w23

In [11] it is shown that for topologies with undirected and connected underlying graphs, the convergence
rate of the quantum consensus algorithm to the consensus state is obtained from the second smallest
eigenvalue of the Laplacian matrix of the underlying graph. Thus it can be concluded that independent of
the value of the weights, for topologies with undirected and connected underlying graphs, the convergence
rates to the consensus and the synchronous states are the same. Hence for topology G3 (3), the convergence
rates to consensus and the synchronous states are always equal and considering the constraint 2w12 +2w23 =

15

1, the pareto region for this topology would be a direct line between points λCons = λSynch = 0 and
λCons = λSynch = 1/4. Point λCons = λSynch = 1/4 is the global optimal point in terms of both
convergence rates which is obtained for w12 = w23 = 1/4.
The fourth topology that we have considered in this section is a digraph with four qudits, one cycle of
length four and two transpositions. The Laplacian matrix of this topology is as below,


−w12
0
−w1234 
 w1234 + w12


 −w1234 − w12 w1234 + w12

0
0


LU = 
,


0
−w1234
w1234 + w34
−w34




0
−w23
−w1234 − w34 w1234 + w34
The weight on edges of the cycle and the transposition are denoted by w1234 and w12 , respectively.
This topology has four induced graphs of sizes 4, 6, 12 and 24. We denote the Laplacian matrices
of these induced graphs by L4 , L6 , L12 , L24 and the second smallest eigenvalues of each one of these
matrices by λ2 (L4 ), λ2 (L6 ), λ2 (L12 ) and λ2 (L24 ). L4 is identical to the Laplacian matrix of the underlying
graph of the topology. The smallest eigenvalue of each one of these Laplacian matrices is zero. Using
the intertwining relation [11] between laplacian matrices of the induced graphs, we can state that all
eigenvalues of L4 , L6 and L12 are amongst those of L6 , L12 and L24 , respectively. Since L12 includes
all irreducible representations of L24 (except the one corresponding to the largest eigenvalue) then based
on [12], it can be concluded that all eigenvalues of L24 (except its largest eigenvalue) are amongst the
eigenvalues of L12 . Therefore, the convergence rates to the synchronous and consensus states are equal
to λ2 (L4 ) and λ2 (L12 ), respectively.
As depicted in figure 4, the boundary of the pareto region for this topology is bounded by lines λCons =
λSynch and λSynch = 0.25 and two concave curves. The line λCons = λSynch stretches between points
λCons = λSynch = 0 and λCons = λSynch = 0.1326 where the latter point is obtained for w1234 = 0.09745,
w12 = 0.1548, w34 = 0.1503 and it is denoted as point A in figure 4. The vertical line λSynch = 0.25
stretches between points λCons = 0, λSynch = 0.25 and λCons = 0.1699, λSynch = 0.25 where the latter
point is obtained for w1234 = 0.1535, w12 = 0.097, w34 = 0.096 and it is denoted as point C in figure 4.
Note that this point is the global optimal point in regards to the convergence rates of the algorithm to both
consensus and synchronous states. The point that two boundary curves meet each other is λCons = 0.15457,
λSynch = 0.19731 which is obtained for w1234 = 0.11995, w12 = 0.212, w34 = 0.0481 and it is denoted

16

Fig. 4.

Pareto region for λCons and λSynch of the graph G1 (4).

as point B in figure 4.
V. C ONCLUSIONS
Considering a network of qudits, we have studied the convergence rate of the distributed consensus
algorithm with general (i.e. either directed or undirected) underlying topology towards consensus and
synchronous states. We have established that the convergence rate to both states are equal iff the Aldous’
conjecture holds true. In case of networks that their underlying graph contains cycles, the Aldous’
conjecture does not necessary hold true and it should be analyzed per case for each combination of
weights. In our future work, we will study the relation between the convergence rates and the Aldous’
conjecture by relaxing the consensus state to a symmetric state which is invariant to only a subset of
all permutations. Other future studies will focus on analysing the discrete-time model of the quantum
consensus algorithm and the quantum gossip algorithm over quantum networks with general underlying
topologies.
R EFERENCES
[1] S. Boyd and L. Vandenberghe, Convex Optimization,

Cambridge University Press, New York, NY, USA. 2004.

[2] L. Xiao and S. Boyd, Fast Linear Iterations for Distributed Averaging,

Systems and Control Letters, vol. 53, pp. 65-78, 2004.

17

[3] P. Caputo and T. M. Liggett, Proof of Aldous spectral gap conjecture,
[4] F. R. K. Chung, Spectral graph theory,

Journal American Math Society, vol. 23, pp. 831-851, 2010.

American Mathematical Society, 1997.

[5] S. Jafarizadeh, Distributed coding and algorithm optimization for large-scale networked systems,

Ph.D. Dissertation. University of

Sydney, NSW, 2015.
[6] L. Mazzarella, A. Sarlette and F. Ticozzi, A new perspective on gossip iterations: From Symmetrization to quantum consensus,

IEEE

52nd Annual Conference on Decision and Control (CDC), pp. 250-255, 2013.
[7] L. Mazzarella, A. Sarlette and F. Ticozzi, Consensus for Quantum Networks: Symmetry From Gossip Interactions,

IEEE Trans.

Automat. Control, vol. 60, no. 1, pp. 158-172, Jan. 2015.
[8] G. Shi, D. Dong, I. R. Petersen and K. Johansson, Reaching a Quantum Consensus: Master Equations that Generate Symmetrization
and Synchronization,

IEEE Trans. Automat. Control, pp. 1-14, 2015.

[9] G. Shi, S. Fu and I. R. Petersen, Quantum network reduced-state synchronization part I-convergence under directed interactions,
American Control Conference (ACC), 2015.
[10] G. Shi, S. Fu and I. R. Petersen, Quantum network reduced-state synchronization part II-the missing symmetry and switching interactions,
American Control Conference (ACC), pp. 92-97, 2015.
[11] S. Jafarizadeh, Optimizing the Convergence Rate of the Continuous Time Quantum Consensus,

arXiv 1509.05823, 2015.

[12] S. Jafarizadeh, Optimizing the Convergence Rate of the Quantum Consensus: A Discrete Time Model,

arXiv 1510.05178v2, 2015.

