# Will My Robot Achieve My Goals? Predicting the Probability that an MDP
Policy Reaches a User-Specified Behavior Target

Alexander Guyer1 and Thomas G. Dietterich2
Collaborative Robotics and Intelligent Systems (CoRIS) Institute
Oregon State University
Corvallis, OR 97331 USA
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

As an autonomous system performs a task, it should maintain a calibrated
estimate of the probability that it will achieve the user’s goal. If that
probability falls below some desired level, it should alert the user so that
appropriate interventions can be made. This paper considers settings where the
user’s goal is specified as a target interval for a real-valued performance
summary, such as the cumulative reward, measured at a fixed horizon $H$. At
each time $t\in\\{0,\ldots,H-1\\}$, our method produces a calibrated estimate
of the probability that the final cumulative reward will fall within a user-
specified target interval $[y^{-},y^{+}].$ Using this estimate, the autonomous
system can raise an alarm if the probability drops below a specified
threshold. We compute the probability estimates by inverting conformal
prediction. Our starting point is the Conformalized Quantile Regression (CQR)
method of Romano et al., which applies split-conformal prediction to the
results of quantile regression. CQR is not invertible, but by using the
conditional cumulative distribution function (CDF) as the non-conformity
measure, we show how to obtain an invertible modification that we call
Probability-space Conformalized Quantile Regression (PCQR). Like CQR, PCQR
produces well-calibrated conditional prediction intervals with finite-sample
marginal guarantees. By inverting PCQR, we obtain marginal guarantees for the
probability that the cumulative reward of an autonomous system will fall
within an arbitrary user-specified target intervals. Experiments on two
domains confirm that these probabilities are well-calibrated.

## Introduction

Consider an agent executing a fixed policy $\pi$ in a Markov Decision Process.
The user specifies some real-valued behavior quantity $b_{t}$ that summarizes
the behavior of the agent from time $0$ through time $t$. For example, in this
paper, $b_{t}=r_{0}+\cdots+r_{t-1}$, the sum of the rewards received over the
first $t$ steps of the trajectory. The user also specifies a target interval
$[y^{-},y^{+}]$. At each time step $t$, the agent should produce a well-
calibrated estimate of the probability, $P[y^{-}\leq b_{H}\leq y^{+}|s_{t}]$,
that the behavior summary at time $H$ falls within the target interval given
the current MDP state $s_{t}$. If this probability falls below a specified
threshold (e.g., $0.99$), the agent should alert the user.

This implements an “autonomy contract” in which the system acts autonomously
but is obligated to report back to the user if the probability of success
falls below a specified level. We will consider two application domains in
this paper: Starcraft 2 and invasive species management. In Starcraft 2, if
the probability of hitting the target interval drops too low, the user might
be able to provide additional resources or reinforcements. In the invasive
species management problem, if the probability of achieving the target total
reward is too small, the conservation manager could request an increase in the
management budget. Importantly, these actions need to be taken as soon as the
predicted probability is too low rather than waiting until $t=H$, by which
time it is too late to take corrective action. This autonomy contract can also
be viewed as a module within a hierarchical MDP policy.

The problem of estimating $P[y^{-}\leq b_{H}\leq y^{+}|s_{t}]$ could be easily
solved if we could compute the conditional cumulative distribution function,
$F(b_{H}|s_{t})$. This predicts the entire CDF of $b_{H}$ conditioned on the
current MDP state $s_{t}$. Given exact estimates, $P[y^{-}\leq b_{H}\leq
y^{+}]=F(y^{+}|s_{t})-F(y^{-}|s_{t})$. Methods for estimating the CDF have
been developed recently (Dabney et al., 2018; Koenker and Bassett, 1978), but
they do not provide finite-sample accuracy guarantees. To obtain those, we
extend the methodology of conformal prediction to invert Conformalized
Quantile Regression (CQR; Romano et al., 2019).

## Related work

We begin with previous work on the “forward problem” of constructing
calibrated prediction intervals for regression. Given a conditioning input
$\mathbf{x}$ and some significance level $\delta$, predict an interval about
the response variable $Y$ with a coverage probability of $1-\delta$. This
problem is similar to standard regression, but the target output is a
$1-\delta$ prediction interval rather than a point estimate of the conditional
mean. Given its similarity to standard regression, a natural solution is to
modify standard regression methods to instead predict conditional quantiles. A
prediction can then be computed as the interval,

$QR(\mathbf{x},\delta)=\left[\hat{Q}_{Y|\mathbf{x}}\left(\frac{\delta}{2}\right),\hat{Q}_{Y|\mathbf{x}}\left(1-\frac{\delta}{2}\right)\right],$
(1)

where $\hat{Q}_{Y|\mathbf{x}}(\alpha)$ is the estimated $\alpha$-quantile of
the response variable $Y$ conditioned on the explanatory vector $\mathbf{x}$.
This strategy is referred to as quantile regression, and it first appeared in
the form of a modification to linear regression Koenker and Bassett (1978).
Newer quantile regression models exist today, such as quantile regression
forests Meinshausen (2006) and quantile neural networks Taylor (2000).

Quantile regression minimizes an appropriate loss function, such as the
pinball loss Koenker and Bassett (1978), averaged over the training data set.
This leads to compromises such that decreasing the loss for some $\mathbf{x}$
may lead to increased losses for other $\mathbf{x}$ values. Consequently,
quantile regression intervals fail to achieve validity—they are not guaranteed
to cover the test data with at least probability $1-\delta$. In practice,
quantile regression intervals can suffer from significant undercoverage or
overcoverage at test time Romano et al. (2019).

To overcome the invalidity of quantile regression estimates, many modern
solutions are derived instead from the technique of conformal prediction Vovk
et al. (2005). Introduced by Vovk et al., conformal prediction is a
distribution-free frequentist approach that provides prediction intervals with
finite-sample guarantees for marginal coverage probability. The more
computationally-attractive versions hold out a “calibration set” in a style
referred to as split conformal prediction. Conformal prediction strategies
exist for classification and regression tasks. In the case of regression,
conformal prediction typically involves regressing the conditional
expectation, as in standard regression, and then forming a symmetric,
constant-width prediction band around the point estimate,

$CP(\mathbf{x},\delta)=[\hat{y}-c_{\delta},\hat{y}+c_{\delta}],$ (2)

where $\hat{y}$ is the estimated expectation of $Y$ conditioned on
$\mathbf{x}$, and $c_{\delta}$ is a conformity score selected to achieve at
least $1-\delta$ coverage over the calibration set. Provided that the data
points in the calibration set are exchangeable draws from a stationary
distribution, the predicted intervals are well calibrated and marginally valid
even with a finite sample, meaning that they are guaranteed to cover the test
data with at least probability $1-\delta$ in expectation over future
exchangeable draws from the same distribution.

Conformal prediction has seen many uses and modifications in the regression
setting. For instance, Vovk et alḟurther applied conformal prediction to
online linear regression Vovk et al. (2009). Lei et alċombined conformal
prediction with nonparametric smoothing to improve the asymptotic efficiency
of the prediction intervals under many function classes Lei et al. (2013); Lei
and Wasserman (2014). Other examples abound.

However, the constant-width property of standard conformal prediction
intervals can be overly restrictive. The variance of a conditional random
variable $Y$ is often heterogeneous (i.e., dependent on the value of the
conditioning variable $\mathbf{x}$). For instance, time series data is often
heteroskedastic with the variance increasing along with the horizon due to the
accumulation of uncertainty over time. Constant-width conditional prediction
intervals computed for data with heterogeneous variance tend to be
inefficient, meaning that they are wider than necessary.

In an effort to achieve more efficient intervals while retaining marginal
validity, Romano et alṙecently introduced an elegant method known as
Conformalized Quantile Regression (CQR; Romano et al., 2019). CQR borrows
techniques from both quantile regression and conformal prediction by applying
a conformalized “correction” to the standard quantile regression interval. The
resulting prediction is the corrected interval,

$CQR(\mathbf{x},\delta)=\left[\hat{Q}_{Y|\mathbf{x}}\left(\frac{\delta}{2}\right)-c_{\delta},\hat{Q}_{Y|\mathbf{x}}\left(1-\frac{\delta}{2}\right)+c_{\delta}\right],$
(3)

where $\hat{Q}_{Y|\mathbf{x}}(\alpha)$ is the conditional $\alpha$-quantile
estimate (the quantile regression prediction), and $c_{\delta}$ is a
conformity score selected to achieve at least $1-\delta$ coverage over a
calibration set as in conformal prediction. CQR intervals offer the
heterogeneous widths of quantile regression intervals as well as the marginal
coverage guarantees of conformal prediction intervals.

Like conformal prediction, CQR has seen many uses and modifications. For
instance, Hu et al. combine CQR with temporal convolutional networks Lea et
al. (2016) for the purpose of wind power interval prediction Hu et al. (2022).
Dietterich and Hostetler extend CQR to multivariate responses to compute
prediction intervals over the trajectories of MDP policies Dietterich and
Hostetler (2022).

Let us now consider the “backward problem”. Given a target interval, we want
to find lower and upper values $\delta^{-}$ and $\delta^{+}$ such that the
prediction interval produced by QCR,

$\left[\hat{Q}_{Y|\mathbf{x}}\left(\delta^{-}\right)-c^{-}(\delta^{-}),\hat{Q}_{Y|\mathbf{x}}\left(1-\delta^{+}\right)+c^{+}(\delta^{+})\right]$

coincides with the target interval. Unfortunately, as we will show below, CQR
is not invertible. In this paper, we mitigate this issue by introducing a
simple modification to CQR—we exploit the invertibility of the estimated
conditional quantile function to move the conformity scores to the probability
space.

## Contributions

The contributions of this paper are threefold:

  1. 1.

We show that even with an invertible estimated conditional quantile function,
CQR itself is not invertible—following the quantile-space conformal
correction, different estimated quantiles can result in the same prediction
interval. Consequently, CQR cannot be employed to predict conditional coverage
probabilities of user-specified target intervals.

  2. 2.

We introduce a simple modification to CQR, moving the conformal correction to
the probability space by exploiting the invertibility of the estimated
quantile function. We refer to our method as Probability-space Conformalized
Quantile Regression (PCQR).

  3. 3.

We show that by applying the conformal correction in the probability space,
PCQR retains the invertibility of the estimated conditional quantile function.
It can be inverted to estimate the CDF and predict conditional coverage
probabilities of user-specified target intervals. We refer to this inverse
algorithm as PCQR-1. We prove that PCQR and PCQR-1 are well-calibrated and
provide the same finite-sample marginal coverage guarantees as CQR. We
evaluate PCQR and PCQR-1 experimentally on two domains.

## Method

### CQR is not Invertible

A natural question is whether CQR can be inverted to predict conditional
coverage probabilities given a target interval. That is, is it possible to
determine which conditional quantile estimates generate the target interval
following the conformal correction? A necessary assumption is that the
underlying quantile regression model is invertible. However, a simple
counterexample shows that this assumption is insufficient. Given some
conditioning input $\mathbf{x}$, suppose the quantile regression model
estimates the conditional quantile function to be continuous and strictly
increasing with respect to the cumulative probability, with

$\displaystyle\hat{Q}_{Y|\mathbf{x}}(0.05)$ $\displaystyle=a,$
$\displaystyle\hat{Q}_{Y|\mathbf{x}}(0.1)$ $\displaystyle=a+\epsilon,$
$\displaystyle\hat{Q}_{Y|\mathbf{x}}(0.9)$ $\displaystyle=b-\epsilon,$
$\displaystyle\hat{Q}_{Y|\mathbf{x}}(0.95)$ $\displaystyle=b,$

for some $a,b,\epsilon\in\mathbf{R}$, such that

$\displaystyle a$ $\displaystyle<b,\quad\mbox{and}$ $\displaystyle 0<\epsilon$
$\displaystyle<\frac{b-a}{2}.$

Suppose that on the calibration set, the underlying quantile regression model
suffers from overcoverage for $90\%$ prediction intervals and undercoverage
for $80\%$ prediction intervals. Then the conformal correction $c_{0.1}$ (as
in (3)) will be negative, and the conformal correction $c_{0.2}$ will be
positive. Suppose that $c_{0.2}-c_{0.1}=\epsilon$. Then the CQR $80\%$
prediction interval is

$\displaystyle CQR(\mathbf{x},0.2)$ $\displaystyle=[a+\epsilon-
c_{0.2},b-\epsilon+c_{0.2}]$ $\displaystyle=[a-c_{0.1},b+c_{0.1}]$
$\displaystyle=CQR(\mathbf{x},0.1),$

which is also the CQR $90\%$ prediction interval. That is, the quantile-space
conformal correction destroys the invertibility of the conditional quantile
estimates. Similar counterexamples show that CQR can introduce quantile
crossings, even when applied on top of a strictly increasing estimate of the
conditional quantile function.

### Introducing Probability-Space Conformity Scores

To solve the invertibility issue and predict coverage probabilities given
target intervals, we start by making a simple modification to CQR. Our method,
like CQR, constructs intervals by applying a conformal correction to an
initial estimate of the conditional quantile function. For the rest of the
paper, we will assume that, as in the counterexample, the estimated
conditional quantile function $\hat{Q}_{Y|\mathbf{x}}(\alpha)$ is continous
and strictly increasing with respect to the cumulative probability $\alpha$.

CQR applies a per-$\alpha$ additive conformal correction to the estimated
quantile. While $\hat{Q}_{Y|\mathbf{x}}(\alpha)$ is a strictly increasing
function of $\alpha$, the correction is not, and so the corrected quantile
estimate is not necessarily invertible. We mitigate this issue by exploiting
the invertibility of the estimated conditional quantile function and moving
the conformal correction to the probability space. That is, our method
predicts intervals of the form,

$PCQR(\mathbf{x},\delta)=\left[\hat{Q}_{Y|\mathbf{x}}\left(\frac{\delta}{2}-c_{\delta}\right),\hat{Q}_{Y|\mathbf{x}}\left(1-\frac{\delta}{2}+c_{\delta}\right)\right],$
(4)

where $c_{\delta}$ is chosen to achieve coverage of at least $1-\delta$ on the
calibration set, as in conformal prediction and CQR. Because the conformal
correction is applied to the cumulative probability rather than the estimated
conditional quantile, we refer to our method as Probability-space
Conformalized Quantile Regression (PCQR).

CQR corrects the estimated conditional quantiles associated with a $1-\delta$
coverage rate in order to achieve at least $1-\delta$ coverage on the
calibration set. In contrast, PCQR determines which estimated conditional
quantiles achieve at least $1-\delta$ coverage on the calibration set without
any conformal corrections. In both methods, the chosen cumulative
probabilities are symmetric about $\frac{1}{2}$. Additionally, the conformal
corrections in both methods can be modified to predict an interval whose
marginal coverage probability is at most $1-\delta$, rather than at least
$1-\delta$. In light of this interpretation, PCQR can instead be expressed as

$PCQR(\mathbf{x},s)=\left[\hat{Q}_{Y|\mathbf{x}}\left(\frac{1}{2}-s\right),\hat{Q}_{Y|\mathbf{x}}\left(\frac{1}{2}+s\right)\right],$
(5)

where $s$ is the calibration conformity score selected to achieve the desired
marginal coverage bound.

To compute $s$, we leverage the same techniques used in split conformal
prediction and CQR. Let $D_{cal}=\\{(\mathbf{x_{i}},y_{i})\\}_{i=1}^{n}$
denote the calibration set, where $\mathbf{x_{i}}$ is the explanatory vector
and $y_{i}$ is the scalar response variable. Let $\mathbf{x_{n+1}}$ denote a
new explanatory vector observed at test time, and let $y_{n+1}$ denote the
corresponding unobserved response variable. Assume that neither
$(\mathbf{x_{n+1}},y_{n+1})$ nor any of the data in $D_{cal}$ have been
observed by the quantile regression model during training. Assume that the
random sequence $(\mathbf{x_{1}},y_{1}),\ldots,(\mathbf{x_{n+1}},y_{n+1})$ is
exchangeable (i.e., the calibration and testing data are exchangeable). Let
$\hat{F}_{Y|\mathbf{x}}$ denote the inverse of $\hat{Q}_{Y|\mathbf{x}}$, so
that

$\hat{F}_{Y|\mathbf{x}}(y)=\alpha\iff\hat{Q}_{Y|\mathbf{x}}(\alpha)=y.$ (6)

Given that $\hat{Q}_{Y|\mathbf{x}}$ is a continuous and strictly increasing
estimate of the conditional quantile function, $\hat{F}_{Y|\mathbf{x}}$ serves
as a continuous and strictly increasing estimate of the conditional CDF.

The conformity score for a given instance $(\mathbf{x},y)$ is computed as

$S(\mathbf{x},y)=\Big{|}\frac{1}{2}-\hat{F}_{Y|\mathbf{x}}(y)\Big{|},$ (7)

where $|\cdot|$ denotes absolute value.

Let $S_{(i)}$ denote the $i^{th}$ order statistic of the sequence of
calibration conformity scores, $\\{S(\mathbf{x_{i}},y_{i})\\}_{i=1}^{n}$, and
assume that they are almost surely unique (i.e., unique with probability $1$).
We use these conformity scores to construct two PCQR interval predictions:

$\displaystyle I^{-}(\mathbf{x_{n+1}},\delta)$
$\displaystyle=PCQR(\mathbf{x_{n+1}},S_{(\lfloor(1-\delta)(n+1)\rfloor)})$ (8)
$\displaystyle I^{+}(\mathbf{x_{n+1}},\delta)$
$\displaystyle=PCQR(\mathbf{x_{n+1}},S_{(\lceil(1-\delta)(n+1)\rceil)})$ (9)

By construction, $I^{+}(\mathbf{x_{n+1}},\delta)$ is only defined for
$\delta\geq\frac{1}{n+1}$, and $I^{-}(\mathbf{x_{n+1}},\delta)$ is only
defined for $\delta>0$. Similar constraints apply to CQR prediction intervals.

######  Theorem 1.

Given an exchangeable sequence
$(\mathbf{x_{1}},y_{1}),\ldots,(\mathbf{x_{n+1}},y_{n+1})$ and almost surely
unique conformity scores
$S(\mathbf{x_{1}},y_{1}),\ldots,S(\mathbf{x_{n+1}},y_{n+1})$, the following
inequalities hold:

$\displaystyle P(y_{n+1}\in I^{-}(\mathbf{x_{n+1}}))$ (10)
$\displaystyle\hskip 20.0pt\leq 1-\delta$ $\displaystyle\hskip 20.0pt\leq
P(y_{n+1}\in I^{+}(\mathbf{x_{n+1}})).$

###### Proof.

Because the tuples $(\mathbf{x_{1}},y_{1}),\ldots,(\mathbf{x_{n+1}},y_{n+1})$
are exchangeable, and because each conformity score $S(\mathbf{x_{i}},y_{i})$
is a function $S(\cdot)$ of the corresponding tuple $(\mathbf{x_{i}},y_{i})$,
the conformity scores
$S(\mathbf{x_{1}},y_{1}),\ldots,S(\mathbf{x_{n+1}},y_{n+1})$ are also
exchangeable.

The rank of any variable in an exchangeable sequence of almost surely unique
random variables is uniformly distributed. Consequently, the marginal
distribution of the rank of each conformity score is uniform in
$\\{1,2,\ldots,n+1\\}$.

Then we have that,

$\displaystyle P(S(\mathbf{x_{n+1}},y_{n+1})\leq S_{(i)})$
$\displaystyle=P(R(S(\mathbf{x_{n+1}},y_{n+1}))\leq i)$ (11)
$\displaystyle=\frac{i}{n+1},$

where $R(\cdot)$ denotes rank in the sequence of all $n+1$ conformity scores.
We can apply this to compute coverage probability bounds on the selected
conformity scores:

$\displaystyle\begin{aligned} P(S(\mathbf{x_{n+1}},y_{n+1})\leq
S_{(\lfloor(1-\delta)(n+1)\rfloor)})&=\frac{\lfloor(1-\delta)(n+1)\rfloor}{n+1}\\\
&\leq 1-\delta\end{aligned}$ (12) $\displaystyle\begin{aligned}
P(S(\mathbf{x_{n+1}},y_{n+1})\leq
S_{(\lceil(1-\delta)(n+1)\rceil)})&=\frac{\lceil(1-\delta)(n+1)\rceil}{n+1}\\\
&\geq 1-\delta.\end{aligned}$ (13)

Recall that $\hat{Q}_{Y|\mathbf{x}}$ and $\hat{F}_{Y|\mathbf{x}}$ are
continuous and strictly increasing. Then the following logical biconditionals
hold:

$\displaystyle y\in PCQR(\mathbf{x},s)$ (14) $\displaystyle\hskip
20.0pt\iff\hat{Q}_{Y|\mathbf{x}}\Big{(}\frac{1}{2}-s\Big{)}\leq
y\leq\hat{Q}_{Y|\mathbf{x}}\Big{(}\frac{1}{2}+s\Big{)}$ $\displaystyle\hskip
20.0pt\iff\frac{1}{2}-s\leq\hat{F}_{Y|\mathbf{x}}(y)\leq\frac{1}{2}+s$
$\displaystyle\hskip
20.0pt\iff\Big{|}\frac{1}{2}-\hat{F}_{Y|\mathbf{x}}(y)\Big{|}\leq s$
$\displaystyle\hskip 20.0pt\iff S(\mathbf{x},y)\leq s.$

Combining (12), (13) and (14) yields the following results:

$\displaystyle\begin{aligned} &P(y_{n+1}\in I^{-}(\mathbf{x_{n+1}}))\\\
&\hskip 20.0pt=P(y_{n+1}\in
PCQR(\mathbf{x_{n+1}},S_{(\lfloor(1-\delta)(n+1)\rfloor)}))\\\ &\hskip
20.0pt=P(S(\mathbf{x_{n+1}},y_{n+1})\leq
S_{(\lfloor(1-\delta)(n+1)\rfloor)})\\\ &\hskip 20.0pt\leq
1-\delta\end{aligned}$ (15) $\displaystyle\begin{aligned} &P(y_{n+1}\in
I^{+}(\mathbf{x_{n+1}}))\\\ &\hskip 20.0pt=P(y_{n+1}\in
PCQR(\mathbf{x_{n+1}},S_{(\lceil(1-\delta)(n+1)\rceil)}))\\\ &\hskip
20.0pt=P(S(\mathbf{x_{n+1}},y_{n+1})\leq S_{(\lceil(1-\delta)(n+1)\rceil)})\\\
&\hskip 20.0pt\geq 1-\delta.\end{aligned}$ (16)

∎

Theorem 1 shows that the marginal coverage probability of
$I^{+}(\mathbf{x_{n+1}})$ is at least $1-\delta$. Hence, it is a marginally
valid prediction interval. Since the coverage probabilities of
$I^{-}(\mathbf{x_{n+1}})$ and $I^{+}(\mathbf{x_{n+1}})$ are separated by at
most $\frac{1}{n+1}$, the prediction intervals are also well-calibrated. It is
important to note that Theorem 1 does not provide conditional coverage
guarantees for any fixed $\mathbf{x_{n+1}}$ or calibration set; it only
provides marginal coverage guarantees over all possible random sequences of
calibration and test data, given that the data from the two sets are
exchangeable. These are the same guarantees provided by CQR.

### PCQR is Invertible

Following the expression of PCQR in (5), it is easy to see that the algorithm
can be inverted to compute the conditional coverage probability within a user-
specified target interval. Indeed, the upper and lower bounds of a PCQR
prediction interval are each directly computed by the estimated conditional
quantile function. The estimated conditional CDF, then, can be employed to
compute the conformally-corrected cumulative probabilities associated with the
target interval bounds. These cumulative probabilities can be used to measure
coverage over the calibration set.

Let $[y^{-},y^{+}]$ denote the user-specified target interval. Let
$\alpha_{i}=\hat{F}_{Y|\mathbf{x_{i}}}(y_{i})$, and let $\alpha_{(i)}$ denote
the $i^{th}$ order statistic of the sequence of calibration cumulative
probabilities, $\\{\alpha_{i}\\}_{i=1}^{n}$. We compute the probability-space
interval coverage statistics,

$\displaystyle\alpha^{-}(\mathbf{x_{n+1}},y^{-})$
$\displaystyle=\min\\{i:\alpha_{(i)}\geq\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-})\\}$
(17) $\displaystyle\alpha^{+}(\mathbf{x_{n+1}},y^{+})$
$\displaystyle=\max\\{i:\alpha_{(i)}\leq\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{+})\\}.$
(18)

We then compute two coverage probability bounds,

$\displaystyle p^{-}(\mathbf{x_{n+1}},y^{-},y^{+})$
$\displaystyle=\frac{\alpha^{+}(\mathbf{x_{n+1}},y^{+})-\alpha^{-}(\mathbf{x_{n+1}},y^{-})}{n+1}$
(19) $\displaystyle p^{+}(\mathbf{x_{n+1}},y^{-},y^{+})$
$\displaystyle=\frac{\alpha^{+}(\mathbf{x_{n+1}},y^{+})-\alpha^{-}(\mathbf{x_{n+1}},y^{-})+2}{n+1}.$
(20)

We refer to $p^{-}(\cdot)$ as the PCQR-1 probability lower bound and
$p^{+}(\cdot)$ as the PCQR-1 probability upper bound.

######  Theorem 2.

Given an exchangeable sequence
$(\mathbf{x_{1}},y_{1}),\ldots,(\mathbf{x_{n+1}},y_{n+1})$ and almost surely
unique conditional cumulative probability estimates
$\alpha_{1},\ldots,\alpha_{n+1}$, the following inequalities hold:

$\displaystyle p^{-}(\mathbf{x_{n+1}},y^{-},y^{+})$ (21) $\displaystyle\hskip
10.0pt\leq P(y_{n+1}\in[y^{-},y^{+}])$ $\displaystyle\hskip 10.0pt\leq
p^{+}(\mathbf{x_{n+1}},y^{-},y^{+}).$

###### Proof.

As in Theorem 1, the standard conformal argument applies. Because
$(\mathbf{x_{1}},y_{1}),\ldots,(\mathbf{x_{n+1}},y_{n+1})$ are exchangeable,
and because each $\alpha_{i}$ is a function
$\hat{F}_{Y|\mathbf{x_{i}}}(\cdot)$ of the corresponding $y_{i}$, the
estimated conditional cumulative probabilities
$\alpha_{1},\ldots,\alpha_{n+1}$ are also exchangeable. Given that each
$\alpha_{i}$ is almost surely unique, the marginal distribution of the rank of
each $\alpha_{i}$ is uniform in $\\{1,2,\ldots,n+1\\}$.

Then we have that

$\displaystyle\begin{aligned}
&P(\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-}),\alpha^{+}(\mathbf{x_{n+1}},y^{+})])\\\
&\hskip 20.0pt=p^{-}(\mathbf{x_{n+1}},y^{-},y^{+})\end{aligned}$ (22)
$\displaystyle\begin{aligned}
&P(\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-})-1,\alpha^{+}(\mathbf{x_{n+1}},y^{+})+1])\\\
&\hskip 20.0pt=p^{+}(\mathbf{x_{n+1}},y^{-},y^{+}).\end{aligned}$ (23)

By construction of $\alpha^{-}(\mathbf{x_{n+1}},y^{-})$ and
$\alpha^{+}(\mathbf{x_{n+1}},y^{+})$, the following implications hold:

$\displaystyle\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-})-1,\alpha^{+}(\mathbf{x_{n+1}},y^{+})+1]$
(24)
$\displaystyle\implies\alpha_{n+1}\in[\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-}),\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-})]$
$\displaystyle\implies\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-}),\alpha^{+}(\mathbf{x_{n+1}},y^{+})].$

Combining (22), (23) and (24) yields the following results:

$\displaystyle p^{-}(\mathbf{x_{n+1}},y^{-},y^{+})$ (25) $\displaystyle\hskip
10.0pt=P(\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-}),\alpha^{+}(\mathbf{x_{n+1}},y^{+})])$
$\displaystyle\hskip 10.0pt\leq
P(\alpha_{n+1}\in[\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-}),\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{+})])$
$\displaystyle\hskip 10.0pt\leq
P(\alpha_{n+1}\in[\alpha^{-}(\mathbf{x_{n+1}},y^{-})-1,\alpha^{+}(\mathbf{x_{n+1}},y^{+})+1])$
$\displaystyle\hskip 10.0pt=p^{+}(\mathbf{x_{n+1}},y^{-},y^{+}).$

Recall that $\hat{F}_{Y|\mathbf{x}}$ is strictly increasing. Then the
following logical biconditionals hold:

$\displaystyle y_{n+1}\in[y^{-},y^{+}]$ (26) $\displaystyle\hskip
10.0pt\iff\hat{F}_{Y|\mathbf{x_{n+1}}}(y_{n+1})\in[\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-}),\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{+})]$
$\displaystyle\hskip
10.0pt\iff\alpha_{n+1}\in[\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-}),\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{+})].$

Hence, the event $y_{n+1}\in[y^{-},y^{+}]$ can be substituted for
$\alpha_{n+1}\in[\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{-}),\hat{F}_{Y|\mathbf{x_{n+1}}}(y^{+})]$
in (25), yielding (21) and concluding the proof. ∎

Since the estimated conditional coverage probabilities
$p^{-}(\mathbf{x_{n+1}},y^{-},y^{+})$ and
$p^{+}(\mathbf{x_{n+1}},y^{-},y^{+})$ are separated by at most
$\frac{2}{n+1}$, they are well-calibrated.

## Experiments

We evaluate PCQR and PCQR-1 on two MDPs: Starcraft 2 Vinyals et al. (2017) and
Tamarisk Hall et al. (2018). In each domain, we sample a total of $n=10{,}000$
episodes. We then randomly partition the episodes into $D_{train}$ with
$n_{train}=2{,}500$ episodes, $D_{cal}$ with $n_{cal}=2{,}500$ episodes, and
$D_{test}$ with $n_{test}=5{,}000$ episodes for testing. We repeat each
experiment with $k=5$ different random partitions of the data. For a fixed
episode and a given time step $t$, the explanatory vector $\mathbf{x_{t}}$ is
a subset of the MDP state variables, and the response variable $y_{t}$ is the
total reward at the end of the episode. The target interval is determined by
computing a marginal $80\%$ interval $[y^{-},y^{+}]$ about the final
cumulative reward for all episodes in $D_{test}$ using the empirical $0.1$\-
and $0.9$-quantiles.

Starcraft 2 is a small subset of the famous RTS game. In this subset, a team
of blue units faces off against a team of red units. In this particular
evaluation, the initial number of blue units is chosen uniformly in
$[5,\ldots,20]$, and the initial number of red units is chosen uniformly in
$[5,\ldots,10]$. The blue team is controlled by a fixed policy commanding its
units to advance toward the red team at each time step. When the teams meet,
they engage in battle under the built-in logic of Starcraft 2. At time step
$t=14$, the red team receives a random number of reinforcements chosen
uniformly in ${0,\ldots,N}$, where $N$ is chosen uniformly in ${0,\ldots,15}$.
The blue team receives $+1$ reward for each eliminated red unit and $-1$
reward for each eliminated blue unit. To avoid ties in PCQR conformity scores
and estimated conditional cumulative probabilities, we add uniform random
noise in $[-5\times 10^{-6},5\times 10^{-6}]$ to the reward at the final time
step ($H=57$) of each episode.

The Tamarisk domain involves controlling the plant species present within a
river network. The river network is represented by a balanced binary tree with
seven edges. At any given time, each edge is either empty, occupied by a
native plant, or occupied by an invasive tamarisk tree. The initial state of
each edge is chosen uniformly. The agent’s action is a vector of seven
primitive actions, each corresponding to an edge in the river network. The
available primitive actions are 1) do nothing; 2) eradicate the existing
tamarisk tree, provided that one is present; 3) plant a native plant, provided
that the edge is empty; and 4) eradicate the existing tamarisk tree, followed
by planting a native plant. Each primitive action is associated with a cost,
and there is a budget on the sum of the seven primitive action costs at each
time step. Additionally, there is a cost at each time step for each edge
occupied by a tamarisk tree. The reward is computed as the negative cost, so
the reward at each time step is non-positive. We implemented a fixed policy
based on the work of Hall et al. (2018). As in the Starcraft 2 domain, we add
uniform random noise in $[-5\times 10^{-6},5\times 10^{-6}]$ to the reward at
the final time step ($H=50$) of each episode to avoid ties in PCQR conformity
scores and estimated conditional cumulative probabilities.

In each domain, for each time step $t$, we train a quantile regression forest
(QRF) on the data in $D_{train}$ corresponding to time step $t$ to estimate
the quantile function of $y_{t}$ conditioned on $\mathbf{x_{t}}$ (i.e.,
$\hat{Q}_{Y_{t}|\mathbf{x_{t}}}$). QRFs estimate conditional quantiles as
weighted empirical quantiles over the response variables in the training data.
We inverted them to estimate the conditional CDF (i.e.,
$\hat{F}_{Y_{t}|\mathbf{x_{t}}}$) by replacing the weighted empirical quantile
by the weighted empirical CDF.

To evaluate the performance of PCQR, we apply it to the data in $D_{cal}$
corresponding to time step $t{=}0$ using the fitted QRFs. For each episode in
$D_{test}$, we predict marginally valid $80\%$ PCQR prediction intervals
(i.e., $I^{+}(\mathbf{x_{0}},0.2)$) for $y_{H}$ conditioned on
$\mathbf{x_{0}}$. We measured the mean and standard deviation of the empirical
coverage of these prediction intervals across all $k$ data partitions to be
$80.32\%\pm 1.07\%$ for Starcraft 2 and $79.89\%\pm 0.79\%$ for Tamarisk; this
provides evidence that PCQR is well-calibrated for these domains.

To evaluate the performance of PCQR-1, we apply PCQR-1 to the data in
$D_{cal}$ separately for each time step $t$. For each episode, we translate
the target interval $[y^{-},y^{+}]$ to the space of reward-to-go values for
time step $t$ by subtracting off the cumulative reward observed up to time
step $t$. We then apply PCQR-1 to this translated interval to predict lower
and upper bounds on the probability that the final cumulative reward will fall
in $[y^{-},y^{+}]$. This involves fitting conditional CDF models to predict
the CDF of the reward-to-go from $t$ to the end of the episode ($H$).

Figure 1: Mean Expected Calibration Error (ECE) across all $k$ data partitions
vs. time for the PCQR-1 probability lower and upper bound predictions in the
Starcraft 2 and Tamarisk domains. ECE is measured with 30 equal-width bins.
Standard deviations are depicted by the semi-transparent regions. Figure 2:
Reliability diagrams for the PCQR-1 probability lower bound predictions in the
Starcraft 2 and Tamarisk domains. Data from all data partitions and time steps
are binned into 30 equal-width bins according to the predicted coverage
probabilities. The gray histograms give the bin counts. The x-axis depicts the
mean predicted coverage probability in each bin. The y-axis shows the observed
coverage rate in each bin. The blue line corresponds to the experimental
results, and the black dashed line reflects perfect calibration.

Figure 1 plots the mean Expected Calibration Error (ECE; Naeini et al., 2015)
of the PCQR-1 probability bounds across all $k$ data partitions as a function
of time. We measured ECE with 30 equal-width bins. Additionally, Figure 2
visualizes reliability diagrams for PCQR-1 probability lower bounds by
combining the predictions across all time steps and all $k$ data partitions.
The x-axis depicts the mean predicted coverage probability in each bin, and
the y-axis depicts the bin’s observed empirical coverage rate. Perfect
calibration is reflected by an ECE of zero. In a reliability diagram, perfect
calibration is reflected by a diagonal line along $y=x$. As shown in the
figures, the ECE is relatively low, and the reliability diagram curves are
close to the diagonal. Lastly, we combine the predictions across all time
steps to compute a single mean and standard deviation of the ECE for PCQR-1
probability lower bounds across all $k$ data partitions. These values were
measured as $0.013\pm 0.0018$ for Starcraft 2 and $0.004\pm 0.0005$ for
Tamarisk. These results provide evidence that PCQR-1 is well-calibrated for
these domains.

Figure 3: PCQR-1 predicted coverage probability lower bounds vsṫime for 10
random episodes in the Starcraft 2 and Tamarisk domains. Each line corresponds
to a separate episode.

To better understand the behavior of PCQR-1, we plot the predicted PCQR-1
probability lower bound as a function of time for 10 randomly-selected
episodes from a single random data partition; these plots are depicted in
Figure 3. Many of the predicted coverage probabilities converge to either $0$
or $1$ by the penultimate time step of the episode. This is because, by the
end of the episode, there is little uncertainty as to whether the final
cumulative reward will land in the target interval. Importantly, however, some
predicted coverage probabilities do not converge. This is because there are
duplicated response values in the original datasets prior to adding uniform
random noise. After applying noise, the distribution of response variables is
often multimodal, with a mode in a $\pm 5\times 10^{-6}$ interval around each
duplicated response value. The distribution of response variables within each
mode is uniform, matching the distribution of the added noise. When the target
interval boundaries fall within one of these modes, any episodes with response
variables falling within the same mode will have a constant amount of
aleatoric uncertainty until the final time step, at which point the noise is
observed and the final cumulative reward is known. The quantity of this
aleatoric uncertainty depends on the location of the interval boundary within
the mode. In other words, this pattern is merely an artifact of the artificial
noise added to break ties in conformity scores and estimated conditional
cumulative probabilities, along with the empirical construction of the target
interval. In practice, the interval bounds could be expanded on both sides by
$10^{-5}$ (an amount equal to the range of the tie-breaking noise
perturbations) to include all of the values in the mode, causing all of the
unconverged probabilities to converge to $1$. Likewise, the interval bounds
could be contracted on both sides by $10^{-5}$ to cause them to converge to
$0$. In some sense, expanding the interval bounds treats it like a closed
interval, and contracting the interval bounds treats it like an open interval.
The best choice is application-dependent.

Additionally, some of the curves for the Tamarisk domain show intermittent
spikes in PCQR-1 predictions throughout the episode. While the cumulative
reward in the Tamarisk domain converges in fewer than 5 time steps for most
episodes, there is a small probability that each plant will die a natural
death in each time step. Once the invasive tamarisk plants have been
eliminated, the river network edges are all occupied by native plants. Hence,
a native plant death will cause a small decrease in the cumulative reward.
Following the death, the agent quickly plants a new native plant to fill the
empty plot, and the cumulative reward stabilizes. If the episode’s cumulative
reward is close to one of the interval bounds, such plant deaths can cause
sudden changes in PCQR-1 predictions, as we observe in Figure 3.

Figure 4: Mean PCQR-1 PCQR-1 predictions vs. time in the Starcraft 2 and
Tamarisk domains. Means are computed across all episodes of all data
partitions. Standard deviations are computed from the per-data-partition means
across all episodes and are depicted by the semi-transparent regions.

Finally, to summarize the performance of PCQR-1 for each domain, we plot the
mean predicted conditional coverage probability across all episodes and all
$k$ data partitions as a function of time; these plots are depicted in Figure
4. Although the predicted conditional coverage probability varies over time
for each episode, the mean predicted conditional coverage probability across
all episodes is close to $0.8$ for every time step.

## Conclusion

Previous work has focused on conditional prediction intervals, which are of
great interest in applications. However, there are other scenarios where the
closely related task of conditional interval coverage prediction is also
important. By introducing a simple modification to conformalized quantile
regression, we are able to construct an algorithm that can easily be inverted
to provide an elegant solution for both tasks.

Both tasks are important in the discussion of reliable autonomy. Conditional
prediction intervals can provide important insight into the future behavior of
an autonomous system in a stochastic environment, provided that those
intervals are efficient and valid. Conditional interval coverage prediction
can provide interpretable estimates for the probability that an autonomous
system’s performance will fall inside a user-specified target interval,
provided that the those estimates are well calibrated.

### Future work

The experiments in this paper were conducted entirely with quantile regression
forests serving as the underlying estimate of the conditional quantile
function. Further experiments could study the performance of PCQR and PCQR-1
under other quantile regression methods, such linear quantile regression
Koenker and Bassett (1978) and implicit quantile networks Dabney et al.
(2018).

While the focus of this paper was PCQR-1 and the task of conditional interval
coverage prediction, PCQR serves as a interesting alternative to CQR,
conformal prediction, and quantile regression. Further experiments should
compare the relative performance of all of the aforementioned methods.
Moreover, given that PCQR-1 exploits the invertibility of the underlying
quantile regression model, a simple baseline would be to use the conditional
cumulative probability estimates from the inverted quantile regression to
directly predict the conditional interval coverage probability, in a manner
similar to quantile regression without conformalization. Further experiments
are required to compare PCQR-1 against this baseline.

Finally, this paper describes PCQR and PCQR-1 in the context of univariate
responses. In many applications, the response variable of interest is
multivariate. Dietterich and Hostetler (2022) extend CQR to form prediction
intervals about the entire trajectory of the cumulative reward achieved by MDP
policies; a natural next step would be to extend PCQR and PCQR-1 to
multivariate responses as well. It would be nice to find a method that could
guarantee the simultaneous calibrated accuracy of all of the probabilities
predicted by PCQR-1 for $t=0,\ldots,H-1$, rather than the single-time-step
guarantees provided in this paper.

### Acknowledgments

This material is based upon work supported by the Defense Advanced Research
Projects Agency (DARPA) under Contract No. HR001119C0112. Any opinions,
findings and conclusions or recommendations expressed in this material are
those of the author(s) and do not necessarily reflect the views of the DARPA.
The authors thank Jesse Hostetler for providing the Starcraft 2 trajectories.

## References

  * Dabney et al. [2018] Will Dabney, Georg Ostrovski, David Silver, and Rémi Munos.  Implicit quantile networks for distributional reinforcement learning, 2018\.  URL https://arxiv.org/abs/1806.06923.
  * Dietterich and Hostetler [2022] Thomas G. Dietterich and Jesse Hostetler.  Conformal prediction intervals for markov decision process trajectories, 2022.  URL https://arxiv.org/abs/2206.04860.
  * Hall et al. [2018] Kim Hall, Heidi Albers, Majid Taleghan, and Thomas Dietterich.  Optimal spatial-dynamic management of stochastic species invasions.  _Environmental and Resource Economics_ , 70, 06 2018.  doi: 10.1007/s10640-017-0127-6.
  * Hu et al. [2022] Jianming Hu, Qingxi Luo, Jingwei Tang, Jiani Heng, and Yuwen Deng.  Conformalized temporal convolutional quantile regression networks for wind power interval forecasting.  _Energy_ , 248:123497, 2022.  ISSN 0360-5442.  doi: https://doi.org/10.1016/j.energy.2022.123497.  URL https://www.sciencedirect.com/science/article/pii/S0360544222004005.
  * Koenker and Bassett [1978] Roger Koenker and Gilbert Bassett.  Regression quantiles.  _Econometrica_ , 46(1):33–50, 1978.  ISSN 00129682, 14680262.  URL http://www.jstor.org/stable/1913643.
  * Lea et al. [2016] Colin Lea, René Vidal, Austin Reiter, and Gregory D. Hager.  Temporal convolutional networks: A unified approach to action segmentation.  In Gang Hua and Hervé Jégou, editors, _Computer Vision – ECCV 2016 Workshops_ , pages 47–54, Cham, 2016. Springer International Publishing.  ISBN 978-3-319-49409-8.
  * Lei and Wasserman [2014] Jing Lei and Larry Wasserman.  Distribution‐free prediction bands for non‐parametric regression.  _Journal of the Royal Statistical Society: Series B (Statistical Methodology)_ , 76, 01 2014.  doi: 10.1111/rssb.12021.
  * Lei et al. [2013] Jing Lei, James Robins, and Larry Wasserman.  Distribution-free prediction sets.  _Journal of the American Statistical Association_ , 108(501):278–287, 2013.  doi: 10.1080/01621459.2012.751873.  URL https://doi.org/10.1080/01621459.2012.751873.  PMID: 25237208.
  * Meinshausen [2006] Nicolai Meinshausen.  Quantile regression forests.  _Journal of Machine Learning Research_ , 7(35):983–999, 2006.  URL http://jmlr.org/papers/v7/meinshausen06a.html.
  * Naeini et al. [2015] Mahdi Pakdaman Naeini, Gregory F Cooper, and Milos Hauskrecht.  Obtaining Well Calibrated Probabilities Using Bayesian Binning.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , pages 2901–2907, 2015.  ISSN 2159-5399.  doi: 10.1038/nbt.3121.ChIP-nexus.  URL http://www.ncbi.nlm.nih.gov/pubmed/25927013%0Ahttp://www.pubmedcentral.nih.gov/articlerender.fcgi?artid=PMC4410090.
  * Romano et al. [2019] Yaniv Romano, Evan Patterson, and Emmanuel Candes.  Conformalized quantile regression.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/5103c3584b063c431bd1268e9b5e76fb-Paper.pdf.
  * Taylor [2000] James W. Taylor.  A quantile regression neural network approach to estimating the conditional density of multiperiod returns.  _Journal of Forecasting_ , 19(4):299–311, 2000\.  doi: https://doi.org/10.1002/1099-131X(200007)19:4¡299::AID-FOR775¿3.0.CO;2-V.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/1099-131X%28200007%2919%3A4%3C299%3A%3AAID-FOR775%3E3.0.CO%3B2-V.
  * Vinyals et al. [2017] Oriol Vinyals, Timo Ewalds, Sergey Bartunov, Petko Georgiev, Alexander Sasha Vezhnevets, Michelle Yeo, Alireza Makhzani, Heinrich Küttler, John Agapiou, Julian Schrittwieser, John Quan, Stephen Gaffney, Stig Petersen, Karen Simonyan, Tom Schaul, Hado van Hasselt, David Silver, Timothy Lillicrap, Kevin Calderone, Paul Keet, Anthony Brunasso, David Lawrence, Anders Ekermo, Jacob Repp, and Rodney Tsing.  Starcraft ii: A new challenge for reinforcement learning, 2017.  URL https://arxiv.org/abs/1708.04782.
  * Vovk et al. [2005] Vladimir Vovk, Alex Gammerman, and Glenn Shafer.  _Algorithmic Learning in a Random World_.  Springer-Verlag, Berlin, Heidelberg, 2005.  ISBN 0387001522.
  * Vovk et al. [2009] Vladimir Vovk, Ilia Nouretdinov, and Alex Gammerman.  On-line predictive linear regression.  _The Annals of Statistics_ , 37(3):1566 – 1590, 2009.  doi: 10.1214/08-AOS622.  URL https://doi.org/10.1214/08-AOS622.


# Proof-of-principle demonstration of temporally multiplexed quantum repeater
link based on atomic ensemble

Minjie Wang  Haole Jiao  Jiajin Lu  Wenxin Fan  Zhifang Yang  Mengqi Xi
Shujing Li<EMAIL_ADDRESS>Hai Wang<EMAIL_ADDRESS>The State Key
Laboratory of Quantum Optics and Quantum Optics Devices, Institute of Opto-
Electronics, Shanxi University, Taiyuan 030006, China  Collaborative
Innovation Center of Extreme Optics, Shanxi University, Taiyuan 030006, China

###### Abstract

Duan-Lukin-Cirac-Zoller quantum repeater protocol provides a feasible scheme
to implement long-distance quantum communication and large-scale quantum
networks. The elementary link, namely the entanglement between two atomic
ensembles, is a fundamental component of quantum repeater. For practical
quantum repeater, it is required that the elementary link can be prepared with
high yield and the spin waves stored in atoms can be efficiently converted
into photons on demand. However, so far, such quantum repeater link has not
been demonstrated in experiments. Here, we demonstrate a proof-of-principle
multiplexed quantum repeater link by entangling two temporally multiplexed
quantum memory. Compared with a single-mode link, the successful preparation
rate of the multiplexed link is increased by one order of magnitude. By using
the cavity-enhanced scheme, the on-demand retrieval efficiency of atomic spin
waves is improved to 70%, which is beneficial for the subsequent entanglement
swapping between adjacent links. The realization of temporally multiplexed
quantum repeater link with high retrieval efficiency lays a foundation for the
development of practical quantum networks.

###  I Introduction

Long-distance entanglement distribution is a fundamental task of large-scale
quantum networks1 ; 2 ; 3 ; 4 . Based on this, one can implement distributed
quantum computation5 , remote quantum key distribution6 , and loophole-free
Bell test7 .Long-distance entanglement distribution can be achieved by
satellite-based free-space quantum communications8  or transferring quantum
information in fiber-based channels.However, the entanglement distribution
distance based on optical fiber is limited by the transmission loss of optical
fiber.Quantum repeater scheme9  has been proposed to extend the communication
distance, in which, the transmission channel is divided into a number of
elementary links. Entanglement is first created between two end nodes of each
link, and the distance of entanglement distribution is extended by
entanglement swapping.

The Duan, Lukin, Cirac, and Zoller (DLCZ) protocol10 , which combines atomic
ensemble and linear optics, has the advantage in entanglement generation and
connection. The protocol has received extensive attention, and many related
impressive advancements have been reported. For example, the storage lifetime
of atomic spin-wave has been expanded to second order by combining magnetic-
field-insensitive11 ; 12 ; 13 , long wavelength spin-wave12 ; 14  and
confining the atoms in optical lattices15 ; 16 ; 17 .The retrieval efficiency
of atomic memory is improved significantly in high optical-depth cold atomic
ensemble18 ; 19 ; 20  or using the cavity-enhanced scheme14 ; 15 ; 21 ; 22 ;
23 .

However, to ensure quantum correlation characteristics, the excitation
probability of spontaneous Raman scattering (SRS) has to be controlled at a
low level (about 1%), which makes the long-distance communication rate
incredibly low10 ; 24 . Multiplexing provides a solution to this problem25 .
Spatially-multiplexed quantum memories have been realized by using many
individually accessible memory cells with programmable addressing26 , by
spatially-resolved single-photon detection27 ; 28  or by collecting the Stokes
photon in multiple spatial directions simultaneously in cold atomic ensemble29
; 30 .Temporally multiplexed DLCZ quantum interfaces have been also
demonstrated by applying a train of write pulses to a cold atomic ensemble
along different directions31 ; 32 , or applying a reversible gradient magnetic
field to control the rephasing of the spin waves33 ; 34  in atomic ensemble.
Temporal multiplexing is more resource efficient and scalable than spatial
multiplexing due to its reuse of the same detectors35 .

Figure 1: Quantum repeater scheme based on the cavity-enhanced and temporally
multiplexed memory node 1 and node 2. A train of write pulses simultaneously
act on two memory nodes from different directions, exciting Stokes photons and
spin waves at both nodes with a certain probability. The emitted Stokes
photons travel to the middle station of the link for bell state measurement
(BSM), and successful detection of photons on D1 or D2 herald entanglement
between the two storage nodes. Wi and Ri: the i-th write pulse and the
corresponding read pulse. D1(D2): single photon detector.

At present, one of the goals of quantum repeater is how to achieve a high-
quality quantum repeater link. Some pioneering progress has been made in this
regard36 ; 37 ; 38 ; 39 ; 40 ; 41 ; 42 ; 43 ; 44 . Pan’s group has realized
entanglement over 22 kilometers based on efficient quantum frequency
conversion and cavity-enhanced emissive quantum memory39 .However, the quantum
memory is single mode type, which limits the entanglement generation rate.
Guo’s group demonstrated the heralded entanglement between absorptive quantum
memories, in which the temporal multiplexing is utilized to enhance the
entanglement distribution rate42 . Hugues de Riedmatten’s group reported
telecom-heralded entanglement between two temporal multiplexing solid-state
quantum memories40 .The solid-state quantum memory has a natural advantage in
terms of multi-mode operation, but the spin-wave stored in atoms cannot be on
demand and efficiently converted into photons the storage lifetime is short
(tens of ${\rm{\mu s}}$).

Here, we demonstrate a temporally multiplexed elementary link, in which the
spin waves stored in a cold atomic cloud can be efficiently converted into
photons on demand. In the atoms, two temporally multiplexed collective excited
states of atoms with different spatial modes are constructed via SRS to
simulate the quantum memories of two end nodes in an elementary link. The
entanglement between two quantum memories is generated via single photon
interference. Compared with single mode link, the rate of entanglement
generation has increased by an order of magnitude (11.8-flod). Besides, we
improve the retrieval efficiency to 70% using cavity-enhanced scheme through
the Purcell effect, which can greatly improve the success probability of
entanglement swapping between adjacent links. The demonstration of temporally
multiplexed elementary link with on-demand and high-efficiency retrieval paves
the road for practical quantum communication and quantum network.

###  II Cavity-enhanced and temporally multiplexed quantum repeater

We show the temporally multiplexed quantum repeater scheme based on the
cavity-enhanced quantum memory in Fig.1. The functional quantum link consists
of two quantum memories, labeled node1 and node 2. In each quantum node, a
87Rb atomic ensemble is placed inside a ring cavity to carry out memory. A
train of write pulses is applied on the atoms in different directions to
create the correlation between atomic spin wave and Stokes photon via SRS
process. The Stokes photon is resonant with cavity, and collected along cavity
mode. To demonstrate the multiplexed quantum repeater link, the two atomic
ensembles are triggered by the synchronous write pulse train. The emitted
Stokes photons are sent to the middle station to perform the Bell state
measurement via single photon interference. When a single photon is detected
by detector D1 or D2, it means that entanglement between two quantum memories
is successfully established. The success probability for entanglement
generation in an individual elementary link with N-mode multiplexing can be
evaluated by25

$P_{0}^{(N)}=1-{(1-{P_{0}})^{N}}\approx N{P_{0}}$ (1)

where ${P_{0}}={\chi}{e^{-{L_{0}}/(2{L_{att}})}}\eta_{FC}\eta_{TD}$ is the
success probability using non-multiplexed nodes, $\chi$ is the excitation
probability of Stokes photon, ${L_{att}}$ is the attenuation length of the
fiber channel, ${L_{0}}$ is the distance between two quantum memory,
$\eta_{FC}$ is the memory-to-telecom frequency conversion efficiency;
$\eta_{TD}$ is the total detection efficiency. Only one attempt at
entanglement generation can be made per communication interval
${T_{cc}}={L_{0}}/c$, where c is the speed of light in fibers. So the time
required to establish entanglement in a elementary link is
${t_{0}}\simeq{T_{cc}}/P_{0}^{(N)}={T_{cc}}/\left({N{P_{0}}}\right)$.

When the entanglement is generated in each quantum link, one can begin the
1-st level entanglement swapping. The atomic spin-waves are mapped into anti-
Stokes photons to perform the Bell state measurement by acting a strong read
pulse on the atom ensembles. To make the anti-Stokes photons propagate
counterclockwise along the cavity mode, the read pulse propagates counter to
the write pulse which produces the Stokes photon. The cavity can enhance the
reading process through the Purcell effect and improve the retrieval
efficiency significantly. The success probability for entanglement swapping at
the 1-st level is ${P_{1}}={R_{0}}{e^{-{t_{0}}/{\tau_{0}}}}\eta_{TD}$, where
${\tau_{0}}$ is the memory lifetime in atomic ensembles, and ${R_{0}}$is the
retrieval efficiency at zero delay.

Followed by analogy, the success probability for entanglement swapping at the
i-th level is ${P_{j}}={R_{0}}{e^{-{t_{i-1}}/{\tau_{0}}}}\eta_{TD}$, where
${t_{i}}\simeq{t_{i-1}}/{P_{i}}$ is the time needed for the entanglement
swapping at the i-th level. It is assumed that n-level entanglement swapping
is required to distribute entanglement to the whole communication channel.
Then the communication rate can be expressed as:

${R_{rate}}\approx\frac{1}{{{T_{cc}}}}P_{0}^{(N)}\left({\prod\nolimits_{i=1}^{i=n}{{P_{i}}}}\right){P_{pr}}$
(2)

where ${P_{pr}}\approx{R_{0}}{e^{-{t_{n}}/{\tau_{0}}}}$ is the success
probability for distributing an entangled photon pair over the distance $L$.

We calculate the repeater rate for entanglement distributing between two
remote quantum nodes. We assume $n=4,{L_{0}}=63km$, and the distance between
two remote quantum nodes is about 1000km. The total detection efficiency
${\eta_{TD}}\approx 90\%$ for the Stokes (anti-Stokes) detection channel. The
memory lifetime ${\tau_{0}}=16{\rm{}}s$45  and quantum frequency conversion
efficiency ${\eta_{FC}}=46\%$46  are the best experimental performance at
present as far as we know. With the retrieval efficiency at 80% and the mode
number at 100, the communication rate can reach 1Hz, which holds promise for
long-distance quantum communication.

###  III Demonstration of temporally multiplexed quantum repeater link

Figure 2: Schematic diagram of entanglement generation between two temporally
multiplexed quantum memory nodes. (a) Experimental setup. A train of 12 write
pulses with different directions is applied to the atoms to create temporally
multiplexed quantum interface between atomic spin wave and Stokes photon via
SRS. The Stokes fields SL and SR are collected at 0.14o to Z axis, which
defines the spatial modes of the atomic ensembles L and R. The modes SL and SR
are combined as the field S at the end of BD2. After the field S outputs from
the cavity, it is collected by a single-mode fiber and sent to the measurement
system. The entanglement between two atomic ensembles L and R is generated via
single photon interference between SL and SR modes. To verity the entanglement
between two atomic memories, the two spin waves are retrieved to aSL and aSR
fields, respectively, by applying a corresponding read pulse. The fields aSL
and aSR are combined as the field aS on BD1. Escaping from the cavity the
field aS is sent to the measurement system. (b) and (c) are the relevant
atomic levels involved in the write and read processes, respectively.

The memory medium is a 87Rb cold atomic cloud trapped in magneto-optical trap
(MOT). A guiding magnetic field (B=4G) along Z axis is applied to define the
quantization axis. A ring-cavity is placed around the atoms to improve the
retrieval efficiency, and the details can be found in our previous work14 .

The atomic ground levels
$\left|g\right\rangle=\left|{5{S_{1/2}},F{\rm{=1}}}\right\rangle$ and
$\left|s\right\rangle=\left|{5{S_{1/2}},F{\rm{=2}}}\right\rangle$ together
with the excited level
$\left|{{e_{\rm{1}}}}\right\rangle=\left|{5{P_{1/2}},F^{\prime}{\rm{=1}}}\right\rangle$($\left|{{e_{\rm{2}}}}\right\rangle=\left|{5{P_{1/2}},F^{\prime}{\rm{=2}}}\right\rangle$)
form a $\Lambda$ -type system, shown in Fig.2(b) and 2(c).The atoms are
initially prepared in the Zeeman state
$\left|{g,{m_{{F_{g}}}}=0}\right\rangle$. A train of 12 write pulses is
applied to the atoms to create the correlation between atomic spin wave and
Stokes field via SRS. The Stokes photons excited by the i-th write pulse will
be detected in the i-th measurement window. Each write pulse enters the atoms
with different propagation directions. The angle between the two adjacent
write pulses is 0.28o, and the angle between the 1-st write pulse and Z axis
is 0.2o. The train lasts $\Delta T{\rm{=}}8\mu{\rm{s}}$ and the interval
between two adjacent write pulses is 400ns. All write pulses are
${\sigma^{\rm{+}}}$-polarized with red-detuned by 110 MHz to the
$\left|g\right\rangle\to\left|{{e_{\rm{1}}}}\right\rangle$ transition. Each
write pulse induces the Raman transition
$\left|{g,{m_{Fg}}={\rm{0}}}\right\rangle\to\left|{s,{m_{Fs}}={\rm{0}}}\right\rangle$
via $\left|{{e_{1}},{m_{F{e_{1}}}}={\rm{1}}}\right\rangle$, which emits a
${\sigma^{\rm{+}}}$-polarized Stokes photon and simultaneously creates an
atomic spin-wave associated with the clock coherence
$\left|{{m_{Fg}}={\rm{0}}}\right\rangle\leftrightarrow\left|{{m_{Fs}}={\rm{0}}}\right\rangle$
probabilistically.

For constructing two atomic ensembles L and R with different spatial modes to
simulate the two end nodes in an elementary link, the two Stokes fields SL and
SR are collected at 0.14o to Z axis. After the interaction of the atoms with
the i-th write pulse, the joint state of the Stokes field and the associated
spin-wave is described as:

${\left|{\psi^{i}}\right\rangle_{L(R)}}=\left|{{{\rm{0}}_{a}}}\right\rangle\left|{{{\rm{0}}_{s}}}\right\rangle+\sqrt{\chi}{\left|{{\rm{1}}_{a}^{i}}\right\rangle_{L(R)}}{\left|{{\rm{1}}_{s}^{i}}\right\rangle_{L(R)}}+O(\chi)$
(3)

where, $\left|{{0_{a}}}\right\rangle$ ($\left|{{0_{s}}}\right\rangle$) denotes
the vacuum part, $\chi$ is the excitation probability of one Stokes photon and
it is the same for each write pulse in the experiment,
${\left|{{\rm{1}}_{s}^{i}}\right\rangle_{L(R)}}$ and
${\left|{1_{a}^{i}}\right\rangle_{L(R)}}$ are the Stokes field with one photon
in mode SL(SR) and the single collective spin excitation in L(R) ensemble
resulted by the i-th write pulse. The single collective spin excitation can be
written as

${\left|{{\rm{1}}_{a}^{i}}\right\rangle_{L(R)}}{\rm{=}}\frac{1}{{\sqrt{{N_{a}}}}}\sum\limits_{{\rm{j}}={\rm{1}}}^{N}{\exp(-i\vec{x}_{j,L(R)}^{i}k_{a,L(R)}^{i})}{\left|{{g_{1}}\cdots
s_{j}^{i}\cdots{g_{N}}}\right\rangle_{L(R)}}$ (4)

where Na is the number of atoms, $\vec{x}_{j,L(R)}^{i}$ denotes the spatial
position of the j-th atom excited by the i-th write pulse,
$k_{a,L}^{i}=k_{w}^{i}-k_{s}^{L}$ ($k_{a,R}^{i}=k_{w}^{i}-k_{s}^{R}$ ) is the
wave vector of atomic spin-wave, $k_{w}^{i}$ is the wave vector of the i-th
write pulse, and $k_{s}^{L}$ ($k_{s}^{R}$ ) is the wave vector of the Stokes
photon in mode SL(SR).

In order to achieve entanglement between the two ensembles, we perform single
photon interference on Stokes fields SL and SR. The ${\sigma^{\rm{+}}}$
-polarized Stokes fields SL and SR are transformed into H- and V-polarization
by a quarter wave-plate and a half wave plate, respectively, and then, they
are combined as the field S on BD2. After the field S outputs from the cavity,
it is collected by a single-mode fiber and sent to the measurement system,
which includes a half-wave plate HWS, a polarization beam splitter PBSS and
detectors DS1 and DS2.At the two outputs of PBSS, the field S is changed into
two modes $S_{+}=\left({S_{R}+S_{L}}\right)/\sqrt{2}$ and
$S_{{}_{-}}=\left({S_{R}-S_{L}}\right)/\sqrt{2}$ when HWS is set at
$\vartheta={22.5^{o}}$. The fields $S_{+}$ and $S_{-}$ are directed to
detectors DS1 and DS2, respectively. A click from DS1 and DS2 in the i-th
measurement window heralds that two ensembles are mapped into an entangled
state:
$\left|{\Psi_{\pm}^{i}}\right\rangle=\left({\left|{1_{a}^{i}}\right\rangle{}_{R}{{\left|0\right\rangle}_{L}}\pm{e^{-i\phi}}\left|0\right\rangle{}_{R}{{\left|{1_{a}^{i}}\right\rangle}_{L}}}\right)/\sqrt{2}$
, where $\phi$ is the phase difference between two Stokes fields before they
are combined on BD2.

To experimentally verify the entanglement state between the two ensembles, we
map the atomic spin-wave into anti-Stokes fields by acting a corresponding
${\sigma^{\rm{+}}}$ -polarized read pulse. A feedforward system based on FPGA
is utilized to determine the propagation direction of the read pulse. When a
Stokes photon is detected in the i-th measurement window, the read pulse with
wave-vector $k_{R}^{i}=-k_{w}^{i}$ is applied on the atoms by a feedforward
controlled acousto-optic modulator (AOM). The atomic spin wave
${\left|{{\rm{1}}_{a}^{i}}\right\rangle_{L}}$
(${\left|{{\rm{1}}_{a}^{i}}\right\rangle_{R}}$) is transformed to
${\sigma^{\rm{+}}}$ -polarized anti-Stokes field aSL(aSR) with wave vector
$k_{aS}^{L}=-k_{S}^{L}$ ($k_{aS}^{R}=-k_{S}^{R}$).The entanglement state
between anti-Stokes photons in modes aSL and aSR can be written as
$\left|{\psi_{aS}^{\pm}}\right\rangle=\left({\left|{{1_{aS}}}\right\rangle{}_{R}{{\left|0\right\rangle}_{L}}\pm{e^{-i(\phi+\varphi)}}\left|0\right\rangle{}_{R}{{\left|{{1_{aS}}}\right\rangle}_{L}}}\right)/\sqrt{2}$
, where ${\left|{{\rm{1}}_{aS}}\right\rangle_{L(R)}}$ is the anti-Stokes field
with one photon in mode aSL (aSR), and $\varphi$ is the phase difference
between two anti-Stokes fields before they are combined on BD1. By controlling
the temperature of BD1 and BD2 precisely, the phase difference $\phi+\varphi$
is kept constant.

Then, the fields aSL and aSR are transformed into H-polarized and V-polarized
by wave plates and combined into the field aS on BD1. After the aS field
escapes from the cavity, it is collected by a single-mode fiber and sent to
the measurement system. The Stokes photon and anti-Stokes fields are resonated
with the cavity. The cavity is locked via the Pound-Drever-Hall (PDH) method
by using a locking laser pulse, which is coupled to the cavity mode through a
beam splitter (BS, R=95%).

###  IV Experimental results

For charactering the temporally multiplexed elementary link, we measure the
concurrence of entanglement between two ensembles, which ranges from 0 for a
separable state to 1 for a maximally entangled state. The concurrence is
measured as
$C=\max\left({0,\frac{{2\left|d\right|-2\sqrt{P_{00}P_{11}}}}{P}}\right)$ 47 ,
$P_{mn}$ corresponds to the probability to find m photons in the field aSR and
n photons in the field aSL in the read process after the Stokes photons are
detected, $P=P_{00}+P_{01}+P_{10}+P_{11}$, $d=V\left({P_{10}+P_{01}}\right)/2$
is the coherence term between the states
$\left|{{1_{aS}}}\right\rangle{}_{R}{\left|0\right\rangle_{L}}$ and
$\left|0\right\rangle{}_{R}{\left|{{1_{aS}}}\right\rangle_{L}}$, V is the
visibility of the interference fringes between the anti-Stokes fields $aS_{R}$
and $aS_{L}$ when their relative phase $\theta$ is scanned.

Figure 3: The counts in detector DaS1 as a function of $\theta$ for storage
time t=1 $\mu$s (a) and storage time t=150 $\mu$s (b).

To measure the interference visibility V, the polarization angle of HWaS is
set at $\vartheta={22.5^{o}}$. The aS field evolves to
$aS_{+}=\left({aS_{R}+aS_{L}}\right)/\sqrt{2}$ and
$aS_{-}=\left({aS_{R}-aS_{L}}\right)/\sqrt{2}$ at the two outputs ofPBSaS,
which are directed into detectors DaS1 and DaS2, respectively. We insert a
phase controller before HWaS, which consists of two quarter wave plates and
one half wave plate sandwiched in the middle. The relative phase $\theta$
between the anti-Stokes fields aSL and aSR can be changed by rotating the
angle of the half wave plate. Along with the scan of $\theta$ , counts in
detector DaS1 vary as a sinusoidal function, as shown in Fig. 3. The
visibility V can be measured
as:$V=\frac{{{\rm{Max(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}-{\rm{M}}in{\rm{(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}}}{{{\rm{Max(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}+{\rm{M}}in{\rm{(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}}}$
, where, ${\rm{Max(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}$
(${\rm{Min(}}{{\rm{C}}_{{D_{S1}},{D_{aS1}}}}{\rm{)}}$) denotes the maximum
(minimum) coincidence counts between the Stokes and anti-Stokes fields. Thus,
we could get $V=0.795\pm 0.015$ at storage time t=1$\mu$s and $V=0.7\pm 0.024$
at storage time t=150 $\mu$s. For all experimental results the excitation
probability $\chi$=1%.

Table 1: The measured $P_{mn}$ at storage time t=1 $\mu$s and t=150 $\mu$s.

To measure the $P_{mn}$, we set the polarization angle of HWaS is set at
$\vartheta={0^{o}}$. The probabilities of $P_{mn}$ can be directly measured
via photon counting in the fields aSR and aSL using detectors DaS1 and DaS2,
as shown in table 1.

Based on the above measurements, the value of the concurrence of the
entanglement between two ensembles can be deduced. The concurrence as a
function of the storage time is shown in Fig.4. We get a concurrence of
C=0.040(2) at storage time t=1 $\mu$s and C=0.001(2) at storage time t=150
$\mu$s for $\left|{\psi_{aS}^{+}}\right\rangle$ . The experimental results
show that the entanglement between the two ensembles can be remained for at
least 150 $\mu$s.

Figure 4: The measured concurrence C as a function of the storage time for
$\chi$=1%.

Meanwhile, we measure the intrinsic efficiency of temporal multiplexed quantum
memory. The intrinsic efficiency defined by
$\eta={{\left({P_{01}+P_{10}}\right)}\mathord{\left/{\vphantom{{\left({P_{01}+P_{10}}\right)}{\left[{\sum\limits_{i}^{12}{\left({P_{{D_{S1}}}^{i}+P_{{D_{S2}}}^{i}}\right)\;{\eta_{D}}\;}}\right]}}}\right.\kern-1.2pt}{\left[{\sum\limits_{i}^{12}{\left({P_{{D_{S1}}}^{i}+P_{{D_{S2}}}^{i}}\right)\;{\eta_{D}}\;}}\right]}}$
, where, $P_{{D_{S1}}}^{i}$ ($P_{{D_{S2}}}^{i}$) denotes the probability of
detecting Stokes photons at the detectors DS1 (DS2) in i-th measurement
window, and ${\eta_{D}}$ is the total detection efficiency for anti-Stokes
photons. Fig.5 plots the measured intrinsic efficiency (circles) as a function
of storage time. We fit the data according to the function
$R(t){\rm{=}}{R_{\rm{0}}}\exp\left({{{{\rm{-t}}}\mathord{\left/{\vphantom{{{\rm{-t}}}{{\tau_{0}}}}}\right.\kern-1.2pt}{{\tau_{0}}}}}\right)$
(shown by the solid curve), which yields the intrinsic efficiency at the zero
delay ${R_{\rm{0}}}={\rm{70}}{\rm{.7}}\%{\rm{}}$ , together with a memory
lifetime ${\tau_{\rm{0}}}\approx{\rm{0}}{\rm{.3}}ms$ .

Figure 5: The measured intrinsic efficiency (circles) as a function of storage
time .

Then, we present the entanglement generation rate (EGR), as a function of the
multiplexed mode number N, shown in Fig.6. The EGR with n-mode multiplexing is
proportional to the sum of the Stokes photon detection probabilities at the
detectors DS1 and DS2
$P_{D}^{(N)}=\sum\limits_{i}^{N}{\left({P_{{D_{S1}}}^{i}+P_{{D_{S2}}}^{i}}\right)\;\;}$
. The result shows the EGR increases linearly with the number of modes, which
is good agreement with the theoretical prediction $P_{D}^{(N)}=N{p_{D}}$ ,
where ${p_{D}}$ is the EGR for single mode. when the number of modes is 12,
${{P_{D}^{(12)}}\mathord{\left/{\vphantom{{P_{D}^{(12)}}{p_{D}}}}\right.\kern-1.2pt}{p_{D}}}=11.79\pm
0.35$ .

Figure 6: The detection probability of Stokes photon $P_{D}^{(N)}$ as a
function of the number of modes at storage time t=1$\mu$s. The line is the
linear fitting according to $P_{D}^{(N)}=N{p_{D}}$ , where
${P_{D}}=2.5\times{10^{-3}}$ is the detection probability with single mode.
Figure 7: The measured concurrence as a function of mode number at storage
time t=1$\mu$s.

Finally, we also measure the concurrence as a function of number of modes at
storage time t=1$\mu$s, which is showed in Fig.7. As the number of modes
increases, the concurrence decreases. We attribute the decrease in concurrence
to the crosstalk between the different modes. When one Stokes photon is
detected in the i-th measurement window, we retrieve the spin wave by the
corresponding read pulse with wave vector $k_{R}^{i}$ in the read process.
However, the phase-mismatched spin waves generated by all the other write
pulses can also be converted photons with a certain probability. These non-
directional emitted photons will enter the anti-Stokes fields $aS_{R}$ and
$aS_{L}$ , and cause a decrease in concurrence. In the future, We can suppress
the background noise by using an asymmetrical photon-collection channel48  or
designing the specially cavity which has different enhancement for Stokes
photon and anti-Stokes34 .

###  V Conclusion and Discussion

We demonstrate a temporally multiplexed elementary link based on atomic
ensembles, wherein spin waves stored in atoms can be effectively transformed
into photons on demand. We generate two atomic memories with distinct spatial
modes by collecting emitted Stokes photons in two spatial modes, and then
entanglement between the two quantum memories is created through single photon
interference. Compared with single mode link, the rate of entanglement
generation has increased by an order of magnitude (11.8-flod). By using the
cavity-enhanced scheme, the on-demand retrieval efficiency of atomic spin
waves is improved to 70%, which is beneficial for the entanglement swapping
between adjacent links.Combining frequency conversion46 ; 49 ; 50 ; 51 , our
multiplexing quantum repeater link with cavity-enhance holds promise for long-
distance communication in optical fiber. To improve the entanglement rate
further, we can load the atoms in optical lattice 21 ; 45  to expand the
storage lifetime. In addition, one can realize large-scale multiplexing
capability by combining temporal and spatial multiplexing52 . The realization
of temporal multiplexing quantum repeater link with high retrieval efficiency
lays a foundation for the development of practical quantum networks.

## Acknowledgements

This work is supported by the National Natural Science Foundation of China
(12174235), the Fund for Shanxi Key Subjects Construction (1331), and the
Fundamental Research Program of Shanxi Province (202203021221011)

### References

  * (1) H. J. Kimble, The quantum internet.  Nature 453, 1023-1030 (2008).
  * (2) Christoph Simon, Towards a global quantum network.  Nat. Photon. 11, 678-680 (2017).
  * (3) S. Wehner, D. Elkouss, R. Hanson, Quantum internet: A vision for the road ahead.  Science 362, 303 ( 2018 ).
  * (4) S. H. Wei, B. Jing, X. Y. Zhang, J. Y. Liao, C. Z. Yuan, B. Y. Fan, C. Lyu, D. L. Zhou, Y. Wang, G. W. Deng, H. Z. Song, D. Oblak, G. C. Guo, Q. Zhou, Towards Real‐World Quantum Networks: A Review.  Laser Photonics Rev. 16, 2100219 (2022).
  * (5) S. L. Severin Daiss, Stephan Welte, Emanuele Distante, Philip Thomas, Lukas Hartung, Olivier Morin1, Gerhard Rempe, A quantum-logic gate between distant quantum-network modules.  Science 371, 614–617 (2021).
  * (6) N. Gisin, R. Thew, Quantum communication.  Nat. Photon. 1, 165-171 (2007).
  * (7) B. Hensen, H. Bernien, A. E. Dreau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. Vermeulen, R. N. Schouten, C. Abellan, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, R. Hanson, Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres.  Nature 526, 682-686 (2015).
  * (8) C.-Y. Lu, Y. Cao, C.-Z. Peng, J.-W. Pan, Micius quantum experiments in space.  Rev. Mod. Phys. 94, 035001 (2022).
  * (9) H. J. Briegel, W. Dür, J. I. Cirac, P. Zoller, Quantum Repeaters: The Role of Imperfect Local Operations in Quantum Communication. Phys. Rev. Lett. 81,5932 (1998).
  * (10) L. M. Duan, M. D. Lukin, J. I. Cirac, P. Zoller, Long-distance quantum communication with atomic ensembles and linear optics.  Nature 414,413-418 (2001).
  * (11) B. Zhao, Y. A. Chen, X. H. Bao, T. Strassel, C. S. Chuu, X. M. Jin, J. Schmiedmayer, Z. S. Yuan, S. Chen, J. W. Pan, A millisecond quantum memory for scalable quantum networks.  Nat. Phys. 5, 95-99 (2009).
  * (12) Z. Xu, Y. Wu, L. Tian, L. Chen, Z. Zhang, Z. Yan, S. Li, H. Wang, C. Xie, K. Peng, Long lifetime and high-fidelity quantum memory of photonic polarization qubit by lifting zeeman degeneracy. Phys. Rev. Lett. 111,240503 (2013).
  * (13) Y.-H. Ye, L. Zeng, M.-X. Dong, W.-H. Zhang, E.-Z. Li, D.-C. Li, G.-C. Guo, D.-S. Ding, B.-S. Shi, Long-Lived Memory for Orbital Angular Momentum Quantum States.  Phys. Rev. Lett. 129, 193601 (2022).
  * (14) M. J. Wang, S. Z. Wang, Teng Fei Ma, Y. Li, Y. Xie, H. L. Jiao, H. L. Liu, S. J. Li, H. Wang, Generation of highly retrievable atom photon entanglement with a millisecond lifetime via a spatially multiplexed cavity.  Quantum 7, 903 (2023).
  * (15) X. J. Wang, S. J. Yang, P. F. Sun, B. Jing, J. Li, M. T. Zhou, X. H. Bao, J. W. Pan, Cavity-Enhanced Atom-Photon Entanglement with Subsecond Lifetime.  Phys. Rev. Lett. 126, 090501(2021).
  * (16) R. Zhao, Y. O. Dudin, S. D. Jenkins, C. J. Campbell, D. N. Matsukevich, T. A. B. Kennedy, A. Kuzmich, Long-lived quantum memory.  Nat. Phys. 5, 100-104 (2009).
  * (17) Y. O. Dudin, A. G. Radnaev, R. Zhao, J. Z. Blumoff, T. A. Kennedy, A. Kuzmich, Entanglement of light-shift compensated atomic spin waves with telecom light.  Phys. Rev. Lett. 105, 260502 (2010).
  * (18) Y. Wang, J. Li, S. Zhang, K. Su, Y. Zhou, K. Liao, S. Du, H. Yan, S.-L. Zhu, Efficient quantum memory for single-photon polarization qubits.  Nat. Photon. 13, 346-351 (2019).
  * (19) P. Vernaz-Gris, K. Huang, M. Cao, A. S. Sheremet, J. Laurat, Highly-efficient quantum memory for polarization qubits in a spatially-multiplexed cold atomic ensemble.  Nat. Commun. 9,363(2018).
  * (20) M. Cao, F. Hoffet, S. Qiu, A. S. Sheremet, J. Laurat, Efficient reversible entanglement transfer between light and quantum memories.  Optica 7, 1440 (2020).
  * (21) S.-J. Yang, X.-J. Wang, X.-H. Bao, J.-W. Pan, An efficient quantum light–matter interface with sub-second lifetime.  Nat. Photon. 10,381-384 (2016).
  * (22) S. J. Yang, X. J. Wang, J. Li, J. Rui, X. H. Bao, J. W. Pan, Highly retrievable spin-wave-photon entanglement source.  Phys. Rev. Lett. 114,210501(2015).
  * (23) X.-H. Bao, A. Reingruber, P. Dietrich, J. Rui, A. Dück, T. Strassel, L. Li, N.-L. Liu, B. Zhao, J.-W. Pan, Efficient and long-lived quantum memory with cold atoms inside a ring cavity.  Nat. Phys. 8, 517-521 (2012).
  * (24) N. Sangouard, C. Simon, H. de Riedmatten, N. Gisin, Quantum repeaters based on atomic ensembles and linear optics.  Rev. Mod. Phys. 83, 33-80 (2011).
  * (25) C. Simon, H. de Riedmatten, M. Afzelius, N. Sangouard, H. Zbinden, N. Gisin, Quantum repeaters with photon pair sources and multimode memories.  Phys. Rev. Lett. 98, 190503 (2007).
  * (26) Y. F. Pu, N. Jiang, W. Chang, H. X. Yang, C. Li, L. M. Duan, Experimental realization of a multiplexed quantum memory with 225 individually accessible memory cells.  Nat. Commun. 8, 15359 (2017).
  * (27) M. Lipka, M. Mazelanik, A. Leszczyński, W. Wasilewski, M. Parniak, Massively-multiplexed generation of Bell-type entanglement using a quantum memory.  Commun. Phys. 4, 46 (2021).
  * (28) M. Parniak, M. Dabrowski, M. Mazelanik, A. Leszczy$\acute{n}$ski, M. Lipka, W. Wasilewski, Wavevector multiplexed atomic quantum memory via spatially-resolved single-photon detection.  Nat. Commun. 8, 2140 (2017).
  * (29) L. Tian, Z. Xu, L. Chen, W. Ge, H. Yuan, Y. Wen, S. Wang, S. Li, H. Wang, Spatial Multiplexing of Atom-Photon Entanglement Sources using Feedforward Control and Switching Networks.  Phys. Rev. Lett. 119, 130505 (2017).
  * (30) S.-Z. Wang, M.-J. Wang, Y.-F. Wen, Z.-X. Xu, T.-F. Ma, S.-J. Li, H. Wang, Long-lived and multiplexed atom-photon entanglement interface with feed-forward-controlled readouts.  Commun. Phys. 4, 168 (2021).
  * (31) . Wen, P. Zhou, Z. Xu, L. Yuan, H. Zhang, S. Wang, L. Tian, S. Li, H. Wang, Multiplexed spin-wave–photon entanglement source using temporal multimode memories and feedforward-controlled readout.  Phys. Rev. A 100, 012342 (2019).
  * (32) H. Liu, M. Wang, H. Jiao, J. Lu, W. Fan, S. Li, H. Wang, Cavity-enhanced and temporally-multiplexed atom-photon entanglement interface.  Opt. Express 31, 7200 (2023).
  * (33) B. Albrecht, P. Farrera, G. Heinze, M. Cristiani, H. de Riedmatten, Controlled Rephasing of Single Collective Spin Excitations in a Cold Atomic Quantum Memory.  Phys. Rev. Lett. 115, 160501 (2015).
  * (34) L. Heller, P. Farrera, G. Heinze, H. de Riedmatten, Cold-Atom Temporally Multiplexed Quantum Memory with Cavity-Enhanced Noise Suppression.  Phys. Rev. Lett. 124, 210504 (2020).
  * (35) C. Xiong, X. Zhang, Z. Liu, M. J. Collins, A. Mahendra, L. G. Helt, M. J. Steel, D. Y. Choi, C. J. Chae, P. H. Leong, B. J. Eggleton, Active temporal multiplexing of indistinguishable heralded single photons.  Nat. Commun. 7, 10853 (2016).
  * (36) Z. S. Yuan, Y. A. Chen, B. Zhao, S. Chen, J. Schmiedmayer, J. W. Pan, Experimental demonstration of a BDCZ quantum repeater node.  Nature 454, 1098-1101 (2008).
  * (37) . van Leent, M. Bock, F. Fertig, R. Garthoff, S. Eppelt, Y. Zhou, P. Malik, M. Seubert, T. Bauer, W. Rosenfeld, W. Zhang, C. Becher, H. Weinfurter, Entangling single atoms over 33 km telecom fibre.  Nature 607, 69-73 (2022).
  * (38) V. Krutyanskiy, M. Galli, V. Krcmarsky, S. Baier, D. A. Fioretto, Y. Pu, A. Mazloom, P. Sekatski, M. Canteri, M. Teller, J. Schupp, J. Bate, M. Meraner, N. Sangouard, B. P. Lanyon, T. E. Northup, Entanglement of Trapped-Ion Qubits Separated by 230 Meters.  Phys. Rev. Lett. 130, 050803 (2023).
  * (39) Y. Yu, F. Ma, X. Y. Luo, B. Jing, P. F. Sun, R. Z. Fang, C. W. Yang, H. Liu, M. Y. Zheng, X. P. Xie, W. J. Zhang, L. X. You, Z. Wang, T. Y. Chen, Q. Zhang, X. H. Bao, J. W. Pan, Entanglement of two quantum memories via fibres over dozens of kilometres.  Nature 578, 240-245 (2020).
  * (40) D. Lago-Rivera, S. Grandi, J. V. Rakonjac, A. Seri, H. de Riedmatten, Telecom-heralded entanglement between multimode solid-state quantum memories.  Nature 594, 37-40 (2021).
  * (41) H. Li, J. P. Dou, X. L. Pang, T. H. Yang, C. N. Zhang, Y. Chen, J. M. Li, I. A. Walmsley, X. M. Jin, Heralding quantum entanglement between two room-temperature atomic ensembles.  Optica 8, 925-929 (2021).
  * (42) X. Liu, J. Hu, Z. F. Li, X. Li, P. Y. Li, P. J. Liang, Z. Q. Zhou, C. F. Li, G. C. Guo, Heralded entanglement distribution between two absorptive quantum memories.  Nature 594, 41-45 (2021).
  * (43) J. Hofmann, M. Krug, N. Ortegel, L. Gérard, M. Weber, W. Rosenfeld, H. Weinfurter, Heralded Entanglement Between Widely Separated Atoms.  Science 337, 72-75 (2012).
  * (44) D. L. Moehring, P. Maunz, S. Olmschenk, K. C. Younge, D. N. Matsukevich, L. M. Duan, C. Monroe, Entanglement of single-atom quantum bits at a distance.  Nature 449, 68-71 (2007).
  * (45) Y. O. Dudin, L. Li, A. Kuzmich, Light storage on the time scale of a minute.  Phys. Rev. A 87, 031801(R) (2013).
  * (46) X. Y. Luo, Y. Yu, J. L. Liu, M. Y. Zheng, C. Y. Wang, B. Wang, J. Li, X. Jiang, X. P. Xie, Q. Zhang, X. H. Bao, J. W. Pan, Postselected Entanglement between Two Atomic Ensembles Separated by 12.5 km.  Phys. Rev. Lett. 129, 050503 (2022).
  * (47) J. Laurat, K. S. Choi, H. Deng, C. W. Chou, H. J. Kimble, Heralded entanglement between atomic ensembles: preparation, decoherence, and scaling.  Phys. Rev. Lett. 99, 180504 (2007).
  * (48) Y. Li, Y.-f. Wen, M.-j. Wang, C. Liu, H.-l. Liu, S.-j. Li, Z.-x. Xu, H. Wang, Noise suppression in a temporal-multimode quantum memory entangled with a photon via an asymmetrical photon-collection channel.  Phys. Rev. A 106, 022610 (2022).
  * (49) T. van Leent, M. Bock, R. Garthoff, K. Redeker, W. Zhang, T. Bauer, W. Rosenfeld, C. Becher, H. Weinfurter, Long-Distance Distribution of Atom-Photon Entanglement at Telecom Wavelength.  Phys. Rev. Lett. 124, 010510(2020).
  * (50) R. Ikuta, T. Kobayashi, T. Kawakami, S. Miki, M. Yabuno, T. Yamashita, H. Terai, M. Koashi, T. Mukai, T. Yamamoto, N. Imoto, Polarization insensitive frequency conversion for an atom-photon entanglement distribution via a telecom network.  Nat. Commun. 9, 1997 (2018).
  * (51) B. Albrecht, P. Farrera, X. Fernandez-Gonzalvo, M. Cristiani, H. de Riedmatten, A waveguide frequency converter connecting rubidium-based quantum memories to the telecom C-band.  Nat. Commun. 5, 3376 (2014).
  * (52) T. S. Yang, Z. Q. Zhou, Y. L. Hua, X. Liu, Z. F. Li, P. Y. Li, Y. Ma, C. Liu, P. J. Liang, X. Li, Y. X. Xiao, J. Hu, C. F. Li, G. C. Guo, Multiplexed storage and real-time manipulation based on a multiple degree-of-freedom quantum memory.  Nat. Commun. 9, 3407 (2018).