L12.0pt

# Repeated Purification versus Concatenated Error Correction in Fault Tolerant
Quantum Networks

Michel Barbeau<EMAIL_ADDRESS>,  Joaquin Garcia-Alfaro
<EMAIL_ADDRESS>and  Evangelos Kranakis<EMAIL_ADDRESS>
∗School of Computer Science, Carleton University1125 Col. By
Dr.OttawaOntarioCanadaK1S 5B6 †SAMOVAR, Télécom SudParis, Institut
Polytechnique de Paris19 place Marguerite PereyPalaiseauFrance91120

(2023)

###### Abstract.

Entanglement distribution is a core mechanism for the future quantum Internet.
The quantum world is, however, a faulty environment. Hence, successful
entanglement swapping is error-prone. The occurrence of quantum state errors
can be mitigated using purification and error correction, which can be
repeated in the former case and concatenated in the latter case. Repeated
purification merges low-fidelity qubits into higher-quality ones, while
concatenated error correction builds upon the redundancy of quantum
information. In this article, we study in-depth and compare the two options:
repeated purification and concatenated error correction. We consider using
repeated purification and concatenated error correction to mitigate the
presence of faults that occur during the establishment of Bell pairs between
remote network nodes. We compare their performance versus the number of
repetitions or concatenations, to reach a certain level of fidelity in quantum
networks. We study their resource requirements, namely, their work memory
complexity (e.g., number of stored qubits) and operational complexity (e.g.,
number of operations). Our analysis demonstrates that concatenated error
correction, versus repeated purification, requires fewer iterations and has
lower operational complexity than repeated purification to reach high fidelity
at the expense of increased memory requirements.

Quantum Network, Quantum Communication, Quantum Repeater, Entanglement
Swapping, Entanglement Distribution, Repeated Purification, Concatenated Error
Correction.

††copyright: acmcopyright††doi: 10.1145/1122445.1122456††booktitle: Woodstock
’18: ACM Symposium on Neural Gaze Detection, June 03–05, 2018, Woodstock,
NY††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

The promise of quantum computing raises doubts and questions in some
(Dyakonov2019, ) and provokes enthusiasm in others (Zhong1460, ). An essential
component of the future quantum world is the quantum Internet, which will
transmit quantum data through a network (gyongyosi2022advances, ). A core
function required by the quantum Internet to achieve this task is entanglement
distribution, which aims at creating Bell pairs between distant nodes. These
Bell pairs can then transfer quantum data, using teleportation, or classical
data, using super-dense coding from one node to the other. However, it is
widely acknowledged that quantum computing and networking are faulty
environments with a high likelihood of errors in quantum states. The rate of
errors can be reduced using purification and error correction. The quality of
a quantum state can be improved by repeating the former multiple times or
concatenating several instances of the latter. Both purification and error
correction deserve to be considered to handle the occurrence of quantum state
faults. Repeated purification enhances the quality of a quantum state by
merging low-fidelity qubits into higher-quality ones. For concatenated error
correction, the quality enhancement procedure leverages redundant quantum
information. Recent research shows the relevance of quantum error correction
to make advances in the quantum Internet (gyongyosi2022advances, ;
biercuk2022quantum, ). Software tools that benefit from such techniques
include security applications (e.g., enforcement of quantum key establishment
(scarani2009security, )) and distributed applications (e.g., augmenting the
parallelism of quantum machine learning (biamonte2017quantum, )).

An interesting question is which, among repeated purification and concatenated
error correction, is best to use in the quantum Internet. In this article, we
analyze this question in depth. For each case, namely, repeated purification
and concatenated error correction, we develop analytic models of fidelity,
quantum memory complexity (number of required qubits), and time complexity
(number of operations). We quantify the requirements (memory and operations)
to improve the quality of a quantum state using repeated purification and
concatenated error correction. The former includes work memory (e.g., number
of qubits stored), while the latter refers to the process’s fidelity
improvement operational complexity (e.g., number of steps required). Our
analysis demonstrates that reaching high fidelity via concatenated error
correction requires fewer iterations than repeated purification at the expense
of increased memory requirements. At the same time, repeated purification
increases the operational complexity in contrast with concatenated error
correction. Numeric simulations complement the results obtained with the
analytic models.

The article is structured as follows. Section 2 surveys related work. Section
3 presents our model for quantum networks and repeaters. Section 4 introduces
entanglement swapping and discusses our error model and repeated purification
in conjunction with concatenated error correction for fidelity enhancement.
Section 5 provides our analysis of the efficiency of each approach (i.e.,
repeated purification vs. concatenated error correction). Section 6 presents
the results of numeric simulations. Finally, Section 7 summarizes our main
work and discusses prospects for future research.

##  2\. Related Work

Metropolitan-scale applications using quantum networks have been recently
analyzed via simulation (yehia2022quantum, ; coopmans2021netsquid, ). Results
show that practical quantum-enhanced network functionalities may soon be ready
for security applications (e.g., enforcement of quantum key establishment
(scarani2009security, )) and distributed applications (e.g., augmenting the
parallelism of quantum machine learning (biamonte2017quantum, )).
Nevertheless, quantum-enhanced networks must face the problem of entanglement
distribution under fidelity constraints (stephens2013hybrid, ). Given a source
and a destination, the length of the channel imposes a significant decay in
the quality of communication. Several protocols have been proposed to address
this problem (Pirandola2019, ; Bauml2018, ; Gyongyosi2018, ; Pant2019, ). The
first step relies on finding a path of quantum repeaters capable of conducting
end-to-end entanglement distribution via entanglement swapping (Zukowski1993,
; Caleffi2017, ; perseguers2010, ; Schoute2018, ). Such repeaters are assumed
to be imperfect (Briegel1998, ), i.e., the execution of Bell pair creation and
entanglement swapping may fail. Hence, entanglement distribution is
traditionally modeled as a probabilistic process (9351761, ). To maximize the
likelihood of success, the process can be scheduled, e.g., following a
sequential or nested model (dai2020optimal, ).

This article assumes an entanglement swapping model with Bell pairs in
homogeneous repeater chains (dur2007entanglement, ). Decay of communication is
considered under the bit-flip error model (i.e., Pauli $X$ errors). We
consider using quantum memories that can store qubits for short periods of
time (Azuma2015, ; Munro2015, ; liu2017semihierarchical, ) to handle failures
in the chain of homogeneous repeaters. Resource requirements, including work
memory (e.g., number of stored qubits) and operational complexity (e.g.,
number of transformations), to attain a certain level of fidelity, are
investigated. The amount of quantum memory required by repeaters performing
entanglement distribution can be quantified to achieve a target fidelity
(barbeau2020capacity, ). There are works with a focus on linear (Jiang2007, ;
Shchukin2019, ; Caleffi2017, ), grid (Pant2019, ), ring (Schoute2018, ;
Shirichian2018, ) or sphere (Schoute2018, ) topologies, in which the size of
the required quantum memory is related to the number of neighbors that a
repeater has. Under this classical error model, repeated purification
(zhou2016purification, ) vs. concatenated repetition codes
(fan2022entanglement, ) can be compared (dur2007entanglement, ) to decide
which one achieves better performance with minimal increase in resources. Our
analysis demonstrates that concatenated error correction requires fewer
iterations and operations than repeated purification at the expense of
increased memory requirements.

##  3\. Quantum Networking

We begin with a description of our quantum network model and architecture. As
network model (peterson2007computer, ), let us consider a connected graph
denoted as the pair $G=(V,E)$, where $V$ is the vertex set and $E$ the edge
set. Assume that the set $V$ of vertices is partitioned into two distinct
subsets $R$ and $T$, such that $V=R\cup T$, where $R$ is the set of repeaters
and $T$ is the set of terminals. A network example is depicted in Fig. 1. An
edge represents a bi-directional quantum channel that can be used to establish
entanglement between its two endpoints. All repeaters and terminals can
perform entanglement swapping, but have limited quantum memory. Let us
consider a path $p=v_{0},v_{1},\ldots,v_{n-1},v_{n}$ of $n+1$ vertices in $V$.
The start and final vertices $v_{0}$ and $v_{n}$ are terminals in $T$. All
intermediate vertices $v_{i}\in R$, $0<i<n$, are repeaters in $R$. The number
$n$ of edges of $p$ is its length and is denoted by $|p|$.

Figure 1. Vertices depicted by disks are terminals in $T$ while those depicted
by squares are repeaters in $R$. Note that terminals are directly connected to
repeaters. A dashed line represents a path consisting of repeaters; the
endpoints of the path connect terminals.

###### Definition 1 (Complete Set of Paths).

A set $P$ of paths in the given graph $G$ is called complete when for any pair
$t,t^{\prime}$ of terminals in $T$ there is a path
$p=v_{0},v_{1},\ldots,v_{n-1},v_{n}$ in $P$ such that
$t=v_{0},t^{\prime}=v_{n}$ and all intermediate vertices $v_{i}$, for $0<i<n$,
are repeaters in $R$.

We require that: i) terminal nodes are not adjacent to each other, ii) every
terminal node is adjacent to at least one repeater, and iii) adjacent
repeaters can communicate directly with each other.

Figure 2. The capacity of a repeater $r$ is the number of paths that go
through $r$; in the picture, this is equal to three. Note that the hollow
squares depict repeaters (from the set $R$) and hollow disks terminals (from
the set $T$).

###### Definition 2 (Capacity of a Repeater).

For a given complete set $P$ of paths in a graph $G$ and a repeater $r\in R$,
let the capacity of $r$, denoted by $C_{P}(r)$, be defined as the number of
paths $p\in P$ that pass through $r$, see Fig. 2.

According to this definition, the capacity of a repeater is proportional to
the number of qubits it must be able to store, paired with entanglement, to
enable communication between terminals.

###### Definition 3 (Capacity Induced by a Complete Set of Paths).

For a given complete set $P$ of paths in a graph $G$, the capacity of $G$
induced by the complete set $P$ of paths is defined as the maximum capacity
caused by repeaters in $R$. It is defined by the formula

(1) $C_{G}(P):=\max_{r\in R}C_{P}(r)\mbox{ qubits.}$

Let ${\mathcal{P}}_{G}$ denote the set of complete sets of paths for the graph
$G$. When this is understood from the context, we omit the subscript $G$ in
${\mathcal{P}}_{G}$. Among the collections of a complete set of paths for the
graph $G$, we are interested in minimizing the quantity $C_{G}(P)$, namely

(2)
$\min_{P\in{\mathcal{P}}_{G}}C_{G}(P)=\min_{P\in{\mathcal{P}}_{G}}\max_{r\in
R}C_{P}(r)\mbox{ qubits},$

where the minimum is taken over the set ${\mathcal{P}}_{G}$ of all possible
complete sets of paths $P$ for the graph $G$.

Figure 3. Quantum network layered architecture.

The main problem concerns the capacity induced by connecting all pairs of
terminals by paths consisting of repeaters. We are aiming for an algorithm
that defines the set $P$ of paths while minimizing the resulting capacity
induced on the graph. The main problem is formally described as follows.

###### Problem 4.

Given a graph $G$, find a complete set $P$ of paths that attains or
approximates the quantity $\min_{P\in{\mathcal{P}}_{G}}C_{G}(P)$.

This capacity is somewhat related to the number of qubits the repeaters would
need to store to allow communication between terminals using qubits. In the
sequel, we explore these various aspects of quantum network architecture.

Quantum networks can be visualized by employing layering architectures
(matsuo2019quantum, ). Figure 3 depicts the layers assumed in this work. Each
network node (repeaters and terminals) comprises a physical, a link, and a
network layer. The physical layer assumes error-prone point-to-point transfer
of quantum bits, using single photons or laser pulses. It also assumes the
generation of low-fidelity entangled pairs using, e.g., entangled photon pair
source devices (jones2016design, ). Such devices can be configured to attempt
the creation of Bell pairs continuously. When Bell pair creation is
successful, the resulting two qubits are physically separated. For instance,
the first qubit can go to the left node and the second to the right node. The
physical transmission of entangled pairs is also prone to errors. Non-perfect
entanglement (fidelity below one) assumes Bell pair creation, but potentially
contains errors. Fidelity improvement methods can be conducted at the upper
layers (at the link and network layers). These two upper layers implement
purification, error correction, and entanglement swapping. There is a
transport layer and an application layer in all the terminals. The transport
layer uses the network layer to provide end-to-end transfer of quantum states
to participating processes. The transport layer may also implement end-to-end
error correction. The application layer comprises processes running quantum
algorithms.

##  4\. Fault Tolerant Quantum Networking

The quantum Internet will rely on establishing quality Bell pairs between
network nodes. Bell pairs can transfer quantum states using teleportation, or
classical data, using super-dense coding. For two neighbor network nodes
connected by a direct link, Bell pairs can be established by leveraging
parametric down-conversion. Bell pairs can be established with entanglement
swapping for remote network nodes, not directly linked. Nevertheless, both
parametric down-conversion and entanglement swapping may be faulty and cause
errors. In the sequel, we assume that adjacent nodes, repeaters, or terminals,
use direct communications to establish Bell pairs. Quantum repeaters and
entanglement swapping establish Bell pairs between non-adjacent repeaters and
terminals. Bell pair establishment procedures can be faulty and introduce
errors. Fault tolerance can be achieved using purification and error
correction. The usage of entanglement swapping, repeated purification, and
concatenated error correction is discussed further.

Quantum errors resulting from faulty procedures are modeled in several ways.
For the sake of simplicity and without loss of generality, let us consider a
bit-flip model. Randomly, qubit $\ket{0}$ is converted to $\ket{1}$, or vice
versa. An error changes the qubit $\alpha\ket{0}+\beta\ket{1}$ to the qubit
$\beta\ket{0}+\alpha\ket{1}$. For a Bell pair such as

(3) $\ket{\Phi^{+}}=\frac{\Ket{00}+\Ket{11}}{\sqrt{2}}$

when both qubits are inverted, the errors are canceled, the term $\Ket{00}$
becomes $\Ket{11}$ and vice versa. However, the presence of a single qubit
error results in the quantum state

(4) $\ket{\Psi^{+}}=\frac{\Ket{01}+\Ket{10}}{\sqrt{2}}.$

In this example, the first or second qubit flips, but not both. However, in
both cases, the outcome is the same. When the qubit in the first position is
flipped, the term $\Ket{00}$ is transformed to $\Ket{10}$ and the term
$\Ket{11}$ is transformed $\Ket{01}$. When the qubit in the second position is
flipped, the term $\Ket{00}$ is transformed to $\Ket{01}$, and the term
$\Ket{11}$ is transformed to $\Ket{10}$. The resulting quantum state is the
same for both events, Eq. (4).

Let $p\in[0,1]$ be the probability of a single qubit inversion error in a Bell
pair. The error model is represented as the quantum state

(5) $\sqrt{1-p}\ket{\Phi^{+}}+\sqrt{p}\ket{\Psi^{+}}.$

Entanglement swapping is a core quantum networking procedure. In an instance
of the procedure, three network nodes are involved: a source $s$, a repeater
$r$, and a destination $d$. The source and destination can be repeaters or
terminals. In the sequel, possession subscripts are used. The subscript $s$ in
the ket-notation $\ket{\phi}_{s}$ means that the qubit $\ket{\phi}$ is
possessed by nodes $s$. The subscript $sd$ in the ket-notation
$\ket{\Phi^{+}}_{sd}$ means that the Bell pair $\ket{\Phi^{+}}$ is shared
between nodes $s$ and $d$. Node $s$ possesses the first qubit, while node $d$
possesses the second qubit. Entanglement swapping assumes that $s,r$ and $r,d$
share the Bell pairs $\ket{\Phi^{+}}_{sr}$ and $\ket{\Phi^{+}}_{rd}$,
respectively. They may have been created using parametric down-conversion or
previous instances of entanglement swapping. Next, the repeater $r$ does Bell
measurement of the second qubit of $\ket{\Phi^{+}}_{sr}$ and the first qubit
of $\ket{\Phi^{+}}_{rd}$ into the classical bits $c_{1}$ and $c_{2}$,
respectively. The repeater sends the two classical bits $c_{1}$ and $c_{2}$
resulting from the measurement to the destination $d$. If $c_{2}$ is equal to
one, then $d$ applies the Pauli gate $X$ to the second qubit of
$\ket{\Phi^{+}}_{rd}$. If $c_{1}$ is equal to one, then $d$ also applies to
gate $Z$. The final result is an end-to-end Bell pair $\ket{\Phi^{+}}_{sd}$
shared between the source and destination, the first qubit of
$\ket{\Phi^{+}}_{sr}$ and second qubit of $\ket{\Phi^{+}}_{rd}$, possibly
transformed by the $X$ and $Z$ gates.

Figure 4. Scheduled swapping, (a) sequential and (b) nested.

Entanglement swapping can be multi-hop. In such a scenario, several swapping
operations are used to establish entanglement between two distant terminals,
$s$ and $d$, connected by a multi-hop path. Using a routing algorithm, a path
$p=r_{0}=s,r_{1},\ldots,r_{n-1},r_{n}=d$ is chosen, where
$r_{1},\ldots,r_{n-1}$ are repeaters, with $r_{0}$ equal to $s$ and $r_{n}$
equal to $d$. Entanglement is established stage by stage. There are two
available scheduled swapping protocols (dai2020optimal, ; 9351761, ), namely,
sequential and nested, see Figure 4. For the sequential protocol, for
$i=1,2,3,\ldots,n-1$, using repeater $r_{i}$ as intermediate, an entanglement
swapping operation creates a Bell pair $\ket{\Phi^{+}}_{sr_{i+1}}$ between
nodes $s$ and $r_{i+1}$. In $n-1$ iterations, a Bell pair
$\ket{\Phi^{+}}_{sd}$ is created between terminals $s$ and $d$.

For the sake of simplicity, let us assume that the path length $n$ is a power
of two. With the nested protocol, firstly, for $i=0,2,4,\ldots,n-2$, using
repeater $r_{i+1}$ as intermediate, an entanglement swapping operation creates
a Bell pair $\ket{\Phi^{+}}_{r_{i}r_{i+2}}$ between nodes $r_{i}$ and
$r_{i+2}$. Next, for $i=0,4,8,\ldots,n-4$, using node repeater $r_{i+2}$ as
intermediate, entanglement swapping creates a Bell pair
$\ket{\Phi^{+}}_{r_{i}r_{i+4}}$ between nodes $r_{i}$ and $r_{i+4}$. Each
iteration doubles the length of the segment bridged by a pair. In $\log_{2}n$
iterations, a Bell pair $\ket{\Phi^{+}}_{sd}$ is created between terminals $s$
and $d$. Note that in both protocols, sequential and nested, every repeater
needs to be able to store two qubits.

Figure 5. Entanglement swapping in the presence of a bit-flip error. (a)
Initial state. (b) Target outcome. (c) Faulty outcome.

Errors may result from faulty entanglement swapping. Figure 5 (a) pictures the
initial state of an instance of the entanglement swapping procedure. There is
a chain of two point-to-point links connecting terminal $s$ to repeater $r$
and repeater $r$ to terminal $d$. Terminal $s$ shares a Bell pair
$\ket{\Phi^{+}}_{sr}$ with repeater $r$. Repeater $r$ shares a Bell pair
$\ket{\Phi^{+}}_{rs}$ with terminal $s$. Part (b) shows the target state
resulting from a successful entanglement swapping. Terminal $s$ shares a Bell
pair $\ket{\Phi^{+}}_{sd}$ with terminal $d$. Assuming the bit flip error
model, Part (c) shows an entanglement swapping that failed to produce a
correct result. Terminal $s$ shares a Bell pair $\ket{\Psi^{+}}$ with terminal
$d$. Qubit errors are an important quantum networking problem. However, the
quality of a Bell pair can be improved with repeated purification and
concatenated error correction, discussed in the sequel.

Purification is a procedure executed between two nodes, a source terminal $s$
and a destination terminal $d$, to augment the fidelity of Bell pairs
(van2014quantum, ). The outcome of purification can be characterized by the
probability to correct errors successfully, referring to the concept of
fidelity. Fidelity indicates the degree of resemblance of a quantum state to
its original value. Fidelity is affected by errors but can be improved using
purification. The goal is to establish high-fidelity Bell pairs between
quantum network nodes.

(Physical, Network) Layer (Bell pair creation) (Link, Network) Layer
(Purification procedure)
$\textstyle{\ket{0}}$$\textstyle{H}$$\textstyle{\bullet}$
$\textstyle{E}$$\textstyle{\bullet}$$\textstyle{\ket{\phi}_{s}}$$\textstyle{\ket{0}}$$\textstyle{H}$$\textstyle{\bullet}$
$\textstyle{\ket{\psi}_{s}}$
$\textstyle{\ket{\psi}^{\prime}_{s}}$$\textstyle{x_{1}}$$\textstyle{\ket{0}}$
$\textstyle{\ket{\psi}_{d}}$
$\textstyle{\ket{\psi}^{\prime}_{d}}$$\textstyle{x_{2}}$$\textstyle{\ket{0}}$
$\textstyle{\bullet}$$\textstyle{\ket{\phi}_{d}}$ Figure 6. Purification
procedure. According to the bit-flip error model, gate $E$ represents the
arbitrary corruption of qubits. As depicted, Bell pair creation may happen at
the physical layer, followed by the link layer; it may also happen at the
network layer.

Figure 6 depicts purification. The goal is to establish the high-fidelity Bell
pair $\ket{\Phi^{+}}_{sd}$. The leftmost dotted-line rectangle represents the
attempt by a repeater $r$ to create two Bell pairs shared with nodes $s$ and
$d$. During Bell pair establishment, qubit errors can be introduced. Rectangle
$E$ models the introduction of errors. For the sake of simplicity, let us
consider solely bit-flip errors. The action of $E$ on every one of the four
qubits is defined as the following weighted sum:

(6) $\sigma=\sqrt{p_{I}}\cdot I+\sqrt{p_{X}}\cdot X,\mbox{ with identity and
Pauli matrices $I$ and $X$, and probabilities }p_{I}+p_{X}=1$

The term $p_{X}$ is a bit-flip error probability. Gate $E$ is the tensor
product of four such gates, that is, $E=\sigma^{\otimes 4}$. In the output of
$E$, let us denote the first pair’s first qubit as $\ket{\phi}_{s}$ while the
first qubit of the second pair is $\ket{\psi}_{s}$, both possessed by terminal
$s$. Using $\ket{\phi}_{s}$ as the control qubit and $\ket{\psi}_{s}$ the
target qubit, node $s$ applies a $CNOT$ gate yielding the pair
$\ket{\phi}_{s}\ket{\psi^{\prime}}_{s}=CNOT\left(\ket{\phi}_{s}\ket{\psi}_{s}\right)$.

Let us denote the first pair’s second qubit as $\ket{\phi}_{d}$ while the
second qubit of the second pair is $\ket{\psi}_{d}$, both possessed by
terminal $d$. Using $\ket{\phi}_{d}$ as the control qubit and $\ket{\phi}_{d}$
as the target qubit, node $d$ applies a $CNOT$ gate yielding the pair
$\ket{\phi}_{d}\ket{\psi}^{\prime}_{d}=CNOT\left(\ket{\phi}_{d}\ket{\psi}_{d}\right)$.
Terminal $s$ measures $\ket{\psi}^{\prime}_{s}$ into classical bit $x_{1}$.
Terminal $d$ measures $\ket{\psi}^{\prime}_{d}$ into classical bit $x_{2}$.
Using classical communications, $s$ and $d$ compare the values of $x_{1}$ and
$x_{2}$. When they are equal, it is concluded that the pair
$\ket{\phi}_{s}\ket{\phi}_{d}$ has been purified and corresponds to the Bell
pair $\ket{\Phi^{+}}_{sd}$. When $x_{1}$ and $x_{2}$ are different, it is
concluded that the pair $\ket{\phi}_{s}\ket{\phi}_{d}$, is not equal to
$\ket{\Phi^{+}}_{sd}$. Purification failed. The pair
$\ket{\phi}_{s}\ket{\phi}_{d}$, is rejected.

There are four possible purification outcomes. When $x_{1}$ is equal to
$x_{2}$, there are two cases. There are no errors, and both pairs
$\ket{\phi}_{s}\ket{\phi}_{d}$ or the pair $\ket{\psi}_{s}\ket{\psi}_{d}$ at
the output of gate $E$ are in state $\ket{\Phi^{+}}_{sd}$. Or, both pairs are
in error in state $\ket{\Psi^{+}}_{sd}$. The probability of the first case is
$q^{2}$, with $q=1-p$. Purification is successful. The probability of the
second case is $p^{2}$. The errors are undetected and purification fails and
wrongly concludes with success. When $x_{1}$ and $x_{2}$ are different, there
is a qubit error in one of the pairs. Either the pair
$\ket{\phi}_{s}\ket{\phi}_{d}$ or the pair $\ket{\psi}_{s}\ket{\psi}_{d}$ is
in state $\ket{\Psi^{+}}$, but not both. The probability for the first or
second pair to be in error is $qp$. In both cases, the error is detected.
Purification fails.

In this setting, as a function of the single qubit inversion error probability
$p$ in a Bell pair, fidelity becomes equivalent to the likelihood of the
absence of errors when purification concludes with a positive result, that is:

(7) $f(p)=\frac{q^{2}}{q^{2}+p^{2}}\mbox{ with $q=1-p$}.$

An important observation is that purification does not improve the fidelity,
i.e., the condition $f(p)>q$, when the input fidelity is $0.5$ or below (see
Fig. 9.2 in Ref. (van2014quantum, )). A desired degree of fidelity,
approaching one, can be obtained with several purification rounds, see Section
5.1.

An alternative to purification is error correction.

Table 1. Error correction codes. In the $(n,k)$ notation, the variables $n$ and $k$ indicate the number of physical qubits and a corresponding number of logical qubits used to encode them. Available choices for $n$ or $k$ are listed, separated by vertical bars. Code | Example $(n,k)$
---|---
Calderbank-Shor-Steane (CSS) (calderbank1996good, ; steane1996error, ) | $(5|7|9,1)$
Hadamard-Steane | $(7,3|4)$
Repetition | $(3,1)$
Shor | $(9,1)$
Steane (steane1996error, ) | $(5|7,1)$

Table 1 lists error correction codes by name. A distinction is made between
physical qubits and logical qubits. All error correction codes use several
physical qubits to represent every abstract logical qubit. A pair $(n,k)$ is
associated with every correction code. Parameter $n$ represents the number of
physical qubits used to encode $k$ logical qubits.

Desurvire’s analysis (Ref. (desurvire2009classical, ) Sec. 24.1) for the bit-
flip model shows that a $(3,1)$ error correction code improves fidelity when
the bit-flip probability is greater than or equal to 0.5. Longer codes ($n>3$)
do not yield better results because they increase the risks of getting more
errors. Error correction can be recursively applied, or concatenated, several
times (knill1996concatenated, ; fan2022entanglement, ). This is further
studied in Section 5.2.

---
Physical Layer (Bell pair creation) Link Layer (Encoding & Decoding)
$\textstyle{\ket{0}}$$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{\ket{\phi}_{1}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{E}$$\textstyle{\ket{\phi}^{\prime}_{s}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\ket{\phi}^{\prime\prime}_{s}}$$\textstyle{\ket{0}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}}$
$\textstyle{\ket{\phi}_{2}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\ket{\phi}^{\prime}_{d}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\ket{\phi}^{\prime\prime}_{d}}$$\textstyle{\ket{0}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}}$ $\textstyle{\bullet}$ Figure 7.
Encoding and decoding procedure. Gate $E$ arbitrarily corrupts qubits
according to the bit-flip error model. The physical layer creates the Bell
pair, while the link layer maps qubits into code words. In addition, the link
layer receives the qubit triples and decodes them back to single qubits.

Figure 7 depicts the circuit associated with a single qubit error correction
procedure, as used in the sequel. It represents repeater $r$ and two terminals
$s$ and $d$. A $(3,1)$ repetition code is used. The leftmost rectangle
represents the behavior of the repeater. The input qubits $\ket{0}_{1}$ and
$\ket{0}_{2}$ are the Bell pair selectors. Since they are both equal to
$\ket{0}$, the $H$ gate and first $CNOT$ gate of $r$ create the Bell pair
$\ket{\Phi^{+}}$. The second and third $CNOT$ gates of $r$ map the two members
of the pair to a specific codeword, for instance, $\ket{0}$ is mapped
$\ket{000}$ and $\ket{1}$ is mapped $\ket{111}$. The quantum channel $E$ can
arbitrarily corrupt qubits and introduce bit-flip errors. The gate $E$ is the
tensor product of six copies of the gate defined in Equation (6), that is,
$E=\sigma^{\otimes 6}$. The behavior of every terminal is identical. Terminal
$s$ ($d$) receives a three-qubit code word. The first and second $CNOT$ gates
map a code word to a single qubit (first line), that is, $\ket{000}$ is mapped
$\ket{000}$ and $\ket{111}$ is mapped $\ket{100}$. The Toffoli gate performs
single qubit error correction. Both qubits on the second and third lines need
to be $\ket{1}$ to flip the qubit’s value on the target on the first line. For
example, if the input to the terminal is the three qubits $\ket{011}$, it
decodes into $\ket{011}$. The first qubit is in error. The Toffoli gate flips
the first qubit into $\ket{1}$.

Entanglement swapping can be used in conjunction with error correction.

|  |  |  |  |  |
---|---|---|---|---|---|---
|  |  |  |  |  |
Network Layer $\textstyle{\ket{0}_{s}}$ $\textstyle{E}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{\phi_{1}}_{s}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\ket{\phi_{3}}_{s}}$$\textstyle{\ket{\phi_{1}}_{r}}$$\textstyle{\bullet}$$\textstyle{H}$$\textstyle{\bullet}$$\textstyle{\ket{\phi_{2}}_{r}}$
$\textstyle{\ket{\phi_{2}}_{d}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{X^{\otimes 3}}$ $\textstyle{Z^{\otimes 3}}$
$\textstyle{E}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\ket{\phi_{3}}_{d}}$$\textstyle{\ket{0}_{d}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{d}}$ $\textstyle{\bullet}$ Figure 8.
Entanglement swapping procedure with bit-flip errors and $(3,1)$ repetition
error correction. Gate $E$ arbitrarily flips qubits, $E=\sigma^{\otimes 3}$.

Figure 8 depicts a circuit describing a qubit-flip error correction procedure
combined with entanglement swapping. It represents repeater $r$ and two
terminals $s$ and $d$. A $(3,1)$ repetition code is used for error correction.
The entanglement-swapping procedure is under the control of repeater $r$. The
repeater $r$ entangles remote three-qubit code words, contrasting with base
entanglement swapping that entangles remote individual qubits. The subscripts
$s$, $r$, and $d$ are used to denote qubit possession by the nodes $s$, $r$,
and $d$, respectively. The qubits $\ket{0}_{s}$ and $\ket{0}_{d}$ are
ancillary. The first and second qubits of the Bell pair $\ket{\Phi^{+}}_{sr}$
shared by terminal $s$ and repeater $r$ are denoted as $\ket{\phi_{1}}_{s}$
and $\ket{\phi_{1}}_{r}$, respectively. The first and second qubits of the
Bell pair $\ket{\Phi^{+}}_{rd}$ shared by repeater $r$ and terminal $d$ are
denoted as $\ket{\phi_{2}}_{r}$ and $\ket{\phi_{2}}_{d}$, respectively.

Before entanglement swapping starts, the physical qubits $\ket{\phi_{1}}_{s}$
and $\ket{\phi_{2}}_{d}$ are encoded into logical qubits. The second and third
$CNOT$ gates of $s$ map qubits $\ket{\phi_{1}}_{s}$ to three qubit code words,
that is, $\ket{0}$ is mapped to $\ket{000}$ and $\ket{1}$ is mapped to
$\ket{111}$. Similarly, the second and third $CNOT$ gates of $d$ map qubits
$\ket{\phi_{2}}_{d}$ to three qubit code words, that is, $\ket{0}$ is mapped
to $\ket{000}$ and $\ket{1}$ is mapped to $\ket{111}$.

The entanglement-swapping procedure introduces bit-flip errors, modeled by the
$E$ gates. Following entanglement swapping with errors, the behavior of every
terminal is similar. Every terminal, $s$ and $d$, possesses a three-qubit
block. They apply consecutively two $CNOT$ gates and a Toffoli gate. They
correct single bit-flip errors.

In the absence of errors, the final state is

$\frac{\ket{000}_{s}\ket{000}_{d}+\ket{111}_{s}\ket{111}_{d}}{\sqrt{2}}.$

Projecting on the third qubit (possessed by $s$) and fourth qubit (possessed
by $d$), it corresponds to the shared Bell pair $\ket{\Phi^{+}}_{sd}$, whose
first qubit is denoted as $\ket{\phi_{3}}_{s}$ and second qubit as
$\ket{\phi_{3}}_{d}$. In case of a single-bit flip error, at $s$, for example,
on the third line, the final state is

$\frac{\ket{110}_{s}\ket{000}_{d}+\ket{111}_{s}\ket{111}_{d}}{\sqrt{2}}.$

Projecting on the third qubit (possessed by $s$) and fourth qubit (possessed
by $d$), it also yields the shared Bell pair $\ket{\Phi^{+}}_{sd}$. Double or
triple bit-flip errors at node $s$ or node $d$ are not corrected.

In the next lemma, the fidelity of a Bell pair corrected with a $(3,1)$
repetition code is characterized.

###### Lemma 4.1.

The fidelity of a Bell pair error-corrected with the $(3,1)$ repetition code
is $\mathcal{F}(p)=(1-p)^{3}+3p(1-p)^{2}$.

###### Proof.

Considering that a Bell pair involves two qubits, the proof follows from an
analysis in Ref. (desurvire2009classical, ). It states that given the bit-flip
error probability $p$, where $p$ is smaller than $1/2$, the fidelity of a
single qubit corrected with a $(3,1)$ repetition code is
$F(p)=\sqrt{(1-p)^{3}+3p(1-p)^{2}}$. Hence, the fidelity of the Bell pair is
$\mathcal{F}(p)=F(p)^{2}=(1-p)^{3}+3p(1-p)^{2}$. ∎

$\textstyle{\ket{0}_{s}}$ $\textstyle{E}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{0}_{s}}$
$\textstyle{\bullet}$$\textstyle{\ket{\phi_{1}}_{s}}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{Swapping}$ $\textstyle{\bullet}$$\textstyle{\bullet}$
$\textstyle{\bullet}$$\textstyle{\bullet}$ $\textstyle{\ket{\phi_{3}}_{s}}$
Figure 9. Entanglement swapping procedure with concatenated $(3,1)$ repetition
error correction. Only the circuit at the location of terminal $s$ is shown. A
similar circuit for terminal $d$ can be drawn. Gate $E$ arbitrarily flips
qubits, $E=\sigma^{\otimes 9}$.

Error correction can also be iterated. Figure 9 shows a two-concatenation
scenario, focusing on the qubit $\ket{\phi_{1}}_{s}$ of terminal $s$. The
$(3,1)$ repetition error correction is used. The qubit $\ket{\phi_{1}}_{s}$ is
mapped to a three-qubit codeword, the first, fourth, and seventh lines from
the bottom. Each qubit of this codeword is recursively mapped to a three-qubit
low-level codeword. Following the swapping procedure, gate $E$ models the
occurence of by flip-errors. Then, every low-level three-qubit block is mapped
to a three-qubit block, which is in turn mapped to the single qubit
$\ket{\phi_{3}}_{s}$. Using this model, error correction can be applied
several times recursively to improve the quality of a qubit involved in an
entanglement swapping procedure on every side. This is analyzed in detail in
the following section.

##  5\. Analysis of Repeated Purification and Concatenated Error Correction

The fidelity of a Bell pair may be increased with repeated purification and
concatenated error correction. This capability is analyzed in detail in this
section. The precise requirements for repeated purification or concatenated
error correction are identified and compared against each other.

###  5.1. Purification Analysis

Let $F$ be the initial fidelity of a Bell pair, with $F>1/2$. Using repeated
purification, let us consider the fidelity sequence $F_{n}$ defined
recursively as follows:

(8) $F_{0}=F\mbox{ and
}F_{n}=\frac{F_{n-1}^{2}}{F_{n-1}^{2}+(1-F_{n-1})^{2}}\mbox{ for
}n=1,2,3,\ldots$

Observe that the sequence $F_{n}$ is increasing. Therefore the limit
$\lambda:=\lim_{n\to\infty}F_{n}$ exists. Passing to the limit in the
righthand side of Equation (8), we conclude that $\lambda=1$. This follows
from the fact that $\lambda=\frac{\lambda^{2}}{\lambda^{2}+(1-\lambda)^{2}},$
which gives the solution $\lambda=1$. Therefore taking into account that
$F_{n}\to 1$ as $n\to\infty$, we can make repeated purifications to the
resulting state

(9)
$\rho_{n}=F_{n}\Ket{\Phi^{+}}\Bra{\Phi^{+}}+(1-F_{n})\Ket{\Psi^{+}}\Bra{\Psi^{+}}.$

To get an idea of the costs required to obtain a certain fidelity, the speed
of convergence of repeated purification is investigated. The main question of
interest is the following:

> Given a starting value $F_{0}>1/2$, how many purification repetitions are
> needed to obtain a certain level of fidelity? Namely, given an arbitrarily
> small $\epsilon>0$ for what value of $n$ can we claim $F_{n}>1-\epsilon$?

The following analysis of our main question requires some claims we state and
prove below as lemmas.

Consider the operation $F\to F^{\prime}:=\frac{F^{2}}{F^{2}+(1-F)^{2}}$. We
look at the ratio of the new value $F^{\prime}$ versus the old $F$, namely
$\frac{F^{\prime}}{F}=\frac{\frac{F^{2}}{F^{2}+(1-F)^{2}}}{F}=\frac{F}{F^{2}+(1-F)^{2}}$
and prove the following lemma.

###### Lemma 5.1.

If $1/2<F<1/{\sqrt{2}}$ then

(10) $\frac{F^{\prime}}{F}>1+\left(F-\frac{1}{2}\right)=\frac{1}{2}+F.$

###### Proof.

Multiply Inequality (10) by two to obtain $\frac{2F}{F^{2}+(1-F)^{2}}>1+2F$.
Then multiply out to derive the equivalent form $2F>(F^{2}+(1-F)^{2})(1+2F)$.
When we expand and simplify the last inequality, it turns out to be equivalent
to $(2F-1)(2F^{2}-1)<0$. Since by assumption $1/2<F$, we conclude that the
last inequality is equivalent to $F<1/{\sqrt{2}}$, which is valid from the
hypothesis of the lemma. ∎

The next observation is that the purification operation is monotone
increasing.

###### Lemma 5.2.

The purification function is monotone increasing, namely if $F<G$ then
$\frac{F}{F^{2}+(1-F)^{2}}<\frac{G}{G^{2}+(1-G)^{2}}$.

###### Proof.

The proof is straightforward. ∎

###### Lemma 5.3.

If $F_{0}<1/{\sqrt{2}}$ then in at most $n+1$ iterations of the purification
operation, where

(11)
$n=\left\lceil\frac{-\log_{2}(F_{0}\sqrt{2})}{\log_{2}(F_{0}+1/2)}\right\rceil$

we have that $F_{n}\geq 1/{\sqrt{2}}$

###### Proof.

Repeat purification as in $F_{0}=F$ and
$F_{n}=\frac{F_{n-1}^{2}}{F_{n-1}^{2}+(1-F_{n-1})^{2}}$ and use Lemma 5.1 to
conclude that if $F_{n}<1/{\sqrt{2}}$ then

$\displaystyle\frac{F_{n}}{F_{0}}$
$\displaystyle=\frac{F_{n}}{F_{n-1}}\cdot\frac{F_{n-1}}{F_{n-2}}\cdots\frac{F_{1}}{F_{0}}>\prod_{i=0}^{n-1}\left(F_{i}+\frac{1}{2}\right)\geq\left(F_{0}+\frac{1}{2}\right)^{n}.$

We conclude that

$F_{n}\geq\left(F_{0}+\frac{1}{2}\right)^{n}F_{0}.$

It follows that the right-hand side above can be made greater than
$1/{\sqrt{2}}$ for
$n\geq\frac{-\log_{2}(F_{0}\sqrt{2})}{\log_{2}(F_{0}+1/2)},$ which implies
that $F_{n}\geq 1/{\sqrt{2}}$. ∎

We conclude by proving the following theorem.

###### Theorem 5.4.

For any initial purification value $F_{0}$ such that $1/2<F_{0}<1/{\sqrt{2}}$
and any $0<\epsilon<1$ arbitrarily small, in at most
$m\leq\left\lceil\frac{-\log_{2}(F_{0}\sqrt{2})}{\log_{2}(F_{0}+1/2)}\right\rceil+\log_{2}\log_{2}(1/\epsilon)$
repetitions of the purification operation we will have that $F_{m}\geq
1-\epsilon$. Moreover, if already $F_{0}\geq 2/3$ then
$m\leq\log_{2}\log_{2}(1/\epsilon)$.

###### Proof.

From the discussion above, we see that starting from any initial value $F_{0}$
such that $1/2<F_{0}<1/{\sqrt{2}}$ we can repeat the purification operation at
$n$ times, where $n$ is given in Equation (11) so that $F_{n+1}\geq
1/{\sqrt{2}}$.

Next, we indicate how many additional steps are needed to obtain accuracy.
First of all, observe that $1/{\sqrt{2}}>2/3$. A simple calculation using the
definition of the purification operation shows that

(12) $\mbox{if $F=\frac{k}{k+1}$ then $F^{\prime}=\frac{k^{2}}{k^{2}+1}$}.$

Because of Lemma 5.2, we may assume without loss of generality that
$F_{n+1}=2/3$. Observe that $F_{n+1}=2/3=\frac{2^{2^{0}}}{2^{2^{0}}+1}$. By
induction, if we assume that $F_{n+k}=\frac{2^{2^{k-1}}}{2^{2^{k-1}}+1}$ then
using the previously proved Assertion (12) we have that
$F_{n+k+1}=\frac{2^{2^{k}}}{2^{2^{k}}+1}$. It follows that for any required
accuracy $\epsilon>0$, we have that $F_{n+k+1}>1-\epsilon,$ provided that
$k>\log_{2}\log_{2}(1/\epsilon)$. ∎

Next, Theorem 5.5 characterizes the memory cost of a one-time execution of
purification and it provides an upper bound on the number of qubits required
inside each repeater to support repeated execution of purification.

###### Theorem 5.5 (Repeated Purification).

For a path of length $\ell$ (a positive integer), a repeater requires at most
$2^{n+\ell-1}$ qubits of memory to complete $n$ purification repetitions.

###### Proof.

The proof is by induction on the path’s length $\ell$. Firstly, let us assume
that $n$ is equal to one, i.e., one-time execution of purification.

Base Case: ($\ell=1$). The path consists of a source $s$ and a destination
$d$, connected by a link. The nodes $s$ and $d$ are terminals or repeaters.
Using two Bell pairs shared by $s$ and $d$, established with direct
communications and purification, their fidelity is improved into a single Bell
pair, as shown in Figure 6. Every endpoint, $s$ and $d$, uses two qubits,
which is equal to $2^{\ell}$ qubits, for $\ell=1$.

Inductive Step: ($\ell>1$). Let $\ell_{1}$ and $\ell_{2}$ be the number of
links to the left and right of repeater $r$ on a path of length $\ell$ between
nodes $s$ and $d$, with $\ell=\ell_{1}+\ell_{2}$. Clearly, both $\ell_{1}$ and
$\ell_{2}$ are equal to or greater than one. Let us assume that the nodes $s$
and $r$ (respectively, $r$ and $d$) share two Bell pairs. Using these four
Bell pairs and two entanglement swapping operations, the repeater $r$
establishes two Bell pairs between $s$ and $d$. Purification improves their
fidelity into a single Bell pair shared between $s$ and $d$. To create the two
Bell pairs between $s$ and $r$ (respectively, $r,d$), repeater $r$ requires
$2\cdot 2^{\ell_{1}}$ (respectively, $2\cdot 2^{\ell_{2}}$) qubits, for a
total of $2\cdot\left(2^{\ell_{1}}+2^{\ell_{2}}\right)$. Because
$\ell_{1},\ell_{2}$ are greater than or equal to one but lower than $\ell$, it
is equal to or lower than $2\cdot\left(2^{\ell-1}+2^{\ell-1}\right)=2^{\ell}$
qubits.

This proves the theorem when $n$ is equal to one. Observe that the general
statement of the theorem regarding the number $n$ of repetitions follows
immediately by applying $n$ iterations of the above argument. Since every
additional repetition of the procedure by repeater $r$ multiplies the number
of qubits by two, we have that $n$ repetitions need $2^{n-1}\cdot
2^{\ell}=2^{n+\ell-1}$ qubits. ∎

###### Definition 5.6 (Purification procedure).

Involving three nodes, where the middle one is a repeater $r$ while the two
others $s$ and $d$ are terminals of repeaters, the purification procedure
consists of seven operations, namely, the generation of four Bell pairs (two
instances between $s$ to $r$ and two instances between $r$ to $d$), two
entanglement swapping operations and one purification cycle under the control
of $r$.

###### Corollary 5.7.

$n$ repetitions of purification by a repeater $r$ for a path of length $\ell$
requires at most $7n(\ell-1)$ operations.

###### Proof.

It follows from the definition of nested entanglement, the proof of Theorem
5.5, as well as Definition 5.6. ∎

###  5.2. Error Correction Analysis

As demonstrated in Lemma 4.1, the efficacy of error correction can also be
captured using the concept of fidelity. Fidelity is used to quantifying the
quality of Bell pairs established by a quantum system. The fidelity of a Bell
pair error-corrected with the $(3,1)$ repetition code is
$\mathcal{F}(p)=(1-p)^{3}+3p(1-p)^{2}$, where $p$ is the probability of a
qubit transformation from $\ket{0}$ to $\ket{1}$, or vice versa

###### Definition 5.8 ($(3,1)$ repetition error correction concatenation for a
single qubit).

Building on Lemma 4.1, let us define the fidelity of concatenated error
corrections as

(13) $F_{0}=F(p)\mbox{ and
}F_{n}=\sqrt{F_{n-1}^{3}+3(1-F_{n-1})F_{n-1}^{2}}\mbox{ for the number of
concatenations }n=1,2,3\ldots.$

Moreover, let us define the sequence $\\{F_{n}:n\geq 1\\}$ with $F_{0}=1/2$.

###### Definition 5.9 ($(3,1)$ repetition error correction for a Bell pair).

Concatenated $n$ times, for the $(3,1)$ repetition error correction, let us
define the fidelity of a Bell pair as

(14) $\mathcal{F}_{n}=F_{n}^{2}=F_{n-1}^{3}+3(1-F_{n-1})F_{n-1}^{2}.$

###### Lemma 5.10.

The sequence $\\{F_{n}:n\geq 1\\}$ is monotone non-decreasing, and its limit
as $n$ goes to infinity equals one.

###### Proof.

Consider the function $f(x)=\sqrt{x^{3}+3(1-x)x^{2}}$. Clearly,
$f(x)=x\sqrt{3-2x}$. It is straightforward to verify that $f(x)\leq 1$, for
all $0\leq x\leq 1$. By definition of $F_{n}$, we have that

$F_{n}=F_{n-1}\sqrt{F_{n-1}+3(1-F_{n-1})}=F_{n-1}\sqrt{3-2F_{n-1}},$

for $n\geq 1$. However, $3-2x\geq 1$, for $0\leq x\leq 1$. Using this and the
fact that $F(p)=p\sqrt{3-2p}$ we see that $F(p)\geq p$, for all $0\leq p\leq
1$. Therefore $F_{n}\geq F_{n-1}$, for all $n\geq 2$. It follows that the
sequence $\\{F_{n}:n\geq 0\\}$ is monotone non-decreasing. Consequently, its
limit $f:=\lim_{n\to+\infty}F_{n}$ exists. It is now shown that the limit $f$
must equal one. Indeed, consider the defining equation of $F_{n}$, namely
$F_{n}=F_{n-1}\sqrt{3-2F_{n-1}}$. In this equation, passing to the limit as
$n\to+\infty$ we see that $f=f\sqrt{3-2f}$. The only solution to this equation
is $f=1$. ∎

Now, let us estimate the convergence speed of the sequence $F_{n}$. First,
consider the formula $F_{n}=F_{n-1}\sqrt{3-2F_{n-1}}$. Let
$F_{n-1}=1-\epsilon_{n-1}$, for some $\epsilon_{n-1}>0$. Observe that

$F_{n}=(1-\epsilon_{n-1})\sqrt{3-2(1-\epsilon_{n-1})}=(1-\epsilon_{n-1})\sqrt{1+2\epsilon_{n-1}}.$

It can be verified that the inequality

$(1-\epsilon_{n-1})\sqrt{1+2\epsilon_{n-1}}>1-\epsilon_{n-1}/2$

is valid as long as $\epsilon_{n-1}<\frac{6-\sqrt{20}}{8}\approx 0.191\ldots$
(to see this claim, multiply out and use the resulting quadratic in the
variable $\epsilon_{n-1}$). Therefore, we can conclude that
$F_{n}=1-\epsilon_{n}$, where $\epsilon_{n}\leq\epsilon_{n-1}/2$. As depicted
in Figure 10, when starting with fidelity $F_{0}>1/2$, after four iterations
we can attain $\epsilon_{n_{0}}\leq 0.1<\frac{6-\sqrt{20}}{8}$. Therefore,
convergence of the fidelity $F_{n}$ to one is exponentially fast, namely
$\epsilon_{n}\leq\epsilon_{n_{0}}/2^{n-n_{0}}$, where $n>n_{0}$. To conclude,
we have the following theorem.

###### Theorem 5.11.

If $1/2<F_{0}\leq 1$ then $(3,1)$ repetition error concatenation fidelity
$F_{n}\geq 1-\epsilon$ can be reached in at most
$\left\lceil\log_{2}(c/\epsilon)\right\rceil$ steps, where $c>0$ is constant.

###### Theorem 5.12 (Concatenated error correction).

Assume that a one-time execution of error correction requires $m$ ancillary
qubits at every subpath’s endpoint. For a path of length $\ell$, a repeater
requires at most $m^{n+\ell-1}$ qubits of memory to complete $n$ error
correction concatenations, $\ell$, $m$ and $n$ are positive integers,
$\ell,n\geq 1$ and $m\geq 3$.

###### Proof.

The proof is by induction on the path’s length $\ell$. Firstly, let us assume
that $n$ is equal to one, i.e., one-time execution of error correction.

Base Case: ($\ell=1$). The path consists of a source $s$ and a destination
$d$, connected by a link. The nodes $s$ and $d$ are terminals or repeaters.
Using direct communications, a $m$ qubit block possessed by $s$ entangled with
a $m$ qubit block possessed by $d$ are established, as depicted in Figure 7.
Using error correction, they are decoded into a single qubit pair shared
between $s$ and $d$. The endpoints $s$ and $d$ require $m$ qubits, which is
equal to $m^{\ell}$, for $\ell=1$ and $m\geq 3$.

Inductive Step: ($\ell>1$). Let $\ell_{1}$ and $\ell_{2}$ be the number of
links to the left and right of repeater $r$ on a path of length $\ell$ between
nodes $s$ and $d$, with $\ell=\ell_{1}+\ell_{2}$. Both $\ell_{1}$ and
$\ell_{2}$ are greater than or equal to one. The nodes $s$ and $d$ can be
either terminals or repeaters. Let us assume the nodes $s$ and $r$
(respectively, $r$ and $d$) share a Bell pair. As depicted in Figure 8, using
entanglement swapping the repeater $r$ establishes entanglement between a $m$
qubit block possessed by $s$ and a $m$ qubit block possessed by $d$. Using
error correction, they are decoded into a single qubit pair shared between $s$
and $d$. The repeater $r$ uses one qubit in each Bell pair, i.e., two qubits.
Every node $s$ and $d$ used $m$ ancillary qubits. To create the Bell pair
between $s$ and $r$ (respectively, $r$ and $d$) it requires at most
$m^{\ell_{1}}$ (respectively, $m^{\ell_{2}}$) qubits, for a total of
$m^{\ell_{1}}+m^{\ell_{2}}$ quibits. Because $\ell_{1},\ell_{2}$ are greater
than or equal to one but lower than $\ell$, it is lower than or equal to
$m^{\ell-1}+m^{\ell-1}$. Which is lower than or equal to $m^{\ell}$ qubits.

This proves the theorem when $n$ is equal to one. Observe that the general
statement of the theorem regarding the number $n$ of concatenations (as
depicted in Figure 9) follows immediately by applying $n$ iterations of the
above argument. Since every additional concatenation of the procedure by
repeater $r$ multiplies the number of qubits by $m$, we have that $k$
concatenations would need $m^{n-1}\cdot m^{\ell}$, or $m^{n+\ell-1}$ qubits. ∎

###### Definition 5.13 (Error correction procedure).

For a $(3,1)$ error correction code, involving three nodes, where the middle
one is a repeater $r$ while the two others $s$ and $d$ are terminals of
repeaters, the error correction procedure consists of four operations, namely,
the generation of two Bell pairs (between $s$ to $r$ and between $r$ to $d$),
one entanglement swapping and one error correction operation performed by $s$
and $d$, at their location.

###### Corollary 5.14.

Concatenation of error correction by a repeater for a path of length $\ell$
requires at most $4(\ell-1)$ operations.

Notice, from Corollary 5.14, that concatenated error correction, compared to
repeated purification, only introduces a constant number of ancillary qubits
per node, independently from the number of iterations, i.e., the number of
operations is proportional to the path length but independent of the number of
concatenations.

##  6\. Analytical and Simulation Results

(a) Repeated purification. (b) Concatenated error correction, $(3,1)$
repetition code.

Figure 10. Fidelity ($F_{n}$ or $\mathcal{F}_{n}$) vs. number of repetitions
or concatenations ($n$), for initial fidelity values $0.51,0.53,0.55,0.57$,
and $0.59$. We can observe that $\mathcal{F}_{n}$ tends to value one faster
than $F_{n}$, for all initial fidelity values $F_{0}$.

Figure 10 (a) shows the evolution of the fidelity sequence $F_{n}$ versus the
number of repeated purifications $n$, for initial fidelity $F_{0}$ values
$0.51,0.53,0.55,0.57$ and $0.59$ (Equation 8). The plot shows that $F_{n}$
rapidly tends to value one, with initial fidelity greater than $0.5$. In
Figure 10 (b), we have the same type of graph but for concatenated error
correction, with the $(3,1)$ repetition code (Equation 14). $\mathcal{F}_{n}$
tends to value one faster than $F_{n}$.

(a) Repeated purification. (b) Concatenated error correction. (c) Repeated
purification. (d) Concatenated error correction.

(e) Repeated purification. (f) Concatenated error correction.

Figure 11. (a,b) Number of repetitions and concatenations ($n$) versus
fidelity ($F_{n}$ or $\mathcal{F}_{n}$). (c,d) Number of required qubits
versus achieved fidelity ($F_{n}$ or $\mathcal{F}_{n}$). (e,f) Number of
required operations versus achieved fidelity ($F_{n}$ or $\mathcal{F}_{n}$).

Figures 11 (a,b) plot the value of $n$, i.e., the number of repetitions and
concatenations required to achieve a given fidelity, $F_{n}$ or
$\mathcal{F}_{n}$. The initial fidelity ($F_{0}$) is $0.51,0.75$, and $0.9$.
There are data points for repeated purification (a) and concatenated error
correction concatenation for the $(3,1)$ repetition code (b). In the $0.51$
case, with low initial fidelity, error correction requires fewer
concatenations than purification repetitions to achieve a given fidelity. They
are almost the same in the $0.7$ case. They are the same in the $0.9$ case.
Figures 11 (c,d) plot the numbers of qubits needed to reach a given fidelity
($F_{n}$ or $\mathcal{F}_{n}$). The initial fidelity ($F_{0}$) is $0.51$. The
path length ($\ell$) is 4, 6 or 8 hops. Repeated purification achieves near
100% fidelity using fewer physical qubits than concatenated error correction.
Figures 11 (e,f) plot the numbers of operations needed to reach a given
fidelity ($F_{n}$ or $\mathcal{F}_{n}$). The initial fidelity ($F_{0}$) is
$0.51$. The path length ($\ell$) is 4, 6 or 8 hops. Error correction achieves
near 100% fidelity using fewer operations than repeated purification.

Figure 12. A sparse grid topology (not depicted) with terminals at the top and
bottom and repeaters in between. Repeaters are depicted with $\Box$ and
terminals with $\bigcirc$. Terminals at the top and bottom are numbered
$1,2,\ldots,n$, respectively. A possible arrangement of three paths
$P_{u},P_{v},P_{w}$ of active terminals $u<v<w$ in a grid topology of
repeaters such that $b(v)\geq b(w)\geq b(u)$.

Let us now consider a $k$ by $k$ sparse grid topology with $k$ terminals at
the top and $k$ terminals at the bottom rows (see Figure 12). The goal is to
determine the memory requirements and operational complexity of the most
congested repeaters in the network. We do not assume full connectivity among
terminals. Instead, with probability $p$, a terminal $u$ at the top of the
grid becomes active and intends to communicate to some terminal at the bottom
row of the grid. Therefore in expectation, $pk$ such terminals become active.
Each terminal $u$ at the top selects a terminal $b(u)$ among the terminals in
the bottom row. For each terminal $u$ at the top, the terminal $b(u)$ is
chosen randomly among the $k$ terminals at the bottom. Moreover, the choice of
any two terminals $u,v$ are independent of each other. For each terminal $u$,
consider a path $P_{u}$ of repeaters connecting terminals $u$ and $b(u)$. The
path $P_{u}$ may be chosen by any standard procedure considering the grid
topology of active repeaters using Dijkstra’s algorithm. It does not have to
have optimal length. We are interested in the expected number of crossings
(see Figure 12). The actual number of crossings may well depend on the paths
$\\{P_{u}:1\leq u\leq k\\}$ selected.

The following argument gives a lower bound on the expected number of
crossings. By the previous discussion, the expected number of active terminals
at the top row is $pk$. We say that the order of a pair of terminal
$\\{u,v\\}$ at the top is reversed if $u<v$ and $b(u)\geq b(v)$. It is clear
that, regardless of the choice of paths $P_{u},P_{v}$, there is a crossing
between them provided there is a reversal, i.e., $u<v$ and $b(u)\geq b(v)$.
Note that at every crossing, between $P_{u},P_{v}$, at least one repeater
(possibly more) must serve both paths. Observe that if $u<v$ then we have that

$\displaystyle\Pr[P_{u}\mbox{ crosses }P_{v}]$ $\displaystyle\geq\sum_{i\geq
j}\Pr[b(u)=i~{}\&~{}b(v)=j]$ $\displaystyle=\sum_{i\geq
j}\Pr[b(u)=i]\cdot\Pr[b(v)=i]$ $\displaystyle=\sum_{i\geq
j}\frac{1}{k^{2}}=\frac{k^{2}+k}{2k^{2}}=\frac{1}{2}+\frac{1}{2k}.$

(a) Repeated purification (b) Concatenated error correction (c) Repeated
purification (d) Concatenated error correction

Figure 13. Extended results using the sparse grid $k$ by $k$ scenario, in
which $10\leq k\leq 20$. (a,b) Concatenated error correction consumes more
physical qubits. (c,d) Repeated purification needs more operations.

If we assume that the random variable $I_{uv}$ indicates that the path $P_{u}$
crosses the path $P_{v}$, then it follows that the expectation of the random
variable ${\mathcal{C}}$ which counts the total number of crossings must
satisfy

(15) $E[{\mathcal{C}}]\geq(pk)^{2}\left(\frac{1}{2}+\frac{1}{2k}\right).$

(a) Repeated purification (b) Concatenated error correction (c) Repeated
purification (d) Concatenated error correction

Figure 14. Congestion setting results in the sparse grid $k$ by $k$ topology,
in which $10\leq k\leq 20$. (a,c) Required number of physical qubits and
operations to ensure entanglement swapping between terminals crossing through
the most congested repeater in the network due to repeated purification. (b,
d) Required number of physical qubits and operations to ensure entanglement
swapping between terminals crossing through the most congested repeater in the
network due to concatenated error correction.

As observed above, every order reversal between terminals at the top row
creates a path crossing. However, it is also clear that the total number of
path crossings depends on the grid topology of the repeaters and on how the
paths are chosen and may well exceed the quantity in the right-hand side of
Inequality (15).

Based on the aforementioned setting, we conduct Monte Carlo simulations using
the NetworkX python library. The simulation code is available online. In each
simulation, congestion is computed as the number of paths crossing through the
most visited repeater. The random activation of terminals follows the strategy
presented in Figure 12, using $\frac{1}{2}$ as probability $p$ for a terminal
at the top of the grid to become active and communicate to some terminal at
the bottom row of the grid. The random arrangement of repeaters and terminals
follows the strategy and constraints defined in Section 3 (i.e., terminal
nodes are not adjacent to each other in the grid and every terminal node is
adjacent to at least one repeater). Figures 13 and 14 show the simulation
Results. Every Boxplot corresponds to fifty independent run executions per
scenario, increasing the size of the sparse $k$ by $k$ grid, from $k=10$ to
$k=20$. We plot the number of required physical qubits and the number of
required operations of the most congested repeater (i.e., the one crossed by
the higher number of paths in each simulation run). Consistently, we can
observe that concatenated error correction, versus repeated purification,
presents lower operational complexity than repeated purification to reach high
fidelity, at the expense of increasing the number of required physical qubits.

##  7\. Conclusion

In a quantum networking environment, we have explored the memory resource
requirements analytically and numerically to attain a certain level of
fidelity. We have also investigated repeated purification and concatenated
error correction in this setting.

We have observed that concatenated error correction can achieve a given degree
of fidelity with fewer iterations than repeated purification, at the cost of
considerably increasing the number of required physical qubits. At the same
time, we have also observed that the cost in number of operations is higher in
the case of repeated purification, compared to concatenated error correction.
This results in a comparable amount of resources for both approaches.

As perspectives for future work, one may want to analyze the requirements when
combining both techniques simultaneously (concatenated error correction and
repeated purification), to estimate the best work memory trade-off while
obtaining the highest possible degree of fidelity.

Acknowledgements — We acknowledge the support of the Natural Sciences and
Engineering Research Council of Canada (NSERC).

## References

  * (1) M. Dyakonov.  When will useful quantum computers be constructed? not in the foreseeable future, this physicist argues. here’s why: The case against: Quantum computing.  IEEE Spectrum, 56(3):24–29, 2019.
  * (2) H.-S. Zhong, H. Wang, Y.-H. Deng, M.-C. Chen, L.-C. Peng, Y.-H. Luo, J. Qin, D. Wu, X. Ding, Y. Hu, P. Hu, X.-Y. Yang, W.-J. Zhang, H. Li, Y. Li, X. Jiang, L. Gan, G. Yang, L. You, Z. Wang, L. Li, N.-L. Liu, C.-Y. Lu, and J.-W. Pan.  Quantum computational advantage using photons.  Science, 370(6523):1460–1463, 2020.
  * (3) L. Gyongyosi and S. Imre.  Advances in the quantum internet.  Communications of the ACM, 65(8):52–63, 2022.
  * (4) M. J. Biercuk and T. M. Stace.  Quantum error correction at the threshold: If technologists don’t get beyond it, quantum computers will never be big.  IEEE Spectrum, 59(7):28–46, 2022.
  * (5) V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev.  The security of practical quantum key distribution.  Reviews of modern physics, 81(3):1301, 2009.
  * (6) J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd.  Quantum machine learning.  Nature, 549(7671):195–202, 2017.
  * (7) R. Yehia, S. Neves, E. Diamanti, and I. Kerenidis.  Quantum city: simulation of a practical near-term metropolitan quantum network.  arXiv preprint arXiv:2211.01190, 2022.
  * (8) T. Coopmans, R. Knegjens, A. Dahlberg, D. Maier, L. Nijsten, J. de Oliveira Filho, M. Papendrecht, J. Rabbie, F. Rozpedek, M. Skrzypczyk, et al.  Netsquid, a network simulator for quantum information using discrete events.  Communications Physics, 4(1):1–15, 2021.
  * (9) A. M. Stephens, J. Huang, K. Nemoto, and W. J. Munro.  Hybrid-system approach to fault-tolerant quantum communication.  Physical Review A, 87(5):052333, 2013.
  * (10) S. Pirandola.  End-to-end capacities of a quantum communication network.  Communications Physics, 2(1):51, 2019.
  * (11) S. Bäuml, K. Azuma, G. Kato, and D. Elkouss.  Linear programs for entanglement and key distribution in the quantum internet.  Communications Physics, 3(1):1–12, 2020.
  * (12) L. Gyongyosi and S. Imre.  Decentralized base-graph routing for the quantum internet.  Phys. Rev. A, 98:022310, Aug 2018.
  * (13) M. Pant, H. Krovi, D. Towsley, L. Tassiulas, L. Jiang, P. Basu, D. Englund, and S. Guha.  Routing entanglement in the quantum internet.  npj Quantum Information, 5(1):25, 2019.
  * (14) M. Żukowski, A. Zeilinger, M. A. Horne, and A. K. Ekert.  “event-ready-detectors” bell experiment via entanglement swapping.  Phys. Rev. Lett., 71:4287–4290, Dec 1993.
  * (15) M. Caleffi.  Optimal routing for quantum networks.  IEEE Access, 5:22299–22312, 2017.
  * (16) S. Perseguers.  Entanglement distribution in quantum networks.  PhD thesis, Technische Universität München, Germany, 2010.
  * (17) E. Schoute, L. Mancinska, T. Islam, I. Kerenidis, and S. Wehner.  Shortcuts to quantum network routing.  arXiv preprint arXiv:1610.05238, 2016.
  * (18) H.-J. Briegel, W. Dür, J. I. Cirac, and P. Zoller.  Quantum repeaters: The role of imperfect local operations in quantum communication.  Phys. Rev. Lett., 81:5932–5935, Dec 1998.
  * (19) G. Vardoyan, S. Guha, P. Nain, and D. Towsley.  On the stochastic analysis of a quantum entanglement distribution switch.  IEEE Transactions on Quantum Engineering, 2:1–16, 2021.
  * (20) W. Dai, T. Peng, and M. Z. Win.  Optimal remote entanglement distribution.  IEEE Journal on Selected Areas in Communications, 38(3):540–556, 2020.
  * (21) W. Dür and H. J. Briegel.  Entanglement purification and quantum error correction.  Reports on Progress in Physics, 70(8):1381, 2007.
  * (22) K. Azuma, K. Tamaki, and H. Lo.  All-photonic quantum repeaters.  Nature Communications, 6(6787):1–7, 2015.
  * (23) W. J. Munro, K. Azuma, K. Tamaki, and K. Nemoto.  Inside quantum repeaters.  IEEE Journal of Selected Topics in Quantum Electronics, 21(3):78–90, May 2015.
  * (24) X. Liu, Z.-Q. Zhou, Y.-L. Hua, C.-F. Li, and G.-C. Guo.  Semihierarchical quantum repeaters based on moderate lifetime quantum memories.  Physical Review A, 95(1):012319, 2017.
  * (25) M. Barbeau, J. Garcia-Alfaro, and E. Kranakis.  Capacity requirements in networks of quantum repeaters and terminals.  In 2020 IEEE International Conference on Quantum Computing and Engineering (QCE), pages 148–157. IEEE, 2020.
  * (26) L. Jiang, J. M. Taylor, N. Khaneja, and M. D. Lukin.  Optimal approach to quantum communication using dynamic programming.  Proceedings of the National Academy of Sciences, 104(44):17291–17296, 2007.
  * (27) E. Shchukin, F. Schmidt, and P. van Loock.  Waiting time in quantum repeaters with probabilistic entanglement swapping.  Phys. Rev. A, 100:032322, Sep 2019.
  * (28) M. Shirichian and S. Tofighi.  Protocol for routing entanglement in the quantum ring network.  In 2018 9th International Symposium on Telecommunications (IST), pages 658–663, Dec 2018.
  * (29) L. Zhou and Y.-B. Sheng.  Purification of logic-qubit entanglement.  Scientific reports, 6(1):1–9, 2016.
  * (30) J. Fan, J. Li, Y. Zhou, M.-H. Hsieh, and H. V. Poor.  Entanglement-assisted concatenated quantum codes.  arXiv preprint arXiv:2202.08084, 2022.
  * (31) L. L. Peterson and B. S. Davie.  Computer networks: a systems approach.  Elsevier, 2007.
  * (32) T. Matsuo, C. Durand, and R. Van Meter.  Quantum link bootstrapping using a ruleset-based communication protocol.  Physical Review A, 100(5):052320, 2019.
  * (33) C. Jones, D. Kim, M. T. Rakher, P. G. Kwiat, and T. D. Ladd.  Design and analysis of communication protocols for quantum repeater networks.  New Journal of Physics, 18(8):083015, 2016.
  * (34) R. Van Meter.  Quantum Networking.  ISTE. Wiley, 2014.
  * (35) A. R. Calderbank and P. W. Shor.  Good quantum error-correcting coedes exist.  Physical Review A, 54(2):1098, 1996.
  * (36) A. M. Steane.  Error correcting codes in quantum theory.  Physical Review Letters, 77(5):793, 1996.
  * (37) E. Desurvire.  Classical and Quantum Information Theory: An Introduction for the Telecom Scientist.  Cambridge University Press, 2009.
  * (38) E. Knill and R. Laflamme.  Concatenated quantum codes.  arXiv preprint quant-ph/9608012, 1996.