  A quantum network distributes quantum entanglements between remote nodes, and
is key to many applications in secure communication, quantum sensing and
distributed quantum computing. This paper explores the fundamental trade-off
between the throughput and the quality of entanglement distribution in a
multi-hop quantum repeater network. Compared to existing work which aims to
heuristically maximize the entanglement distribution rate (EDR) and/or
entanglement fidelity, our goal is to characterize the maximum achievable
worst-case fidelity, while satisfying a bound on the maximum achievable
expected EDR between an arbitrary pair of quantum nodes. This characterization
will provide fundamental bounds on the achievable performance region of a
quantum network, which can assist with the design of quantum network topology,
protocols and applications. However, the task is highly non-trivial and is
NP-hard as we shall prove. Our main contribution is a fully polynomial-time
approximation scheme to approximate the achievable worst-case fidelity subject
to a strict expected EDR bound, combining an optimal fidelity-agnostic
EDR-maximizing formulation and a worst-case isotropic noise model. The EDR and
fidelity guarantees can be implemented by a post-selection-and-storage protocol
with quantum memories. By developing a discrete-time quantum network simulator,
we conduct simulations to show the characterized performance region (the
approximate Pareto frontier) of a network, and demonstrate that the designed
protocol can achieve the performance region while existing protocols exhibit a
substantial gap.
