C_{r_{0}}^{r_{0}+n}\right)\geqslant\mathbf{Pr}\left(E\mid
C_{r_{0}}^{r_{0}+n},D_{s_{0}}\leqslant
n\right)\mathbf{Pr}\left(D_{s_{0}}\leqslant n\mid C_{r_{0}}^{r_{0}+n}\right)$
(120)

Since each edge chooses its destination uniform at random among the nodes in
the network, we have that

$\mathbf{Pr}\left(E\mid C_{r_{0}}^{r_{0}+n},D_{s_{0}}\leqslant
n\right)\geqslant\left(1-\frac{1}{0.9n}\right)^{dn}\geqslant e^{-2d}$ (121)

Replacing and (121) and (120) in (119) we get

$\mathbf{Pr}\left(E\mid
C_{r_{0}}^{r_{0}+n}\right)\geqslant\frac{(1-e^{-1})e^{-2d}}{2}$ (122)

Finally, from (118), since $A$ and $E$ are independent and because of (116)
and (122)

$\mathbf{Pr}\left(|I_{t}|\leqslant d+1\hbox{ for all $t\geqslant
t_{0}$}\right)\geqslant\mathbf{Pr}\left(A\cap E\mid
C_{r_{0}}^{r_{0}+n}\right)\mathbf{Pr}\left(C_{r_{0}}^{r_{0}+n}\right)\geqslant\frac{(1-e^{-1})e^{-2d}}{8}\cdot\left(\frac{e^{-2d}}{20}\right)^{d}=c(d)\,.$

Finally, as for the stated linear bound on the flooding time $\tau$, we
observe this is an easy consequence of Lemma 4.10. Indeed, in the network
there are at least $\frac{1}{18}e^{-2d}n$ isolated nodes that will remain
isolated for the rest of their lifetime: to have all the nodes informed, we
have to wait that these nodes leave the network, and so $\tau=\Omega_{d}(n)$.

####  7.2.4 Proof of Theorem 4.13

We begin by reminding the reader that, in order to account for the fact that a
live node might die at any point of a given flooding interval, the proof of
Theorem 4.13 uses the discretized version of the flooding process described by
Definition 4.3, which clearly provides a worst case scenario when we are
interested in proving lower bounds on the extent and upper bounds on the speed
of flooding. The first observation is that, without edge regeneration, the
distribution of links created by a node $v$ is uniform over the set of nodes
that were in the network as $v$ joined. In particular, this distribution does
not depend on past history of the network as is the case in the model with
edge regeneration, where death of a node triggers reallocation of incoming
links. We begin by showing a number of preliminary facts that will be useful
in the remainder of this proof. The first is the following lemma, which is
just a variant of Lemma 4.8 that is of easier use here.

######  Lemma 7.1 (Nodes’ lifetimes).

Let $G_{t}=(N_{t},E_{t})$ be a $\mathcal{G}(n,d)$ Poisson random graph. If $n$
is large enough, for every $t\geqslant 4n\log n$, each node in $N_{t}$ has
life $\leqslant 4n\log n$ with probability at least $1-1/n^{2}$.

###### Proof.

We condition on the event $\mathcal{E}=(|N_{t-4\log n}|\leqslant 2n)$. From
Lemma 4.4:

$\mathbf{Pr}\left(|N_{t-4\log n}|\leqslant 2n\right)\geqslant
1-\frac{1}{2n^{2}}.$

Next, for every $i\in N_{t}$ we define a binary variable $L_{i}$, such that
$L_{i}=1$ if $i$ is alive at time $t$. Note that, conditioned on the event
$\mathcal{E}$, each $\mathbf{Pr}\left(L_{i}\right)=1$ is exponential with
parameter $\mu=1/n$, hence:

$\mathbf{Pr}\left(L_{i}=1\mid\mathcal{E}\right)=e^{-\frac{4n\log
n}{n}}=\frac{1}{n^{4}},$

which implies:

$\mathbf{Pr}\left(\exists i\in N_{t-4n\log
n}:L_{i}=1\mid\mathcal{E}\right)\leqslant\frac{2}{n^{3}}.$

Denote by $\mathcal{O}$ the event that there exists a node with age higher
than $4n\log n$ at time $t$. We have:

$\mathbf{Pr}\left(\mathcal{O}\right)\leqslant\mathbf{Pr}\left(\exists i\in
N_{t-4n\log
n}:L_{i}=1\mid\mathcal{E}\right)\mathbf{Pr}\left(\mathcal{E}\right)+\mathbf{Pr}\left(\neg\mathcal{E}\right)\leqslant\frac{1}{n^{2}}.$

∎

The following fact is instead a simple corollary of Lemma 4.4.

######  Fact 7.2.

With probability at least $1-1/n^{2}$, $0.9n\leqslant N_{t}\leqslant 1.1n$,
for every $t\in[t_{0}-n^{2},t_{0}]$.

Now, assume $N_{t_{0}}=m$ and recall that $m\in[0.9n,1.1n]$ from Fact 7.2.
Next, we consider the number of nodes that die in the interval
$[t_{0},t_{0}+\log n]$.

######  Lemma 7.3.

With probability at least $1-1/n^{c}$, at most $4\log n$ nodes die in the
interval $[t_{0},t_{0}+\log n]$.

###### Proof.

Consider the generic node $i\in N_{t_{0}}$. We define a binary variable
$L_{i}(\tau)$, such that $L_{i}(\tau)=1$ if $i$ is alive at time $t_{0}+\tau$,
$L_{i}(\tau)=0$ otherwise. Clearly, since the death process follows the
exponential distribution with parameter $\mu=1/n$ and is thus memoryless, we
have:

$\mathbf{Pr}\left(L_{i}(\tau)=1\right)=e^{-\frac{\tau}{n}}\geqslant
1-\frac{\tau}{n}.,$

Denote by $Z$ the number of nodes that die in the interval $[t_{0},t_{0}+a\log
n]$. Setting $\tau=a\log n$ we immediately have:

$\mathbf{E}\left[Z\right]\leqslant m-m+\frac{m\log n}{n}\leqslant 1.1\log n,$

where we used $m\leqslant 1.1n$ with probability $1-1/n^{2}$. Finally, since
$Z=\sum_{i\in N_{t_{0}}}L_{i}(\log n)$ and since the $L_{i}(\log n)$’s are
independent, a simple application of Chernoff’s bound yields:

$\mathbf{Pr}\left(Z>4\log n\right)\leqslant e^{-1.1\log n},$

which proves our claim. ∎

Finally, we bound the number of nodes’ arrivals in an interval of logarithmic
duration starting at time $t_{0}$.

######  Lemma 7.4.

With probability at least $1-1/n^{c}$, at most $4\log n$ nodes join the
network in the interval $[t_{0},t_{0}+\log n]$.

###### Proof.

Nodes enter the system according to a Poisson process with rate $1$ in each
step, which corresponds to a Poisson process with rate $4\log n$ over an
interval of $4\log n$ steps. This fact and tail bounds for the Poisson
distribution imply the claim. ∎

We next prove that, starting from $s$ at time $t_{0}$, with probability
$1-2e^{-\frac{d}{576}}-o(1)$ we reach a fraction $1-e^{-\frac{d}{20}}$ of the
nodes that are in the network at time $t_{0}+T$, where $T=\mathcal{O}(\log
n/\log d+d)$. To this purpose, we apply the “onion skin” technique as we did
in Section 3.1.2, although with a number of more or less significant changes.
To begin, differently from the SDG model, we consider all nodes that are in
the system when the informed node joins the network at time $t_{0}$. On the
other hand, we completely disregard nodes that were born in the interval
$[t_{0},t_{0}+\log n]$ (i.e., we don’t count them as hits, though we keep into
account that they remove probability mass from destinations in $N_{t_{0}}$),
since their number is negligible with high probability from Lemma 7.4.
Conversely, we do need to consider nodes that die in the interval
$[t_{0},t_{0}+\log n]$, since their failure might in principle significantly
affect flooding. Removing them at the onset or at the end may be tricky, since
in both cases we need to argue that their removal has no significant
topological effects (we cannot simply assume an adversarial removal). To
sidestep these challenges, we remove each of them with probability $\log n/n$
(this is an upper bound on the probability that a node dies in the interval
$[t_{0},t_{0}+\log n]$) as we proceed.

In particular, we define an “extended” _onion-skin process_ , which is
dominated by the real flooding process. In this process, new links are
generated (with restrictions with respect to the original process) as flooding
unfolds (deferred decisions), while each new informed node has a chance to
independently die with probability $\log n/n$ upon receiving the information
for the first time, thus without any chance of informing other nodes of the
network, which clearly is a worst-case scenario.

##### The onion-skin process.

Denote by $S$ the set of nodes that were in the network at time $t_{0}$ and
let $m=|S|$. From Fact 7.2, we know that $m\in[0.9n,1.1n]$ with probability at
least $1-1/n^{2}$. We now build a map $h:S\rightarrow[m]$, so that for $v\in
S$, $h(v)=i$ if $v$ is the $i$-th youngest node in the system at time $t$.
Note that $h(s)=1$ by definition. We next define $Y=\\{v\in
N_{t}:h(v)\leqslant m/2\\}$ as the subset of _young_ nodes and $O=\\{v\in
N_{t}:h(v)\geqslant m/2+1\\}$ as the subset of _old_ nodes.

Starting from $s$, the onion-skin process builds a connected, bipartite graph,
so that young nodes are only connected to old ones. In particular, each
realization of this process generates a subset of the edges generated by the
original topology dynamics. Moreover, each iteration of the process
corresponds to a partial flooding in the original graph. Flooding is partial
since i) the network uses a subset of the edges that would be present in the
original graph and ii) every newly informed node tosses a coin and dies, with
probability equal to the overall probability of dying in the interval
$[t_{0},t_{0}+\log n]$.

The process unfolds over a suitble number $k$ of phases, with
$k=\mathcal{O}(\log n/\log d)$. Each phase corresponds to $2$ flooding rounds,
each consisting of two steps. In the following, we denote by $Y_{k}\subseteq
Y$ and $O_{k}\subseteq O$ the subsets of young and old nodes that are informed
by the end of phase $k$, respectively. In the remainder, we let
$O_{-1}=\emptyset$ for notational convenience and, without loss of generality,
we use the interval $[d]$ to number the links established by each vertex.

Onion-skin process (extended version): Phase $\mathbf{0}$: $Y_{0}=\\{s\\}$;
$O_{0}$ is obtained as follows: 1. $s$ establishes $d$ links. We let
$Z_{0}\subset O$ denote the subset of old nodes that are destinations of these
links. Links with endpoints in $Y$ are discarded; 2. Let $R$ the subset
obtained by removing each vertex in $Z_{0}$ (and the just established links)
independently, with probability $\log n/n$. $O_{0}=Z_{0}-R$; Phase
$\mathbf{k}\geqslant 1$: (two flooding steps) 1.a Each node in $Y-Y_{k-1}$
establishes links $\\{1,\ldots,d/2\\}$. Denote by $W_{k}\subseteq Y-Y_{k-1}$
the subset of nodes with at least one link to nodes in $O_{k-1}-O_{k-2}$.
Links to nodes in $Y$ are again discarded; 1.b Let $R$ the subset obtained by
removing each vertex in $W_{k}$ (and the just established links)
independently, with probability $\log n/n$. $Y_{k}-Y_{k-1}=W_{k}-R$; 2.a Each
node in $Y_{k}-Y_{k-1}$ establishes links $\\{d/2+1,\ldots,d\\}$. Denote by
$Z_{k}$ the subset of nodes in $O-O_{k-1}$ that are reached by at least one
such link. Links to nodes in $Y$ are discarded; 2.b Let $R$ the subset
obtained by removing each node in $Z_{k}$ (and the links just established)
independently, with probability $\log n/n$. $O_{k}-O_{k-1}=Z_{k}-R$;

A couple remarks are in order. First of all, we are using the principle of
deferred decisions, delaying decision as to the establishment of a link
$(u,v)$ to the moment one of its endpoints is informed in the flooding
process. On the other hand, this means that the probability that the $j$-th
link originating from $u$ has $v$ as destination is equal to $1/N_{T_{r}}$ if
$u$’s arrival in the network corresponds to the $r$-th event. We use Lemma 7.1
and Fact 7.2 to claim that, with probability at least $1-1/n^{2}$ the above
probability fell in the interval $\left[\frac{1}{1.1n},\frac{1}{0.9n}\right]$
for every node in the network at time $t_{0}$. Second, the aforementioned
probabilities do not depend on nodes that joined or left the network in the
interval $[t_{0},t_{0}+\log n]$. Accordingly, all events we consider in the
remainder of this proof are conditioned on $\\{N_{t}\in[0.9n,1.1n],\forall
t\in[t_{0}-n^{2},t_{0}]\\}$ and on the ages of all nodes alive at time $t_{0}$
belonging to the interval $[1,\ldots,4n\log n]$. We omit these conditionings
for ease of notation.

We next analyze Phase 0 and the generic Phase $k$ separately. To this purpose,
we use the same random variables we defined in the proof of Theorem 3.7, whose
definition is repeated here to make the proof self-contained. For each
$i=1,\dots,d$, for each node $v\in N_{t_{0}}$ and for each set $A\subseteq
N_{t_{0}}$, we define the Bernoulli random variable $R_{v,A}$ as follows:

$R_{v,A}=\left\\{\begin{array}[]{l}1\quad\hbox{if $x\geqslant 1$ links in
}\\{\frac{d}{2},\dots,d\\}\hbox{ from $v$ have destination in $A$}\\\
0\quad\hbox{otherwise}\end{array}\right.$ (123)

Moreover, for each $i=1,\dots,d$ and for every $v\in N_{t_{0}}$ that joined
the network at time $\hat{t}\leqslant t_{0}$, we define the variable
$A_{v}^{(i)}\in N_{\hat{t}}$ as follows: $A_{v}^{(i)}=w$ if $w\in N_{\hat{t}}$
is the destination of the $i$-th link of $v$.

##### Analysis of phase $0$.

For phase $0$ we begin with the following claim.

######  Claim 7.5.

The following holds at the end of phase $0$:

$\mathbf{Pr}\left(|O_{0}|\geqslant\frac{d}{16}\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{d}{128}}\right).$ (124)

###### Proof.

We begin with step 1. Assume $v\in O$. We have:

$\mathbf{Pr}\left(\exists
i\in[d]:A_{s}^{(i)}=v\right)=1-\left(1-\frac{1}{m}\right)^{d},$

which implies

$\mathbf{E}\left[Z_{0}\right]=|O|\left(1-\left(1-\frac{1}{m}\right)^{d}\right)\geqslant|O|\frac{d}{2m}=\frac{d}{4},$

where the last equality follows since $|O|=m/2$. We next bound the probability
that $Z_{0}$ is smaller than $d/8$. To this purpose, we cannot simply apply a
Chernoff bound to the binary variables that describe whether or not a node
$v\in O$ was the recipient of at least one link originating from $s$, since
these are not independent. We instead resort to Theorem A.2. In particular,
similarly to what we did in the proof of Theorem 3.7, we define the function
$f(A_{s}^{(1)},\ldots,A_{s}^{(d)})=|Z_{0}|$. Clearly, $f$ is well-defined and
it satisfies the Lipschitz condition with values
$\beta_{1}=\cdots=\beta_{d}=1$, since changing the destination of one link can
affect the value of $|Z_{0}|$ by at most $1$. We can thus apply Theorem A.2 to
obtain:

$\mathbf{Pr}\left(|Z_{0}|<\frac{d}{8}\right)\leqslant\mathbf{Pr}\left(|Z_{0}|<\mathbf{E}\left[|Z_{0}|\right]-\frac{d}{8}\right)\leqslant
e^{-\frac{d}{128}}.$

We next obtain $O_{0}$. If $|Z_{0}|=x$ and $R$ is the number of nodes in
$Z_{0}$ that are removed, we have:

$\mathbf{E}\left[R\right]\leqslant\frac{ax\log n}{n}.$

Applying Markov’s inequality immediately yields

$\mathbf{Pr}\left(R\geqslant\frac{x}{2}\right)\leqslant\frac{2\log n}{n},$

whence the thesis immediately follows. ∎

##### Analysis of Phase $k$ \- step 1.

We next examine the number of nodes in $Y-Y_{k-1}$ that connect to nodes in
$|O_{k-1}-O_{k-2}|$ using their links belonging to the subset
$\\{d/2+1,\ldots,d\\}$.

######  Claim 7.6.

Assume that $|O_{k-1}-O_{k-2}|=y$ and $|Y_{k-1}|\leqslant m/10$. For
sufficiently large $n$, the following holds at the end of phase $k$:

$\displaystyle\mathbf{Pr}\left(|Y_{k}-Y_{k-1}|\geqslant\frac{yd}{48}\mid|O_{k-1}-O_{k-2}|=y\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{yd}{48}}\right),$ $\displaystyle
y\leqslant\frac{1.1n}{d}$ (125)
$\displaystyle\mathbf{Pr}\left(|Y_{k}-Y_{k-1}|\geqslant\frac{m}{20}\mid|O_{k-1}-O_{k-2}|=y\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{n}{240}}\right),$ $\displaystyle
y>\frac{1.1n}{d}.$ (126)

###### Proof.

It should be noted that i) no links originating from nodes in $Y-Y_{k-1}$ have
been established so far and ii) at this point we know that, for each $u\in
Y-Y_{k-1}$, none of its links in $\\{d/2+1,\ldots,d\\}$ had destination in
$O_{k-2}$, thus the probability of pointing to some vertex in
$O_{k-1}-O_{k-2}$ can only be magnified. With these premises, if $u\in
Y-Y_{k-1}$ we have:

$\mathbf{Pr}\left(R_{v,O_{k-1}-O_{k-2}}=1\mid|O_{k-1}-O_{k-2}|=y\right)=1-\left(1-\frac{y}{\ell}\right)^{\frac{d}{2}}>1-e^{-\frac{yd}{2\ell}},$

where $\ell\in[0.9n,1.1n]$ denotes the number of nodes when $u$ joined the
network. If $y\leqslant 1.1n/d$ we have $\frac{yd}{2\ell}<0.61$, which implies
$e^{-\frac{yd}{2\ell}}<\frac{2}{3}\frac{yd}{2\ell}$, whence:

$\mathbf{Pr}\left(R_{v,O_{k-1}-O_{k-2}}=1\mid|O_{k-1}-O_{k-2}|=y\right)>\frac{yd}{3\ell}>\frac{yd}{3.3n}.$

As a consequence, if $|Y_{k-1}|\leqslant m/10$:

$\mathbf{E}\left[|W_{k}|\mid|O_{k-1}-O_{k-2}|=y\right]>|Y-Y_{k-1}|\frac{yd}{3.3n}\geqslant\frac{2}{5}\frac{myd}{3.3n}>\frac{yd}{12},$

where in the last inequality we used $m\geqslant 0.9n$. On the other hand, the
$R_{v,O_{k-1}-O_{k-2}}$’s are independent. We can thus apply a standard
Chernoff bound to obtain:

$\mathbf{Pr}\left(|W_{k}|<\frac{yd}{24}\mid|O_{k-1}-O_{k-2}|=y\right)\leqslant
e^{-\frac{yd}{48}}.$

We next consider step 1.b. Assume $|W_{k}|=x$. If $R$ denotes the number of
vertices removed from $W_{k}$ we can argue exactly like for the analysis of
step 2 of Phase $0$ to obtain:

$\mathbf{Pr}\left(|Y_{k}-Y_{k-1}|\geqslant\frac{yd}{48}\mid|O_{k-1}-O_{k-2}|=y\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{yd}{48}}\right).$

Conversely, if $y>1.1n/d$ we have $\frac{yd}{2\ell}>1/2$, so that

$\mathbf{Pr}\left(R_{v,O_{k-1}-O_{k-2}}=1\mid|O_{k-1}-O_{k-2}|=y\right)>1-e^{-1/2}.$

In this case:

$\mathbf{E}\left[|W_{k}|\mid|O_{k-1}-O_{k-2}|=y\right]\geqslant|Y-Y_{k-1}|\left(1-\frac{1}{\sqrt{e}}\right)\geqslant\frac{2}{5}m\left(1-\frac{1}{\sqrt{e}}\right)>\frac{0.78}{5}m,$

which is both larger than $(2/15)m$ and $(2/15)n$ (the latter follows since
$m\geqslant 0.9n$). We therefore have:

$\mathbf{Pr}\left(|W_{k}|\geqslant\frac{m}{10}\mid|O_{k-1}-O_{k-2}|=y\right)\geqslant\mathbf{Pr}\left(|W_{k}|\geqslant\frac{3}{4}\mathbf{E}\left[|W_{k}|\right]\mid|O_{k-1}-O_{k-2}|=y\right)\leqslant
e^{-\frac{n}{240}}.$

Hence, arguing as we did before, we conclude:

$\mathbf{Pr}\left(|Y_{k}-Y_{k-1}|\geqslant\frac{m}{20}\mid|O_{k-1}-O_{k-2}|=y\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{n}{240}}\right).$

∎

##### Analysis of Phase $k$ \- step 2.

In this case, we are interested in nodes from $Y_{k}-Y_{k-1}$ that connect to
nodes in $O-O_{k-1}$ using their first $d/2$ links.

######  Claim 7.7.

Assume $|Y_{k}-Y_{k-1}|=x$ and $|O_{k-1}|\leqslant m/10$. For sufficiently
large $n$, the following holds at the end of phase $k$:

$\displaystyle\mathbf{Pr}\left(|O_{k}-O_{k-1}|\geqslant\frac{xd}{48}\mid|Y_{k}-Y_{k-1}|=x\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{xd}{576}}\right),$ $\displaystyle
x\leqslant\frac{1.1n}{d},$ (127)
$\displaystyle\mathbf{Pr}\left(|O_{k}-O_{k-1}|\geqslant\frac{m}{20}\mid|Y{k}-Y_{k-1}|=x\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\sqrt{n}}\right),$ $\displaystyle x>\frac{1.1n}{d}.$
(128)

###### Proof.

Assume $v\in O-O_{k-1}$. We have:

$\mathbf{Pr}\left(\exists u\in Y_{k}-Y_{k-1},\exists
i\in[d/2]:A_{u}^{(i)}=v\mid|Y_{k}-Y_{k-1}|=x\right)\geqslant
1-\left(1-\frac{1}{1.1n}\right)^{\frac{xd}{2}}>1-e^{-\frac{xd}{2.2n}}.$

As a consequence:

$\mathbf{E}\left[|Z_{k}|\mid|Y_{k}-Y_{k-1}|=x\right]>|O-O_{k-1}|(1-e^{-\frac{xd}{2.2n}}).$

We consider two cases, as we did in the proof of Claim 7.6. If
$x\leqslant\frac{1.1n}{d}$ we have:

$\mathbf{E}\left[|Z_{k}|\mid|Y_{k}-Y_{k-1}|=x\right]\geqslant|O-O_{k-1}|\frac{xd}{3.3n}\geqslant\frac{2}{5}\frac{mxd}{3.3n}>\frac{xd}{12},$

where similarly to Claim 7.6, we used $|O_{k-1}|\leqslant m/10$ and
$m\geqslant 0.9n$. where the second inequality follows since i) $|O|=m/2$ and
ii) we are assuming $|Y_{k-1}|\leqslant m/10$. Again and differently from
Claim 7.6, we cannot simply concentrate, since the events
$\\{A_{u}^{(i)}=v\\}$ are negatively correlated as $v$ varies over
$O-O_{k-1}$. We again resort to Theorem A.2. In this case, we have
$\frac{xd}{2}$ links that are established (independently of each other) from
vertices in $Y_{k}-Y_{k-1}$. Consider the $xd/2$ variables
$\\{A_{u}^{(i)}\\}_{u\in Y_{k}-Y_{k-1},i\in[d/2]}$. The domain of
$A_{u}^{(i)}$ is the set $N_{t}$ if $u$ joined the system at time $t$, where
$0.9n\leqslant|N_{t}|\leqslant 1.1n$ with high probability, from Lemma 7.1 and
Fact 7.2. We then define the function $f(\\{A_{u}^{(i)}\\}_{u\in
Y_{k}-Y_{k-1},i\in[d/2]})=|Z_{k}|$. Like in the analysis of step 1 of Phase 0,
we note that $f$ satisfies the Lipschitz condition with constants
$\beta_{1}=\cdots=\beta_{\frac{xd}{2}}=1$. We can thus apply Theorem A.2 to
obtain:

$\displaystyle\mathbf{Pr}\left(|Z_{k}|<\frac{xd}{24}\mid|Y_{k}-Y_{k-1}|=x\right)\leqslant\mathbf{Pr}\left(|Z_{k}|<\mathbf{E}\left[|Z_{k}|\mid|Y_{k}-Y_{k-1}|=x\right]-\frac{xd}{24}\mid|Y_{k}-Y_{k-1}|=x\right)$
$\displaystyle\leqslant e^{-\frac{xd}{576}}.$

Finally, we remove nodes from $Z_{k}$ exactly as we did in Phase 0 and in step
1.b of Phase $k$. The analysis proceeds exactly the same, so that we can
conclude:

$\mathbf{Pr}\left(|O_{k}-O_{k-1}|\geqslant\frac{xd}{48}\mid|Y_{k}-Y_{k-1}|=x\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\frac{xd}{576}}\right).$

Conversely, if $x>1.1n/d$ we have $\frac{xd}{d}>\frac{1}{2}$, so that:

$\mathbf{Pr}\left(\exists u\in Y_{k}-Y_{k-1},\exists
i\in[d/2]:A_{u}^{(i)}=v\mid|Y_{k}-Y_{k-1}|=x\right)>1-e^{-1/2},$

whence:

$\mathbf{E}\left[|Z_{k}|\mid|Y_{k}-Y_{k-1}|=x\right]\geqslant|O-O_{k-1}|\left(1-\frac{1}{\sqrt{e}}\right)\geqslant\frac{2}{5}m\left(1-\frac{1}{\sqrt{e}}\right)>\frac{2}{15}m.$

Next, application of Theorem Theorem A.2 yields in this case:

$\displaystyle\mathbf{Pr}\left(|Z_{k}|<\frac{m}{10}\mid|Y_{k}-Y_{k-1}|=x\right)\leqslant\mathbf{Pr}\left(|Z_{k}|<\mathbf{E}\left[|Z_{k}|\right]-\frac{m}{30}\mid|Y_{k}-Y_{k-1}|=x\right)$
$\displaystyle\leqslant e^{-\frac{2m^{2}}{900xd}}\leqslant
e^{-\frac{m}{225d}}<e^{-\sqrt{n}},$

where the third inequality follows from $x\leqslant|Y|\leqslant m/2$, while
the fourth follows since $d$ is a constant and $m\geqslant 0.9$, so it holds
for sufficiently large $n$. Finally, proceeding like in Claim 7.6 (analysis of
step 1.b) we obtain:

$\mathbf{Pr}\left(|O_{k}-O_{k-1}|\geqslant\frac{m}{20}\mid|Y_{k}-Y_{k-1}|=x\right)\geqslant\left(1-\frac{2\log
n}{n}\right)\left(1-e^{-\sqrt{n}}\right).$

∎

Finally, Claims 7.5, 7.6 and 7.7 imply the following result.

######  Lemma 7.8 (Flooding completes, part 1).

For sufficiently large and constant $d\geqslant 1152$, there exist a constant
$c>0$ and $k=\mathcal{O}(\log n/\log d)$, such that:

$\mathbf{Pr}\left(|Y_{k}|\geqslant\left(\frac{m}{20}\right)\cap|O_{k}|\geqslant\left(\frac{m}{20}\right)\right)\geqslant
1-2e^{-\frac{d}{576}}-o(1).$ (129)

###### Proof.

Consider the generic $i$-th phase and assume i)
$|Y_{i-1}|,|O_{i-1}|<1.1n/d\leqslant n/10$ (i.e., $d\geqslant 11$) and ii)
$|O_{i-1}-O_{i-1}|\geqslant\left(\frac{d}{48}\right)^{2i-1}$. Then, Claims
7.5, 7.6 and 7.7 imply that, conditioned to i) and ii) we have:

$\displaystyle\mathbf{Pr}\left(|Y_{i}-Y_{i-1}|\geqslant\left(\frac{d}{48}\right)^{2i}\cap|O_{i}-O_{i-1}|\geqslant\left(\frac{d}{48}\right)^{2i+1}\right)$
(130) $\displaystyle\geqslant\left(1-\frac{2\log
n}{n}\right)^{2}\left(1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{2i}}\right)\left(1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{2i+1}}\right).$
(131)

Since $|Y_{i}|\geqslant|Y_{i}-Y_{i-1}|$ and $|O_{i}|\geqslant|O_{i}-O_{i-1}|$,
using the chain rule and (130), for

$k\geqslant\frac{\log\left(\frac{n}{20}\right)}{2\log\left(\frac{d}{48}\right)},$

at the end of phase $k$ we have:

$\mathbf{Pr}\left(|Y_{k}|\geqslant\frac{m}{20}\cap|O_{k}|\geqslant\frac{m}{20}\right)\geqslant\left(1-e^{-\sqrt{n}}\right)^{2}\left(1-\frac{2\log
n}{n}\right)^{2k+1}\left(1-e^{-\frac{d}{128}}\right)\prod_{i=1}^{2k+1}\left(1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{i}}\right).$
(132)

Let
$P=\prod_{i=1}^{2k+1}\left(1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{i}}\right)$.
We next show that $P\geqslant c$ for a suitable constant $c$. This is
equivalent to showing that $-\log P\leqslant c^{\prime}$, where
$c^{\prime}=\log\frac{1}{c}$. We have:

$\displaystyle-\log
P=-\sum_{i=1}^{2k+1}\log\left(1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{i}}\right)=\sum_{i=1}^{2k+1}\log\frac{1}{1-e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{i}}}\leqslant
2\sum_{i=1}^{2k+1}e^{-\frac{1}{12}\left(\frac{d}{48}\right)^{i}}$
$\displaystyle=2\sum_{i=0}^{2k}e^{-\frac{d}{576}\left(\frac{d}{48}\right)^{i}}<2e^{-\frac{d}{576}}\sum_{i=0}^{\infty}e^{-\left(\frac{d}{48}\right)^{i}}<2e^{-\frac{d}{576}},$

where the third inequality follows from $x\geqslant\log\frac{2}{2-x}$ for
$0\leqslant x\leqslant 1$ which, considered that $i\geqslant 1$, in our case
is certainly satisfied if
$\left(\frac{d}{48}\right)^{2}\geqslant\frac{1}{12}$, i.e., for $d$ a
sufficiently large, absolute constant. The fifth inequality follows since
$\frac{d}{576}+\left(\frac{d}{48}\right)^{i}\leqslant\frac{d}{576}\left(\frac{d}{48}\right)^{i}$,
whenever $d/576\geqslant 2$, while the last inequality follows since the
double exponential is dominated by a simple one, summing to a constant not
exceeding $1$. Proceeding like in the final steps of Claim 3.11 we obtain
$P>1-2e^{-\frac{d}{576}}$. Since

$\mathbf{Pr}\left(|Y_{k}|\geqslant\left(\frac{m}{20}\right)\cap|O_{k}|\geqslant\left(\frac{m}{20}\right)\right)\geqslant\left(1-e^{-\sqrt{n}}\right)^{2}\left(1-\frac{2\log
n}{n}\right)^{2k+1}\left(1-e^{-\frac{d}{128}}\right)P,$

the proof follows for sufficiently large $n$. ∎

##### Information spreading via the expansion of large subsets.

We finally show that, if at least $m/10$ nodes become informed (which occurs
with probability at least $1-2e^{-\frac{d}{576}}-o(1)$ within
$\mathcal{O}(\log n/\log d)$ flooding steps from Lemma 7.8), then at least
$(1-e^{-\frac{d}{20}})m$ nodes become informed within a further, constant
number of flooding steps, w.h.p.

To prove this, we leverage Lemma 4.11 and we proceed along the same lines as
Theorem 3.8 and in particular Lemma 3.12, albeit with the following
difference: in each flooding step, we need to account for the fact that a node
that was present at time $t_{0}$ might die before being informed (or right
upon being informed) and thus be unable to contribute to the flooding process.
We have the following

######  Lemma 7.9 (Flooding completes, part 2).

Under the hypotheses of Theorem 4.13, for some $\tau_{2}=\mathcal{O}(d)$ and
for $\tau_{1}=\mathcal{O}(\log n/\log d)$ as in Lemma 7.8, we have:

$\mathbf{Pr}\left(|I_{t_{0}+\tau_{1}+\tau_{2}}|\geqslant(1-e^{-\frac{d}{20}})m\right)\geqslant
1-2e^{-\frac{d}{576}}-o(1)\,.$ (133)

###### Proof.

The proof proceeds along the very same lines as Lemma 3.12, hence we only
discuss the differences.

If we start with $n/10$ informed nodes, in each flooding step the set of
informed nodes increases by a constant factor, exactly like in the proof of
Lemma 3.12, but this time we use Lemma 4.11 for the expansion. The main
difference is that, this time, each newly informed node has a chance to die.
Assume $S$ is the set of the newly informed nodes at the end of the generic
expansion/flooding step. Since we are interested in a constant number of
rounds, we can handle nodes’ deaths in a simplified way with respect to what
we did in the proof of Lemma 7.8. In particular, with high probability, at
most $4\log n$ nodes are removed from $S$ in worst-case fashion, but this
still implies that, with high probability, $|S|-4\log n$ new nodes have been
informed, thus the set of informed nodes has increased by a constant factor,
since $|S|=\Omega(n)$. If we iterate over a sufficiently large, _constant_
number $\tau_{2}=\mathcal{O}(d)$ of flooding steps, we can conclude, like in
the proof of Lemma 3.12, that $(1-e^{-\frac{d}{20}})m$ nodes have been
informed within time $t_{0}+\tau_{1}+\tau_{2}$. ∎

This last step concludes the proof of Theorem 4.13.

###  7.3 Proofs for the Poisson model with edge regeneration

####  7.3.1 Proof of Lemma 4.15

We define the following event avoiding the use of

$A_{u,v}=\\{\text{a fixed request of $u$ has destination $v$ at time
$T_{r}$}\\}\,.$ (134)

Notice that we avoid to index the specific request since the considered graph
process is perfectly symmetric w.r.t. the $d$ random requests of every node.
We first bound the probability that a fixed request of $u$ has destination $v$
when $v$ is younger than $u$. Calling $L_{r}$ the event

$L_{r}=\\{\hbox{each node in $N_{T_{r}}$ is born after time $T_{r-7n\log
n}$}\\}\cap\\{|N_{T_{i}}\in[0.9n,1.1n]\hbox{ with }i=r-7n\log n,\dots,r\\}$
(135)

from Lemma 4.4 and Lemma 4.8 we get that
$\mathbf{Pr}\left(L_{r}\right)\geqslant 1-1/n^{2}$. We notice that the event
$L_{r}$ means that, when each node in $N_{T_{r}}$ joined the network, the
network was composed by at least $0.9n$ nodes and at most $1.1n$ nodes. From
the law of total probability, we have

$\displaystyle\mathbf{Pr}\left(A_{u,v}\right)\leqslant\mathbf{Pr}\left(A_{u,v}\mid
L_{r}\right)+\frac{1}{n^{2}}\leqslant\frac{1}{0.9n}+\frac{1}{n^{2}}\leqslant\frac{1}{0.8n}\,,$
(136)

where $\mathbf{Pr}\left(A_{u,v}\mid L_{r}\right)\leqslant 1/0.9n$ since $u$
can choose $v$ only after a death of one of its neighbours, being $v$ younger
than $u$.

We now analyze the case in which $v$ is older than $u$, where $u$ is born at
step $T_{r-i}$. For the law of total probability,

$\displaystyle\mathbf{Pr}\left(A_{u,v}\right)\leqslant\mathbf{Pr}\left(A_{u,v}\mid
L_{r}\right)+\frac{1}{n^{2}}\,.$ (137)

So, the next step is to evaluate $\mathbf{Pr}\left(A_{u,v}\mid L_{r}\right)$.
For each $k\geqslant 1$ and $w\in N_{T_{k}}$, define the following event:

$\displaystyle D_{w,k}=\\{w\text{ dies at time }T_{k}\\}\,.$ (138)

To bound $\mathbf{Pr}\left(D_{w,k}\mid L_{r}\right)$, for each $k=r-i,\dots,r$
and $w\in N_{T_{k}}$, we use Lemma 4.7 to get
$\mathbf{Pr}\left(D_{w,k}\right)\leqslant 1/(1.8n)$, and, hence, for the
Bayes’ rule,

$\displaystyle\mathbf{Pr}\left(D_{w,k}\mid
L_{r}\right)=\frac{\mathbf{Pr}\left(D_{w,k}\cap
L_{r}\right)}{\mathbf{Pr}\left(L_{r}\right)}\leqslant\frac{\mathbf{Pr}\left(D_{w,k}\right)}{1-1/n^{2}}=\frac{1/1.8n}{1-1/n^{2}}\leqslant\frac{1}{1.7n}\,.$
(139)

Now, for each $j=r-i,\dots,r$, define the following events

$A_{u,v}^{j}=\\{\text{a fixed request of $u$ connects to $v$ at time
$T_{j}$}\\}\,,$ (140)

and write $A_{u,v}=\cup_{j=r-i}^{r}A_{u,v}^{j}$. Notice that there is some
difference between the probability distribution of $A_{u,v}^{r-i}$ and that of
$A_{u,v}^{j}$ for each $j>r-i$. Indeed, it holds that

$\mathbf{Pr}\left(A_{u,v}^{r-i}\mid L_{r}\right)\leqslant\frac{1}{0.9n}\,,$
(141)

since this is the probability that the request of $u$ has destination $v$ at
the time of $u$’s arrival (since $v$ is older than $u$). On the other hand,
for each $j=r-i+1,\dots,r$, thanks to the memoryless property of the
exponential distribution,

$\mathbf{Pr}\left(A_{u,v}^{j}\mid L_{r}\right)\leqslant
1\cdot\frac{1}{1.7n}\cdot\frac{1}{0.9n}\,.$ (142)

The above bound holds since any fixed request of $u$ can choose $v$ as
destination at round $T_{j}$ only if, at round $T_{j-1}$, $u$ is not connected
to $v$. So, the first factor $1$ in the r.h.s. of (142) is an upper bound on
the probability that, at time $T_{j-1}$, $u$ is not connected to $v$. The
second factor, $1/(1.7n)$, is the upper bound on the probability (conditional
to $L_{r}$ from (139)) that the node to which $u$ is connected dies at time
$T_{j}$. Moreover, $1/(0.9n)$ is the probability, conditional to $L_{r}$, that
the request of $u$ connects to $v$ at time $T_{j}$, if its neighbour is died
at time $T_{j}$.

So, recalling that $A_{u,v}=\cup_{j=r-i}^{r}A_{u,v}^{j}$, from (141) and
(142),

$\mathbf{Pr}\left(A_{u,v}\mid
L_{r}\right)\leqslant\sum_{j=r-i}^{r}\mathbf{Pr}\left(A_{u,v}^{j}\mid
L_{r}\right)\leqslant\frac{1}{0.9n}\left(1+\frac{i}{1.7n}\right)\,.$ (143)

Finally, since conditional to $L_{r}$ we have that $i\leqslant 7n\log n$,
using (143) into (137), the proof is completed.

####  7.3.2 Proof of Lemma 4.17

We proceed as in the proof of the analogous lemma in the SDGR model (Lemma
6.4): we want to show that two disjoint sets $S,T\subseteq N_{t}$, with
$|S|\leqslant n/\log^{2}n$ and $|T|=0.1|S|$, such that
$\partial_{out}(S)\subseteq T$, exist with negligible probability.

We recall the definition

$A_{S,T}=\\{\partial_{out}(S)\subseteq T\\}\,.$ (144)

Then, as for the event

$L_{r}=\\{\text{each node in $N_{T_{r}}$ is born after time $T_{r-7n\log
n}$}\\}\cap\\{|N_{T_{r}}|\in[0.9n,1.1n]\\}\,,$ (145)

from Lemma 4.4 and Lemma 4.8, we obtain
$\mathbf{Pr}\left(L_{r}\right)\geqslant 1-1/n^{2}$. So, for the law of total
probability,

$\displaystyle\mathbf{Pr}\left(\min_{0\leqslant|S|\leqslant
n/\log^{2}n}\frac{|\partial_{out}(S)|}{|S|}\leqslant
0.1\right)\leqslant\sum_{\begin{subarray}{c}|S|\leqslant n/\log^{2}n\\\
|T|=0.1|S|\end{subarray}}\mathbf{Pr}\left(A_{S,T}\mid
L_{r}\right)+\frac{1}{n^{2}}\,.$ (146)

The next step of the proof is to upper bound $\mathbf{Pr}\left(A_{S,T}\mid
L_{r}\right)$. From Lemma 4.15, since $L_{r}$ implies that all the active
nodes were born after time $T_{r-7n\log n}$,

$\mathbf{Pr}\left(A_{S,T}\mid L_{r}\right)\leqslant\left(\frac{|S\cup
T|}{0.8n}\left(1+\frac{7n\log
n}{1.7n}\right)\right)^{d|S|}\leqslant\left(\frac{|S\cup
T|}{0.8n}\left(1+5n\log n\right)\right)^{d|S|}\,.$ (147)

Notice that, since $|S|\leqslant n/\log^{2}n$, the above equation offers a
sufficiently small bound. So, combining (147) with (146), we obtain

$\displaystyle\mathbf{Pr}\left(\min_{0\leqslant|S|\leqslant
n/\log^{2}n}\frac{|\partial_{out}(S)|}{|S|}\leqslant
0.1\right)\leqslant\sum_{s=1}^{n/\log^{2}n}\binom{1.1n}{s}\binom{1.1n-s}{0.1s}\left(\frac{1.1s}{0.8n}(1+5n\log
n)\right)^{ds}+\frac{1}{n^{2}}\,.$ (148)

In the equation above, we bounded each binomial coefficient with the
inequality $\binom{n}{k}\leqslant\left(\frac{n\cdot e}{k}\right)^{k}$ for each
$k\leqslant n$ and $n\geqslant 2$. Then, by calculating the derivative of the
function $f(s)$ that represents each term of the sum, we derive that each of
such terms reaches its maximum at the extremes, i.e. in $s=1$ or in
$s=n/\log^{2}n$. So, we get that the sum in (148), if $d\geqslant 35$, is
bounded by $2/n^{2}$.

####  7.3.3 Proof of Theorem 4.20

As remarked in Subsection 4, the discretized version of the flooding process
(Definition 4.3) is always slower than the original one (Definition 4.2), so
we can analyze the former version along three consecutive phases.

_Phase 1: The Boostrap._ The first phase lasts until the source information
reaches a subset of size $n^{\epsilon}$, for some constant $\epsilon<1$ (in
our analysis we fix $\epsilon=1/10$).

######  Lemma 7.10 (Phase 1: The Bootstrap).

Under the hypotheses of Theorem 4.20 there is a $\tau_{1}=\mathcal{O}(\log n)$
such that, w.h.p.

$|I_{t_{0}+\tau_{1}}|\geqslant n^{1/10}\,.$

###### Proof.

Let $I_{t}$ be the set of informed nodes, with $t\geqslant t_{0}=T_{r_{0}}$
and $|I_{t}|\leqslant n^{1/10}$. We want to prove that, w.h.p.,
$I_{t}=I_{t}\cap N_{t+1}$, i.e. all the nodes in $I_{t}$ survive for a time
interval equal to $1$. Since the life of a node follows an exponential
distribution of parameter $1/n$, and since $|I_{t}|\leqslant n^{1/10}$, this
event has probability $e^{-|I_{t}|/n}\geqslant 1-1/n^{9/10}$. According to
Definition 4.3, we let $I_{t+1}=(I_{t}\cup\partial_{out}^{t}(I_{t}\cap
N_{t+1}))\cap N_{t+1}$ be the set of informed nodes at time $t+1$. Since the
graph $G_{t}$ is an expander of parameter $0.1$, w.h.p. (Theorem 4.16) and
since $I_{t}\cap N_{t+1}=I_{t}$ w.h.p., it holds w.h.p.

$|\partial_{out}^{t}(I_{t}\cap N_{t+1})|\geqslant 0.1|I_{t}|\,.$

Since $|I_{t}|\leqslant n^{1/10}$, all the nodes in
$\partial_{out}^{t}(I_{t}\cap N_{t+1})$ survive for a time interval equal to
$1$ with probability $e^{-0.1|I_{t}|/n}\geqslant 1-1/n^{9/10}$, so w.h.p.

$|I_{t+1}|\geqslant|(\partial_{out}^{t}(I_{t}\cap N_{t+1}))\cap
N_{t+1}|\geqslant 1.1|I_{t}|\,.$

It follows that, after a phase of length $\tau_{1}=\mathcal{O}(\log n)$, we
get $|I_{t_{0}+\tau_{1}}|\geqslant n^{1/10}$, w.h.p. ∎

_Phase 2: Exponential growth of the informed nodes._ In the next lemma, we
show that, after the bootstrap, the flooding process yields an exponential
increase of the number of informed nodes until it reaching half of the nodes
in the network.

######  Lemma 7.11 (Phase 2).

Under the same hypotheses of Theorem 4.20, there is a
$\tau_{2}=\mathcal{O}(\log n)$ such that, for $\tau_{1}=\mathcal{O}(\log n)$
(as in Lemma 7.10), w.h.p.

$|I_{t_{0}+\tau_{1}+\tau_{2}}|\geqslant\frac{|N_{t_{0}+\tau_{1}+\tau_{2}}|}{2}\,.$

###### Proof.

Observe first that in any interval of time equal to $1$, w.h.p. at most $2\log
n$ nodes leave the network. Indeed, the number of nodes that leave the network
in the time interval $[t,t+1]$ is a random variable

$D=\sum_{v\in N_{t}}D_{v}\,,$

where each $D_{v}$ is a Bernoulli random variable, such that
$\mathbf{Pr}\left(D_{v}=1\right)=1-e^{-1/n}$, which indicates if the node
$v\in N_{t}$ leaves the network before $t+1$. So, from Lemma 4.4 and the
Chernoff Bound (Theorem A.1),

$\mathbf{Pr}\left(D\geqslant 2\log n\right)\leqslant\frac{1}{n^{1/3}}\,.$
(149)

We recall that the set of infected nodes at time $t+1$ is
$I_{t+1}=(I_{t}\cup\partial_{out}^{t}(I_{t}\cap N_{t+1})\cap N_{t+1}$. Since
we have shown that, in the interval $[t,t+1]$, at most $2\log n$ nodes leave
the network w.h.p. and since the graph $G_{t}$ is a expander with parameter
$0.1$ w.h.p. (Theorem 4.16), it holds, w.h.p.,

$|I_{t+1}|\geqslant|I_{t}|+0.1\left(|I_{t}|-2\log n\right)-2\log n\,.$

So, for each $t\geqslant t_{0}+\tau_{1}$, since $|I_{t_{0}+\tau_{1}}|\geqslant
n^{1/10}$, w.h.p.

$|I_{t+1}|\geqslant 1.09|I_{t}|\,.$

We thus have an exponential growth of the set of the informed nodes and, so,
there exists $\tau_{2}=\mathcal{O}(\log n)$ such that
$|I_{t_{0}+\tau_{1}+\tau_{2}}|\geqslant|N_{t_{0}+\tau_{1}+\tau_{2}}|/2$,
w.h.p. ∎

_Phase 3: Exponential decrease of the non-informed nodes._ The analysis of
this phase considers the subset $S_{t}\subseteq N_{t}$ of the non-informed
nodes. More precisely, we prove that $S_{t+1}$ w.h.p. decreases by a constant
factor despite the node churn.

######  Lemma 7.12 (Phase 3).

Under the same hypotheses of Theorem 4.20, there is a
$\tau_{3}=\mathcal{O}(\log n)$ such that, for $\tau_{1}=\mathcal{O}(\log n)$
(as in Lemma 7.10) and $\tau_{2}=\mathcal{O}(\log n)$ (as in Lemma 7.11), we
have w.h.p.

$I_{t_{0}+\tau_{1}+\tau_{2}+\tau_{3}}=N_{t_{0}+\tau_{1}+\tau_{2}+\tau_{3}}\,.$

###### Proof.

To prove this lemma, we will consider the set $S_{t}\subseteq N_{t}$ of non
informed nodes at time $t$, i.e. $S_{t}=N_{t}-I_{t}$. Notice that, since every
node $v$ in $\partial_{out}^{t+1}(S_{t+1})\subseteq I_{t+1}$ is reachable in
1-hop to the set of non-informed nodes at time $t+1$, $v$ was not informed at
time $t$. This implies that

$\partial_{out}^{t+1}(S_{t+1})\subseteq(S_{t}-S_{t+1})\cap N_{t+1}\,.$

Consider the random variable $J_{t,t+1}$ that indicates the number of nodes
that join the network in the time interval $[t,t+1]$. Then, the above
consideration implies that

$|S_{t}|-|S_{t+1}|+J_{t,t+1}\geqslant|\partial_{out}^{t+1}(S_{t+1})|.$ (150)

Since $J_{t,t+1}$ is a Poisson random variable of parameter $1$, for the tail
bound for the Poisson distribution (Theorem 155), $J_{t,t+1}\leqslant\log n$,
w.h.p. Since
$|S_{t_{0}+\tau_{1}+\tau_{2}}|\leqslant|N_{t_{0}+\tau_{1}+\tau_{2}}|/2$
w.h.p., from the expansion of the graph $G_{t+1}$ (Theorem 4.16) it holds
w.h.p. that, for each $t\geqslant t_{0}+\tau_{1}+\tau_{2}$,

$|S_{t+1}|\leqslant\frac{1}{1.1}\left(|S_{t}|+\log n\right).$

Then, a time $\tau_{3}^{\prime}=\mathcal{O}(\log n)$ exists such that
$|S_{t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}}|\leqslant\log^{2}n$.

After the process reaches the above small number of non-informed nodes, we
consider the set of non-informed nodes at time $t$ without including the set
of nodes that join the network after time
$t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}$: we call the latter set as
$S_{t}^{*}$, for each $t\geqslant t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}$.
As in the first part of the proof, we get that
$\partial_{out}^{t+1}(S_{t+1}^{*})\subseteq(S_{t}^{*}-S_{t+1}^{*})\cap
N_{t+1}$. Since the graph $G_{t+1}$ is an expander w.h.p. (Theorem 4.16), we
have that w.h.p.

$|S_{t+1}^{*}|\leqslant\frac{1}{1.1}|S_{t}^{*}|.$

Since $|S_{t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}}^{*}|\leqslant\log^{2}n$,
there is a $\tau_{3}=\mathcal{O}(\log n)$ such that,
$|S_{t_{0}+\tau_{1}+\tau_{2}+\tau_{3}}^{*}|<1$ w.h.p.

In conclusion, let $J_{\tau_{3}^{\prime},\tau_{3}}$ be the number of nodes
that join the network from time $t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}$ to
time $t_{0}+\tau_{1}+\tau_{2}+\tau_{3}$. Since the arrival of the nodes during
an interval of length $\tau_{3}-\tau_{3}^{\prime}$ is a Poisson process of
mean $\tau_{3}-\tau_{3}^{\prime}$, for the tail bound for the Poisson
distribution (Theorem 155), w.h.p.
$J_{\tau_{3}^{\prime},\tau_{3}}=\mathcal{O}(\log n)$. Moreover, from Lemma
4.4, each of these new nodes connect to the set of informed nodes with
probability at least $(1-(2\log^{2}n/n)^{d})(1-1/n^{2})$. Moreover, each
informed node to which the new nodes have connected survive for the 1-hop
transmission with probability $e^{-1/n}\geqslant 1-\frac{1}{n}$. So, each node
that joins the network after time $t_{0}+\tau_{1}+\tau_{2}+\tau_{3}^{\prime}$
gets informed within time $t_{0}+\tau_{1}+\tau_{2}+\tau_{3}$, w.h.p. ∎

## References

  * [1] Zeyuan Allen-Zhu, Aditya Bhaskara, Silvio Lattanzi, Vahab Mirrokni, and Lorenzo Orecchia.  Expanders via local edge flips.  In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 259–269. Society for Industrial and Applied Mathematics, 2016.
  * [2] J. Augustine, G. Pandurangan, P. Robinson, S. Roche, and E. Upfal.  Enabling robust and efficient distributed computation in dynamic peer-to-peer networks.  In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 350–369, 2015.
  * [3] John Augustine, Gopal Pandurangan, and Peter Robinson.  Distributed algorithmic foundations of dynamic networks.  ACM SIGACT News, 47(1):69–98, 2016.
  * [4] John Augustine, Gopal Pandurangan, Peter Robinson, and Eli Upfal.  Towards robust and efficient computation in dynamic peer-to-peer networks.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’12, page 551–569, USA, 2012. Society for Industrial and Applied Mathematics.
  * [5] Baruch Awerbuch and Christian Scheideler.  The hyperring: A low-congestion deterministic data structure for distributed environments.  In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’04, page 318–327, USA, 2004. Society for Industrial and Applied Mathematics.
  * [6] Andrea E. F. Clementi, Claudio Macci, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri.  Flooding time of edge-markovian evolving graphs.  SIAM Journal on Discrete Mathematics, 24(4):1694–1712, 2010.
  * [7] Andrea E. F. Clementi, Angelo Monti, Francesco Pasquale, and Riccardo Silvestri.  Information spreading in stationary markovian evolving graphs.  IEEE Trans. Parallel Distrib. Syst., 22(9):1425–1432, 2011.
  * [8] Colin Cooper, Martin Dyer, and Catherine Greenhill.  Sampling regular graphs and a peer-to-peer network.  Combinatorics, Probability and Computing, 16(4):557–593, 2007.
  * [9] Bitcoin Core.  Bitcoin Core 0.11 (ch 4): P2P Network.  https://en.bitcoin.it/wiki/Bitcoin_Core_0.11_(ch_4):_P2P_Network.  Accessed: 2020-07-15.
  * [10] Sergi Delgado-Segura, Surya Bakshi, Cristina Pérez-Solà, James Litton, Andrew Pachulski, Andrew Miller, and Bobby Bhattacharjee.  Txprobe: Discovering bitcoin’s network topology using orphan transactions.  In International Conference on Financial Cryptography and Data Security, pages 550–566. Springer, 2019.
  * [11] Devdatt Dubhashi and Alessandro Panconesi.  Concentration of Measure for the Analysis of Randomized Algorithms.  Cambridge University Press, USA, 1st edition, 2009.
  * [12] Philippe Duchon and Romaric Duvignau.  Local update algorithms for random graphs.  In Alberto Pardo and Alfredo Viola, editors, LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, volume 8392 of Lecture Notes in Computer Science, pages 367–378. Springer, 2014.
  * [13] Riko Jacob, Andrea Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig.  A distributed polylogarithmic time algorithm for self-stabilizing skip graphs.  In Proceedings of the 28th ACM Symposium on Principles of Distributed Computing, PODC ’09, page 131–140, New York, NY, USA, 2009. Association for Computing Machinery.
  * [14] J.R.Norris.  Markov Chains.  Cambridge University Press, 1998.
  * [15] Fabian Kuhn, Nancy Lynch, and Rotem Oshman.  Distributed computation in dynamic networks.  In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 513–522, New York, NY, USA, 2010. Association for Computing Machinery.
  * [16] Fabian Kuhn and Rotem Oshman.  Dynamic networks: Models and algorithms.  SIGACT News, 42(1):82–96, March 2011.
  * [17] Ching Law and K-Y Siu.  Distributed construction of random expander networks.  In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications (INFOCOM 2003), volume 3, pages 2133–2143. IEEE, 2003.
  * [18] Peter Mahlmann and Christian Schindelhauer.  Peer-to-peer networks based on random transformations of connected regular undirected graphs.  In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, SPAA ’05, page 155–164, New York, NY, USA, 2005. Association for Computing Machinery.
  * [19] Yifan Mao, Soubhik Deb, Shaileshh Bojja Venkatakrishnan, Sreeram Kannan, and Kannan Srinivasan.  Perigee: Efficient peer-to-peer network design for blockchains.  In Proc. of the ACM Symposium on Principles of Distributed Computing, to appear, 2020.  Technical report available at https://arxiv.org/abs/2006.14186.
  * [20] Othon Michail.  An introduction to temporal graphs: An algorithmic perspective.  Internet Mathematics, 12(4):239–280, 2016.
  * [21] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  https://bitcoin.org/bitcoin.pdf, 2008.
  * [22] Till Neudecker, Philipp Andelfinger, and Hannes Hartenstein.  Timing analysis for inferring the topology of the bitcoin peer-to-peer network.  In 2016 Intl IEEE Conferences on Ubiquitous Intelligence & Computing, Advanced and Trusted Computing, Scalable Computing and Communications, Cloud and Big Data Computing, Internet of People, and Smart World Congress (UIC/ATC/ScalCom/CBDCom/IoP/SmartWorld), pages 358–367. IEEE, 2016.
  * [23] Gopal Pandurangan, Prabhakar Raghavan, and Eli Upfal.  Building low-diameter peer-to-peer networks.  IEEE Journal on selected areas in communications, 21(6):995–1002, 2003.  Preliminary version in FOCS’01.
  * [24] Gopal Pandurangan and Amitabh Trehan.  Xheal: A localized self-healing algorithm using expanders.  Distrib. Comput., 27(1):39–54, February 2014.
  * [25] Addy Yeow.  Global Bitcoin Nodes Distribution.  https://bitnodes.io/.  Accessed: 2020-07-15.

Appendix

##  Appendix A Mathematical tools

######  Theorem A.1 (Chernoff Bound, [11]).

Let $X_{1},\dots,X_{n}$ be independent Poisson trials such that
$\mathbf{Pr}\left(X_{i}=1\right)=p_{i}$. Let $X=\sum_{i=1}^{n}X_{i}$,
$\mu=\mathbf{E}\left[X\right]$ and suppose
$\mu_{L}\leqslant\mu\leqslant\mu_{H}$. Then, for all $0<\varepsilon\leqslant
1$ the following Chernoff bounds hold

$\mathbf{Pr}\left(X\geqslant(1+\varepsilon)\mu_{H}\right)\leqslant
e^{-\frac{\varepsilon^{2}}{3}\mu_{H}}$ (151)
$\mathbf{Pr}\left(X\leqslant(1-\varepsilon)\mu_{L}\right)\leqslant
e^{-\frac{\varepsilon^{2}}{2}\mu_{L}}\,.$ (152)

######  Theorem A.2 (Method of bounded differences,[11]).

Let $\mathbf{Y}=(Y_{1},\dots,Y_{m})$ be independent random variables, with
$Y_{j}$ taking values in the set $A_{j}$. Suppose the real-valued function $f$
defined on $\prod_{j}A_{j}$ satisfies the Lipschitz condition with
coefficients $\beta_{j}$, i.e.

$|f(\mathbf{y})-f(\mathbf{y^{\prime}})|\leqslant\beta_{j}$

whenever vectors $\mathbf{y}$ $\mathbf{y^{\prime}}$ differs only in the $j$-th
coordinate. Then, for any $M>0$, it holds that

$\mathbf{Pr}\left(f(\mathbf{Y})\geqslant\mathbf{E}\left[f(\mathbf{Y})\right]+M\right)\leqslant
e^{-\frac{2M^{2}}{\sum_{j=1}^{m}\beta_{j}^{2}}}\,,$

and

$\mathbf{Pr}\left(f(\mathbf{Y})\leqslant\mathbf{E}\left[f(\mathbf{Y})\right]-M\right)\leqslant
e^{-\frac{2M^{2}}{\sum_{j=1}^{m}\beta_{j}^{2}}}\,.$

######  Theorem A.3 (Kullback-Leibler divergence inequality).

Let $p_{m}$ and $q_{m}$ be two discrete probability mass functions, with
$m\in\\{1,\dots,L\\}$. We have that

$\sum_{r=1}^{L}p_{m}\log_{2}\left(\frac{p_{m}}{q_{m}}\right)\geqslant 0\,.$
(153)

##  Appendix B Static Random Graphs

######  Lemma B.1.

The static random graph in which each node picks $d$ random neighbors is a
$\Theta(1)$-expander w.h.p., for each $d\geqslant 3$.

###### Proof.

We consider the static random graph $G=(N,E)$ and $S\subset N$ a subset of the
nodes with $|S|=s$. Let $T\subseteq N-S$ be an arbitrary set disjointed from
$S$, with $|T|=0.1s$. In this model we know that an edge starting from a node
$v$ has destination $u$ with probability $\frac{1}{n-1}$. We know that the
probability that the edges from $S$ are in $S\cup T$

$\left(\frac{|S\cup T|}{n-1}\right)^{d|S|}\,.$

So, the probability that the outer boundary of $S$ is at most in $T$ is

$\mathbf{Pr}\left(\partial_{out}(S)\subseteq
T\right)\leqslant\left(\frac{1.1s}{n-1}\right)^{ds}.$

From an union bound over all the set $T$ disjointed with $S$ and with
$|T|=0.1s$, all the set $S$ with $s$ elements and all the possible sizes
$s=1,\dots,n/2$ of $s$ we get

$\mathbf{Pr}\left(\text{$G$ is not an
expander}\right)\leqslant\sum_{s=1}^{n/2}\binom{n}{s}\binom{n-k}{0.1s}\left(\frac{1.1s}{n-1}\right)^{ds}\,.$
(154)

From standard calculus, it can be proved that, for $d\geqslant 3$, the
equation above is upper bounded by $1/n^{d-2}$. This is obtained by bounding
each binomial coefficient with the bound
$\binom{n}{k}\leqslant\left(\frac{n\cdot e}{k}\right)^{k}$ and by computing
the derivative of the function $f(s)$ (representing each term of the sum),
obtaining that each of these terms attained its maximum in $s=1$ or in
$s=n/2$. ∎

##  Appendix C Useful Tools for the Poisson Models

######  Definition C.1 (Counting process).

The stochastic process $\\{X(t),t\geqslant 0\\}$ is said to be a _counting
process_ if $X(t)$ represents the total number of events which have occurred
up to time $t$.

######  Definition C.2.

Let $\\{X(t),t\geqslant 0\\}$ be a counting process. It is a _Poisson process_
if

  1. 1.

$X(0)=0$;

  2. 2.

$X(t)$ has independent increments;

  3. 3.

The number of events in any interval of length $t$ has a Poisson distribution
with mean $\lambda t$. That is, for all $s,t\geqslant 0$

$\textbf{Pr}\left(X(t+s)-X(s)=n\right)=e^{-\lambda t}\frac{(\lambda
t)^{n}}{n!}\quad n\geqslant 0\,.$

######  Theorem C.3.

Let $\\{X(t),t\geqslant 0\\}$ be a Poisson process. Then, given $X(t)=n$, the
$n$ arrival times $S_{1},\dots,S_{n}$ have the same distribution as the order
statistics corresponding to $n$ independent random variables uniformly
distributed in the interval $(0,t)$.

######  Theorem C.4 (Tail bound for the Poisson distribution).

Let $X$ have a Poisson distribution with mean $\lambda$. Then, for each
$\varepsilon>0$,

$\textbf{Pr}\left(\left|X-\lambda\right|\geqslant x\right)\leqslant
2e^{-\frac{x^{2}}{2(\lambda+x)}}$ (155)

######  Theorem C.5 ([14]).

Let $I$ be a countable set and let $T_{k}$, $k\in I$, be independent
exponential random variables of parameter $q_{k}$. Let $0<q=\sum_{j\in
I}q_{k}\leqslant\infty$. Set $T=\inf_{k}T_{k}$. Then this infimum is attained
at a unique random value $K$ of $k$, with probability $1$. Moreover, $T$ and
$K$ are independent with $T$ exponential of parameter $q$ and
$\mathbf{Pr}\left(K=k\right)=q_{k}/q$.


# IQGAN: Robust Quantum Generative Adversarial Network
for Image Synthesis On NISQ Devices

###### Abstract

In this work, we propose IQGAN, a quantum Generative Adversarial Network (GAN)
framework for multiqubit image synthesis that can be efficiently implemented
on Noisy Intermediate Scale Quantum (NISQ) devices. We investigate the reasons
for the inferior generative performance of current quantum GANs in our
preliminary study and conclude that an adjustable input encoder is the key to
ensuring high-quality data synthesis. We then propose the IQGAN architecture
featuring a trainable multiqubit quantum encoder that effectively embeds
classical data into quantum states. Furthermore, we propose a compact quantum
generator that significantly reduces the design cost and circuit depth on NISQ
devices. Experimental results on both IBM quantum processors and quantum
simulators demonstrated that IQGAN outperforms state-of-the-art quantum GANs
in qualitative and quantitative evaluation of the generated samples, model
convergence, and quantum computing cost.

Index Terms—  Quantum machine learning, generative adversarial networks, noisy
intermediate-scale quantum

##  1 Introduction

Related Work and Motivation. The recent success of supervised Neural Networks
(QNNs) [1, 2, 3, 4] has inspired several quantum Generative Adversarial
Network (GAN) frameworks [5, 6, 7, 8, 9] that extend the application of QNNs
to unsupervised generative learning. A GAN [10, 11] consists of a generator
(G) that generates synthetic samples, and a discriminator (D) that tries to
distinguish between true and fake data. Such an adversarial game converges to
the point where G generates the same statistics as the true data and D is
unable to discriminate between the true and generated data. Lloyd et al. [6]
theoretically proved that quantum GANs exhibit potential exponential
advantages over classical GANs in high-dimensional data synthesis. QuGAN18 [7]
presented an implementation of quantum GAN, which however, suffers from
convergence issues. QuGAN21 [8] and EQ-GAN [9] showed that a quantum fidelity
based loss function stabilizes the training process, but both works generate
data with low quality and require high implementation cost. In this work, we
are motivated to advance previous work [8, 9] by proposing IQGAN, a robust
multiqubit Quantum Generative Adversarial Network architecture for Image
synthesis that can be efficiently implemented on today’s noisy intermediate-
scale quantum (NISQ) devices. We summarize the comparisons between IQGAN and
state-of-the-arts (SOTA) quantum GANs in Table 1.

Table 1: Comparisons between IQGAN and previous works (Conv: Convergence; MultiQ: multiple-qubit output). Scheme | Loss | Conv | MultiQ | Quality | Cost
---|---|---|---|---|---
QGAN [6] | N/A | N/A | N/A | N/A | N/A
QuGAN18 [7] | Trace | ✘ | ✘ | Med. | High
QuGAN21 [8] | Fidelity | ✔ | ✔ | Low | High
EQ-GAN [9] | Fidelity | ✔ | ✘ | Low | Med.
IQGAN | Fidelity | ✔ | ✔ | High | Low

Our Contributions. This work makes the following contributions. (1) We study
the reasons for the low generative performance in previous work [8, 9] and
conclude that the standard quantum encoders limit the generative ability of a
quantum GAN. We then propose a trainable multiqubit quantum encoder that
achieves SOTA quality on the generated data (Section 3.1); (2) We present a
compact generator circuit ansatz that reduces hardware cost and circuit depth
compared with previous work [8, 9] (Section 3.2); (3) We demonstrate that
IQGAN can be efficiently implemented on NISQ devices and provide the training
procedure (Section 3.3); (4) We evaluate IQGAN on both IBM quantum processors
and simulators and show that IQGAN outperforms the prior arts in qualitative
and quantitative evaluations of the generated samples, model convergence, and
quantum computing cost (Section 4).

Limitations and Scope. The potential exponential advantage of quantum GANs
over classical GANs is proved in [6]. In this work, we focus on the situation
where the data is classical while the generator and discriminator are quantum,
same as [8]. We implement a small-scale IQGAN and evaluate its performance
against prior arts on MNIST dataset – a small dataset considered by classical
machine learning but SOTA dataset on QNN evaluation [8, 12, 13, 14]. The
limitations on the scale of the implementation and the dataset are due to the
NISQ technology capabilities. The implementation scale of IQGAN and its
corresponding generative performance will improve with the rapidly improving
technology. IQGAN demonstrates how NISQ computers can be used to perform
nontrivial generative learning tasks with a reasonable performance by
overcoming the current quantum obstacles.

##  2 Background and Preliminary Analysis

###  2.1 Quantum GANs Background

Figure 1 shows the mainstream quantum GAN (QGAN) architecture [8, 9], which
consists of (1) a data encoder S($\mathbf{x}$) that embeds a real classical
input $\mathbf{x}$ to a quantum state $|\psi_{\sigma}\rangle$; (2) a
Variational Quantum Circuit (VQC) based generator G($\mathbf{\theta_{g}}$)
that generates synthetic data represented as a quantum state
$|\psi_{\rho}(\theta_{g})\rangle$; and (3) a SWAP test based discriminator
D($|\psi_{\sigma}\rangle$, $|\psi_{\rho}\rangle$) that measures the fidelity
between the real data $|\psi_{\sigma}\rangle$ and the fake data
$|\psi_{\rho}\rangle$. Due to the limited number of qubits in NISQ devices,
high-dimensional inputs are down-sampled using Principal Component Analysis
(PCA) [8], while the generated data is obtained by first measuring the qubits
of the generator, i.e., $q_{3},q_{4}$ in Figure 1, on the probability of the
$|0\rangle$ state, and then transforming the measured vector into a high-
dimensional data using inverse PCA. Note that we consider two-qubit inputs and
a G($\mathbf{\theta_{g}}$) with a single circuit block as an example. The
input size and number of blocks in G($\mathbf{\theta_{g}}$) can be adjusted to
fit the problem of interest.

Classical-to-Quantum Encoder, S($\mathbf{x}$). Angle encoding is the most
widely used method in QNNs [8, 13, 14, 15] due to its noise immunity and
simplicity of implementation. Angle encoding encodes an $N$-dimensional data
as the radians of rotation gates acting on $N$ qubits, i.e.,
$|\psi_{\mathbf{x_{i}}}\rangle$=(R($x_{i}$)$|0\rangle$)⊗N, where R can be one
of or a combination of the rotate gates {RX, RY, RZ} and $\otimes$ represents
the tensor product operation.

VQC Circuit Ansatz, G($\mathbf{\theta_{g}}$). Mainstream QNNs [13, 16, 17]
adopt a VQC ansatz constructed by parameterized single-qubit rotation gates
followed by nearest-neighbor coupling of qubits using fixed two-qubit CNOT
gates, as illustrated in Figure 1. Such a circuit ansatz has demonstrated
superior expressive capability in various applications. The logic behind such
designs is that single-qubit rotations provide a way to parameterize circuits,
while two-qubit CNOT gates provide maximal entanglement between the two target
qubits.

SWAP Test Circuit, D($|\psi_{\sigma}\rangle$, $|\psi_{\rho}\rangle$). A SWAP
test circuit is a standard quantum module used for quantum fidelity
measurement. As shown in Figure 1, it consists of one ancillary qubit $q_{0}$,
two Hadamard gates (i.e., H gate), and several controlled SWAP gates (i.e.,
CSWAP gate) that interchange the two quantum states under test only if $q_{0}$
is in state $|1\rangle$. The ancillary qubit $q_{0}$ is finally measured on
the z-basis and the probability it yields a measured output $|0\rangle$ is
$P_{0}=\frac{1+{\langle{\psi_{\sigma}}|{\psi_{\rho}}\rangle}^{2}}{2}$. $P_{0}$
is defined as quantum fidelity as it provides a good estimate of how close two
states are, i.e., $P_{0}=\frac{1}{2}$ for two orthogonal states and $P_{0}=1$
for two exactly same states.

Training Objective. The parameter matrix $\mathbf{\theta_{g}}$ can be
equivalently viewed as the weights in classical neural networks and is trained
iteratively to minimize a fidelity based loss shown in Equation 1.

$\displaystyle\vspace{-24pt}\begin{split}\min_{\theta_{g}}L(\theta_{g})=\min_{\theta_{g}}[1-{\langle{\psi_{\sigma}}|{\psi_{\rho}(\theta_{g})}\rangle}^{2}]\\\
\end{split}$ (1)

Fig. 1: A standard QGAN (shaded gates are trainable).

###  2.2 Preliminary Analysis

Low-quality Generated Images. Although prior work [8, 9] achieved training
convergence with the fidelity based loss, their generated data is of low
quality. We show the fidelity between the learned quantum state
$|\psi_{\rho}\rangle$ and the target quantum state $|\psi_{\sigma}\rangle$
using angle encoding in Equation 2$\sim$3. For the sake of simplicity, we
highlight a special case of Equation 3 in Equation 4 by adding $2n\pi$ to the
learned angle $\theta_{\rho}$. It is clear that the same fidelity and hence
the same loss can be achieved with different parameter sets due to the
periodic repeatability of the sine and cosine functions, resulting in
distorted generated images (See Figure 2). Although input data can be mapped
to the range [0,$\pi$] before applying the angle encoding [8, 16], such
unfaithful normalization prevents a QNN from learning an accurate model and
producing high-quality output. We therefore conclude that the de facto angle
encoding (even with normalization) fails to ensure high-quality output in a
fidelity based GAN framework. We investigate if a new quantum encoding method
with learnablity can improve performance for a quantum GAN.

$\displaystyle\langle\psi_{\rho}|\psi_{\sigma}\rangle^{2}$
$\displaystyle=(\begin{bmatrix}\cos\frac{\theta_{\rho}}{2}&\sin\frac{\theta_{\rho}}{2}\\\
\end{bmatrix}\begin{bmatrix}\cos\frac{\theta_{\sigma}}{2}\\\
\sin\frac{\theta_{\sigma}}{2}\end{bmatrix})^{2}$ (2)
$\displaystyle=(\cos\frac{\theta_{\rho}}{2}\cos\frac{\theta_{\sigma}}{2}+\sin\frac{\theta_{\rho}}{2}\sin\frac{\theta_{\sigma}}{2})^{2}$
(3)
$\displaystyle=(\cos\frac{\theta_{\rho}+2n\pi}{2}\cos\frac{\theta_{\sigma}}{2}+\sin\frac{\theta_{\rho}+2n\pi}{2}\sin\frac{\theta_{\sigma}}{2})^{2}$
(4)

Complex and High-Cost Generator. The standard circuit ansatz for generator
shown in Figure 1 requires each pair of nearest-neighbors to be maximally
entangled using expensive two-qubit CNOT gates. We hypothesize that (1) a
flexible amount of entanglement rather than fixed maximal entanglement may
performs better for a QNN algorithm; (2) a generator without entanglement
gates maybe good enough to provide acceptable generative capability since the
encoding circuit S($\mathbf{x}$) normally embeds target data without any
entanglement gates. Therefore, we proposed to explore the replacement of fixed
CNOT gates with other two-qubit gates (e.g., fixed or parameterized), or even
completely remove two-qubit gates in a generator circuit. We investigate the
effect of two-qubit gates on the performance of a generative ansatz and set
out to reduce the circuit complexity of a generator.

Table 2: Comparison on quantum GANs with different two-qubit gate (2QGate). 2QGate | Block # | Normalized Cost | Fidelity | $\theta_{0}$ | $\theta_{1}$ | $\theta_{2}$ | $\theta_{3}$ | $\theta_{4}$ | $\theta_{5}$ | $\theta_{6}$ | $\theta_{7}$
---|---|---|---|---|---|---|---|---|---|---|---
CNOT | 2 |  2.8$\times$ | 0.813 | N/A
ISWAP | 2 |  3.7$\times$ | 0.954 | N/A
CRX($\theta$) | 2 |  6$\times$ | 0.969 |  | -0.007
---
0.003
| -0.023
---
0.036
| -0.228
---
1.799
| 0.034
---
0.018
| -0.093
---
-0.118
| -0.154
---
0.013
| -0.015
---
0.033
| 3.348
---
3.167
CROT($\phi$, $\theta$, $\omega$) | 2 |  6$\times$ | 0.969 |  | 0.911
---
0.079
| -0.057
---
-0.086
| 2.049
---
-0.068
| 0.059
---
-0.971
| -1.883
---
-0.043
| 0.013
---
0.098
| 2.827
---
0.262
| 0.090
---
-0.062
w/o 2QGate | N/A |  1$\times$ | 0.969 | N/A

##  3 IQGAN: Design and Implementation

In this section, we present the design and implementation of the proposed
IQGAN framework. The IQGAN architecture has two innovative components: (1) a
variational encoder S($arcsin(\mathbf{x}\cdot\mathbf{\theta_{s}}$)) that
adaptively embeds classical training data into quantum states; and (2) a
compact quantum generator G($\mathbf{\theta_{g}}$) without costful two-qubit
entanglement gates.

###  3.1 Trainable Multiqubit Quantum Encoder

Instead of using a de facto fixed encoder (FE) circuit S($\mathbf{x}$), we
investigate trainable encoder (TE) using the PennyLane [18] software package
and show that a properly designed variational classical-to-quantum encoder
results in improved performance for a QNN model (See results in Section 4). We
introduce adaptivity into the encoder circuit by defining a variational
encoder function S($arcsin(\mathbf{x}\cdot\mathbf{\theta_{s}}$)) with
trainable parameters $\mathbf{\theta_{s}}$. To obtain an angle encoding, we
utilize the arcsin function, which is common practice in QNN encoding [16].
The parameter set $\theta_{s}$ are pre-trained to produce faithful quantum
presentations in which data from different clusters are separated.
Specifically, the encoder is trained with a pre-train dataset (CIFAR10 [19] in
this work) $\mathcal{T}$={($\mathbf{x_{i}},y_{i})|0$$\leq$$i$$\leq$$N$}, where
$\mathbf{x_{i}}$ is an $n$-dimensional vector and $y_{i}$ is the label. We
first prepare a quantum ensemble
$\mathbf{\sigma_{y_{i}}}$=$\frac{1}{N_{i}}\sum\nolimits_{i}|\psi_{\sigma}(x_{i})\rangle\langle\psi_{\sigma}(x_{i})|$
by uniformly sampling $\mathbf{N_{i}}$ inputs from class $y_{i}$ and feeding
them into the encoder. We then train the encoder to obtain a set of optimal
parameters $\theta^{*}_{s}$ that maximize the distance between
$\mathbf{\sigma_{y_{i}}}$ and $\mathbf{\sigma_{y_{j}}}$ when $i{\neq}j$. IQGAN
uses the pre-trained values of
S($arcsin(\mathbf{x}\cdot\mathbf{\theta^{*}_{s}}$)) as the initial parameters
of the encoder.

###  3.2 Compact Quantum Generator

To investigate the impact of two-qubit entanglement gates on the performance
of a generator circuit ansatz, we replace the default CNOT gates in Figure 1
with widely used two-qubit gates, including fixed ISWAP gates, and
parameterized CRX($\theta$) and CROT($\phi,\theta,\omega$) gates. We refer
interested readers to [20] for detailed explanations of each candidate gate.
We provide a full comparison between different generator circuit ansatzes in
Table 2. The default CNOT gates do not perform very well and actually perform
worse than other types of two-qubit entanglement gates. Parameterized gates,
i.e., CRX and CROT, perform better than fixed ISWAP gates (i.e., 0.954 vs.
0.969), which is attributed to the trainable amount of entanglement. However,
the hardware overhead of CRX and CROT gates is significantly higher than fixed
two-qubit gates. In particularly, we find that a generator without two-qubit
gates, denoted as w/o 2QGate in Table 2 achieves same performance as CRX and
CROT with 6$\times$ reduced hardware cost. Therefore, we propose to implement
the generator in IQGAN with no two-qubit gates.

###  3.3 Implementation of IQGAN

Hardware Implementation Cost. Multiqubit gates are decomposed in practice into
basic single-qubit and two-qubit gates supported by specific gate libraries.
We assume an ideal quantum circuit library that supports all types of single-
qubit and two-qubit gates, and provide a quantitative comparison of design
cost between IQGAN and prior arts in Table 3. IQGAN requires the minimum
hardware resource and reduces hardware cost by at least $6\times$ in the
simplest case when the generator uses only one VQC block, as detailed in Table
2.

Training Procedure. IQGAN requires a two-step training process. At the
beginning of the algorithm, the encoder
S($arcsin(\mathbf{x}\cdot\mathbf{\theta_{s}}$)) is initialized by arbitrary
parameters $\theta^{0}_{s}$ and trained on a pre-train dataset to obtain the
optimized parameter set of $\theta^{*}_{s}$ as explained in Section 3.1. We
then utilize S($arcsin(\mathbf{x}\cdot\mathbf{\theta_{s}^{*}}$)) in an IQGAN
framework with uniformly initialized $\theta^{0}_{g}$, and train the whole
model to minimize the object function in Equation 1. After the model reaches
its convergence, we record the optimal parameter set of $\theta^{*}_{g}$.

Table 3: Hardware cost of different quantum GAN schemes ($n$: input size; $b$: repeated VQC block number; 1QG#/2QG#: one-/two-qubit gates number; Param.#: parameter number). Scheme | Qubit# | 1QG# | 2QG# | Param.#
---|---|---|---|---
QuGAN21 [8] |  $2n$+$1$ |  $nb$+$1$ | $4nb$ | $5nb$
EQ-GAN [9] |  $2n$+$1$ |  $2nb$+$n$+$2$ | $(b+1)n$ | $2nb$
IQGAN |  $2n$+$1$ |  $2nb$+$n$+$2$ | $n$ | $2nb$

##  4 Experiments and Results

Fig. 2: MNIST images generated by QuGAN2021 [8] (1st row), EQ-GAN [9] (2nd
row), and IQGAN (bottom row).

###  4.1 Experimental Setup

Schemes and Benchmarks. We compare IQGAN with two SOTA quantum GANs [8, 9]
using the MNIST [21] dataset. Note that we exclude QuGAN2018 [7] because it
suffers from convergence oscillation and is difficult to train in practice
[9]. We demonstrate the proof-of-principle of IQGAN using a 5-qubit IBM
quantum processor, ibmq_quito [22]. We confirm that IQGAN is reasonably
accurate in generating synthetic images on real NISQ devices.

Simulation. All quantum GANs are implemented using PennyLane [18], a quantum
computing software library. We train QuGAN2021 [8] using their open-source
code by following their training configuration. We implement EQ-GAN [9] by
following their design strategy but extending their original design to support
multiqubit data. EQ-GAN [9] and IQGAN are trained with the ADAM optimizer,
while the learning rate, batch size, and the number of epochs are set
respectively as 0.001, 32, and 30. The learning rate is scheduled by
CosineAnnealingLR with a $T_{max}$ of 30.

###  4.2 Results and Analysis

Table 4: Accuracy comparison of Fixed Encoder(FE) and Trainable Encoder (TE) on different subset of MNIST. Task | Input | Qubit # | Accuracy (%)
---|---|---|---
Size | FE | TE
MNIST-2 | 4*4 | 16 | 89.5 | 90.9
MNIST-4 | 2*2 | 4 | 43.2 | 45.6
MNIST-4 | 4*4 | 16 | 45.9 | 49.4
MNIST-8 | 4*4 | 16 | 23.25 | 24.3

Effectiveness of the Trainable Encoder. To compare the faithful data embedding
capability between the de facto fixed encoder (FE) and the proposed trainable
encoder (TE), we apply both FE and TE to downstream classification tasks and
report their accuracy in Table 4. TE boosts the model accuracy under different
input sizes. We also make two observations that can be extended for general
quantum machine learning algorithm: (1) The effectiveness of TE increase as
the input qubit size increases, e.g., the accuracy improvement comparison on
MNIST-4 for input sizes of $2\times 2$ and $4\times 4$; (2) The effectiveness
of TE increases with the model complexity, e.g., the accuracy improvement
comparison between MNIST-2 and MNIST-4 with both 16-qubit inputs.

Comparison on Image Quality. As visualized in Figure 2, QuGAN2021 [8] shows
limited generative capability. For images of 0 and 9, a blurred outline can be
identified. However, for images of 3 with more complex visual structures,
QuGAN2021 [8] fails to reproduce the images. The results of EQ-GAN [9]
demonstrate an unstable image quality with a large deviation. For instance,
the 4th, 5th, 8th, 13th, 17th, and 18th images are highly distorted. Note that
the results for QuGAN2021 [8] and EQ-GAN [9] are simulated data, while the
results on IQGAN are collected on ibmq_quito [22]. Compared with previous
quantum GANs, we see IQGAN achieves a stable and consistent high-quality
output even on NISQ devices.

Fig. 3: IQGAN Convergence.

Fig. 4: Impact of noises.

Convergence of IQGAN. In Figure 4, we present the measured fidelity of the
discriminator in IQGAN. We reported results with both fixed encoder (FE) and
trainable encoder (TE). A stable convergence within ten iterations can be
observed for both configurations, confirming that IQGAN converges to a high
(i.e., $>$0.92) state overlap with the target inputs. Compared with a standard
FE, the proposed TE achieved a lower (e.g., 0.85 vs. 0.90) fidelity in the
first several iterations, however, the final learned fidelity of TE is
$\sim$0.039 higher (i.e., 0.966 vs. 0.927 ) than FE. Furthermore, the learned
fidelity of TE increases faster than that of FE, which is mainly attributed to
the higher flexibility and adaptability of the TE circuit and the richer
expressive power.

Impact of Quantum Errors. We also explore the impact of quantum errors on
IQGAN performance. We consider bit-flip and phase-flip [23, 24], which are two
most significant error types on NISQ devices. We down-sample the original
images to 1$\times$2, 1$\times$4, 1$\times$6, and 1$\times$8 vectors using PCA
algorithm, and report the fidelity of generated images in Figure 4. Although
the quality of the target images increases monotonically with the input size,
the fidelity between the learned images and the inputs decreases. This
phenomenon is counterintuitive, but can be explained in quantum GAN when
quantum errors are considered. First, the increased input sizes require
increased number of qubits. Second, as the dimension of the data increases,
the required generative capability of the generator also increases. Therefore,
a more deep generator circuit with an increased number of blocks is required
to fit the data. A quantum system with more qubits and gates is more
susceptible to noise. In this case, while a more complex IQGAN circuit
increases the expressive power of the model, quantum noise from excessive
overhead reduces the overall fidelity.

##  5 Conclusion

We propose IQGAN, a quantum generative adversarial network for image synthesis
that can be implemented on Noisy Intermediate Scale Quantum devices with
limited circuit width and depth. We compared IQGAN with previous work and
demonstrate that IQGAN outperforms the state-of-arts in image quality and
quantum hardware implementation cost.

## References

  * [1] Vojtěch Havlíček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta,  “Supervised Learning with Quantum-Enhanced Feature Spaces,”  Nature, vol. 567, no. 7747, pp. 209–212, 2019.
  * [2] Hsin-Yuan Huang et al.,  “Quantum advantage in learning from experiments,”  Science, vol. 376, no. 6598, pp. 1182–1186, 2022.
  * [3] Francesco Tacchino, Panagiotis Barkoutsos, Chiara Macchiavello, Ivano Tavernelli, Dario Gerace, and Daniele Bajoni,  “Quantum Implementation of An Artificial Feed-forward Neural Network,”  Quantum Science and Technology, vol. 5, no. 4, pp. 044010, 2020\.
  * [4] Iris Cong, Soonwon Choi, and Mikhail D Lukin,  “Quantum Convolutional Neural Networks,”  Nature Physics, vol. 15, no. 12, pp. 1273–1278, 2019.
  * [5] Seth Lloyd, Masoud Mohseni, and Patrick Rebentrost,  “Quantum Algorithms for Supervised and Unsupervised Machine Learning,”  arXiv e-prints, p. arXiv:1307.0411, July 2013.
  * [6] Seth Lloyd and Christian Weedbrook,  “Quantum Generative Adversarial Learning,”  Phys. Rev. Lett., vol. 121, pp. 040502, Jul 2018.
  * [7] Pierre-Luc Dallaire-Demers and Nathan Killoran,  “Quantum Generative Adversarial Networks,”  Phys. Rev. A, vol. 98, pp. 012324, Jul 2018.
  * [8] Samuel A. Stein, Betis Baheri, Daniel Chen, Ying Mao, Qiang Guan, Ang Li, Bo Fang, and Shuai Xu,  “QuGAN: A Quantum State Fidelity based Generative Adversarial Network,”  in IEEE International Conference on Quantum Computing and Engineering (QCE). 2021, pp. 71–81, IEEE.
  * [9] Murphy Yuezhen Niu, Alexander Zlokapa, Michael Broughton, Sergio Boixo, Masoud Mohseni, Vadim Smelyanskyi, and Hartmut Neven,  “Entangling Quantum Generative Adversarial Networks,”  arXiv preprint arXiv:2105.00080, 2021.
  * [10] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio,  “Generative Adversarial Nets,”  in Advances in Neural Information Processing Systems (NIPS), 2014, pp. 2672–2680.
  * [11] Alec Radford, Luke Metz, and Soumith Chintala,  “Unsupervised representation learning with deep convolutional generative adversarial networks,”  arXiv preprint arXiv:1511.06434, 2015.
  * [12] Johannes Bausch,  “Recurrent quantum neural networks,”  Advances in neural information processing systems (NeurIPS), vol. 33, pp. 1368–1379, 2020.
  * [13] Hanrui Wang, Yongshan Ding, Jiaqi Gu, Yujun Lin, David Z Pan, Frederic T Chong, and Song Han,  “Quantumnas: Noise-adaptive search for robust quantum circuits,”  in IEEE International Symposium on High-Performance Computer Architecture (HPCA). IEEE, 2022, pp. 692–708.
  * [14] Edward Farhi and Hartmut Neven,  “Classification with quantum neural networks on near term processors,”  arXiv preprint arXiv:1802.06002, 2018.
  * [15] Ryan LaRose and Brian Coyle,  “Robust data encodings for quantum classifiers,”  Physical Review A, vol. 102, no. 3, pp. 032420, 2020.
  * [16] Samuel Yen-Chi Chen, Shinjae Yoo, and Yao-Lung L Fang,  “Quantum long short-term memory,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 8622–8626.
  * [17] Jun Qi and Javier Tejedor,  “Classical-to-quantum transfer learning for spoken command recognition based on quantum neural networks,”  in IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE, 2022, pp. 8627–8631.
  * [18] pennylane,  “PennyLane,” https://pennylane.ai/.
  * [19] Alex Krizhevsky, Geoffrey Hinton, et al.,  “Learning multiple layers of features from tiny images,”  Master’s thesis, Department of Computer Science, University of Toronto, 2009.
  * [20] pennylane,  “Quantum operators,” https://docs.pennylane.ai/en/stable/introduction/operations.html.
  * [21] Yann LeCun,  “The mnist database of handwritten digits,”  http://yann. lecun. com/exdb/mnist/, 1998.
  * [22] IBM,  “IBM Quantum Computing,” https://quantum-computing.ibm.com/.
  * [23] Samson Wang, Enrico Fontana, Marco Cerezo, Kunal Sharma, Akira Sone, Lukasz Cincio, and Patrick J Coles,  “Noise-Induced Barren Plateaus in Variational Quantum Algorithms,”  Nature communications, vol. 12, no. 1, pp. 1–11, 2021.
  * [24] Lena Funcke, Tobias Hartung, Karl Jansen, Stefan Kühn, Paolo Stornati, and Xiaoyang Wang,  “Measurement Error Mitigation in Quantum Computers through Classical Bit-Flip Correction,”  arXiv preprint arXiv:2007.03663, 2020.