  The ability to distribute high-quality entanglement between remote parties is
a necessary primitive for many quantum communication applications. A large
range of schemes for realizing the long-distance delivery of remote
entanglement has been proposed, both for bipartite and multipartite
entanglement. For assessing the viability of these schemes, knowledge of the
time at which entanglement is delivered is crucial. For example, if the
communication task requires two entangled pairs of qubits and these pairs are
generated at different times by the scheme, the earlier pair will need to wait
and thus its quality will decrease while being stored in an (imperfect) memory.
For the remote-entanglement delivery schemes which are closest to experimental
reach, this time assessment is challenging, as they consist of nondeterministic
components such as probabilistic entanglement swaps. For many such protocols
even the average time at which entanglement can be distributed is not known
exactly, in particular when they consist of feedback loops and forced restarts.
In this work, we provide improved analytical bounds on the average and on the
quantiles of the completion time of entanglement distribution protocols in the
case that all network components have success probabilities lower bounded by a
constant. A canonical example of such a protocol is a nested quantum repeater
scheme which consists of heralded entanglement generation and entanglement
swaps. For this scheme specifically, our results imply that a common
approximation to the mean entanglement distribution time, the 3-over-2 formula,
is in essence an upper bound to the real time. Our results rely on a novel
connection with reliability theory.
