]https://peterrohde.github.io/QuNet

# QuNet: Cost vector analysis & multi-path entanglement routing in quantum
networks

Hudson Leone<EMAIL_ADDRESS>School of Mathematical and Physical Sciences,
University of Technology Sydney, Ultimo, NSW 2007, Australia  Centre for
Quantum Software & Information (UTS:QSI), University of Technology Sydney,
Ultimo, NSW 2007, Australia  Nathaniel R. Miller  Hearne Institute for
Theoretical Physics, Department of Physics & Astronomy, Louisiana State
University, Baton Rouge LA, United States  Deepesh Singh  Centre for Quantum
Computation & Communication Technology, School of Mathematics and Physics, The
University of Queensland, St Lucia, Queensland 4072, Australia  Nathan K.
Langford  School of Mathematical and Physical Sciences, University of
Technology Sydney, Ultimo, NSW 2007, Australia  Centre for Quantum Software &
Information (UTS:QSI), University of Technology Sydney, Ultimo, NSW 2007,
Australia  Peter P. Rohde<EMAIL_ADDRESS>[ Centre for Quantum Software &
Information (UTS:QSI), University of Technology Sydney, Ultimo, NSW 2007,
Australia  Hearne Institute for Theoretical Physics, Department of Physics &
Astronomy, Louisiana State University, Baton Rouge LA, United States

###### Abstract

Entanglement distribution will form the backbone of many future distributed
quantum technologies, especially the quantum internet. The act of purifying
multiple noisy entangled states into a single one of higher quality has no
analogue in classical networking and as such, this transforms the way in which
we will consider future algorithms for routing entanglement. We outline the
differences that arise because of this, demonstrate some elementary formalisms
for ‘multi-path entanglement routing’, and discuss the philosophical
differences that arise when comparing this regime to conventional digital
network theory. We also present a software package, QuNet, that uses novel
‘quantum cost-vector analysis’ to simulate and benchmark routing in multi-user
entanglement networks in a way that is is highly scalable in network size and
the number of competing users. Our software accommodates both ground- and
space-based networks, and implements efficient multi-user time-optimisation
for mitigating congestion when quantum memories are available.

###### Contents

  1. I Introduction
  2. II Entanglement distribution networks
    1. II.1 Bell pairs — A resource for quantum networking
    2. II.2 Quantum channels
      1. II.2.1 General quantum channels
      2. II.2.2 Loss channels
      3. II.2.3 Decoherence channels
      4. II.2.4 State fidelity and channel cost-vectors
    3. II.3 Cost vector analysis in entanglement swapping networks
    4. II.4 Cost-vector analysis with entanglement purification
  3. III Graph reduction
    1. III.1 Purification trees
    2. III.2 Entanglement networks as abelian groups
    3. III.3 General reduction strategies
  4. IV Entanglement routing strategies
    1. IV.1 Shortest-path routing
    2. IV.2 Multi-path routing
    3. IV.3 Analytic area laws
    4. IV.4 Greedy multi-path routing
    5. IV.5 Multi-user routing
  5. V The philosophy of quantum vs. classical networking
  6. VI QuNet: A package for simulating quantum networks
    1. VI.1 Related work and motivation
    2. VI.2 Design principles
    3. VI.3 Simulating quantum memories with temporal meta-graphs
  7. VII Advanced route optimisation in entanglement distribution networks using QuNet
    1. VII.1 Benchmarking multi-path purification with single-user networks
    2. VII.2 Multi-user, multi-path routing
    3. VII.3 Channel percolation effects
    4. VII.4 Network scaling effects
  8. VIII Temporal multiplexing in entanglement distribution networks using QuNet
    1. VIII.1 Network Performance with Time-depth
    2. VIII.2 Effect of Quantum Memories on Unrestricted Temporal Routing
  9. IX Further applications
    1. IX.1 Quantum key distribution
    2. IX.2 Distributed quantum computation
    3. IX.3 Space-based quantum networks
  10. X Conclusion
  11. A Efficient multi-user temporal routing algorithm
  12. B Average $L_{1}$-distance between random user-pairs on a square lattice
  13. C Derivation of analytic heat map curves

##  I Introduction

In classical networking, communication is carried out via direct transmission
of classical information along communication channels, and errors are
mitigated through repeat-until-success strategies that transmit redundant
information. In quantum networking, the no-cloning theorem prevents arbitrary
copying of unknown quantum information, so direct transmission of quantum
information is limited in quality and success probability by the intrinsic
noise characteristics of the communication channel. However, these no-cloning
limitations can be circumvented if quantum information is distributed in the
form of known entangled states, which can be used to communicate arbitrary
quantum information using repeat-until-success entanglement transmission and
quantum teleportation [3]. When combined, in addition, with entanglement
swapping and entanglement purification, quantum communication links can be
extended to arbitrary length with arbitrarily high transmission quality,
effectively bypassing the inevitable transmission noise limitations of the
quantum channel. Due to these desirable properties, entanglement distribution
will be arguably the most essential requirement in a future quantum internet
[31], with significant potential economic benefits facilitating many essential
future quantum technologies [25] such as quantum key distribution (QKD) [2,
12] (see Sec. IX.1), quantum state teleportation [3], and most importantly
distributed quantum computing (see Sec. IX.2).

Here we present some formalisms, insights, and algorithmic approaches for how
future multi-user quantum entanglement distribution networks might operate,
and highlight the significant conceptual differences between how multi-user
quantum and digital networks operate, some of which are highly
counterintuitive to those coming from classical networking backgrounds. One of
the primary distinctions between quantum and classical networks is that
entanglement purification enables multi-path routing, whereby rather than
using a single shortest path for routing we employ multiple redundant paths
which are subsequently purified down into a single Bell pair of higher
fidelity than allowed by any of the available constituent paths, as per Fig.
1.

Figure 1: In shortest-path routing, as is often employed in classical
networking protocols, we wish to find the route between two nodes that
minimises the sum of their edge distances. This notion could similarly be
employed in entanglement routing, where the edge weights represent a loss or
dephasing noise metric. In multi-path routing, we do not employ just a single
shortest-path, but simultaneously communicating Bell pairs across multiple
available routes, which are subsequently purified, thereby yielding a single
Bell pair with greater fidelity than the shortest-path route would have
enabled.

We present a high-performance software package QuNet, which implements these
ideas, allowing for efficient benchmarking of large-scale multi-user quantum
networks, accommodating for both static (e.g ground based) and dynamic (e.g
space-based) networks, as well as temporal routing and optimisation when
quantum memories are available.

A range of different technologies have been proposed for information
distribution and storage in quantum networks approaches based on photonic
information distribution including polarisation, time-bin, and spatial mode
encoding. Our graph-based network simulation software can be applied in any of
these contexts, and extended to include specific details of each (e.g.
relevant error mechanisms and network structure properties). So far, our
simulations have focused on the context of photonic qubit distribution, but
are agnostic to the specific details of information encoding during
distribution and storage within the nodes. It seems inevitable that by mere
virtue of photons being ‘flying qubits’ (which propagate at the speed of
light), that the future quantum internet will be optically mediated by quantum
states of light [14]. Here there are a multitude of possible mechanisms for
encoding quantum information into optical states. For the purposes of our
presentation we will primarily refer to examples based upon polarisation-
encoded single photons, however the formalism is indeed generally applicable
to all manner of quantum communications networks beyond this.

##  II Entanglement distribution networks

Suppose our objective is to find the path through a network that is least
likely to incur one or more errors in transmitting data. This is a simple
matter for a classical network since the dominant error mechanism is loss. We
can define weights for each channel based on how likely the channel is to fail
at transmitting a bit, and then use any shortest-path algorithm over those
weights to find the optimal solution. With quantum networks however,
developing a scalar cost for each link is not possible since there are
multiple orthogonal error channels, and so the action of an error channel
generally depends on the underlying state. Our aim in this section is to
implement a formalism that can exploit a similar kind of cost-analysis over
entanglement distribution networks. This requires that we consider a
simplified error model so as to describe the effects of quantum channels with
one or more scalar costs.

We want to describe such networks as generally as possible, so another goal is
to use generic tools that apply comprehensively across different varieties and
instances of networks. We therefore take a graph theoretic approach for
representing networks. Specifically, we model our network as a graph of nodes
and communication channels,

$\displaystyle G=(V,E).$ (1)

Here, the graph vertices $V$ represent local nodes, defining end-users, or
devices that implement quantum operations (such as entanglement sources,
swappers or routers), and edges $E$ between vertices represent quantum
communication channels.

###  II.1 Bell pairs — A resource for quantum networking

In entanglement distribution networks, entangled states represent the
fundamental underlying resource we wish to utilise. For qubit-based networks,
the archetypal entangled states are the maximally entangled Bell states
between a pair of qubits,

$\displaystyle\ket{\Phi^{\pm}}_{A,B}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0}_{A}\ket{1}_{B}\pm\ket{1}_{A}\ket{0}_{B}),$
(2) $\displaystyle\ket{\Psi^{\pm}}_{A,B}$
$\displaystyle=\frac{1}{\sqrt{2}}(\ket{0}_{A}\ket{0}_{B}\pm\ket{1}_{A}\ket{1}_{B}).$

These become the basic resource for all operations in the network. The four
states are equivalent as entanglement resources and provide the same utility
for elementary network operations. As a known resource state, these Bell pairs
are not subject to the no-cloning limitation. Bell pairs also have the useful
property that Pauli errors commute across the the qubits of an entangled pair,
meaning that an error on one qubit can be equivalently taken to mean an error
on the other qubit (up to global phase),

$\displaystyle(\hat{\sigma}\otimes\hat{I})\ket{\psi}\propto(\hat{I}\otimes\hat{\sigma})\,\ket{\psi},$
(3)

where $\hat{\sigma}\in\\{\hat{X},\hat{Y},\hat{Z}\\}$ and
$\ket{\psi}\in\\{\ket{\Phi^{\pm}},\\{\ket{\Psi^{\pm}}\\}$.

###  II.2 Quantum channels

In describing our quantum channels, we take an approach that naturally adapts
the cost analysis of classical networking to the regime of quantum networks.
Specifically, our channels are weighted with vectors of additive costs that
characterise the accumulation of noise as qubits traverse network paths.
Although we focus here primarily on _physical_ cost mechanisms, such as
decoherence and loss, the formalism we present can also be extended to non-
physical costs, such as monetary cost.

####  II.2.1 General quantum channels

We consider physical quantum error channels of the form,

$\displaystyle\mathcal{E}(\hat{\rho})=p\hat{\rho}+(1-p)\hat{\rho}_{\mathrm{ss}},$
(4)

where $\hat{\rho}_{\mathrm{ss}}$ is the steady state of the channel,
satisfying,

$\displaystyle\mathcal{E}(\hat{\rho}_{\mathrm{ss}})=\hat{\rho}_{\mathrm{ss}}.$
(5)

This means the channel has some probability to transmit the encoded
information successfully, and some probability to replace it with the steady
state of the channel. Under repeated applications of the channel, we find that
the success probability scales exponentially with the number of repetitions
$n$,

$\displaystyle\mathcal{E}^{n}(\hat{\rho})=p^{n}\hat{\rho}+\left(1-p^{n}\right)\hat{\rho}_{\mathrm{ss}}.$
(6)

Likewise, a sequence of channels of the same type (i.e. dephasing,
depolarising, etc.) but with different success probabilities give rise to the
aggregate error channel,

$\displaystyle\mathcal{E}_{(n)}\circ\dots\circ\mathcal{E}_{(1)}(\hat{\rho})=\left(\prod_{i=1}^{n}p_{i}\right)\hat{\rho}+\left(1-\prod_{i=1}^{n}p_{i}\right)\hat{\rho}_{\mathrm{ss}},$
(7)

Thus, under the right circumstances, we see that ${-}\log(p)$ can be used as
an additive cost for a particular type of error across a quantum network. In
the next sections, we define the specific channels for several of the most
common decoherence and loss errors.

####  II.2.2 Loss channels

The loss channel is a very important effect in any quantum network, especially
photonic quantum networks. For a single-qubit state $\hat{\rho}$, it is
defined as,

$\displaystyle\mathcal{E}_{\mathrm{loss}}(\hat{\rho})$
$\displaystyle=\eta\hat{\rho}+(1-\eta)\ket{vac}\\!\bra{vac},$ (8)

where $\eta$ is the transmission efficiency and $\ket{vac}$ denotes the vacuum
state. This channel naturally takes the form of Eq. 4, with the channel
success probability $p=\eta$ and the vacuum as the steady state
$\hat{\rho}_{\textrm{ss}}=\ket{vac}\\!\bra{vac}$.

####  II.2.3 Decoherence channels

The most commonly studied types of decoherence channels are the dephasing
channel,

$\displaystyle\mathcal{E}_{\mathrm{deph}}(\hat{\rho})=p_{\mathrm{deph}}\,\hat{\rho}+(1-p_{\mathrm{deph}})\left[\frac{\hat{\rho}+\hat{Z}\hat{\rho}\hat{Z}}{2}\right],$
(9)

where the steady state is the maximally dephased state
$(\hat{\rho}+\hat{Z}\hat{\rho}\hat{Z})/2$; the depolarising channel,

$\displaystyle\mathcal{E}_{\mathrm{depol}}(\hat{\rho})$ $\displaystyle=p_{\rm
depol}\,\hat{\rho}+(1-p_{\rm depol})\,\frac{\hat{\mathbb{I}}}{2},$ (10)

where the steady state is the maximally mixed state $\hat{\mathbb{I}}/2$; and
the energy decay or amplitude damping channel,

$\displaystyle\mathcal{E}_{\mathrm{damp}}(\hat{\rho})=p_{\mathrm{damp}}\,\hat{\rho}+(1-p_{\mathrm{damp}})\,\ket{0}\bra{0},$
(11)

which arises very naturally in the context of atom-like qubits, where the
finite energy gap causes all states to decay towards a steady state of the
ground state, which encodes the logical ‘0’ state.

For the dephasing channel, it is often parameterized differently as a pure
phase-flip process [25],

$\displaystyle\mathcal{E}_{\mathrm{deph}}(\hat{\rho})$
$\displaystyle=\left(\frac{1+p_{\mathrm{deph}}}{2}\right)\,\hat{\rho}+\left(\frac{1-p_{\mathrm{deph}}}{2}\right)\,\hat{Z}\hat{\rho}\hat{Z}.$
(12)

For certain special cases, such as when a dephasing channel is applied to one
half of a maximally entangled Bell state, the error state defined in this way,
$\hat{Z}\hat{\rho}\hat{Z}$, is orthogonal to the input state, $\hat{\rho}$,
and we can directly identify $p_{\mathrm{deph}}$ as the overlap probability
between the input and output states.

While QuNet’s formalism can be used for a wide range of error channels that
can be written in the above form, for illustration in the remainder of this
paper, we will consider a common scenario where quantum networks are affected
by loss and dephasing [32].

####  II.2.4 State fidelity and channel cost-vectors

Figure 2: Graph representation for an entanglement distribution network, where
a graph $G$, specified by a set of vertices $v_{i}$, and edges $e_{i,j}$.
Edges represent the communication of noisy Bell pairs (one pair per edge),
each characterised by both their own preparation probability $P$ and fidelity
$F$.

While quantum channels may be described quite generally in the form of Eq. 4,
this is not how the quality of shared states is usually characterised. One of
the most common metrics used for this purpose is the fidelity, which measures
of overlap between the input (or target) state and the transmitted state,

$\displaystyle F$
$\displaystyle=\bra{\psi}\mathcal{E}(\ket{\psi}\\!\bra{\psi})\ket{\psi}.$ (13)

In the case of dephasing, Eq. 12 highlights that this fidelity can be directly
related to the channel success probability via $F=(1+p_{\rm deph})/2$, in
cases like the sharing of entangled Bell pairs that we consider throughout the
majority of this paper.

In practice, it is useful to separate measures of state degradation into
components associated with decoherence and loss. Then we can define the
fidelity conditional upon no loss, and the probability of no loss as,

$\displaystyle F_{\textrm{cond}}$
$\displaystyle=\frac{\bra{\psi}\mathcal{E}(\ket{\psi}\\!\bra{\psi})\ket{\psi}}{\eta},$
$\displaystyle\eta$
$\displaystyle=1-\bra{vac}\mathcal{E}(\ket{\psi}\\!\bra{\psi})\ket{vac}.$ (14)

In terms of the generic quantum channels above, this approach can be
understood in terms of conditional success probabilities. For example, for a
channel with both loss and dephasing, we can define an overall channel success
probability,

$\displaystyle p_{\rm overall}=p_{\text{deph | (no loss)}}\times p_{\text{(no loss)}},$ (15)

where $p_{\text{(no loss)}}=\eta$.

Clearly, efficiency and conditional fidelity are in some sense “orthogonal”.
They are independent measures that characterise two different phenomena of
quantum error channels. The former is attributed to amplitude while the latter
is of orientation with respect to the ideal state. It is helpful therefore to
consider each link in our quantum network in terms of a “cost-vector” that
contains the expected efficiency and conditional fidelity for a qubit that
passes through it,

$\displaystyle e=(\eta,F),$ (16)

From this point on, every mention of fidelity will be understood to mean the
conditional fidelity as defined in Eq. 14, unless stated otherwise. In the
following sections, we describe two key primitive processes of entanglement
distribution quantum networking—entanglement swapping and purification—and how
to track them within our cost vector formalism.

###  II.3 Cost vector analysis in entanglement swapping networks

Having defined the costs and error processes associated with individual
quantum links, we now develop the tools required to aggregate the costs for a
path in the network. Eq. 7 describes a state after it is sent through a
special-case sequence of quantum channels. In this case, we find that
$-\log(p)$ can be used as an additive cost for the individual links. For
entanglement distribution networks however, the constituent qubits of
entangled states are often transmitted along separate channels. Fortunately,
for the distribution of Bell pairs, we find that the same simple result holds,
which results from the symmetry of the state. Specifically, we refer to Eq. 3
which demonstrates that Pauli errors commute across the qubits of an entangled
pair.

It remains to be shown however that entanglement swapping—perhaps the most
important operation in quantum networking—obeys the relation of Eq. 7.
Entanglement swapping is an operation where two halves of distinct entangled
pairs are taken and measured in the Bell basis. This projects entanglement
across the outer two qubits, which are never physically interacted, and
creates a longer range entangled pair at the cost of two shorter ones. A
schematic of this operation is illustrated in Fig. 3. Importantly, the
specific order in which entanglement swapping operations are carried out to
distribute entanglement across the ends of a network path has no bearing on
the success probability of transmitting the state. Because our primary
interest is to develop a cost formalism in terms of this probability, we
neglect the logistics of distributing entanglement and only consider the costs
of doing so.

It is intuitively demonstrated that entanglement swapping has the effect of
accumulating the Pauli errors of the constituent Bell states, which allows us
to represent the processes within our cost-vector formalism. First, we can
always assume that the inner two qubits of the swapping procedure are ideal
given that any Pauli errors may be commuted to the outer qubits of the Bell
pair. If the projective measurement is assumed to be ideal, then clearly the
resulting state will inherit the errors accumulated on the outer two qubits.
Additionally, any non-ideal measurement can be represented as an ideal
measurement followed by some error channel, and so our cost-vector approach is
consistent for all swapping scenarios.

Figure 3: Entanglement swapping of two Bell-pairs, using a Bell measurement
between one half of each, to project the remaining two qubits, which were not
previously entangled, into a Bell-pair.

Entanglement swapping can be performed deterministically using a CNOT gate, or
non-deterministically in the photonic context using a polarising beamsplitter
(PBS), which implements a partial Bell measurement and is only able to resolve
two of the four Bell states [27]. Whether or not an entanglement swapping
operation is deterministic has no bearing on the underlying cost-vector
formalism, since any non-deterministic effect can be built into the cost.

###  II.4 Cost-vector analysis with entanglement purification

The second key ingredient in entanglement distribution networks is
entanglement purification, whereby two low-fidelity Bell pairs are reduced
into a single higher-fidelity one. This process can be applied recursively so
as to achieve arbitrarily high fidelities in principle. However, given that
each application of the protocol reduces two Bell-pairs to one, the number of
Bell-pair resource states required to apply $n$ rounds of purification scales
as $2^{n}$.

As with entanglement swapping, entanglement purification can be implemented
using CNOT gates, as shown in Fig. 4, or optically using polarizing
beamsplitters (PBSs), as shown in Fig. 5, which comes at the cost of non-
deterministic operations similar to PBS-based Bell measurements.

Figure 4: Entanglement purification of two noisy Bell-pairs under dephasing
channels, using two CNOT gates. Figure 5: Entanglement purification of two
noisy Bell-pairs under dephasing channels, using two polarising beamsplitters
(PBS), which implement partial Bell-state projections.

We remarked earlier in Sec. II.2.4 that any state can be described in terms of
a “cost-vector” of efficiency and fidelity with respect to some ideal. One
reason why this is useful is that cost-vectors of input states can be used to
calculate the cost-vector of a purification scheme. For this paper, we
consider the photonic implementation of purification as shown in Fig. 5 with
the following transformation rules [17]:

$\displaystyle F^{\prime}$
$\displaystyle=\frac{F_{1}F_{2}}{F_{1}F_{2}+(1-F_{1})(1-F_{2})},$
$\displaystyle\eta^{\prime}$
$\displaystyle=\eta_{1}\eta_{2}[F_{1}F_{2}+(1-F_{1})(1-F_{2})],$ (17)

$F_{i}$ and $P_{i}$ denote the fidelity and probability of the two input Bell-
pairs, where $i\in\\{1,2\\}$. This relationship is shown in Fig. 6. The
protocol has the property that so long as both input Bell-pairs satisfy
$F>\frac{1}{2}$, the fidelity of the output Bell-pair will be greater than
that of both input pairs,

$\displaystyle
F^{\prime}>F_{1},F_{2}\,\,\,\forall\,\,\,F_{1},F_{2}>\frac{1}{2}.$ (18)

Figure 6: Input versus output fidelities for the entanglement purification
protocol shown in Fig. 5, where both input Bell states are assumed to be
identical with fidelity $F_{\mathrm{in}}$. So long as
$F_{\mathrm{in}}>\frac{1}{2}$, the protocol increases the output fidelity,
$F_{\mathrm{out}}>F_{\mathrm{in}}$.

##  III Graph reduction

Given a large network graph it can be useful to reduce the overall complexity
of the graph topology using graph reduction rules that arise from the graph
transformations implemented by elementary operations such as swappers and
purification.

For example, a linear chain of entanglement swappers has the effect of
reducing that chain to a single end-to-end entanglement link, and purification
operations collapse cyclic subgraphs. These graph reductions can then be
implemented via simple substitution rules applied to subgraphs with the
respective topology, as per Fig. 8 and Alg. 1.

In this section we discuss some of these observations and how they may be
applied.

###  III.1 Purification trees

The purification of an arbitrary number of Bell pairs can be described in
terms of an operation that maps two Bell states to one. Given states
$\hat{\rho}_{1}$ and $\hat{\rho}_{2}$, the purified state
$\hat{\rho}^{\prime}$ is,

$\displaystyle\hat{\rho}^{\prime}$
$\displaystyle=\hat{\rho}_{1}\ast\hat{\rho}_{2}$
$\displaystyle=\hat{\rho}_{2}\ast\hat{\rho}_{1}.$ (19)

Given that this operation is non-linear (as seen in Fig. 6), the resultant
fidelity may depend on the order in which purifications are applied. Any such
ordering can be represented with a binary tree, where states on branches are
purified into their intersecting node.

Consider for example the Dür and Deutsch protocols acting on 4 distinct input
states $\hat{\rho_{i}}$,

$\displaystyle\hat{\rho}_{\text{D{\"{u}}r}}$
$\displaystyle=(\hat{\rho}_{1}\ast\hat{\rho}_{2})\ast(\hat{\rho}_{3}\ast\hat{\rho}_{4}),$
$\displaystyle\hat{\rho}_{\text{Deutsch}}$
$\displaystyle=\hat{\rho}_{1}\ast(\hat{\rho}_{2}\ast(\hat{\rho}_{3}\ast\hat{\rho}_{4})),$
(20)

where the corresponding binary trees are shown in Fig. 7. Generally, the total
number of purification orderings for $n$ states corresponds to the number of
$n$-leaf binary trees,

$\displaystyle(2n-3)!!.$ (21)

Clearly, a naïve search for the optimal purification tree is computationally
inefficient. However in Sec. III.2, we demonstrate that for commutative
operations (e.g purifications along a common Pauli axis) the resultant
purified state is independent of ordering. In the more general case, however,
this does not hold and outcomes will be highly order-dependent in general.

Figure 7: Phylogenetic purification trees for the Dür and Deutsch protocols,
representing the ordering in which multiple Bell pairs are purified into a
single one. Lines represent noisy Bell pairs, and forks denote purification
protocols, where time runs from top to bottom.

###  III.2 Entanglement networks as abelian groups

Let us now consider a simple noise model in which only Pauli dephasing
channels are applied (i.e there is no noise along other Pauli axes). Then we
find that the following algebraic rules hold for our system. Take
$F(f_{1},f_{2})$ to be the the fidelity after purification for two states with
fidelity $f_{1},f_{2}$ as given in Eq. II.4. Then,

$\displaystyle F(f_{1},f_{2})$ $\displaystyle=F(f_{2},f_{1}),$ $\displaystyle
F(F(f_{1},f_{2}),f_{3})$ $\displaystyle=F(f_{1},F(f_{2},f_{3})),$
$\displaystyle F(f_{1},1/2)$ $\displaystyle=f_{1},$ $\displaystyle
F(f_{1},1-f_{1})$ $\displaystyle=\frac{1}{2},$ (22)

which in the the domain of $[0,1]$ allows purification to form an abelian
group.

Furthermore, by considering the properties of the entanglement swapping
operation $S$, we find that,

$\displaystyle S(f_{1},S(f_{2},f_{3}))$
$\displaystyle=S(S(f_{1},f_{2}),f_{3}),$ $\displaystyle S(f_{1},1)$
$\displaystyle=f_{1},$ $\displaystyle S(f_{1},f_{2})$
$\displaystyle=S(f_{2},f_{1}),$ $\displaystyle
S\left(f_{1},\frac{2f_{1}-4}{2f_{1}-1}\right)$ $\displaystyle=1,$ (23)

which is an abelian group under swapping in the domain
$[0,1]\setminus\frac{1}{2}$.

Now, considering success probability, we can define,

$\displaystyle P(p_{1},p_{2})$ $\displaystyle=P(p_{2},p_{1}),$ $\displaystyle
P(P(p_{1},p_{2}),p_{3})$ $\displaystyle=P(p_{1},P(p_{2},p_{3})),$
$\displaystyle P(p_{1},1)$ $\displaystyle=p_{1},$ (24)

This forms an abelian monoid,

$\displaystyle\hat{\rho}_{1}\ast\hat{\rho}_{2}$
$\displaystyle=\hat{\rho}_{2}\ast\hat{\rho}_{1},$
$\displaystyle(\hat{\rho}_{1}\ast\hat{\rho}_{2})\ast\hat{\rho}_{3}$
$\displaystyle=\hat{\rho}_{1}\ast(\hat{\rho}_{2}\ast\hat{\rho}_{3}).$ (25)

These properties also hold for the success probabilities as well. In the case
of purification for a multi-edge graph, there exists a unique reduction, which
implies that,

$\displaystyle\hat{\rho}_{\text{D{\"{u}}r}}=\hat{\rho}_{\text{Deutsch}}.$ (26)

This unique reduction is,

$\displaystyle
F=\frac{\prod_{i=1}^{n}F_{i}}{\prod_{i=1}^{n}F_{i}+\prod_{i=1}^{n}(1-F_{i})},$
(27)

for the case of fidelity.

It is important to note that for more general error models this relationship
no longer holds. The abelian nature of this result ultimately stems from the
commutativity of the errors through the underlying processes, which need not
hold in general for general error models. For example, in the case of general
Pauli channels, the need for twirling prevents the fidelity functions from
being associative [11].

###  III.3 General reduction strategies

More generally, the combined effect of an arbitrary sequence of elementary
operations and orderings can be reduced to a single cost-vector. In the
instances above we were able to derive these analytically owing to their
commutative behaviour and determinism in their ordering. In a more general
scenario where operations might not commute and randomisation (e.g via
twirling operations) is involved, sampling techniques could be applied to find
their average case behaviour and hence equivalent cost-vector.

The greedy multi-path routing algorithm (Alg. 2) is an example of a graph
reduction algorithm that reduces a sub-graph to an effective end-to-end cost
vector. In the future, we anticipate more sophisticated techniques will be
developed based on the application of graph reduction identities, which would
be applied on the network in advance to simplify the complexity of subsequent
routing algorithms. Alg. 1 shows a computationally efficient algorithm for
graph reduction based upon iterative application of such identities. This
approach needn’t be optimal in general since the outcome is dependent on the
ordering of the substitutions, and a full optimisation would involve
investigating combinations of these. Despite being sub-optimal, applying Alg.
1 prior to subsequent routing algorithms (e.g greedy shortest-path, as per
Alg. 2) would allow for better utilisation of the graph regions and therefore
better entanglement resources between the end-users.

Figure 8: Two graph reduction primitives emerge from our elementary physical
devices. Entanglement swapping as a physical primitive, yields reduction rules
for mapping linear sub-graphs to a single pair. Entanglement purification
allows a 2-cycle sub-graph to similarly reduce to a single pair.

input : graph $G$, threshold $\epsilon$.

output : reduced graph $H$.

begin

$H=G$

repeat

$H^{\prime}=H$

$H=$ reduce_cycles(_$H$_)

$H=$ reduce_linear(_$H$_)

for  _$e\in E$_ do

if  _$d(e) >\epsilon$_ then

$H=H\setminus e$

until  _$H=H^{\prime}$_

return _$H$_

Algorithm 1 Pseudo-code for entanglement distribution network graph reduction.

##  IV Entanglement routing strategies

We now discuss entanglement routing strategies, which are the ultimate
application in graph reduction, where for some number of arbitrary user-pairs,
we wish to collapse the entire network graph down to the effective cost
vectors between them. We begin by discussing conventional shortest-path
routing, before moving onto multi-path routing, a uniquely quantum routing
technique.

###  IV.1 Shortest-path routing

A graph optimisation algorithm we make heavy use of, due to its inherent
efficiency, is Dijkstra’s shortest-path algorithm [10]. For single source and
destination, $A\to B$, this exhibits worst-case runtime,

$\displaystyle O(|V|^{2}),$ (28)

for $|V|$ vertices, which can be reduced to,

$\displaystyle O(|E|+|V|\log{|V|}),$ (29)

for sparse graphs [13].

This generalises to the Vehicle Scheduling Problem for $n$ pairs of sources
and destinations,

$\displaystyle\\{A_{i}\to B_{i}\\},\,i=1\dots n,$ (30)

that must be simultaneously minimised. Unlike Dijkstra’s algorithm, this
problem does not scale efficiently with $n$, and is known to be NP-hard in
general. Thus, as a greedy approximation heuristic, multiple applications of
single-user Dijkstra may be employed instead of performing the full multi-user
optimisation.

###  IV.2 Multi-path routing

Ordinary routing problems involve finding the shortest paths between end-users
of a network. With quantum networks however, we are more interested in finding
optimal path-sets between end-users. This is because paths in the quantum
network represent entanglement links, and with purification, we can make use
of multiple paths simultaneously to generate high-quality entangled states.
This more general objective of finding the best sets of paths is known as
multi-path routing [28, 35], and its goal is to make use of as much of the
network as possible.

This motivates the development of analytic laws that characterise how
different network areas relate to the costs associated with routing and
purifying entangled states across said areas.

###  IV.3 Analytic area laws

Consider the case where we have a strand of vertices of depth $d$ where
between each pair of vertices there are $b$ edges, defining a region of the
graph as per Fig. 9.

Figure 9: A graph with a regular structure (such as a lattice), or with
certain statistical properties (such as random or percolation graphs), will
exhibit area laws, relating their geometry to quality of a final Bell-pair
that can be prepared across it.

Then the log-fidelity between two vertices is given by,

$\displaystyle\log(F)=\log\left(\frac{2\prod_{i=1}^{b}F_{i}}{\prod_{i=1}^{b}F_{i}+\prod_{i=1}^{b}(1-F_{i})}-1\right).$
(31)

For depth $d$, the log-fidelity then becomes,

$\displaystyle\log(F)$
$\displaystyle=\sum^{\infty}_{n=0}(-1)^{n}\log\left(\prod_{i=1}^{b}F_{i}-\prod_{i=1}^{b}(1-F_{i})\right)^{d-n}$
$\displaystyle\cdot\log\left(\prod_{i=1}^{b}F_{i}+\prod_{i=1}^{b}(1-F_{i})\right)^{n}.$
(32)

It is clear that the fidelity of the established entanglement link scales with
depth and width as $O(b^{d})$. In the case of success probability we can
establish a corresponding result. The probability of success for swapping down
a chain of length $d$ is ${P_{s}}^{d}$ where $P_{s}$ is the swapper success
probability. Then the overall success rate scales as,

$\displaystyle P_{\mathrm{tot}}=P^{bd},$ (33)

for breadth $b$. Thus, the failure rate grows exponentially in the area of the
circuit.

###  IV.4 Greedy multi-path routing

Since determining optimal graph regions to allocate to users is in general
computationally hard, we define an algorithm based on multiple applications of
Dijkstra, which although not optimal in general, provides a highly efficient
approximation, whose complexity scales only linearly with the number of users,
described in Alg. 2.

input : graph $G$, source $A$, destination $B$, threshold $\epsilon$.

output : Bell pair $\hat{\rho}_{A,B}$.

begin

$\mathrm{pairs}=\emptyset$

repeat

$g=$ shortest_path(_$G_{A\to B}$_)

if  _$d(g)\leq\epsilon$_ then

$\hat{\rho}^{\prime}=$ reduce(_$g$_)

$\mathrm{pairs}=\mathrm{pairs}\cup\hat{\rho}^{\prime}$

$G=G\setminus g$

until  _$d(g) >\epsilon$_

$\hat{\rho}_{A,B}=$ purify(_pairs_)

return _$\hat{\rho}_{A,B}$_

Algorithm 2 Pseudo-code for the greedy shortest-path-removal algorithm for
multi-path entanglement routing.

Conceptually, this algorithm iteratively eliminates shortest paths between
end-points up to a cutoff threshold. These paths all parse into a purification
protocol to reduce the traversed region into a single entanglement link.

This is trivially generalised to the multi-user context with an additional
inner loop over the end-user pairs, providing a computational overhead only
linear in the number of users. An example application of the greedy multi-
user, multi-path routing algorithm to a lattice network is shown in Fig. 10.

Figure 10: Example execution of the greedy multi-user, multi-path routing
algorithm for 3 user-pairs on a $10\times 10$ lattice. Colour coding denotes
which channels are allocated to which user-pairs by the algorithm. For each
user-pair, resultant paths are finally purified together, yielding end-to-end
entanglement links of higher fidelity than the individual shortest-paths. Fig.
19 provides a similar example for multi-user temporal routing.

###  IV.5 Multi-user routing

Given that multi-path routing reduces a sub-graph of $G$ to an entanglement
link between end-users, the multi-user case is equivalent to a graph
partitioning problem.

Let us assign $G_{i}$ to each pair of users $A_{i}\to B_{i}$. These sub-graphs
partition the entire graph, such that,

$\displaystyle G$ $\displaystyle=\bigcup_{i}G_{i},$ $\displaystyle G_{i}\cap
G_{j}$ $\displaystyle=\emptyset\,\,(i\neq j),$ (34)

illustrated in Fig. 11. This yields an algorithmic generalisation of Alg. 2 to
the multi-user case, provided in Alg. 3.

Figure 11: For multi-user networks, we associate a sub-graph $G_{i}$ to each
pair of users $A_{i}\to B_{i}$. These sub-graphs partition the entire graph,
and a metric is associated with each sub-graph, specifying its quality (e.g
effective fidelity). A graph-partitioning algorithm is to employed to find an
optimal (or approximation thereof) partitioning that satisfies constraints
imposed on the metric associated with each sub-graph. Shown above is an
example for a 3-user network.

input : graph $G$, sources ${\vec{A}}$, destinations ${\vec{B}}$, threshold
$\epsilon$.

output : Bell pairs $\\{\hat{\rho}_{{\vec{A}},{\vec{B}}}\\}$.

begin

$\mathrm{pairs}=\emptyset$

repeat

${\vec{g}}=$ multi_user_shortest_path(_$G_{{\vec{A}}\to{\vec{B}}}$_)

if  _$d(g_{i})\leq\epsilon\,\forall\,i$_ then

$\hat{\rho}^{\prime}=$ reduce(_${\vec{g}}$_)

$\mathrm{pairs}=\mathrm{pairs}\cup\hat{\rho}^{\prime}$

$G=G\setminus{\vec{g}}$

until  _$d(g_{i}) >\epsilon\,\forall\,i$_

$\hat{\rho}_{{\vec{A}},{\vec{B}}}=$ purify(_$\mathrm{pairs}$_)

return _$\hat{\rho}_{{\vec{A}},{\vec{B}}}$_

Algorithm 3 Pseudo-code for the multi-user implementation of the iterative
shortest-path removal algorithm for multi-path entanglement routing. Note that
this relies on a multi-user shortest-path subroutine, which are NP-hard in
general. However efficient approximations such via sucessive applications of
Dijkstra could be employed instead.

##  V The philosophy of quantum vs. classical networking

From our theoretical framework, there emerge a number of distinct conceptual
and philosophical principles that distinguish multi-path entanglement routing
networks from conventional digital networks:

  * •

In classical networks we conceptually desire to use the shortest available
path within a graph to form a communication link (e.g using a Dijkstra-type
shortest path algorithm) whereas in the quantum case we desire to exploit the
optimal subgraph between two points — the subgraph that upon reduction
provides the optimal best possible end-to-end cost vector.

  * •

Equivalently, in the classical case we wish to minimise use of the network
graph, whereas in the quantum case we want to exploit all of it.

  * •

In the multi-user scenario, both multi-user shortest-path algorithms (in the
classical case), and optimal graph partitioning algorithms (in the quantum
case), are NP-hard in general to perform optimally. However, heuristic
approximation methods for these have been well studied (and obviously our
current classical internet relies heavily on such sub-optimal approximation
techniques).

  * •

Multi-path entanglement routing can be considered conceptually similar to the
classical notion of load balancing, whereby instead of maximising bandwidth by
distributing data-packets via redundant routes, we are engaging in decoherence
balancing by distributing entanglement via redundant routes and subsequently
purifying them into one.

  * •

Because entanglement purification consumes Bell pairs in order to increase
fidelity, it induces a direct trade-off between bandwidth (i.e the rate of
Bell-pair distribution) and fidelity, since it necessarily consumes Bell-pairs
in the process.

  * •

Much like classical resistance networks, adding resources to a quantum network
cannot decrease network performance. Redundant pathways in quantum networks
are in fact highly desirable since they imply additional possibilities for
graph reduction/routing.

##  VI QuNet: A package for simulating quantum networks

QuNet is open-source software for simulating entanglement networks and
benchmarking entanglement routing algorithms, available at
https://peterrohde.github.io/QuNet, including source code, documentation, and
the demonstration files used to generate the results presented here.

###  VI.1 Related work and motivation

Several quantum internet simulators currently exist, the most established of
which are (in no particular order) NetSquid (https://www.netsquid.org) [6],
QuNetSim [9], SQUANCH [1], QuISP [21] and SimulaQron [7]. Although these
packages differ in their methodology, they share the following similarities to
some degree:

  * •

Network agents (end-users) hold registers of qubits.

  * •

There exists a scheme for relating the local registers in such a way to
describe entangled states that are shared between end-users.

  * •

The evolution of the underlying quantum states of the network is simulated
under some combination of local operations and measurements, usually by
interfacing the software with an existing quantum circuit simulator.

  * •

Noise effects, which are often time sensitive, and or event broadcasting are
implemented with the use of a discrete-time event engine.

  * •

The goal is to test end-user applications, the scope of which is predominantly
low-level communication protocols, or towards the development of a quantum
protocol stack.

The primary distinction of QuNet is that it considers a subset of error
channels that are expressible in terms of additive cost metrics. This allows
us to represent complex quantum networks with a simple set of weighted graphs
(one graph for each cost). QuNet therefore operates at a high level of
abstraction as opposed to a low-level link layer where the control sequences
of individual network components are implemented.

In using this approach we are able to exploit existing graph theoretic routing
algorithms, which are computationally efficient and well-studied. Furthermore,
we are able to extend these techniques to accommodate for quantum memories
using temporal meta-graphs, described in Sec. VI.3. A limitation of this
approach is that it doesn’t lend itself to modeling arbitrary channels, in
particular non-commutative ones that cannot be expressed as additive metrics.

###  VI.2 Design principles

The goal of QuNet is to perform cost-vector analysis in quantum networks,
based on user demand, to make optimal routing decisions. Because QuNet is
highly algorithmically efficient, it could be employed for overseeing quantum
networks and making real-time routing decisions for the purposes of classical
control of the network in the response to live user demand. QuNet employs the
following methodology:

  1. 1.

Given a graph with a number of end users, we apply sequences of elementary
physical operations (notably purification and swapping) to perform graph
reduction, yielding equivalent cost vectors for established entanglement
links.

  2. 2.

Efficient cost vector analysis algorithms are performed on the graph to find
optimal routing strategies for establishing these entanglement links in
response to end-user requests.

The principle advantage of QuNet’s cost vector approach is that it does not
require direct tracking of quantum states, thereby bypassing some quantum
complexity issues, and ensuring compatibility with existing graph theoretic
techniques.

Figure 12: Users interact with the QuNet package via QNetwork objects,
comprising any number of QNode and QChannel objects. QuNet interfaces with the
LightGraphs package to implement core functionality, which is interchangeable
for other graph libraries, and which users do not interact with directly.
Figure 13: A temporal meta-graph is constructed by layering instances of the
underlying graph over some number of time-steps, $T$. Nodes possessing quantum
memories have vertical directed edges connecting the node to itself at the
next time-step, representing a delay. To find a route from $A$ to $B$, we
construct dummy asynchronous nodes for each. The asynchronous source for $A$
connects outwardly to all nodes $A$ for each time-step. Similarly, the
asynchronous sink for $B$ connects inwardly to all nodes $B$ for each time-
step. Thus, the asynchronous nodes allow the route-finding algorithm to
discover all nodes associated with $A$ and $B$ throughout the entire temporal
meta-graph. The incremental weights $\epsilon$ guide route-finding to
prioritise the earliest available time-slots for a given user. Thus by
increasing the overall graph by a factor of $T$, we remain fully compatible
with existing route-finding algorithms based on shortest-path removal, and
retain their associated efficiency, without the need for any temporal
combinatorics. Fig. 19 shows an actual example from a QuNet simulation,
demonstrating channel allocation to multiple user-pairs under multi-path
temporal routing.

QuNet is based on the following design considerations, and structured as shown
in Fig. 12:

  1. 1.

QuNet is written in Julia (https://www.julialang.org), a high level language
that compiles to high-performance native code, interfaces with Python and
C/C++, and can be embedded into interactive Jupyter (https://www.jupyter.org)
notebooks.

  2. 2.

We ensure scalability for large networks by utilising only computationally
efficient routines and avoiding complex combinatoric optimisation. Most
notably, we rely heavily on Dijkstra’s shortest path algorithm, which is
highly efficient in graph size.

  3. 3.

Graph library independence: although the current implementation relies on the
Julia LightGraphs package (https://www.juliagraphs.org), this is designed to
be easily interchangeable for any graph library implementing the necessary
primitives. A current limitation is that LightGraphs does not provide support
for multi-graphs.

  4. 4.

Users interface with QuNet using only a QNetwork object and its constituent
QNode and QChannel objects, which are graph library agnostic.

  5. 5.

Dynamic simulations: nodes may not be stationary, as is the case for satellite
nodes, in which case the cost vectors of associated channels dynamically
update accordingly. QuNet accommodates for different channel types, including
free-space and optical fibre links, with their respective decay
characteristics.

  6. 6.

Network abstraction: QuNet’s QNode and QChannel types can take arbitrary form,
independent of the underlying technological implementation. Cost vectors
needn’t be restricted to representing device-level properties, but could
abstractly represent entire device sequences by reducing them to their
equivalent cost vector. For example, an entire quantum repeater sequence [15,
22, 34, 33, 23] comprising complex control over swapping and purification
operations could be reduced to a single abstract QChannel representing its net
effective cost vector. Similarly a large SneakerNet [8] channel, in which
entanglement is physically transported under heavy error correction, can be
represented by a single QChannel representative of overall state decay under
that mode of communication, independent of its internal operation. Thus, a
QNetwork object can represent an entire network at any level of abstraction,
ranging down from the device level up to high level abstractions of
constituent sub-networks, backbones, or regions of interest.

###  VI.3 Simulating quantum memories with temporal meta-graphs

A major problem facing multi-user networks is congestion as the number of
competing users increases. Obviously, the availability of quantum memories
[16, 20] can easily overcome congestion by enabling qubits to wait until
channels become available for their use. Many conventional multi-user graph
optimisation techniques are highly inefficient as the number of users
increases, since combinatoric optimisation must be employed. To overcome this,
we developed a temporal optimisation algorithm based on Dijkstra’s algorithm
that is highly efficient and bypasses any combinatoric optimisation.

The algorithm and its computational complexity are described in detail in App.
A. The concept of the algorithm, based on so-called temporal meta-graphs is
shown in Fig. 13.

The overall computational complexity of multi-user route-finding using
temporal meta-graphs scales as,

$\displaystyle O(M^{3}V^{2}),$ (35)

where there are $M$ user-pairs in a $V$-node graph.

Figure 14: Two examples of entanglement routing between users $A$ and $B$,
where time flows downwards. (top) An alternating sequence of entanglement
sources and swappers. Here the path between $A$ and $B$ is allowed to route
backwards in time since entanglement swapping is time-independent. (bottom) A
simple sequence of qubit routers, which cannot route backwards in time.

A natural expectation is that temporal links are all fixed in the same
direction. Surprisingly however, temporal links could be bidirectional for
system comprised of alternating entanglement sources and swapper nodes. This
is shown in Fig. 14. The reason for this bidirectionality is that entanglement
swapping is not a time sensitive operation. A sequence of swaps needn’t be
performed in a specific chronological order.

In a similar but unrelated vein, asynchronous links can be manipulated for
different timing requirements. For example, if Alice strictly requires that
she receive her qubit at a given time(s), then every one of her incoming
asynchronous edges that do not satisfy her time condition can be removed.
Similarly, if Bob wishes to send a qubit at a given time(s), then all his
outgoing asynchronous edges that fail his condition can be removed. The
asynchronous edges chosen by a temporal routing algorithm specifies a routing
queue for users.

##  VII Advanced route optimisation in entanglement distribution networks
using QuNet

We now showcase the capabilities of QuNet by benchmarking our greedy multi-
path routing algorithm against a range of relevant network scenarios. To aid
in benchmarking, we limit ourselves to the study of square lattice networks,
however QuNet is equally readily applicable to arbitrary network topologies
and routing strategies. Here, we use QuNet to investigate network performance
the following scenarios:

  * •

Single-user networks with purification-based multi-path routing.

  * •

Multi-user networks in the context of competition and congestion effects.

  * •

Percolated networks with random channel failure.

  * •

Overcoming multi-user network congestion through network scaling.

  * •

Overcoming multi-user network congestion via temporal routing and the use of
quantum memories.

Our greedy multi-path algorithm represents the simplest such algorithm that is
suited to cost-vector analysis, but is readily adaptable and allows many
opportunities for further optimisation for quantum network engineers.

###  VII.1 Benchmarking multi-path purification with single-user networks

Figure 15: Single-user network performance versus grid size for different
numbers of maximum allowed (edge-disjoint) paths. For each trial run, one
random user pair was selected on a $n\times n$ rectangular lattice and was
routed using greedy_multi_path. Each edge has 1dB costs in efficiency and
fidelity, and each data point is the average of 5000 random trials. (a)
Average routing costs in terms of efficiencies $\eta_{j}$ and fidelities
$F_{j}$, where $j$ is the maximum number of allowed paths. (b, c) Average
costs plotted on a log scale for fidelity ($F_{j}-\frac{1}{2}$) (b) and
efficiency (c). A solid line is plotted for the one-path case where an exact
analytical solution is known. For the multi-path cases, the shaded areas show
estimated expected scalings for each case, based on analytical approximations.
(d) Probability $P_{j}$ that a user finds $j$ paths in the case where up to
four paths may be purified. Analytical curves for each path probability are
overlaid.

The primary goal of QuNet is to use efficient, classical cost-vector analysis
to predict the expected performance of a quantum network, thus avoiding the
need for full quantum-state simulations of a complex network. Entanglement
swapping and multi-path purification are the critical elements that allow
quantum network links to be established in the presence of real-world
imperfections like loss and decoherence. To validate and benchmark QuNet’s
performance in simulating these elements, we first study the simplest possible
case for multi-path routing of a single, randomly chosen user pair in a
rectangular lattice, and in particular how this performance varies with
network size.

For this context, we consider a rectangular lattice of variable size $n$,
where each link is affected by both loss and dephasing noise with a 1dB cost
to the loss rate and the dephasing probability respectively. For each trial,
we select a random user pair in the network, and use our greedy_multi_path
algorithm to identify a good set of paths connecting the two users, up to some
specified maximum number of allowed paths. This allows us to explicitly study
the effect of multi-path purification on single-user network performance. In
this context, where there is no competition between user pairs, the number of
available paths will then be further constrained only by the degree or
connectivity of each end user, which is determined by their location near the
edge or within the body of the graph.

We present the results for this scenario in Fig. 15. The average fidelity and
efficiency of a transmitted Bell pair is given in Fig. 15(a). As expected from
the post-selective nature of the purification process, we see fidelity
increase with successive purifications at the cost of decreasing efficiency.
We also find that both the fidelity and efficiency decrease with grid size,
due to the consequent increase in average distance between randomly selected
user pairs. For a rectangular lattice, the average separation between two
vertices, known as the average L1 or Manhattan distance, scales linearly with
the grid size according to the fraction $\frac{2}{3}n$ (See App. B). By
plotting the fidelity and efficiency costs on a log scale (Figs. 15(b,c)),
except at small $n$, we confirm that these costs scale exponentially towards
their asymptotic values of $\frac{1}{2}$ and $0$, respectively, as expected
from Eq. 6. We see some deviation from this asymptotic scaling at small grid
sizes, which we attribute primarily to edge effects that arise because end
users located at the edge may not have access to the maximum number of paths
available for purification. These edge effects, and the fact that they
diminish with grid size, are illustrated in Fig. 15(d), which shows the
probabilities that a randomly chosen user pair will have access to a certain
number of paths as a function of the grid size.

Having validated QuNet’s qualitative predictions, we now turn to the question
of how to validate its quantitative performance against analytical
expectations. In fact, predicting the behaviour of complex networks
analytically in any scenario involving competition is a very challenging
problem. This is a scenario that arises naturally in the case of quantum
networks where the aim is to exploit multi-path routing for the purpose of
purification. For a single path, Fig. 15 shows that QuNet agrees exactly with
a simple analytical prediction calculated as a function of average Manhattan
distance. As soon as purification is incorporated, however, even for simple
single-user networking scenarios, the path competition that this introduces
increases the difficulty of the analytics combinatorically. This is exactly
why a numerical simulation package like QuNet is invaluable for benchmarking
quantum networks.

Here, we identify three effects that complicate the calculation of analytic
costs in the context of networks with purification. Firstly, the lengths of
available network paths will depend on whether the end users lie in the same
row or column. To illustrate, let $L$ be the Manhattan distance between an
end-user pair in the middle of a large grid lattice (that is, neither end user
located on a lattice edge). The four shortest edge-disjoint paths connecting
them will have lengths $(L,L+2,L+2,L+8)$ for users in the same row or column,
and $(L,L,L+4,L+4)$ otherwise. The proportion of user pairs in each category
is easily calculated, at least in the single-user case: The chances of
selecting a user pair in the same row or column diminishes quadratically with
grid size, and this fraction can be neglected if the grid is sufficiently
large. Secondly, users on the boundary of the network have constrained
connectivity, and therefore may not be able to utilise up to the maximum
number of allowed paths for purification. Again, the proportion of user pairs
affected by this is readily calculated: Fig. 15(d) shows first that an
analytical calculation of available path probabilities (solid lines) exactly
agrees with the numerical data obtained from QuNet simulations, and second
that this effect also diminishes with grid size, and can be neglected for
large enough grid sizes. Except for the next effect, both of these could be
readily accounted for in analytical calculations, but the final issue, that
arises because purification leads to non-linear propagation of costs (Eq.
II.4), is unavoidable. For example, the average costs associated with purified
paths (averaged over randomly selected user pairs) is not equal to the cost of
purified paths calculated from the average Manhattan distance between user
pairs, which is how we predicted the single-path costs in Fig. 15.
Unfortunately, calculating the proportion of users separated by a given
Manhattan distance when randomly selecting both users in a pair on a fixed
finite grid increases in difficulty combinatorically, compounded by the first
two effects described above. This is already prohibitively difficult for the
single user pair case, and only becomes more challenging for more complicated
scenarios involving complex network topologies or competition between multiple
user pairs. As a result, using a package like QuNet which enables a Monte-
Carlo random-sampling approach becomes a much simpler and more efficient way
to calculate costs in the context of purification.

Because of this, we elected to check our multi-path data against two
oversimplified estimates that do not account for the non-linearity of
purification, but provide a rough region for the expected values, and help
establish confidence that QuNet’s purification scheme is working correctly.
These estimates, which define the edges of the shaded regions in Figs. 15(b,
c), are calculated by purifying a set of paths with lengths given by the edge-
disjoint path sets described above—$(L,L+2,L+2,L+8)$ for users in the same row
or column, and $(L,L,L+4,L+4)$ otherwise—with $L$ taken to be the average
Manhattan distance for a given lattice size.

###  VII.2 Multi-user, multi-path routing

Figure 16: Network performance with the number of competing end users. For
each sample, $n$ random userpairs were selected on a $10\times 10$ grid
lattice and were routed using greedy_multi_path. Each edge has 1dB costs in
efficiency and fidelity, and each data point was collected with 5000 samples.
(top) Average routing costs in terms of average conditional efficiency $\eta$,
average conditional fidelity $F$, and average unconditional efficiency.
(middle) The probability that the last userpair queued in greedy_multi_path
finds at least one path. Unfilled circles are data points where no path was
found in the 5000 samples. [top right] log plot. (bottom) Probability $P_{j}$
that a user finds $j$ paths. $P_{P}$ is the probability of purification, that
is, the likelihood a userpair finds at least two paths between them.

Competition between end-users is an important consideration in any network,
but is especially significant in quantum networks, where information to be
shared cannot be cloned to mitigate against the inevitable effects of
transmission loss, and purification is instead required. As such,
understanding how user demand and competition affects overall network
performance is extremely useful in the design of quantum networks. Here, we
benchmark the performance of our greedy_multi_path algorithm for a $10\times
10$ grid lattice with an increasing number of randomly selected user-pairs up
to the fully saturated limit of 50 user pairs. Each link has a 1dB cost in
loss rate and dephasing probability, and users can route up to the maximum
four edge-disjoint paths allowed by the degree of graph connectivity. The
results of this scenario are shown in Fig. 16.

Fig. 16 (top) shows how average networking costs change with the number of
competing user pairs. As discussed in Sec. II.2.4, we analyse the network
performance in terms of complementary costs, efficiency and conditional
fidelity. Starting from the maximal fidelity expected for the $10\times 10$,
single-pair case already analysed in Fig. 15, we see the fidelity initially
decrease, before flattening out to a steady-state value after approximately 10
user pairs. By contrast, while the efficiency initially increases, it reaches
a maximum value at around 10 user pairs, before decaying away towards zero.
The initial change reflects the fact that as more users are introduced into
the network, fewer user pairs are able to access multi-path routing, and
without the ability to exploit the post-selective purification process, this
leads to higher efficiencies, but lower fidelities. In Fig. 16 (bottom), we
see that the rates associated with users finding multiple paths all decrease
rapidly, and the proportion of users finding only one path increases to a
maximum at around 10 user pairs. However, we also see a new effect, arising
due to multiuser competition, namely that the proportion of users finding no
paths ($P_{0}$) increases rapidly after the same point. Thus while the
conditional fidelity appears to reach a steady-state value even for large
numbers of users, the decaying overall efficiency for a randomly selected user
pair highlights that the network becomes less and less effective at
distributing entanglement. To isolate the different efficiency effects at
play, we also plot a conditional efficiency cost, where the efficiency is
averaged only over those users who are able to find at least one path. Now,
the efficiency also reaches a steady state value after around 10 user pairs.
In this multiuser scenario, QuNet’s greedy multipath algorithm cycles
sequentially through all randomly chosen user pairs (in a fixed order),
looking first for one path each, then more paths. Fig. 16 (middle) shows that
the rate at which the final user finds at least one path decays very rapidly
towards zero, and shows that even though it is possible to choose up to 50
non-colocated user pairs in a $10\times 10$, overall network congestion
increases very rapidly and the network capacity effectively reaches full
saturation at many fewer user pairs. And once new user pairs can no longer
find any new paths, adding users no longer affects how many paths can be found
by the other user pairs and the distribution over path numbers remains
constant. Indeed, by aggregating the multiple-path rates into a single
probability of a user pair being able to access purification, $P_{P}$, we see
that this probability drops rapidly and monotonically from 1 to a low steady-
state value at around 10 user pairs, with the curve closely tracking the shape
of the efficiency curve observed in the top panel. These results are
consistent with the change in purification rate being the main effect driving
the changing path costs in this multiuser setting.

###  VII.3 Channel percolation effects

Figure 17: Network performance with edge percolation rate. For each sample,
one randomly chosen userpair on a $10\times 10$ grid lattice was routed using
greedy_multi_path. Each edge has 1dB costs in efficiency and fidelity, and
every edge has an identical probability of being removed. Each data point was
collected with 5000 samples. (top) Average costs for routing in terms of the
efficiency $\eta$, and fidelity $F$ of the Bell pair. The solid lines are the
average Manhattan distance postselected on whether the userpair is connected
in the network. (middle) [left] the average Manhattan distance and the average
shortest path distance between the userpair, both of which are post-selected
on whether the userpair is connected. (bottom) Probabilities of different path
finding scenarios such that $P_{j}$ is the case that $j$ paths were found
between the userpair.

Real-world networks inevitably fail when nodes or channels malfunction. This
leads to the notion of _percolation theory_ in networks [4, 36, 18], which
shows that communication can remain robust provided failure rates lie below
some percolation threshold associated with the topology. Although this is
something well-understood in classical networks, we start to explore how the
dynamics may vary in quantum networks where multi-path routing may be
utilised. For this scenario, we consider a single random user pair routed on a
$10\times 10$ grid lattice where each edge has an identical probability of
being removed. As before, surviving edges have 1dB costs in loss and
dephasing. Fig. 17 (top) shows how the routing costs of our algorithm vary
with the percolation rate in terms of average fidelity ($F$) and efficiency
($\eta$). At percolation probability equals zero, this scenario reduces to the
single-user, multipath routing scenario studied in the previous figures, so
the costs start from same, previously calculated values. As the percolation
probability increases, however, the cost trends show two distinct regions,
which we now explain.

In the first region, at percolation probabilities up to around 0.4, we see
that fidelity steadily decreases, while the efficiency increases. (Plotting
the log of efficiency, not included here, shows that the efficiency initially
increases exponentially with percolation probability.) This behaviour is a
result of changing purification rates. From Fig. 17 (bottom), which shows the
rates at which the user pair finds multiple paths, we observe a steady trend,
as expected, towards fewer paths being available for use in multipath
purification. Since purification increases fidelity at the cost of efficiency,
this trend results in decreased fidelity and increasing efficiency as a
function of percolation probability.

In the second region, the efficiency continues to increase, but the fidelity
turns around and starts increasing again. Recall, however, that here we are
plotting the conditional fidelity. As with the previous multi-user scenario,
increasing percolation rates introduce effective competition into the network,
and we see an increasing probability that even a single user pair fails to
find any viable communication paths. In the $10\times 10$ lattice case, this
starts to be significant for percolation probabilities above approximately 0.3
to 0.4 (Fig. 17 (bottom)).

To understand why this leads to increasing fidelities, we plot two
complementary measures of average user pair separation (Fig. 17 (middle)). The
average shortest path distance calculates the length of the shortest available
path between the user pair. The initially increase in this value highlights
the fact that percolation forces users to communicate via more circuitous
paths to detour around missing links. Despite this effect, we see that this
path length steadily decreases after percolation probabilities of around 0.4.
The conditional average Manhattan distance (calculated for sample pairs with
available communication paths) shows no similar initial increase, but also
steadily decreases for percolations above 0.4. Since this quantity depends
only on the users’ relative positions, this decrease directly reflects the
fact that far separated user pairs become significantly less likely to find
any available paths for large percolation probabilities. The graph begins to
break up into multiple disconnected patches, and user pairs located on
different disjoint patches are unable to find a viable communication path. The
conditional Manhattan distance provides a measure of the typical size of
intact patches, and the disparity between it and the conditional shortest path
distance provides a measure of the irregularity of shape in these patches.
Because only closer spaced user pairs survive, both fidelity and efficiency
costs increase for higher percolation rates. We can also illustrate the
changing conditional Manhattan distance directly in the corresponding expected
costs (Fig. 17 (top)). When the percolation probability is small, the ability
to purify multiple paths on average causes a strong mismatch between these
costs. For large percolation rates, however, where purification capacity is
limited, the simulated costs converge towards the values predicted from the
conditional average Manhattan distance.

###  VII.4 Network scaling effects

Figure 18: Routing data for fifty randomly chosen userpairs using using
greedy_multi_path on a grid lattice with variable size. Each edge has 1dB
costs in loss and dephasing probability, and each data point was collected
with 500 samples. (top) Average multipath routing costs, shown in log scale,
for the efficiency $\eta$, and fidelity $F$ of the Bell pair (or rather,
$F-\frac{1}{2}$). Note that, in log scale, the fidelity data does not show
across the full range, because the fidelity rapidly saturates to its
asymptotic value of 0.5 beyond the floating point precision used to store the
data. (middle) Probability that the last pair is able to find at least one
path between them. (bottom) Probabilities of different path finding scenarios
such that $P_{j}$ is the case that $j$ paths were found between the user pair.

In the previous sections, we demonstrated two competition effects, user
congestion and link percolation, which hinder the performance of multi-path
entanglement routing. Here, we consider strategies to ameliorate the effects
of competition, which we will demonstrate for the case of network congestion.
A simple, if perhaps brute-force strategy for mitigating competition is to
increase the scale of the network.

To explore this scenario, shown in Fig. 18, we start with the same fully
saturated $10\times 10$ rectangular lattice network with fifty randomly chosen
end-users that was studied in Fig. 16, and analyse performance as we increase
the size of the network. As before, each edge has a 1dB cost in loss and
dephasing probability. In this scenario, we expect that as we decrease the
relative density of user pairs, more links will be routed on average in
exchange for a larger average path length. Fig. 18 (top) is a logarithmic plot
showing the average routing costs in terms of $\eta$ and $F-\frac{1}{2}$
versus grid size, the clear linear trends showing the expected exponentially
decaying success probabilities with average path length. What is perhaps
somewhat surprising is that this effect completely dominates any improvement
in congestion that might have been expected to result from increasing the
number of paths available for path routing.

As seen in Fig. 18 (bottom), and earlier, for the fully saturated $10\times
10$ lattice, there is more than an 80% chance that a randomly chosen user pair
will not be able to find any viable communication pathways. In Fig. 18
(bottom), we also see that the proportion of users that do find paths
increases rather rapidly with gridsize. Despite this, Fig. 18 (middle) shows
that the rate that the last (50th) user is able to find a path does not start
to increase significantly until we reach a grid size around $50\times 50$ (a
network 25 times larger than the initial $10\times 10$ case). Even then, this
increases rather slowly, not even exceeding 50% until a lattice size around
$130\times 130$, by which point the end-user pairs already occupy just a
fraction of a percent of the total nodes. The proportion of users finding the
most paths (3 or 4) increases even more slowly. Indeed, across the full range,
$P_{3}$ and $P_{4}$ combined only reach around 5%, whereas $P_{2}$ (still
increasing) reaches in excess of 80%, substantially larger than the maximum
$P_{2}$ reached in either Fig. 16 or 17.

By comparison, the probability a random user pair will have the connectivity
required to find 3 or 4 paths in principle, is already much larger than 99%.
These results indicate that it is much more difficult to unlock paths by
expanding the size of a network than it is to increase congestion by adding
user pairs. Furthermore, the exponential increase in path costs associated
with a larger network, more than counterbalances any potential improvement in
multipath routing that the larger network enables. Even when the user-pairs
make up a tiny fraction of the total number of nodes, we still find
significant competitive effects that limit the multi-path routing capacity.
Increasing lattice size is therefore clearly an ineffective strategy for
solving network congestion in multipath entanglement networks. In the next
section, we explore the alternative paradigm for mitigating congestion with
temporal multiplexing, rather than spatial multiplexing.

##  VIII Temporal multiplexing in entanglement distribution networks using
QuNet

###  VIII.1 Network Performance with Time-depth

In this section, we use our temporal meta-graph formalism developed in Sec.
VI.3 to study the performance of a temporal multiplexing strategy. For
consistency, we again start with a fully saturated $10\times 10$ rectangular
lattice with 50 user-pairs and, this time, analyse the routing performance as
we increase the temporal depth. A simplified example of this temporal multi-
path routing is illustrated in Fig. 19.

In this simulation scenario, we equip each node with one bit of lossless
quantum memory for multi-path routing, which allows our greedy-multi-path
algorithm to find paths that route between temporal-layers. Here, we are
interested in the simplest possible routing scenario where there are no
temporal routing constraints, so that any path connecting a user-pair should
be valid, irrespective of whether the ends of the path lie on the same
temporal layer. Our first assumption, however, that each node has a lossless
memory, does not guarantee that this unconstrained routing will always be
possible. To this end, we therefore endow each node with an auxiliary bit of
lossless quantum memory, to facilitate multipath purification by allowing
users to store an intermediate state until the next qubit is routed to the end
user. One memory is always sufficient for such routing, since multiple Bell
pairs can be purified sequentially, such that at most one bit needs to be
stored at a given time step. In addition, we impose a four-path limit for each
pair so that our comparison is consistent with that of the previous section.

We present the results of this new simulation in Fig. 20. Fig. 20 (top) has
the average routing costs of the network versus the maximum temporal depth of
the meta-graph. The two dotted lines show the asymptotic “competition-free”
values for average efficiency $\eta$ and fidelity $F$, respectively,
calculated by considering the single-user case with up to five temporal layers
available for redundancy. Fig. 20 (bottom) shows the average path
probabilities for a given user in the network. Here, we find that only a few
temporal slices are required to completely resolve the effects of multi-user
competition. In Fig. 20 (bottom), we see $P_{0}$ rapidly becomes negligibly
small: Only five time steps are needed for the congestion effects in a fully
saturated, 50 user-pair network to be completely mitigated. This is consistent
with our previous observations from Fig. 16 that the performance of a
$10\times 10$ network saturates at around 10 user-pairs, because of the large
end-to-end path failure $P_{0}$.

Increasing the temporal depth further, we see network performance quickly
improves towards its optimal costs. Indeed, when using just fewer than 15
layers, we see our network is comparable in performance to an identical
network with just a single user-pair. Far fewer effective nodes are required
to achieve such performance than for spatial multiplexing. We also note how
the path probabilities of Fig. 20 (bottom) strongly contrast those of Fig. 18,
where even the largest graphs have only a marginal increase in multi-path
capacity. Here, on the other hand, the time-depth capacity is maximised after
just fifteen temporal layers.

Another key benefit of temporal multiplexing is the ability to circumvent edge
effects. In Figs 15 and 16, even the single user-pair case, without any
competition, does not achieve maximum multi-path capacity, because user pairs
located at the boundary of the lattice do not have access to the same number
of connecting links, and these edge effects only vanish for very large grid
sizes. In a temporal multiplexing scheme, however, the number of paths that
can be routed does not only depend on the connectivity of the node, but is
augmented by the maximum time-depth. Thus, for applications where very high
fidelity states, and hence large amounts of purification, are required,
temporal multiplexing will be absolutely essential.

###  VIII.2 Effect of Quantum Memories on Unrestricted Temporal Routing

Although our results are conclusively in favour of temporal multiplexing over
spatial multiplexing, and quantum memories will be critical for enabling large
amounts of purification, it is not yet clear how critical quantum memories are
for mitigating congestion. This is because QuNet allows two mechanisms for
routing entanglement through time: memory channels and asynchronous links. We
quantify the effect of memories by considering the average maximum time-depth
reached by our greedy_multi_path algorithm for two different $10\times 10$
grid networks: One with no memory channels for routing, and one with
additional memories available at each node for routing. Note that the nodes in
both networks also each have access to one bit of quantum memory for the
purpose of multi-path purification.

If the addition of memory channels improves the efficiency of multipath
routing through our network, we expect the average maximum time-depth to be
lower in the case where memories are used because of more efficient resource
allocation. What we find in Fig. 21, however, is that the memory channels make
no significant difference in the maximum time-depths reached in any of the
maximum path cases. This means that asynchronous communication along already
appears to be sufficient to achieve a minimal time depth for full multipath
capacity, and the maximum communication bandwidth for our greedy_multi_path
scheme. This therefore suggests that the key benefit of quantum memories for
entanglement networking is not to improve the efficiency of multi-path
routing, but rather to enable multi-path purification between time layers, and
to circumvent the constraints of node connectivity on multipath capacity.
Since purification provides asymptotic improvements to fidelity, we conclude
that memories will be particularly vital for quantum networks with stringent
fidelity requirements.

Figure 19: Example of multi-user, multi-path temporal routing with 3 temporal
steps (stacked). Utilised channels are colour coded according to which user-
pair they serve.

Figure 20: Network performance versus the maximum allowed time-depth. The
underlying network is a $10\times 10$ grid lattice that is extended to $n$
distinct temporal layers and 1 asynchronous layer that represents the nodes
irrespective of time. Each node is equipped with a lossless quantum memory and
so has a directed edge to itself at the next time layer up to the maximum
depth. For each sample, a random user pair is chosen at the asynchronous layer
and is routed through the temporal network using greedy_multi_path. Each edge
(Except for those corresponding to lossless memory) has 1dB costs in
efficiency and fidelity, and each data point was collected with 1000 samples.
(top) Average routing costs in terms of the efficiency $\eta$, and fidelity
$F$ of the Bell pair. The dotted lines are the costs for $\eta$ and $F$ in the
limit where it is assumed each userpair has a time layer to themselves.
(bottom) Probabilities of different path finding scenarios such that $P_{j}$
is the case that $j$ paths were found between the userpair. Figure 21: A
comparison of the average maximum time depth reached by greedy_multi_path for
two different networks; Both are $10\times 10$ grids extended in time by 20
layers but one has lossless quantum memories on each node while the other has
none. If a node has a memory, there exists a directed edge pointing the node
to itself at the next time-layer. The routing between temporal layers is
unrestricted, meaning that users may start and finish at any level they like
so long as it respects causality. Earlier times are prioritised over later
times, and asynchronous routing is prioritised over memory channels. Each edge
(Except for those corresponding to lossless memory) has 1dB costs in
efficiency and fidelity, and each data point was collected with 1000 samples
of randomly chosen user pairs. Data analysis confirmed that the maximum time
depth of 20 was never reached in any of the samples.

##  IX Further applications

In the previous sections, we validated the performance of QuNet for key
primitive networking scenarios, and demonstrated how QuNet can be used to
study complex network features like temporal multiplexing. Here, we conclude
with a few brief examples of how QuNet can be applied to analyse the
performance of networks of real-world significance. Specifically, we explore
how to use QuNet to determine secret key rates for quantum key distribution
(QKD), and determine the bandwidth of above-threshold Bell pairs for fault-
tolerant distributed quantum computation. We also demonstrate how QuNet could
be used as a framework for simulating entanglement distribution satellite
networks. Our proof of concept is a cost-evaluation for a simple time-
dependent satellite network.

###  IX.1 Quantum key distribution

The raw mean Bell pair distribution rate for a single user within the network
is given by,

$\displaystyle R_{u}=\frac{(1-P_{0})\langle\eta\rangle}{\tau},$ (36)

and the net mean Bell pair rate for the entire network across all users is,

$\displaystyle R_{n}$ $\displaystyle=MR_{u}$
$\displaystyle=\frac{M(1-P_{0})\langle\eta\rangle}{\tau},$ (37)

where $M$ is the number of user-pairs, $P_{0}$ is the probability of no paths
being found, $\langle\eta\rangle$ is the average efficiency, and $\tau$ the
number of time-steps required to route all users (i.e the utilised depth of
the temporal meta-graph).

For QKD, the secret key rate ($C$) is related to the fidelity ($F$) and raw
qubit-rate ($R$) via, [24],

$\displaystyle C=R\cdot[1-H(\varepsilon)],$ (38)

where,

$\displaystyle H(x)=-x\log_{2}x-(1-x)\log_{2}(1-x),$ (39)

is the binary entropy, and the error rate $\varepsilon=1-F$. Thus for a given
secret key rate we can establish a trade-off curve between the required
fidelity and efficiency.

We can visualise the routing costs for a quantum network as a density plot and
overlay a contour of curves for different secret key rates, shown in Fig. 22.
Each point in the plot represents the fidelity and efficiency achieved by a
single user-pair, where the intensity of the point is the relative outcome
rate. For a large sample of user-pairs over many trials, such a plot fully
captures the scope of the cost-vector distribution of the network.

Visualising network routing costs in the form of a heatmap additionally
provides insights into cost tradeoffs across all user-pair configurations in
the network. In Fig. 22 we see two dominant curves corresponding to single-
and two-path routing. In Fig. 23 we overlay the scatterplot of this data with
analytic curves representing competition-free multi-path routing costs for up
to four paths. The derivation for these is provided in App. C. Fig. 24
provides deeper insight into the relationship between path utilisation and
fidelity/efficiency tradeoffs in a multi-user setting.

Figure 22: Density heatmap in fidelity/efficiency space of randomly chosen
user-pairs in a $100\times 100$ grid network, sampled over 5000 instances of
50 competing user-pairs. A single user-pair contributes a single point in the
plane, representing its end-to-end fidelity and efficiency. Superimposed is
the tradeoff curve for QKD given by Eq. 38, where contour labels denote the
secret key rate per user, $C$. Figure 23: Scatterplot of fidelity/efficiency
tradeoffs analogous to Fig. 22, superimposed with the analytic curves (red)
derived in App. C. The four red curves show ideal congestion-free tradeoff
curves for different numbers of paths utilised in multi-path routing. The blue
dots correspond to simulated data points, which deviate from these curves as a
result of congestion effects. Figure 24: Fidelity/efficiency tradeoff curves
for multi-user, multi-path routing. From left to right the subplots correspond
to different numbers of maximum allowed paths. From top to bottom we increase
the number of competing user pairs.

###  IX.2 Distributed quantum computation

A more ambitious and challenging future application for the quantum internet
is distributed quantum computation (DQC). The incentive for unifying
geographically disjoint quantum computers is far greater than that for
conventional classical infrastructure given the superlinear scaling in their
computational return upon unification. Furthermore, the prospects of such
cloud-based quantum computing are strengthened by the possibility of
information-theoretically secure homomorphic encryption [37, 26] and blind
quantum computing [5], which are either impractical (in the former case) or
impossible (in the latter case) in the classical context.

For $n$ unified classical computing nodes we expect an $\sim n$-fold gain in
their unified computational power. However the computational return on
monetary investment is roughly invariant under unification given that $n$
nodes also cost $n$ times as much.

This observation changes in the quantum regime. Considering a quantum
algorithm with exponential scaling as an example: When operating independently
we make the same observation as before, however when unified the factor of $n$
shifts into the exponent creating a superlinear return on investment. However
this can only be realised when the underlying network is also quantum.

A simple model for realising this is in the measurement based model using
graph states [29, 30]. Where $n$ nodes each to hold a lattice graph state,
shared Bell pairs (which are equivalently 2-qubit graph states themselves) can
be utilised to mediate fusing them together in a patchwork manner. Now rather
than $n$ instances of smaller quantum computers, we have a single one with an
$n$-fold increase in its qubit resources. This concept is shown in Fig. 25.

Figure 25: Toy model for distributed quantum computing using graph states.
(top) Two geographically separated nodes with local lattice graph states.
Distributed Bell pairs (cyan) are equivalently 2-qubit graph states, which may
be locally fused onto each of the separated lattices using CZ gates (red).
(bottom) The equivalent distributed graph state following entanglement
distribution and local fusing operations. These distributed unified graph
states have greater computational power than the two individual nodes
operating independently, or networked via only classical channels.

More precisely, we can quantify this as follows. Let $f_{\mathrm{sc}}(n)$
denote a _computational scaling function_ [31], characterising the net
computational power associated with physical computational resources $n$
(measured in say bits, qubits, cores or nodes). Let $n_{i}$ be the
computational resources held by the $i$th of $N$ nodes. Then the computational
advantage provided by networked computational nodes relative to unnetworked
nodes is,

$\displaystyle\lambda=\frac{f_{\mathrm{sc}}\left(\sum_{i=1}^{N}n_{i}\right)}{\sum_{i=1}^{N}f_{\mathrm{sc}}(n_{i})}.$
(40)

Considering the case where all nodes have identical resources at their
disposal this simplifies to,

$\displaystyle\lambda=\frac{f_{\mathrm{sc}}(Nn)}{N\cdot f_{\mathrm{sc}}(n)}.$
(41)

In the classical case, where $f_{\mathrm{sc}}=n$, we have $\lambda=1$, whereas
in the best case quantum scenario we have $\lambda=O(\exp(N))$. This ratio
$\lambda$ directly relates to the economic incentive to unify remote
computational resources, self-evidently far greater in the quantum
computational context.

In the context of DQC our requirements are quite different than for QKD, and
we might instead consider the rate of pairs above a required fault-tolerance
threshold ($F_{\mathrm{th}}$),

$\displaystyle R_{\mathrm{th}}=R\cdot\mathbb{P}(F\geq F_{\mathrm{th}}).$ (42)

This is a quantity which, given a data set for the routed costs, is easy to
infer by simply counting the data-points that meet or exceed the required
fidelity.

###  IX.3 Space-based quantum networks

QuNet accommodates for dynamic nodes and channels and, in principle, could be
used as a high-level tool for simulating and benchmarking entanglement
distribution satellite networks. [38] In this section, we model a basic
satellite network and demonstrate how the costs of distributing entanglement
between an end-user pair vary in time. This network is shown in Fig. 26. It
consists of two ground nodes and a satellite node that tracks overhead at
constant velocity.

Figure 26: A schematic of the toy satellite network evaluated in Fig. 27.
Nodes $A$ and $B$ are fixed communication pairs with a static channel between
them. A satellite capable of transmitting entanglement between $A$ and $B$
moves overhead with constant velocity.

Channels $S\leftrightarrow A$ and $S\leftrightarrow B$ are atmospheric free-
space links. We employ a simple model for efficiency and fidelity through
atmospheric channels, beginning with a model for effective atmospheric depth,

$\displaystyle\rho(h)=\rho_{0}\cdot\exp\left(-\frac{h-h_{0}}{H}\right),$ (43)

where $\rho(h)$ is the atmospheric density at altitude $h$, and $\rho_{0}$ and
$H$ characterise density at ground level and the attenuation with altitude.
Since the atmospheric density is variable with height, we perform a numerical
integral to establish an effective distance $d$ with respect to a standard
density,

$\displaystyle d=\frac{1}{\rho_{0}}\int_{0}^{L}\rho(x\sin{\theta})\,dx,$ (44)

where $L$ is the Euclidean distance between the ground node and satellite, and
$\theta$ is the azimuth from ground node to satellite.

With dephasing, we assume an exponential decay in the state fidelity with
respect to effective distance, parameterised such that as $d\to\infty$ the
state fidelity approaches $\frac{1}{2}$,

$\displaystyle F=\frac{1+e^{-\beta d}}{2}.$ (45)

For loss, we assume a similar exponential decay associated with atmospheric
attenuation, in addition to a quadratic dispersion term,

$\displaystyle\eta=e^{-\beta d}\cdot\frac{d_{0}^{2}}{(d+d_{0})^{2}},$ (46)

where $d_{0}$ is a focal length such that $\eta|_{d=0}=1$.

For the network in Fig. 27, there are three possible ways for the end users
$A$ and $B$ to distribute entanglement:

  * •

Via the static channel.

  * •

Via the free-space channel.

  * •

Using entanglement purification across both (Sec. II.4).

These are shown in Fig. 27 as the satellite follows its trajectory over time.

Figure 27: An evolution of the various costs of the distribution methods
between end users $A$ and $B$ in Fig. 26. The best available single path in
terms of fidelity is given by the black dotted line.

As expected from the plot, we see the costs from the free-space channels are
minimised when the satellite is directly overhead at $t=5$. Notice also that
the fidelity of the purified route outperforms both of its constituents, but
at the expense of higher loss via the non-determinism of the purification
protocol. That is, there is a direct trade-off between fidelity (quality) and
efficiency (quantity or bandwidth). Though this example is more illustrative
than practical, it can be readily extended to larger scale networks, in
particular towards the objective of simulating quantum satellite
constellations.

##  X Conclusion

In this paper we developed a formalism for entanglement distribution quantum
networks with Bell pairs as the entanglement resource. We introduced a novel
method for quantifying the effects of noisy channels on states with additive
cost-metrics thereby making the framework compatible with existing highly
optimised shortest-path algorithms. We designed an efficient multi-user,
multi-path routing algorithm using greedy iterations of series and parallel
graph reductions via entanglement purification and swapping respectively. We
also examined the trade-offs between the fidelity and bandwidth that emerge
from multi-path routing techniques. Finally to demonstrate our theory, we
developed a software package QuNet that allows users to simulate time-
dependent entanglement networks and benchmark multi-user routing algorithms
over an extensive range of applications.

There are many options for further research. In this paper we predominantly
considered grid-lattice networks, but one could develop graph topologies that
are more optimal for achieving end-user demands. Additional one could study
more advanced graph reduction and multi-path routing techniques and benchmark
them against the simple greedy case. QuNet can also be used as a tool to
evaluate infrastructure costs. For example, a quantum satellite constellation
could form the backbone for a global quantum network by distributing
entanglement between far away ground stations. By simulating such a network
with respect to the anticipated demand, one could then put a dollar cost value
on the implementation.

“The day science begins to study non-physical phenomena, it will make more
progress in one decade than in all the previous centuries of its existence.” –
Nikola Tesla.

## Acknowledgements

We thank Darcy Morgan, Alexis Shaw, Marika Kieferova, Zixin Huang, Louis
Tessler, Yuval Sanders, Jasminder Sidhu, Simon Devitt & Jon Dowling for
conversation (both helpful, unhelpful, meaningless, derogatory, and diatribe).
Deepesh Singh was supported by the Australian Research Council Centre of
Excellence for Quantum Computation and Communication Technology (project
CE110001027). Peter Rohde and Nathan Langford are funded by ARC Future
Fellowships (projects FT160100397 and FT170100399, respectively).

##  Appendix A Efficient multi-user temporal routing algorithm

Referring to Fig. 13, the temporal meta-graph $H$ can be conceptualised as the
direct sum of the planar graphs $G$ representing underlying network, with
directed edges between corresponding nodes in the temporal direction.

In the case where all nodes have memory this is equivalent to the Cartesian
product of the network graph $G$ and a path graph representing forward time
evolution, $P_{T}$,

$\displaystyle H=G\times P_{T},$ (47)

for a time-independent graph $G$.

Alternately, if no nodes have memory there are no temporal links and we are
left with a direct sum of the graphs,

$\displaystyle\tilde{H}=\bigoplus_{t=1}^{T}G.$ (48)

Following this, user-pair endpoints are fused to create asynchronous nodes.

The shortest path algorithm is applied to this 3D structure, in which routes
can weave both across the planar degrees of freedom and over forward time-
steps. So long as a route $A_{i}\to B_{i}$ exists in $G_{i}$ for all $i$ the
algorithm is guaranteed to find simultaneous routes for all user-pairs in $H$,
but in general will find more optimal ones than by restricting user-pair $i$
to $G_{i}$ alone. In the worst case, each user-pair utilises a distinct layer,
thus $T=M$. The incrementing multiples of $\epsilon$ associated with the edge
weights of asynchronous nodes guides the algorithm to prioritise earlier
routes, effectively compacting routes in the temporal degree of freedom. Thus,
in general $T<M$.

The number of vertices in the temporal meta-graph with asynchronous nodes is
given by,

$\displaystyle\tilde{V}=TV+2M,$ (49)

where $TV$ denotes the number of vertices in the $T$ slices of the temporal
meta-graph, $2M$ accommodates for the asynchronous nodes, and $V$ denotes the
number of vertices in the original (static) graph. Edge weights of the
directed vertical temporal channels specify the cost of waiting a single
discrete time-step. Thus, the construction allows conflicts between users to
be resolved by the shortest path algorithm rather than relying on
combinatorics.

The worst-case complexity of performing a single instance of Dijkstra’s
algorithm on the temporal meta-graph is,

$\displaystyle O((TV+2M)^{2}).$ (50)

Note that the worst-case scenario for ensuring conflict-free routings between
all user-pairs is when each user-pair is forced into a distinct layer of the
temporal meta-graph. Thus, $T$ is upper-bounded by $M$, and Eq. 50 simplifies
to,

$\displaystyle O(M^{2}V^{2}).$ (51)

And to route all $M$ user-pairs via successive applications of Dijkstra’s
algorithm, the net time-complexity is,

$\displaystyle O(M^{3}V^{2}).$ (52)

Thus the multi-user shortest-path temporal routing algorithm incurs an $M^{3}$
overhead on top of Dijkstra’s algorithm and remains a deterministic
polynomial-time algorithm.

This technique avoids the exponential overhead associated with naïvely
performing combinatoric optimisation over the distinct time-slots designated
to each user-pair, for which $T^{2M}$ permutations exist, exponential in the
number of users.

It appears that this algorithm is a slightly modified rediscovery of the
shortest-path temporal routing algorithm presented by [19].

This variant has the benefit that the incremental weighting of asynchronous
node edges guides the underlying shortest-path algorithm to preferentially
seek the earliest available routing, and the integer multipliers of $\epsilon$
specify the time-ordering for each user-pair, implicitly providing the routing
queue as an output. Note that $\epsilon$ is chosen to be smaller than the
smallest edge weight in the graph,

$\displaystyle\epsilon\ll\min(w(G)),$ (53)

such that they preferentially guide the algorithm towards the earliest
available time-slots without corrupting the identification of which path is
shortest (identified shortest path lengths must subsequently be discounted by
the appropriate multiples of $\epsilon$).

The maximum index of the traversed nodes provides the worst-case latency
experienced by users,

$\displaystyle\tau=\left\lfloor\frac{\max(\vec{V}_{\mathrm{trav}})}{V}\right\rfloor,$
(54)

where $\vec{V}_{\mathrm{trav}}$ is the set of traversed nodes within the
temporal graph (not including asynchronous nodes), and $V$ is the number of
nodes in the original non-temporal graph. This not only acts as an indicator
of latency and congestion in the network, but also provides a useful guide for
optimising execution time. Specifically, if $\tau<T$ this implies the
remaining $T-L$ time-slices are algorithmically redundant for the current
problem instance.

The ratio,

$\displaystyle B=\frac{M}{\tau},$ (55)

represents net network bandwidth measured in end-to-end Bell pairs per time-
step across the whole network. The theoretical lower bound on this is $B=1$,
corresponding to each user-pair being allocated to a distinct time-step,
$\tau=M$. And the theoretical upper bound is $B=M$, when all successfully
communicate in a single-shot, $\tau=1$.

The ratio,

$\displaystyle R_{c}=\frac{B(\tilde{H})}{B(H)},$ (56)

between the bandwidths with full memory connectivity (Eq. 47) and none (Eq.
48), effectively defines a compression ratio for how much additional bandwidth
is enabled by temporal routing through memory channels.

##  Appendix B Average $L_{1}$-distance between random user-pairs on a square
lattice

The number of ways $N$, to pick two distinct vertices in an $n\times n$ grid
lattice is equivalent to the number of ways to pick two distinct pairs of
positive integers no greater than $n$:

$\displaystyle N\equiv n^{2}(n^{2}-1)$ (57)

The average $L_{1}$ distance between two distinct vertices is therefore:

$\displaystyle\langle
L_{1}\rangle=\frac{\sum_{x_{1},x_{2},y_{1},y_{2}}^{n}|x_{1}-x_{2}|+|y_{1}-y_{2}|}{N}$
(58)

Where $(x_{1},y_{1}),(x_{2},y_{2})$ are the coordinates of the vertices in the
lattice. Expanding the series to separate $x$ and $y$:

$\displaystyle\langle
L_{1}\rangle=\frac{n^{2}(\sum_{x_{1},x_{2}}^{n}|x_{1}-x_{2}|+\sum_{y_{1},y_{2}}^{n}|y_{1}-y_{2}|)}{N}$
(59)

$\displaystyle=\frac{n^{2}(2\Delta)}{N}$ (60)

Where

$\displaystyle\Delta\equiv\sum_{x_{1},x_{2}}^{n}|x_{1}-x_{2}|=\sum_{y_{1},y_{2}}^{n}|y_{1}-y_{2}|$
(61)

Let $\Delta=\Delta^{+}+\Delta^{-}$ where $\Delta^{+}$ contains the terms such
that $x_{2}<x_{1}$, and $\Delta^{-}$ the ones where $x_{1}<x_{2}$. By symmetry
we see that, $\Delta^{+}=\Delta^{-}$. Then,

$\displaystyle\Delta$
$\displaystyle=2\Delta^{+}=2\sum_{x_{1}=1}^{n-1}\sum_{x_{2}=x_{1}+1}^{n}(x_{2}-x_{1})$
$\displaystyle=\frac{n(n^{2}-1)}{3}.$ (62)

By substitution, we find that

$\displaystyle\langle L_{1}\rangle=\frac{2}{3}n$ (63)

##  Appendix C Derivation of analytic heat map curves

In Fig. 23 of Sec. IX.1, we visualised the routing costs for competing end-
users in the form of a heatmap, overlaid with analytic fidelity/efficiency
curves for competition-free routing. Here we provide the derivation of these,
each corresponding to multipath routing utilising a given number of paths.

Considering a square lattice network with identical channel costs for both
dephasing and efficiency, the efficiency and fidelity are related via,

$\displaystyle F_{1}=\frac{1}{2}(E_{1}+1).$ (64)

The notation $(E_{1},F_{1})$ denotes the efficiency and fidelity associated
with single path routing. Referring to Eq. II.4 describing the efficiency and
fidelity of a purified state, we use the following recursion relations to
establish lower bounds for $(E_{i},F_{i})$ curves where $1<i\leq 4$ denotes
the number of utilised paths,

$\displaystyle F_{i+1}$
$\displaystyle=\frac{F_{i}F_{1}}{F_{i}F_{1}+(1-F_{i})(1-F_{1})},$
$\displaystyle E_{i+1}$
$\displaystyle=E_{1}E_{i}(F_{1}F_{i}+(1-F_{1})(1-F_{i})).$ (65)

Note that these approximate relationships neglect path competition resulting
from multi-path routing (as opposed to competition from other users) and
assume all utilised paths are identical. In reality path competition arising
from multi-path routing will necessarily extend the length of some paths.
Hence these result provide only a lower bound on net cost following
purification.

## References

  * Bartlett [2018] Bartlett, Ben (2018), “A distributed simulation framework for quantum networks and channels,” arXiv:1808.07047 [quant-ph] .
  * Bennett and Brassard [1984] Bennett, C H, and G. Brassard (1984), “Quantum cryptography: Public key distribution and coin tossing,” Proceedings of the IEEE 1, 175, arXiv:2003.06557 .
  * Bennett  _et al._ [1993] Bennett, Charles H, Gilles Brassard, Claude Crépeau, Richard Jozsa, Asher Peres, and William K. Wootters (1993), “Teleporting an unknown quantum state via dual classical and einstein-podolsky-rosen channels,” Physical Review Letters 70, 1895.
  * Bollobás and Riordan [2006] Bollobás, Béla, and Oliver Riordan (2006), “Sharp thresholds and percolation in the plane,” Random Structures & Algorithms 29, 524.
  * Broadbent  _et al._ [2009] Broadbent, A, J. Fitzsimons, and E. Kashefi (2009), “Universal blind quantum computation,” in  _2009 50th Annual IEEE Symposium on Foundations of Computer Science_, Vol. 50, p. 517, arXiv:0807.4154 .
  * Coopmans  _et al._ [2020] Coopmans, Tim, Robert Knegjens, Axel Dahlberg, David Maier, Loek Nijsten, Julio Oliveira, Martijn Papendrecht, Julian Rabbie, Filip Rozpędek, Matthew Skrzypczyk, Leon Wubben, Walter de Jong, Damian Podareanu, Ariana Torres Knoop, David Elkouss, and Stephanie Wehner (2020), “Netsquid, a discrete-event simulation platform for quantum networks,” arXiv:2010.12535 .
  * Dahlberg and Wehner [2018] Dahlberg, Axel, and Stephanie Wehner (2018), “Simulaqron – a simulator for developing quantum internet software,” Quantum Science & Technology 4, 015001, arXiv:1712.08032 .
  * Devitt  _et al._ [2016] Devitt, Simon J, Andrew D. Greentree, Ashley M. Stephens, and Rodney Van Meter (2016), “High-speed quantum networking by ship,” Scientific Reports 6, 36163, arXiv:1410.3224 .
  * DiAdamo  _et al._ [2020] DiAdamo, Stephen, Benjamin Zanger Janis Nötzel, and Mehmet Mert Bese (2020), “Qunetsim: A software framework for quantum networks,” arXiv:2003.06397 .
  * Dijkstra [1959] Dijkstra, Edsger W (1959), “A note on two problems in connexion with graphs,” Numerische Mathematik 1, 269.
  * Dür  _et al._ [1999] Dür, W, H.-J. Briegel, J. I. Cirac, and P. Zoller (1999), “Quantum repeaters based on entanglement purification,” Physical Review A 59, 169, arXiv:quant-ph/9808065 .
  * Ekert [1991] Ekert, Artur K (1991), “Quantum cryptography based on bell’s theorem,” Physical Review Letters 67, 661.
  * Fredman and Tarjan [1984] Fredman, Michael Lawrence, and Robert E. Tarjan (1984), “Fibonacci heaps and their uses in improved network optimization algorithms,” in  _IEEE 25th Annual Symposium on Foundations of Computer Science_, p. 338.
  * Gerry and Knight [2005] Gerry, Christopher C, and Peter L. Knight (2005),  _Introductory quantum optics_ (Cambridge University Press).
  * Gisin and Thew [2007] Gisin, N, and R. Thew (2007), “Quantum communication,” Nature Photonics 1, 165, arXiv:quant-ph/0703255 .
  * Gouët and Moiseev [2012] Gouët, Jean-Louis Le, and Sergey Moiseev (2012), “Quantum memory,” Journal of Physics B 45, 120201.
  * Jian-Wei  _et al._ [2001] Jian-Wei, Pan, Christoph Simon, Caslav Brukner, and Anton Zeilinger (2001), “Entanglement purification for quantum communication,” Nature 410 (6832), 1067–70, copyright - Copyright Macmillan Journals Ltd. Apr 26, 2001; Last updated - 2017-10-31; CODEN - NATUAS.
  * Kesten [1982] Kesten, Harry (1982),  _Percolation Theory for Mathematicians_ (Springer).
  * Kim and Tanchoco [1991] Kim, Chang W, and J. M. A. Tanchoco (1991), “Conflict-free shortest-time bidirectional agv routeing,” International Journal of Production Research 29, 2377.
  * Lvovsky  _et al._ [2009] Lvovsky, A, B. Sanders, and W. Tittel (2009), “Optical quantum memory,” Nature Photonics 3, 706, arXiv:1002.4659 .
  * Matsuo [2019] Matsuo, Takaaki (2019), “Simulation of a dynamic, ruleset-based quantum network,” arXiv:1908.10758 [quant-ph] .
  * Munro  _et al._ [2008] Munro, W J, R. Van Meter, S. G. R. Louis, and K. Nemoto (2008), “High-bandwidth hybrid quantum repeater,” Physical Review Letters 101, 040502, arXiv:0808.0307 .
  * Munro  _et al._ [2015] Munro, William J, Koji Azuma, Kiyoshi Tamaki, and Kae Nemoto (2015), “Inside quantum repeaters,” IEEE Journal of Selected Topics in Quantum Electronics 21, 6400813.
  * Nemoto  _et al._ [2016] Nemoto, Kae, Michael Trupke, Simon J. Devitt, Burkhard Scharfenberger, Kathrin Buczak, Jörg Schmiedmayer, and William J. Munro (2016), “Photonic quantum networks formed from nv-centers,” Scientific Reports 6, 26284, arXiv:1412.5950 .
  * Nielsen and Chuang [2000] Nielsen, M A, and I. L. Chuang (2000),  _Quantum Computation and Quantum Information_ (Cambridge University Press).
  * Ouyang  _et al._ [2020] Ouyang, Yingkai, Joseph Fitzsimons Si-Hui Tan, and Peter P. Rohde (2020), “Homomorphic encryption of linear optics quantum computation on almost arbitrary states of light with asymptotically perfect security,” Physical Review Research 2, 013332, arXiv:1902.10972 .
  * Pan  _et al._ [1998] Pan, Jian-Wei, Dik Bouwmeester, Harald Weinfurter, and Anton Zeilinger (1998), “Experimental entanglement swapping: Entangling photons that never interacted,” Physical Review Letters 80, 3891.
  * Proctor  _et al._ [2018] Proctor, Timothy J, Paul A. Knott, and Jacob A. Dunningham (2018), “Multiparameter estimation in networked quantum sensors,” Physical Review Letters 120, 080501, arXiv:1707.06252 .
  * Raussendorf and Briegel [2001] Raussendorf, Robert, and Hans J. Briegel (2001), “A one-way quantum computer,” Physical Review Letters 86, 5188.
  * Raussendorf  _et al._ [2003] Raussendorf, Robert, Daniel E. Browne, and Hans J. Briegel (2003), “Measurement-based quantum computation on cluster states,” Physical Review A 68, 10.1103/physreva.68.022312, arXiv:quant-ph/0301052 .
  * Rohde [2021] Rohde, Peter P (2021),  _The Quantum Internet_ (Cambridge University Press).
  * Rohde and Ralph [2006] Rohde, Peter P, and Timothy C. Ralph (2006), “Error models for mode mismatch in linear optics quantum computing,” Physical Review A 73, 062312, arXiv:quant-ph/0602004 .
  * Sangouard  _et al._ [2011] Sangouard, Nicolas, Christoph Simon, Hugues De Riedmatten, and Nicolas Gisin (2011), “Quantum repeaters based on atomic ensembles and linear optics,” Reviews in Modern Physics 83, 33, arXiv:0906.2699 .
  * Sangouard  _et al._ [2007] Sangouard, Nicolas, Christoph Simon, Jiří Minář, Hugo Zbinden, Hugues De Riedmatten, and Nicolas Gisin (2007), “Long-distance entanglement distribution with single-photon sources,” Physical Review A 76, 050301, arXiv:0706.1924 .
  * Sidhu and Kok [2020] Sidhu, Jasminder S, and Pieter Kok (2020), “Geometric perspective on quantum parameter estimation,” AVS Quantum Science 2, 014701, arXiv:1907.06628 .
  * Stauffer and Aharony [1992] Stauffer, D, and A. Aharony (1992),  _Introduction To Percolation Theory_ (Taylor & Francis).
  * Tan  _et al._ [2016] Tan, Si-Hui, Joshua A. Kettlewell, Yingkai Ouyang, Lin Chen, and Joseph F. Fitzsimons (2016), “A quantum approach to homomorphic encryption,” Scientific Reports 6, 33467, arXiv:1411.5254 .
  * Yin  _et al._ [2020] Yin, Juan, Yu-Huai Li, Sheng-Kai Liao, Meng Yang, Yuan Cao, Liang Zhang, Ji-Gang Ren, Wen-Qi Cai, Wei-Yue Liu, Shuang-Lin Li, Rong Shu, Yong-Mei Huang, Lei Deng, Li Li, Qiang Zhang, Nai-Le Liu, Yu-Ao Chen, Chao-Yang Lu, Xiang-Bin Wang, Feihu Xu, Jian-Yu Wang, Cheng-Zhi Peng, Artur K. Ekert, and Jian-Wei Pan (2020), “Entanglement-based secure quantum cryptography over 1,120 kilometres,” Nature 582, 501.