# High-efficient two-step entanglement purification using hyperentanglement

Lan Zhou,1 Yu-Bo<EMAIL_ADDRESS>1 School of Science, Nanjing
University of Posts and Telecommunications, Nanjing, 210003, China
2Institute of Quantum Information and Technology, Nanjing University of Posts
and Telecommunications, Nanjing, 210003, China

###### Abstract

Entanglement purification is a powerful method to distill the high-quality
entanglement from low-quality entanglement. In the paper, we propose an
efficient two-step entanglement purification protocol (EPP) for the
polarization entanglement by using only one copy of two-photon hyperentangled
state in polarization, spatial-mode, and time-bin DOFs. We suppose that the
entanglement in all DOFs suffer from channel noise. In two purification steps,
the parties can reduce the bit-flip error and phase-flip error in polarization
DOF by consuming the imperfect entanglement in the spatial-mode and time-bin
DOFs, respectively. This EPP effectively reduces the consumption of
entanglement pairs and the experimental difficulty. Moreover, if consider the
practical photon transmission and detector efficiencies, our EPP has much
higher purification efficiency than previous recurrence EPPs. Meanwhile, when
one or two purification steps fail, the distilled mixed state may have
residual entanglement. Taking use of the residual entanglement, the parties
may still distill higher-quality polarization entanglement. Even if not, they
can still reuse the residual entanglement in the next purification round. The
existence of residual entanglement benefits for increasing the yield of the
EPP. All the above advantages make our EPP have potential application in
future quantum information processing.

###### pacs:

03.67.Pp, 03.67.Hk, 03.65.Ud

##  I Introduction

Entanglement is an indispensable resource which is widely applied in quantum
communication field, such as quantum teleportationteleportation1 ;
teleportation2 ; teleportation3 , quantum repeater repeater1 ; repeater2 ;
repeater3 , quantum key distribution (QKD) qkd , quantum secret sharing (QSS)
qss , and quantum secure direct communication (QSDC) qsdc1 ; qsdc2 ; qsdc3 ;
qsdc4 . The above applications often require the maximal entanglement.
However, entanglement is generally fragile due to the channel noise. During
the practical applications, the degraded entanglement may decrease the quantum
communication efficiency or even make quantum communication insecure.

Entanglement purification which was first proposed by Bennett _et al._ in 1996
EPP0  is an efficient method to distill high quality entanglement from low
quality entanglement with local operation and classical communications (LOCC).
Recurrence entanglement purification is the most common entanglement
purification form, which has been well developed in both theory and experiment
EPP0 ; Deustch ; Murao ; Pan1 ; Pan2 ; Pan3 ; graph ; atom ; Cheong ; sheng1 ;
sheng2 ; Zhou1 ; Wang ; Zhou2 ; Zhang ; Dur ; Rozpeedek ; Krastanov ; Wu ;
zhouap ; zhouoe ; hu ; Du ; nest ; network ; shenghyper1 ; shenghyper2 . The
recurrence entanglement purification protocols (EPPs) require two or more
copies of low-quality entangled states from the same enables. After two
communication parties in distant locations performing the controlled-not
(CNOT) or other similar operations, one pair of low-quality entangled state is
measured. If the purification is successful, the fidelity of left photon pair
can be increased. For example, in 2001, Pan _et al._ presented an EPP of
general mixed entangled states with linear optical elements Pan1 , and later
they improved their EPP by adopting available parametric down conversion
sources Pan2 . In 2003, Pan _et al._ demonstrated the experiment of the
entanglement purification for general mixed states of polarization-entangled
photons Pan3 . In 2008, Sheng _et al._ proposed an EPP based on nondestructive
quantum nondemolition detectors sheng1 . In 2017, Pan _et al._ experimentally
realized the nested purification for a linear optical quantum repeater nest .
In addition, the experimental purification between two-atom entanglement and
solid state quantum network nodes were also demonstrated atom ; network . In
2010, Sheng _et al._ proposed the deterministic EPPs (DEPPs) by adopting the
hyperentanglement shenghyper1 ; shenghyper2 .

Although the recurrence entanglement purification has been well studied,
existing recurrence EPPs often have relatively low yield. The reason is that
in each purification round, at least one pair of low-quality entangled states
should be consumed. In practical applications, entanglement purification
process often has to be iterated for many rounds to obtain high-fidelity
entangled pairs, so that a large amount of low-quality entangled pairs have to
be consumed. It is a big waste of the precious entanglement resources. In
2021, Hu _et al._ proposed and experimentally demonstrated the first long-
distance polarization entanglement recurrence purification using only one
polarization-spatial-mode hyperentangled photon pair hu . They supposed that
the entanglement in both polarization and spatial-mode DOFs suffer from one
kind of error, say, the bit-flip error or phase-flip error. After performing
the EPP, they obtained a significant improvement in the fidelity of
polarization entanglement. This protocol effectively reduces consumption of
copies of entanglement pairs, especially in purification consisting of many
rounds.

Actually, in practical entanglement distribution process, the bit-flip error
and phase-flip error may be occurred simultaneously. In the paper, we consider
a more general recurrence EPP which can simultaneously reduce the bit-flip
error and phase-flip error of the polarization entanglement by using only one
pair of polarization-spatial-time-bin hyperentangled photon pair. We choose
the spatial mode and time-bin entanglement for the entanglement in both two
DOFs, especially in time-bin DOF being highly robust to the channel noise. The
entanglement in time-bin DOF has been successfully used in the transmission of
qubits over hundreds of kilometers Pan2 ; time1 ; time2 ; time3 ; time4  and
in teleportation using real-world fiber networks time5 ; time6 . In 2005,
Barreiro _et al._ experimentally demonstrated the generation of
hyperentanglement in polarization, spatial-mode and time-energy DOFs of photon
systems using pairs of photons produced in spontaneous parametric down-
conversion generation5 . In our protocol, we suppose that the entanglement in
all DOFs suffer from channel noise and degrade to mixed states. As the
entanglement in above three DOFs have different noise robustness, after the
photon transmission, the fidelities in three DOFs are naturally different.
After performing our EPP, we can efficiently reduce both the bit-flip error
and phase-flip error rate in polarization DOF by consuming the imperfect
entanglement in the spatial-mode and time-bin DOFs. Moreover, we will prove
that if a purification step fails, there may exist residual entanglement in
the corresponding distilled mixed state. By using the residual entanglement,
we may also increase the fidelity of the polarization entanglement after the
whole purification process.

The paper is organized as follows. In Sec. II, we describe our EPP in a simple
case where the entanglement in spatial-mode and time-bin DOFs only suffer from
a bit-flip error. In Sec. III, we extend our EPP to a general case where both
the entanglement in spatial-mode and time-bin DOFs suffer from both bit-flip
error and phase-flip error. In Sec. IV, we make a discussion. In Sec. V, we
make a conclusion.

##  II Entanglement purification principle

In this section, we propose our long-distance EPP using a hyperentangled
photon pair. Suppose the photon hyperentanglement source S generates a two-
photon hyperentanglement in polarization, spatial-mode, and time-bin DOFs,
which can be described as

$\displaystyle|\Phi^{+}_{p}\rangle|\Phi^{+}_{s}\rangle|\Phi^{+}_{t}\rangle=\frac{1}{\sqrt{2}}(|HH\rangle+|VV\rangle)$
(1) $\displaystyle\otimes$
$\displaystyle\frac{1}{\sqrt{2}}(|a_{1}^{\prime}b_{1}^{\prime}\rangle+|a_{2}^{\prime}b_{2}^{\prime}\rangle)\otimes\frac{1}{\sqrt{2}}(|LL\rangle+|SS\rangle).$

Here, $H$ ($V$) represents the horizontal (vertical) polarization,
$a_{1}^{\prime}$, $a_{2}^{\prime}$, $b_{1}^{\prime}$ and $b_{2}^{\prime}$ are
four different spatial modes, and $L$ ($S$) represents the long (short) time-
bin.

The photon in $a_{1}^{\prime}$ and $a_{2}^{\prime}$ are sent to Alice, while
the photon in $b_{1}^{\prime}$ and $b_{2}^{\prime}$ are sent to Bob. After
long distance transmission, the channel noise may degrade the entanglement in
all DOFs. Here, we suppose that the entanglement in polarization DOF degrade
to a Werner state with the form of

$\displaystyle\rho_{p}$ $\displaystyle=$ $\displaystyle
p_{p}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+\frac{1-p_{p}}{3}(|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|$
(2) $\displaystyle+$
$\displaystyle|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|+|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|),$

where

$\displaystyle|\Phi^{\pm}_{p}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|HH\rangle\pm|VV\rangle),$
$\displaystyle|\Psi^{\pm}_{p}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|HV\rangle\pm|VH\rangle).$ (3)

We notice that the state $|\Phi^{+}_{p}\rangle$ becomes $|\Psi^{+}_{p}\rangle$
when a bit-flip error occurs, $|\Phi^{+}_{p}\rangle$ becomes
$|\Phi^{-}_{p}\rangle$ when a phase-flip error occurs, and
$|\Phi^{+}_{p}\rangle$ becomes $|\Psi^{-}_{p}\rangle$ when bit-flip error and
phase-flip error both occur.

Considering the noise robustness of the entanglement in spatial-mode and time-
bin DOFs are higher than that in the polarization DOF, we first focus on a
simple case where the entanglement in spatial-mode and time-bin DOFs only
suffer from bit-flip error. In this case, the entanglement in both DOFs
degrade to

$\displaystyle\rho_{s}$ $\displaystyle=$ $\displaystyle
p_{s}|\Phi^{+}_{s}\rangle\langle\Phi^{+}_{s}|+(1-p_{s})|\Psi^{+}_{s}\rangle\langle\Psi^{+}_{s}|,$
(4) $\displaystyle\rho_{t}$ $\displaystyle=$ $\displaystyle
p_{t}|\Phi^{+}_{t}\rangle\langle\Phi^{+}_{t}|+(1-p_{t})|\Psi^{+}_{t}\rangle\langle\Psi^{+}_{t}|,$
(5)

where

$\displaystyle|\Phi^{\pm}_{s}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|a_{1}b_{1}\rangle\pm|a_{2}b_{2}\rangle),$
$\displaystyle|\Psi^{\pm}_{s}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|a_{1}b_{2}\rangle\pm|a_{2}b_{1}\rangle),$
$\displaystyle|\Phi^{\pm}_{t}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|LL\rangle\pm|SS\rangle),$
$\displaystyle|\Psi^{\pm}_{t}\rangle$ $\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}(|LS\rangle\pm|SL\rangle).$ (6)

Therefore, the initial state in Eq. (1) degrades to
$\rho_{p}\otimes\rho_{s}\otimes\rho_{t}$. Here, we suppose that all the
fidelity $p_{p}$, $p_{s}$, and $p_{t}$ are higher than $\frac{1}{2}$. The
schematic principle of our EPP is shown in Fig. 1. The protocol includes two
steps. In the first step, Alice and Bob correct the bit-flip error in
polarization DOF by consuming the entanglement in spatial-mode DOF. In the
second step, they correct the phase-flip error in polarization DOF with the
help of the entanglement in time-bin DOF.

Figure 1: The basic principle of our two-step EPP. Suppose a photon pair
hyperentangled in polarization, spatial-mode, and time-bin DOFs suffer from
channel noise, and the entanglement in all DOFs degrade to mixed states. Here,
PBS means polarization beam splitter, which can totally transmit the photon in
$|H\rangle$ and reflect the photon in $|V\rangle$. QWP means the
$\lambda/4$-wave plate, which can make the Hadamard (H) operation in the
polarization DOF. $PC_{l(s)}$ presents the Pockels cell, which can revers the
polarization of a photon with the time-bin L (S). $D_{1}-D_{8}$ are the single
photon detectors.

In the first step, we only use the states in polarization and spatial-mode DOF
and leave the state in time-bin DOF unchanged, so that we first neglect the
state in time-bin DOF and only consider the mixed state as
$\rho_{1}=\rho_{p}\otimes\rho_{s}$ for simplicity. There are totally eight
possible cases. The photon system may be in
$|\Phi^{+}_{p}\rangle|\Phi^{+}_{s}\rangle$ with the probability of
$p_{p}p_{s}$, while it may be in $|\Phi^{+}_{p}\rangle|\Psi^{+}_{s}\rangle$
with the probability of $p_{p}(1-p_{s})$. Meanwhile, the photon system may be
in $|\Psi^{+}_{p}\rangle|\Phi^{+}_{s}\rangle$,
$|\Phi^{-}_{p}\rangle|\Phi^{+}_{s}\rangle$, or
$|\Psi^{-}_{p}\rangle|\Phi^{+}_{s}\rangle$ with the equal probability of
$\frac{(1-p_{p})p_{s}}{3}$, and it may be in the state
$|\Psi^{+}_{p}\rangle|\Psi^{+}_{s}\rangle$,
$|\Phi^{-}_{p}\rangle|\Psi^{+}_{s}\rangle$, or
$|\Psi^{-}_{p}\rangle|\Psi^{+}_{s}\rangle$ with the probability of
$\frac{(1-p_{p})(1-p_{s})}{3}$.

Alice and Bob pass the photons in $a_{1}$ and $a_{2}$, $b_{1}$ and $b_{2}$
spatial modes through two polarization beam splitters (PBSs), which can
totally transmit the photon in $|H\rangle$ and reflect the photon in
$|V\rangle$. If the initial photon state is
$|\Phi^{\pm}_{p}\rangle|\Phi^{+}_{s}\rangle$, after the PBS, the state will
evolve to

$\displaystyle|\Phi^{\pm}_{p}\rangle|\Phi^{+}_{s}\rangle=\frac{1}{\sqrt{2}}(|HH\rangle\pm|VV\rangle)\otimes\frac{1}{\sqrt{2}}(|a_{1}b_{1}\rangle+|a_{2}b_{2}\rangle)$
(7) $\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HH\rangle\pm|VV\rangle)\otimes\frac{1}{\sqrt{2}}(|a_{3}b_{3}\rangle+|a_{4}b_{4}\rangle).$

When the initial state is $|\Psi^{\pm}_{p}\rangle|\Psi^{+}_{s}\rangle$, it
will evolve to

$\displaystyle|\Psi^{\pm}_{p}\rangle|\Psi^{+}_{s}\rangle=\frac{1}{\sqrt{2}}(|HV\rangle\pm|VH\rangle)\otimes\frac{1}{\sqrt{2}}(|a_{1}b_{2}\rangle+|a_{2}b_{1}\rangle)$
(8) $\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HV\rangle\pm|VH\rangle)\otimes\frac{1}{\sqrt{2}}(|a_{3}b_{3}\rangle+|a_{4}b_{4}\rangle).$

All the four above states make the spatial modes $a_{3}b_{3}$ or $a_{4}b_{4}$
each have one photon. In these cases, the first step is successful. On the
other hand, if the initial state is one of the other four cases, say,
$|\Phi^{\pm}_{p}\rangle|\Psi^{+}_{s}\rangle$ and
$|\Psi^{\pm}_{p}\rangle|\Phi^{+}_{s}\rangle$, after the PBSs, we can obtain
the spatial-modes $a_{3}b_{4}$ or $a_{4}b_{3}$ each has one photon and the
first step fails.

As a result, when the first step is successful, we can distill a new mixed
state as

$\displaystyle\rho_{1p}$ $\displaystyle=$ $\displaystyle
F_{1}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F_{2}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|+F_{3}(|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|$
(9) $\displaystyle+$ $\displaystyle|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|),$

in the spatial modes $a_{3}b_{3}$ or $a_{4}b_{4}$ with the success probability
of

$\displaystyle P_{1}$ $\displaystyle=$ $\displaystyle
p_{p}p_{s}+\frac{1-p_{p}}{3}[p_{s}+2(1-p_{s})]$ (10) $\displaystyle=$
$\displaystyle\frac{1}{3}(4p_{p}p_{s}-p_{s}-2p_{p}+2).$

The four coefficients in Eq. (9) can be written as

$\displaystyle F_{1}$ $\displaystyle=$
$\displaystyle\frac{p_{p}p_{s}}{P_{1}}=\frac{3p_{p}p_{s}}{4p_{p}p_{s}-p_{s}-2p_{p}+2},$
$\displaystyle F_{2}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})p_{s}}{3P_{1}}=\frac{(1-p_{p})p_{s}}{4p_{p}p_{s}-p_{s}-2p_{p}+2},$
$\displaystyle F_{3}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})(1-p_{s})}{3P_{1}}=\frac{(1-p_{p})(1-p_{s})}{4p_{p}p_{s}-p_{s}-2p_{p}+2}.$
(11)

It is obvious that when $p_{p}>\frac{1}{2}$ and $p_{s}>\frac{1}{2}$, the rate
of $|\Psi^{\pm}_{p}\rangle$ ($F_{3}$) is smaller than their original rate
$\frac{(1-p_{p})}{3}$. As a result, the first step can reduce the rate of
$|\Psi^{\pm}_{p}\rangle$. Moreover, the reduction of bit-flip error directly
increases the fidelity of $|\Phi^{+}_{p}\rangle$. We can obtain $F_{1}>p_{p}$
and $F_{1}>p_{s}$ when $p_{p}>\frac{1}{2}$ and
$\frac{5p_{p}-2}{4p_{p}-1}>p_{s}>\frac{1}{2}$. However, the first step cannot
deal with the phase-flip error ($|\Phi^{-}_{p}\rangle$) and the rate of
$|\Phi^{-}_{p}\rangle$ is still in a relatively high level. Next, we try to
correct the phase-flip error.

In the second step, we require to consume the entanglement in the time-bin
DOF. After the first step, the whole photon system collapse to
$\rho_{1p}\otimes\rho_{t}$ in $a_{3}b_{3}$ or $a_{4}b_{4}$ modes. We first
consider that the photons are in $a_{3}b_{3}$. Alice and Bob first pass the
photons in $a_{3}b_{3}$ modes through two $\lambda/4$-wave plates (QWPs),
respectively. The QWP performs a Hadamard (H) operation in the polarization
DOF, which makes $|H\rangle\rightarrow\frac{1}{\sqrt{2}}(|H\rangle+|V\rangle)$
and $|V\rangle\rightarrow\frac{1}{\sqrt{2}}(|H\rangle-|V\rangle)$. After the H
operation, $|\Phi^{-}_{p}\rangle\leftrightarrow|\Psi^{+}_{p}\rangle$, while
$|\Phi^{+}_{p}\rangle$ and $|\Psi^{-}_{p}\rangle$ keep unchanged. In this way,
they can transform $\rho_{1p}$ to

$\displaystyle\rho_{2p}$ $\displaystyle=$ $\displaystyle
F_{1}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F_{2}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+F_{3}(|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(12) $\displaystyle+$ $\displaystyle|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|)$

in the spatial modes $a_{5}b_{5}$. The whole photon system
$\rho_{2p}\otimes\rho_{t}$ can be described as follows. With probability of
$F_{1}p_{t}$ and $F_{1}(1-p_{t})$ the photon pair is in
$|\Phi^{+}_{p}\rangle|\Phi^{+}_{t}\rangle$ and
$|\Phi^{+}_{p}\rangle|\Psi^{+}_{t}\rangle$, respectively. With a probability
of $F_{2}p_{t}$ and $F_{2}(1-p_{t})$, it is in
$|\Psi^{+}_{p}\rangle|\Phi^{+}_{t}\rangle$ and
$|\Psi^{+}_{p}\rangle|\Psi^{+}_{t}\rangle$, respectively. On the other hand,
the whole system is in $|\Phi^{-}_{p}\rangle|\Phi^{+}_{t}\rangle$ or
$|\Psi^{-}_{p}\rangle|\Phi^{+}_{t}\rangle$ with an equal probability of
$F_{3}p_{t}$, and in $|\Phi^{-}_{p}\rangle|\Psi^{+}_{t}\rangle$ or
$|\Psi^{-}_{p}\rangle|\Psi^{+}_{t}\rangle$ with an equal probability of
$F_{3}(1-p_{t})$.

Suppose that the photon pair is in
$|\Phi^{+}_{p}\rangle_{a_{5}b_{5}}|\Phi^{+}_{t}\rangle$. As shown in Fig. 1,
Alice (Bob) passes the photon in $a_{5}$ $(b_{5})$ through a Pockels cell
($PC_{S}$), which can flip the polarization feature of the incoming photon
under the temporal mode $S$. After the $PC_{s}$, Alice (Bob) passes the photon
through a PBS, which makes the photon in $|H\rangle$ be in $a_{7}$ $(b_{7})$
and enter a $PC_{S}$ and the photon in $|V\rangle$ be in $a_{8}$ $(b_{8})$ and
enter a $PC_{L}$. As a result, the states
$|\Phi^{\pm}_{p}\rangle|\Phi^{+}_{t}\rangle$ will finally evolve to

$\displaystyle|\Phi^{\pm}_{p}\rangle_{a_{3}b_{3}}|\Phi^{+}_{t}\rangle$ (13)
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{2}(|H^{L}H^{L}\rangle_{a_{9}b_{9}}+|V^{S}V^{S}\rangle_{a_{10}b_{10}}$
$\displaystyle\pm$
$\displaystyle|H^{L}H^{L}\rangle_{a_{10}b_{10}}\pm|V^{S}V^{S}\rangle_{a_{9}b_{9}}).$

Then, with the help of two PBSs, Alice and Bob can make the photon in
$|H\rangle$ pass through the short (S) arm and photon in $|V\rangle$ pass
through the long (L) arm. By precisely controlling the length of long and
short arms, they can adjust the time-bin feature of the photons in $|H\rangle$
and $|V\rangle$ to be the same. In this way, we can neglect the time-bin
features of the photons, and the state in Eq. (13) evolves to

$\displaystyle|\Phi^{\pm}_{p}\rangle_{a_{3}b_{3}}|\Phi^{+}_{t}\rangle$ (14)
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HH\rangle\pm|VV\rangle)\otimes\frac{1}{\sqrt{2}}(|d_{2}d_{6}\rangle\pm|d_{1}d_{5}\rangle),$

and will be detected by the single photon detector $D_{2}D_{6}$ or
$D_{1}D_{5}$. In this case, the second purification step is successful. The
polarization feature of the photon pair remains to be
$|\Phi^{\pm}_{p}\rangle$.

If the initial state is $|\Psi^{\pm}_{p}\rangle|\Psi^{+}_{t}\rangle$, after
the above operations, it will evolve to

$\displaystyle|\Psi^{\pm}_{p}\rangle|\Psi^{+}_{t}\rangle$ (15)
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HV\rangle\pm|VH\rangle)\otimes\frac{1}{\sqrt{2}}(|d_{2}d_{6}\rangle\pm|d_{1}d_{5}\rangle),$

which will also lead to the successful detection results. The state in Eq.
(15) will finally collapse to $|\Psi^{\pm}_{p}\rangle$.

If the initial state is $|\Phi^{\pm}_{p}\rangle|\Psi^{+}_{t}\rangle$ or
$|\Psi^{\pm}_{p}\rangle|\Phi^{+}_{t}\rangle$, after the above operations,
Alice and Bob would never obtain the successful measurement results. In
detail, after above operations, we can obtain

$\displaystyle|\Phi^{\pm}_{p}\rangle|\Psi^{+}_{t}\rangle$ (16)
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HV\rangle\pm|VH\rangle)\otimes\frac{1}{\sqrt{2}}(|d_{2}d_{5}\rangle\pm|d_{1}d_{6}\rangle),$
$\displaystyle|\Psi^{\pm}_{p}\rangle|\Phi^{+}_{t}\rangle$
$\displaystyle\rightarrow$
$\displaystyle\frac{1}{\sqrt{2}}(|HH\rangle\pm|VV\rangle)\otimes\frac{1}{\sqrt{2}}(|d_{2}d_{5}\rangle\pm|d_{1}d_{6}\rangle),$

which makes the single photon detectors $D_{1}D_{6}$ or $D_{2}D_{5}$ each
register a single photon. In this case, the second purification step fails.

On the other hand, if the photon state is in $a_{4}b_{4}$ modes, we can obtain
when the photon detectors $D_{3}D_{7}$ or $D_{4}D_{8}$ each register one
photon, the second purification step is successful.

Therefore, when the second purification step is successful, we can distill a
new mixed state in polarization DOF as

$\displaystyle\rho_{3p}$ $\displaystyle=$ $\displaystyle
F^{\prime}_{1}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F^{\prime}_{2}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(17) $\displaystyle+$ $\displaystyle
F^{\prime}_{3}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+F^{\prime}_{4}|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|,$

with a success probability of

$\displaystyle P_{2}$ $\displaystyle=$
$\displaystyle(F_{1}+F_{3})p_{t}+(F_{2}+F_{3})(1-p_{t})$ (18) $\displaystyle=$
$\displaystyle\frac{1-p_{p}-p_{s}p_{t}+4p_{p}p_{s}p_{t}}{2-2p_{p}-p_{s}+4p_{p}p_{s}}.$

The four coefficients in Eq. (17) can be written as

$\displaystyle F^{\prime}_{1}$ $\displaystyle=$
$\displaystyle\frac{F_{1}p_{t}}{P_{2}}=\frac{3p_{p}p_{s}p_{t}}{1-p_{t}p_{s}+p_{p}(4p_{t}p_{s}-1)},$
$\displaystyle F^{\prime}_{2}$ $\displaystyle=$
$\displaystyle\frac{F_{3}p_{t}}{P_{2}}=\frac{(1-p_{p})(1-p_{s})p_{t}}{1-p_{t}p_{s}+p_{p}(4p_{t}p_{s}-1)},$
$\displaystyle F^{\prime}_{3}$ $\displaystyle=$
$\displaystyle\frac{F_{2}(1-p_{t})}{P_{2}}=\frac{(1-p_{p})(1-p_{t})p_{s}}{1-p_{t}p_{s}+p_{p}(4p_{t}p_{s}-1)},$
$\displaystyle F^{\prime}_{4}$ $\displaystyle=$
$\displaystyle\frac{F_{3}(1-p_{t})}{P_{2}}=\frac{(1-p_{p})(1-p_{s})(1-p_{t})}{1-p_{t}p_{s}+p_{p}(4p_{t}p_{s}-1)}.$
(19)

Similarly as the first step, the second step can reduce the rate of
$|\Psi^{\pm}_{p}\rangle$ ($F^{\prime}_{3}<F_{2}$ and $F^{\prime}_{4}<F_{3}$).
It can be calculated that $F^{\prime}_{1}>F_{1}$ and $F^{\prime}_{1}>p_{t}$
when $\frac{3p_{p}p_{s}}{+}p_{p}-1{p_{s}(4p_{p}-1)}>p_{t}>\frac{1}{2}$.
Comparing with original mixed state $\rho_{p}$ in Eq. (2), after two steps of
purification, the rates of $|\Psi^{\pm}\rangle$ and $|\Phi^{-}\rangle$ can be
all reduced, so that the fidelity of $|\Phi^{+}_{p}\rangle$ can be efficiently
increased.

##  III General entanglement purification

In this section, we consider a general case that after the long-distance
transmission in noisy channel, the entanglement in the spatial-mode and time-
bin DOFs also degrade to Werner states. In this way, the mixed states in above
two DOFs can be written as

$\displaystyle\rho_{sn}$ $\displaystyle=$ $\displaystyle
p_{s}|\Phi^{+}_{s}\rangle\langle\Phi^{+}_{s}|+\frac{1-p_{s}}{3}(|\Psi^{+}_{s}\rangle\langle\Psi^{+}_{s}|$
$\displaystyle+$
$\displaystyle|\Phi^{-}_{s}\rangle\langle\Phi^{-}_{s}|+|\Psi^{-}_{s}\rangle\langle\Psi^{-}_{s}|),$
$\displaystyle\rho_{tn}$ $\displaystyle=$ $\displaystyle
p_{t}|\Phi^{+}_{t}\rangle\langle\Phi^{+}_{t}|+\frac{1-p_{t}}{3}(|\Psi^{+}_{t}\rangle\langle\Psi^{+}_{t}|$
(20) $\displaystyle+$
$\displaystyle|\Phi^{-}_{t}\rangle\langle\Phi^{-}_{t}|+|\Psi^{-}_{t}\rangle\langle\Psi^{-}_{t}|).$

In Eq. (2) and Eq. (20), we also suppose that $p_{p(t,s)}>\frac{1}{2}$.

In the first step, we only consider $\rho_{p}\otimes\rho_{sn}$, which has 16
possible cases, say $|\Phi^{\pm}_{p}\rangle|\Phi^{\pm}_{s}\rangle$,
$|\Phi^{\pm}_{p}\rangle|\Psi^{\pm}_{s}\rangle$,
$|\Psi^{\pm}_{p}\rangle|\Phi^{\pm}_{s}\rangle$, and
$|\Psi^{\pm}_{p}\rangle|\Psi^{\pm}_{s}\rangle$. By passing the photons in
$a_{1}a_{2}$ and $b_{1}b_{2}$ modes through the PBSs, we also select the items
which make the spatial modes $a_{3}b_{3}$ or $a_{4}b_{4}$ each have one
photon. All the 8 initial states
$|\Phi^{\pm}_{p}\rangle|\Phi^{\pm}_{s}\rangle$ and
$|\Psi^{\pm}_{p}\rangle|\Psi^{\pm}_{s}\rangle$ can lead to the successful
cases. As a result, when the first step is successful, the parties can distill
a new mixed state in polarization DOF as

$\displaystyle\rho_{1pn}$ $\displaystyle=$ $\displaystyle
F_{1n}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F_{2n}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(21) $\displaystyle+$ $\displaystyle
F_{3n}(|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|).$

with a probability of

$\displaystyle P_{1n}$ $\displaystyle=$ $\displaystyle
p_{p}p_{s}+\frac{(1-p_{p})(1-p_{s})}{9}$ (22) $\displaystyle+$
$\displaystyle\frac{p_{p}(1-p_{s})+p_{s}(1-p_{p})}{3}+\frac{4(1-p_{p})(1-p_{s})}{9}$
$\displaystyle=$ $\displaystyle\frac{8p_{p}p_{s}-2p_{p}-2p_{s}+5}{9}.$

In $\rho_{1pn}$, the rates of $|\Phi^{\pm}_{p}\rangle$ and
$|\Psi^{\pm}_{p}\rangle$ can be written as

$\displaystyle F_{1n}$ $\displaystyle=$
$\displaystyle\frac{p_{p}p_{s}+\frac{(1-p_{p})(1-p_{s})}{9}}{P_{1n}}$
$\displaystyle=$
$\displaystyle\frac{10p_{p}p_{s}-p_{p}-p_{s}+1}{8p_{p}p_{s}-2p_{p}-2p_{s}+5},$
$\displaystyle F_{2n}$ $\displaystyle=$
$\displaystyle\frac{p_{p}(1-p_{s})+(1-p_{p})p_{s}}{3P_{1n}}$ $\displaystyle=$
$\displaystyle\frac{3p_{p}+3p_{s}-6p_{p}p_{s}}{8p_{p}p_{s}-2p_{p}-2p_{s}+5},$
$\displaystyle F_{3n}$ $\displaystyle=$
$\displaystyle\frac{2(1-p_{p})(1-p_{s})}{9P_{1n}}$ (23) $\displaystyle=$
$\displaystyle\frac{2(1-p_{p})(1-p_{s})}{8p_{p}p_{s}-2p_{p}-2p_{s}+5}.$

Figure 2: The value of $F_{1n}$, $F_{2n}$, and $F_{3n}$ as a function of
$p_{s}$. Here, we control $p_{p}=0.6$ and adjust $p_{s}$ from 0.505 to 1.

In Fig. 2, we show the values of $F_{1n}$, $F_{2n}$, and $F_{3n}$ as a
function of $p_{s}$. Here, we control $p_{p}=0.6$ and adjust $p_{s}$ from
0.505 to 1. It is obvious that both $F_{2n}$ and $F_{3n}$ reduce with the
growth of $p_{s}$, which makes $F_{1n}$ increase with the growth of $p_{s}$.
We also obtain that $F_{3n}<\frac{1-p_{p}}{3}$ when $p_{s}>\frac{1}{2}$, so
that we can reduce the rate of bit-flip error. However, in this general case,
as the rate of $|\Phi^{-}_{p}\rangle$ ($F_{2n}$) may be relatively high, and
we cannot simply obtain $F_{1n}>p_{p}$ or $F_{1n}>p_{s}$ when
$p_{s}>\frac{1}{2}$ and $p_{p}>\frac{1}{2}$. Here, we provide the criterion of
$F_{1n}>p_{p}$ as

$\displaystyle p_{s}>\frac{6p_{p}-2p_{p}^{2}-1}{12p_{p}-8p_{p}^{2}-1},$ (24)

and the criterion of $F_{1n}>p_{s}$ as

$\displaystyle(8p_{p}-2)p_{s}^{2}+6(1-2p_{p})p_{s}+p_{p}-1<0.$ (25)

Figure 3: The minimum threshold of $p_{s}$ corresponding to $F_{1n}>p_{p}$,
and the maximum threshold of $p_{s}$ corresponding to $F_{1n}>p_{s}$ as a
function of $p_{p}$. Here, we control $p_{p}\in[0.505,0.95]$.

Fig. 3 provides the minimum threshold of $p_{s}$ corresponding to
$F_{1n}>p_{p}$, and the maximum threshold of $p_{s}$ corresponding to
$F_{1n}>p_{s}$ under different values of $p_{p}$. It can be found that both
the minimum and maximum thresholds of $p_{s}$ increase with the growth of
$p_{p}$. Combined with Fig. 2 and Fig. 3, we can obtain that a high $p_{s}$
can lead to a small $F_{3n}$ and relatively high $F_{1n}$. However, when the
value of $p_{s}$ is too high, we cannot ensure that $F_{1n}>p_{s}$. In this
way, for satisfying both the criterions in Eq. (24) and Eq. (30), the
practical value of $p_{s}$ should be between two thresholds. On the other
hand, even when $p_{s}$ is relatively high, $F_{2n}$ can be still in a
relatively high level, so that we need to perform the second purification step
to further reduce $F_{2n}$ and increase the fidelity of
$|\Phi^{+}_{p}\rangle$.

In the second purification step, with the help of H operation, we can
transform $\rho_{1pn}$ to $\rho_{2pn}$ with the form of

$\displaystyle\rho_{2pn}$ $\displaystyle=$ $\displaystyle
F_{1n}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F_{3n}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(26) $\displaystyle+$ $\displaystyle
F_{2n}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+F_{3n}|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|,$

and $F_{2n}$ transforms to the rate of $|\Psi^{+}_{p}\rangle$. In this way,
the whole photon system is $\rho_{2pn}\otimes\rho_{tn}$, which also has 16
possible cases. Alice and Bob pass the photons in $a_{3}b_{3}$ and
$a_{4}b_{4}$ modes through the purification units. When the detection result
is $D_{2}D_{6}$, $D_{1}D_{5}$, $D_{3}D_{7}$ or $D_{4}D_{8}$ each registering
one photon, the second purification step will be successful. According to the
description in Sec. II, all the states
$|\Phi^{\pm}_{p}\rangle|\Phi^{\pm}_{t}\rangle$ and
$|\Psi^{\pm}_{p}\rangle|\Psi^{\pm}_{t}\rangle$ can lead to above successful
detection. In this way, the success probability of the second step is

$\displaystyle P_{2n}$ $\displaystyle=$ $\displaystyle
F_{1n}p_{t}+F_{1n}\frac{1-p_{t}}{3}+F_{3n}p_{t}$ $\displaystyle+$
$\displaystyle 3F_{3n}\frac{1-p_{t}}{3}+2F_{2n}\frac{1-p_{t}}{3}$
$\displaystyle=$
$\displaystyle\frac{7-p_{s}+p_{p}(4p_{s}-1)+2p_{t}(4p_{p}-1)(4p_{s}-1)}{3(8p_{p}p_{s}-2p_{p}-2p_{s}+5)}.$

When the successful detection is obtained, we can distill a new mixed state as

$\displaystyle\rho_{3pn}$ $\displaystyle=$ $\displaystyle
F^{\prime}_{1n}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+F^{\prime}_{2n}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(28) $\displaystyle+$ $\displaystyle
F^{\prime}_{3n}(|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|),$

where

$\displaystyle F^{\prime}_{1n}$ $\displaystyle=$
$\displaystyle\frac{F_{1n}p_{t}+F_{3n}\frac{1-p_{t}}{3}}{P_{2n}}$
$\displaystyle=$
$\displaystyle\frac{2(1-p_{p})(1-p_{s})+p_{t}(1-p_{s}-p_{p}+28p_{p}p_{s})}{7-p_{s}-p_{p}+4p_{p}p_{s}+2p_{t}(4p_{p}-1)(4p_{s}-1)},$
$\displaystyle F^{\prime}_{2n}$ $\displaystyle=$
$\displaystyle\frac{F_{1n}\frac{1-p_{t}}{3}+F_{3n}p_{t}}{P_{2n}}$
$\displaystyle=$
$\displaystyle\frac{p_{s}+p_{p}-10p_{p}p_{s}-1+p_{t}(5p_{s}+5p_{p}+4p_{p}p_{s}-5)}{7-p_{s}-p_{p}+4p_{p}p_{s}+2p_{t}(4p_{p}-1)(4p_{s}-1)},$
$\displaystyle F^{\prime}_{3n}$ $\displaystyle=$
$\displaystyle\frac{(F_{2n}+F_{3n})\frac{1-p_{t}}{3}}{P_{2n}}$ (29)
$\displaystyle=$
$\displaystyle\frac{(1-p_{t})(p_{s}+p_{p}+2-4p_{p}p_{s})}{7-p_{s}-p_{p}+4p_{p}p_{s}+2p_{t}(4p_{p}-1)(4p_{s}-1)}.$

Figure 4: The value of $F^{\prime}_{1n}$, $F^{\prime}_{2n}$, and
$F^{\prime}_{3n}$ as a function of $p_{t}$. Here, we control $p_{p}=0.6$ and
$p_{s}=0.8$, and adjust $p_{t}$ from 0.505 to 1.

In Fig. 4, we control $p_{p}=0.6$ and $p_{s}=0.8$ (In this case, we can obtain
$F_{1n}\approx 0.7285$), and show the values of $F^{\prime}_{1n}$,
$F^{\prime}_{2n}$, and $F^{\prime}_{3n}$ as a function of $p_{t}$. It can be
found that both $F^{\prime}_{2n}$ and $F^{\prime}_{3n}$ reduce with the growth
of $p_{t}$, which makes $F^{\prime}_{1n}$ increase. The higher value of
$p_{t}$ leads to higher $F^{\prime}_{1n}$ and lower $F^{\prime}_{2n}$ and
$F^{\prime}_{3n}$. It is important to compare $F^{\prime}_{1n}$ with $F_{1n}$
and $p_{t}$. We can also calculate the criterion for $F^{\prime}_{1n}>F_{1n}$
as

$\displaystyle\frac{3(p_{t}-\frac{1}{2})}{1-p_{t}}>\frac{(F_{1n}-\frac{1}{2})(F_{1n}+F_{3n})}{F_{1n}[1-(F_{1n}+F_{3n})]}.$
(30)

and the criterion for $F^{\prime}_{1n}>p_{t}$ as

$\displaystyle
p_{t}^{2}(4p_{p}-1)(4p_{s}-1)+3p_{t}(1-4p_{p}p_{s})<(1-p_{p})(1-p_{s}).$ (31)

Figure 5: The minimum threshold of $p_{t}$ corresponding to
$F^{\prime}_{1n}>F_{1n}$, and the maximum threshold of $p_{t}$ corresponding
to $F^{\prime}_{1n}>p_{t}$ as a function of $p_{s}$. Here, we control
$p_{p}=0.65$, and change $p_{s}$ from 0.61 to 0.71.

Similar as the fist step, Eq. (30) and Eq. (31) provide the minimum threshold
and maximum threshold of $p_{t}$. The practical value of $p_{t}$ should be
between the two thresholds. For example, we suppose that $p_{p}=0.65$, where
the suitable value of $p_{s}$ should be in the scale $(0.601,0.715)$. Under
this case, we control the $p_{s}$ in the scale of $[0.61,0.71]$ and provide
the minimum value and maximal value of $p_{t}$ altered with the value of
$p_{s}$ in Fig. 5.

##  IV Discussion

In the paper, we demonstrate an efficient and simple two-step EPP assisted
with hyperentanglement. This EPP requires only one copy of photon pair
hyperentangled in polarization, spatial-mode, and time-bin DOFs. We consider a
general degradation model that the entanglement in all DOFs suffer from
channel noise. By consuming the imperfect entanglement in spatial-mode and
time-bin DOFs, we can reduce both the bit-flip error and phase-flip error in
polarization DOF and increase the fidelity of the target polarization state.
Our two-step EPP has some attractive advantages. First, comparing with
previous recurrence EPPs which require two or more copies of low-quality
entangled pairs, our EPP uses the spatial and time-bin information to complete
the measurement pointer, which avoids consuming an entangled photon copy. In
this way, our EPP protocol effectively reduces consumption of entanglement
pairs, especially in purification consisting of many rounds. Second, using
only one pair of hyperentangled state also reduces the experimental
difficulty, for it is hard to generate two pairs of hyperentangled states
simultaneously. Third, all the devices in our EPP are available under current
experimental condition, so that our EPP is feasible for experiment.

Figure 6: The value of $LgR$ as a function of the photon distribution length.
We set $\eta_{d}=0.9$ and $\eta_{c}=0.95$ L , and consider the low initial
fidelity case ($p_{p}=0.52$, $p_{s}=0.56$, $p_{t}=0.60$) and high initial
fidelity case ($p_{p}=0.8$, $p_{s}=0.82$, $p_{t}=0.85$), respectively.

It is important to compare the purification efficiency of our two-step EPP
with previous recurrence EPPs Pan1  in linear optics in a practical
environment. In previous EPPs, for reducing both the bit-flip and phase-flip
error in polarization DOF, four pairs of identical low-quality mixed states
should be distributed to Alice and Bob (Suppose that the low quality mixed
states are the Werner states with the form of Eq. (2)). The transmission
efficiency of each photon is $\eta_{t}=e^{-\frac{d}{d_{0}}}$, where $d_{0}$ is
the attenuation length of the channel (25 km for commercial fibre L ) and $d$
is the practical photon transmission distance. They first perform the
purification operation on each two identical pairs to reduce the bit-flip
error. Only when both the purification operations are successful, they perform
the H operation on the distilled two photon pairs and further correct the
phase-flip error. We suppose that $\eta_{d}$ and $\eta_{c}$ are the detection
efficiency of the practical photon detector and the coupling efficiency of a
photon to the photon detector, respectively. The total purification efficiency
of previous EPP Pan1  can be calculated as

$\displaystyle
E_{o}=\frac{1}{4}P_{1t}^{2}P_{2t}\eta_{t}^{8}\eta_{d}^{8}\eta_{c}^{8}.$ (32)

Here, $P_{1t}$ and $P_{2t}$ represent the success probability of the first and
second purification rounds, respectively, which can be calculated as

$\displaystyle P_{1t}$ $\displaystyle=$
$\displaystyle\frac{1}{2}[p_{p}^{2}+\frac{2p_{p}(1-p_{p})}{3}+\frac{5(1-p_{p})^{2}}{9}],$
$\displaystyle P_{2t}$ $\displaystyle=$
$\displaystyle\frac{1}{8P_{1t}^{2}}\\{[p_{p}^{2}+\frac{(1-p_{p})^{2}}{9}]^{2}+\frac{8}{81}(1-p_{p})^{4}$
(33) $\displaystyle+$
$\displaystyle\frac{4}{9}[p_{p}^{2}+\frac{(1-p_{p})^{2}}{9}](1-p_{p})^{2}+\frac{4}{9}p_{p}^{2}(1-p_{p})^{2}$
$\displaystyle+$ $\displaystyle\frac{8}{27}p_{p}(1-p_{p})^{3}\\}.$

On the other hand, according to above description, the total purification
efficiency of our two-step EPP is

$\displaystyle E_{n}=P_{1n}P_{2n}\eta_{t}^{2}\eta_{d}^{2}\eta_{c}^{2}.$ (34)

In this way, the ratio of $E_{n}$ and $E_{o}$ can be defined as

$\displaystyle
R=\frac{E_{n}}{E_{o}}=\frac{4P_{1n}P_{2n}}{P_{1t}^{2}P_{2t}\eta_{t}^{6}\eta_{d}^{6}\eta_{c}^{6}}$
(35)

Fig. 6 shows the value of $LgR$ as a function of the photon transmission
length $d$. Here, we set $d_{0}=25$ $km$, $\eta_{d}=0.9$ and $\eta_{c}=0.95$ L
, and change the distance $d$ from 0 to 100 $km$. Here, we select the low
initial fidelity case ($p_{p}=0.52$, $p_{s}=0.56$, $p_{t}=0.60$) and high
initial fidelity case ($p_{p}=0.8$, $p_{s}=0.82$, $p_{t}=0.85$), respectively.
It can be found that the influences from the initial fidelities in three DOFs
on $LgR$ are slight, and $LgR$ increases linearly with the growth of $d$. In
this way, our EPP is extremely useful in the long-distance entanglement
distribution.

Next, we discuss the residual entanglement when the purification steps fail.
Here, we consider the case in Sec. II for simplicity. We first consider the
case that the first purification step fails, but the second step is
successful. When the first step fails, say, the spatial modes $a_{3}b_{4}$ or
$a_{4}b_{3}$ each have a photon, the parties can distill a new mixed state
with the form of

$\displaystyle\rho_{fail1}$ $\displaystyle=$ $\displaystyle
F_{fail1}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+A_{fail1}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(36) $\displaystyle+$ $\displaystyle
B_{fail1}(|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|),$

with the probability of

$\displaystyle P_{fail1}$ $\displaystyle=$ $\displaystyle
p_{p}(1-p_{s})+\frac{(1-p_{p})(1-p_{s})}{3}+\frac{2(1-p_{p})p_{s}}{3}$ (37)
$\displaystyle=$ $\displaystyle\frac{1+p_{s}+2p_{p}-4p_{p}p_{s}}{3}.$

The three coefficients can be calculated as

$\displaystyle F_{fail1}$ $\displaystyle=$
$\displaystyle\frac{p_{p}(1-p_{s})}{P_{fail1}}=\frac{3p_{p}(1-p_{s})}{1+p_{s}+2p_{p}-4p_{p}p_{s}},$
$\displaystyle A_{fail1}$ $\displaystyle=$
$\displaystyle\frac{\frac{(1-p_{p})(1-p_{s})}{3}}{P_{fail1}}=\frac{(1-p_{p})(1-p_{s})}{1+p_{s}+2p_{p}-4p_{p}p_{s}},$
$\displaystyle B_{fail1}$ $\displaystyle=$
$\displaystyle\frac{\frac{(1-p_{p})p_{s}}{3}}{P_{fail1}}=\frac{(1-p_{p})p_{s}}{1+p_{s}+2p_{p}-4p_{p}p_{s}}.$
(38)

In order to make the distilled mixed state have residual entanglement, we
require $F_{fail1}>\frac{1}{2}$. This requirement can be satisfied when
$p_{s}<\frac{4p_{p}-1}{1+2p_{p}}$. Under this case, when the second
purification step is successful, say, the photon detectors $D_{2}D_{7}$,
$D_{1}D_{8}$, $D_{3}D_{6}$, or $D_{4}D_{5}$ each registering a single photon,
the parties can obtain a new mixed state as

$\displaystyle\rho^{\prime}_{fail1}$ $\displaystyle=$ $\displaystyle
F^{\prime}_{fail1}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+A^{\prime}_{fail1}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(39) $\displaystyle+$ $\displaystyle
B^{\prime}_{fail1}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+C^{\prime}_{fail1}|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|,$

with the probability of

$\displaystyle P^{\prime}_{fail1}$ $\displaystyle=$
$\displaystyle(F_{fail1}+B_{fail1})p_{t}+(A_{fail1}+B_{fail1})(1-p_{t})$ (40)
$\displaystyle=$
$\displaystyle\frac{1-p_{p}+p_{t}(4p_{p}-1)(1-p_{s})}{1+p_{s}-2p_{p}(2p_{s}-1)}.$

The coefficients in Eq. (39) can be written as

$\displaystyle F^{\prime}_{fail1}$ $\displaystyle=$
$\displaystyle\frac{F_{fail1}p_{t}}{P^{\prime}_{fail1}}$ $\displaystyle=$
$\displaystyle\frac{3p_{t}p_{p}(1-p_{s})}{1-p_{p}+p_{t}(4p_{p}-1)(1-p_{s})},$
$\displaystyle A^{\prime}_{fail1}$ $\displaystyle=$
$\displaystyle\frac{B_{fail1}p_{t}}{P^{\prime}_{fail1}}$ $\displaystyle=$
$\displaystyle\frac{p_{t}p_{s}(1-p_{p})}{1-p_{p}+p_{t}(4p_{p}-1)(1-p_{s})},$
$\displaystyle B^{\prime}_{fail1}$ $\displaystyle=$
$\displaystyle\frac{A_{fail1}(1-p_{t})}{P^{\prime}_{fail1}}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{t})(1-p_{s})(1-p_{p})}{1-p_{p}+p_{t}(4p_{p}-1)(1-p_{s})},$
$\displaystyle C^{\prime}_{fail1}$ $\displaystyle=$
$\displaystyle\frac{B_{fail1}(1-p_{t})}{P^{\prime}_{fail1}}$ (41)
$\displaystyle=$
$\displaystyle\frac{p_{s}(1-p_{t})(1-p_{p})}{1-p_{p}+p_{t}(4p_{p}-1)(1-p_{s})}.$

Figure 7: The value of $F^{\prime}_{fail}$ as a function of $p_{t}$. Here, we
control $p_{p}=0.65$, so that maximal value of $p_{s}$ for ensuring
$F_{fail1}>\frac{1}{2}$ is 0.70. In this way, we control $p_{s}=$ 0.52, 0.62,
0.68, respectively.

Fig. 7 shows the value of $F^{\prime}_{fail1}$ as a function of $p_{t}$ when
$p_{p}=0.65$. For ensuring $F_{fail1}>\frac{1}{2}$, we require $p_{s}<0.7$. In
this way, we control $p_{s}=$ 0.52, 0.62, 0.68, respectively. It can be found
that $F^{\prime}_{fail1}$ increases with the growth of $p_{t}$, but reduces
with the growth of $p_{s}$. With suitable value of $p_{t}$, we can obtain
$F^{\prime}_{fail1}>p_{p}$ and $F^{\prime}_{fail1}>p_{t}$.

Second, we consider the case that the first purification is successful, but
the second purification fails. After the first step, the parties share a mixed
state as $\rho_{1p}$ in Eq. (9). When the second purification step fails, say,
the photon detectors $D_{1}D_{6}$, $D_{2}D_{5}$, $D_{3}D_{8}$, or $D_{4}D_{7}$
each registering a single photon, they can distill a new mixed state with the
form of

$\displaystyle\rho_{fail2}$ $\displaystyle=$ $\displaystyle
F_{fail2}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+A_{fail2}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(42) $\displaystyle+$ $\displaystyle
B_{fail2}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+C_{fail2}|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|,$

with the probability of

$\displaystyle P_{fail2}$ $\displaystyle=$
$\displaystyle(F_{1}+F_{3})(1-p_{t})+(F_{2}+F_{3})p_{t}$ (43) $\displaystyle=$
$\displaystyle\frac{1-(1-p_{t})p_{s}-p_{p}+4p_{p}p_{s}(1-p_{t})}{2-p_{s}-2p_{p}(1-2p_{s})}.$

The coefficients in Eq. (42) can be written as

$\displaystyle F_{fail2}$ $\displaystyle=$
$\displaystyle\frac{F_{1}(1-p_{t})}{P_{fail2}}$ $\displaystyle=$
$\displaystyle\frac{3(1-p_{t})p_{p}p_{s}}{1-p_{s}+p_{t}p_{s}-p_{p}+4p_{p}p_{s}(1-p_{t})},$
$\displaystyle A_{fail2}$ $\displaystyle=$
$\displaystyle\frac{F_{3}(1-p_{t})}{P_{fail2}}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})(1-p_{s})(1-p_{t})}{1-p_{s}+p_{t}p_{s}-p_{p}+4p_{p}p_{s}(1-p_{t})},$
$\displaystyle B_{fail2}$ $\displaystyle=$
$\displaystyle\frac{F_{2}p_{t}}{P_{fail2}},$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})p_{s}p_{t}}{1-p_{s}+p_{t}p_{s}-p_{p}+4p_{p}p_{s}(1-p_{t})},$
$\displaystyle C_{fail2}$ $\displaystyle=$
$\displaystyle\frac{F_{3}p_{t}}{P_{fail2}},$ (44) $\displaystyle=$
$\displaystyle\frac{(1-p_{p})(1-p_{s})p_{t}}{1-p_{s}+p_{t}p_{s}-p_{p}+4p_{p}p_{s}(1-p_{t})}.$

Figure 8: The value of $F_{fail2}$ as a function of $p_{t}$. Here, we control
$p_{p}=0.65$ and $p_{s}=$ 0.52, 0.62, 0.7, 0.8, respectively, and adjust
$p_{t}$ from 0.51 to 1.

In Fig. 8, we show the value of $F_{fail2}$ as a function of $p_{t}$ by
controlling $p_{p}=0.65$ and $p_{s}=$ 0.52, 0.62, 0.7, 0.8. It can be found
that $F_{fail2}$ increases with the growth of $p_{s}$ but reduces with the
growth of $p_{t}$. In this way, for obtaining $F_{fail2}>p_{p}$, we require
$p_{t}$ to be relatively low. With the growth of $p_{s}$, the maximal values
of $p_{t}$ which make $F_{fail2}>p_{p}$ increase. In detail, when
$p_{p}=0.65$, and $p_{s}=$ 0.52, 0.62, 0.7, 0.8, the maximal values of $p_{t}$
are 0.519, 0.596, 0.642, and 0.687, respectively.

Figure 9: The values of $F_{fail3}$ as a function of $p_{t}$. Here, we control
$p_{p}=0.65$ and $p_{s}=$ 0.52, 0.62, 0.68, respectively, and adjust $p_{t}$
from 0.51 to 1.

Finally, we will discuss the case that both two purification steps fail. This
case corresponds to the photon detector $D_{2}D_{8}$, $D_{1}D_{7}$,
$D_{3}D_{5}$, or $D_{4}D_{6}$ each registering one photon. After the first
purification step, the parties share a new mixed state with the form of
$\rho_{fail1}$ in Eq. (36). Then, when the second purification step fails,
they can finally obtain a new mixed state as

$\displaystyle\rho_{fail3}$ $\displaystyle=$ $\displaystyle
F_{fail3}|\Phi^{+}_{p}\rangle\langle\Phi^{+}_{p}|+A_{fail3}|\Phi^{-}_{p}\rangle\langle\Phi^{-}_{p}|$
(45) $\displaystyle+$ $\displaystyle
B_{fail3}|\Psi^{+}_{p}\rangle\langle\Psi^{+}_{p}|+C_{fail3}|\Psi^{-}_{p}\rangle\langle\Psi^{-}_{p}|,$

with the probability of

$\displaystyle P_{fail3}$ $\displaystyle=$
$\displaystyle(F_{fail1}+B_{fail1})(1-p_{t})+(A_{fail1}+B_{fail1})p_{t},$ (46)
$\displaystyle=$
$\displaystyle\frac{p_{p}(3-4p_{s})-p_{t}(4p_{p}-1)(1-p_{s})+p_{s}}{1-2p_{p}(2p_{s}-1)+p_{s}}.$

The four coefficients can be calculated as

$\displaystyle F_{fail3}$ $\displaystyle=$
$\displaystyle\frac{F_{fail1}(1-p_{t})}{P_{fail3}}$ $\displaystyle=$
$\displaystyle\frac{3p_{p}(1-p_{t})(1-p_{s})}{p_{p}(3-4p_{s})-p_{t}(4p_{p}-1)(1-p_{s})+p_{s}},$
$\displaystyle A_{fail3}$ $\displaystyle=$
$\displaystyle\frac{B_{fail1}(1-p_{t})}{P_{fail3}}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})(1-p_{t})p_{s}}{p_{p}(3-4p_{s})-p_{t}(4p_{p}-1)(1-p_{s})+p_{s}},$
$\displaystyle B_{fail3}$ $\displaystyle=$
$\displaystyle\frac{A_{fail1}p_{t}}{P_{fail3}}$ $\displaystyle=$
$\displaystyle\frac{(1-p_{p})(1-p_{s})p_{t}}{p_{p}(3-4p_{s})-p_{t}(4p_{p}-1)(1-p_{s})+p_{s}},$
$\displaystyle C_{fail3}$ $\displaystyle=$
$\displaystyle\frac{B_{fail1}p_{t}}{P_{fail3}}$ (47) $\displaystyle=$
$\displaystyle\frac{(1-p_{p})p_{s}p_{t}}{p_{p}(3-4p_{s})-p_{t}(4p_{p}-1)(1-p_{s})+p_{s}}.$

In Fig. 9, we show the value of $F_{fail3}$ as a function of $p_{t}$ with
$p_{p}=0.65$. For ensuring the existence of residual entanglement after the
first purification step, we require $p_{s}<0.7$. In this way, we control
$p_{s}=$ 0.52, 0.62, and 0.68, respectively. It can be found that $F_{fail3}$
reduces with the growth of $p_{s}$ and $p_{t}$. $F_{fail3}$ is lower than
$p_{p}$ under arbitrary value of $p_{s}$ and $p_{t}$. However, with relatively
low $p_{s}$ and $p_{t}$, there may still exist residual entanglement
($F_{fail3}>\frac{1}{2}$) in $\rho_{fail3}$. For example, for ensuring the
existence of residual entanglement in $\rho_{fail3}$, we can calculate the
maximal values of $p_{t}$ to be 0.682, 0.599, and 0.523, corresponding to
$p_{s}=$ 0.52, 0.62, and 0.68, respectively.

From above discussion, there may residual entanglement exist when the
purification steps fail. When only one purification step fails, the parties
may still distill high-quality entanglement with suitable $p_{s}$ and $p_{t}$
by using of the residual entanglement. Even if the parties can not directly
obtain high-quality polarized mixed state, they can still reuse the residual
entanglement to distill high-quality entanglement in the next purification
round. The existence of residual entanglement provides us a possibility to
increase the fidelity of polarization entanglement, thus increase the yield of
our EPP.

Finally, it is interesting to compare out two-step EPP with the deterministic
EPPs (DEPPs), which also adopt the hyperentanglement to realize the
purification shenghyper1 ; shenghyper2 . The DEPPs require one pair of
hyperentangled state, i.e., polarization-spatial-mode and polarization-
spatial-mode-frequency hyperentanglement, respectively. Actually, the DEPPs
can completely transform the entanglement in the other DOF to the target DOF,
and they do not require the initial target DOF to be entangled. The upper
bound of the fidelity in the target DOF is the initial fidelity of the
consumed entanglement. On the other hand, our current two-step EPP belongs to
recurrence EPP. In our two-step EPP, we suppose that the initial fidelities in
three DOFs are larger than $\frac{1}{2}$. After two purification steps, the
fidelity of the target polarization state can be higher than $p_{p}$, $p_{s}$,
and even $p_{t}$. Actually, in the first purification step, if
$p_{p}<\frac{1}{2}$, we can obtain the fidelity $p_{p}<F_{1n}<p_{s}$. Under
this case, when the $p_{p}$ and $p_{s}$ satisfy $p_{p}p_{s}>\frac{1}{4}$, we
can obtain $F_{1n}>\frac{1}{2}$, say, the distilled new mixed state in
polarization DOF has entanglement. In the second purification step, the
fidelity of the target polarization DOF can be increased to be higher than
$F_{1n}$ and even $p_{t}$. If $p_{p}$ is so low that $p_{p}p_{s}>\frac{1}{4}$
can not be satisfied, our two-step EPP can not work. Based on above
comparison, if the initial fidelity in the polarization DOF is relatively
high, the current two-step EPP may be more advantageous, and while if that of
the polarization DOF is low, the DEPP may be more advantageous.

##  V Conclusion

In conclusion, we present an efficient two-step recurrence EPP for purifying
the entanglement in polarization DOF. In the protocol, we only require one
copy of two-photon pair, which is hyperentangled in polarization, spatial-
mode, and time-bin DOFs. We suppose that after the photon transmission, the
entanglement in all DOFs suffer from the channel noise and degrade to mixed
states. As the entanglement in different DOFs have different noisy robustness,
the initial mixed states in three DOFs have different fidelities. In the first
purification step, the bit-flip error in polarization DOF can be reduced by
consuming the imperfect spatial-mode entanglement, while in the second step,
the phase-flip error in polarization DOF can be reduced by consuming the
imperfect time-bin entanglement. As a result, the fidelity of the target
polarization state can be efficiently increased. Our EPP has some attractive
advantages. First, comparing with previous two-step recurrence EPPs, which
require two or more same copies of nonlocal entangled pairs, our EPP largely
reduces the consumption of entanglement pairs. Second, using only one pair of
hyperentangled state also reduces the experimental difficulty, for it is hard
to generate two pairs of hyperentangled states simultaneously. Third, if we
consider the practical photon transmission and detector efficiency, our EPP
has much higher purification efficiency. Forth, all the devices in our EPP are
available under current experimental condition, so that our EPP is feasible
for experiment. Moreover, in traditional two-step recurrent EPP, the parties
can distill a high-quality entanglement only when both two steps are
successful. If any one step fails, there are no residual entanglement in the
distilled mixed state and the distilled photon states have to be discarded.
However, when a purification step of our EPP fails, there may exist residual
entanglement in the distilled mixed state. The existence of residual
entanglement may make the parties distill higher-fidelity polarization
entanglement. Even not, the residual entanglement may be reused in the next
purification round. In this way, the existence of residual entanglement
benefits for further increasing the yield of our EPP. All the above features
make our EPP protocol have potential application in future quantum information
processing field.

## ACKNOWLEDGEMENTS

This work was supported by the National Natural Science Foundation of China
(No. 11974189).

## References

  * (1) C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres and W. K. Wootters, Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
  * (2) D. Bouwmeester, J. W. Pan, K. Mattle, M. Eibl, H. Weinfurter, and A. Zeilinger, Experimental quantum teleportation, Nature 390, 575-579 (1997).
  * (3) X. M. Hu, C. Zhang, C. J. Zhang, B. H. Liu, Y. F. Huang, Y. J. Han, C. F. Li, and G. C. Guo, Experimental certification for nonclassical teleportation, Quan. Engin. 1, e3 (2019).
  * (4) L. M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller, Long-distance quantum communication with atomic ensembles and linear optics, Nature 414, 413 (2001).
  * (5) C. Simon, H. de Riedmatten, M. Afzelius, N. Sangouard, H. Zbinden, and N. Gisin, Quantum repeaters with photon pair sources and multimode memories, Phys. Rev. Lett. 98, 190503 (2007).
  * (6) N. Sangouard, C. Simon, H. de Riedmatten, and N. Gisin, Quantum repeaters based on atomic ensembles and linear optics, Rev. Mod. Phys. 83, 33 (2011).
  * (7) A. K. Ekert, Quantum cryptography based on Bell’s theorem, Phys. Rev. Lett. 67, 661 (1991).
  * (8) M. Hillery, V. Buz̆ek, and A. Berthiaume, Quantum secret sharing, Phys. Rev. A 59, 1829 (1999).
  * (9) G. L. Long and X. S. Liu, Theoretically efficient high-capacity quantum-key-distribution scheme, Phys. Rev. A 65, 032302 (2002).
  * (10) F. G. Deng, G. L. Long, and X. S. Liu, Two-step quantum direct communication protocol using the Einstein- Podolsky-Rosen pair block, Phys. Rev. A 68, 042317 (2003).
  * (11) W. Zhang, D. S. Ding, Y. B. Sheng, L. Zhou, B. S. Shi, and G. C. Guo, Quantum secure direct communication with quantum memory, Phys. Rev. Lett. 118, 220501 (2017).
  * (12) L. Zhou, Y. B. Sheng, and G. L. Long, Device-independent quantum secure direct communication against collective attacks, Sci. Bull. 65, 12-20 (2020).
  * (13) C. H. Bennett, G. Brassard, S. Popescu, et al. Purification of noisy entanglement and faithful teleportation via noisy channels. Phys. Rev. Lett. 76, 722-725 (1996).
  * (14) D. Deutsch, A. Ekert, R. Jozsa, C. Macchiavello, S. Popescu, and A. Sanpera, Quantum privacy amplification and the security of quantum cryptography over noisy channels, Phys. Rev. Lett. 77, 2818-2821 (1996).
  * (15) M. Murao, M. B. Plenio, S. Popescu, V. Vedral, and P. L. Knight, Multiparticle entanglement purification protocols, Phys. Rev. A 57, R4075-R4078 (1998).
  * (16) J. W. Pan, C. Simon, and A. Zellinger, Entanglement purification for quantum communication. Nature (London) 410, 1067 (2001).
  * (17) C. Simon and J. W. Pan, Polarization entanglement purification using spatial entanglement. Phys. Rev. Lett. 89, 257901 (2002).
  * (18) J. W. Pan, S. Gasparoni, R. Ursin, G. Weihs, A. Zeilinger, Experimental entanglement purification of arbitrary unknown states, Nature, 423, 417-422 (2003).
  * (19) W. Dür, H. Aschauer, and H. J. Briegel, Multiparticle entanglement purification for graph states, Phys. Rev. Lett. 91, 107903 (2003).
  * (20) R. Reichle, D. Leibfried, E. Knill, et al. Experimental purification of two-atom entanglement, Nature 443, 838-841 (2006).
  * (21) Y. W. Cheong, S. W. Lee, J. Lee, and H. W. Lee, Entanglement purification for high-dimensional multipartite systems, Phys. Rev. A 76, 042314 (2007).
  * (22) Y. B. Sheng, F. G. Deng, and H. Y. Zhou, Efficient polarization-entanglement purification based on parametric down-conversion sources with cross-kerr nonlinearity, Phys. Rev. A 77, 042308 (2008).
  * (23) Y. B. Sheng and F. G. Deng, Deterministic entanglement purification and complete nonlocal Bell-state analysis with hyperentanglement, Phys. Rev. A 81, 032307 (2010).
  * (24) Y. B. Sheng and F. G. Deng, One-step deterministic polarization-entanglement purification using spatial entanglement, Phys. Rev. A 82, 044305 (2010).
  * (25) Y. B. Sheng, L. Zhou, and G. L. Long, Hybrid entanglement purification for quantum repeaters, Phys. Rev. A 88, 022302 (2013).
  * (26) L. Zhou and Y. B. Sheng, Purification of logic-qubit entanglement, Sci. Rep. 6, 28813 (2016).
  * (27) T. J. Wang, S. C. Mi, and C. Wang, Hyperentanglement purification using imperfect spatial entanglement, Opt. Express 25, 2969 (2017).
  * (28) L. Zhou and Y. B. Sheng, Polarization entanglement purification for concatenated Geenberger-Horne-Zeilinger state, Ann. Phys. 385, 10-35 (2017).
  * (29) H. Zhang, Q. Liu, X. S. Xu, J. Xiong, A. Alsaedi, T. Hayat, and F. G. Deng, Polarization entanglement purification of nonlocal microwave photons based on the cross-kerr effect in circuit qed, Phys. Rev. A 96, 052330 (2017).
  * (30) L. K. Chen, H. L. Yong, and P. Xu et al., Experimental nested purification for a linear optical quantum repeater, Nat. Photon. 11, 695-699 (2017).
  * (31) Kalb, N., et al. Entanglement distillation between solid state quantum network nodes. Science 356, 928-932 (2017).
  * (32) J. Miguel-Ramiro and W. Dür, Efficient entanglement purification protocols for d-level systems, Phys. Rev. A 98, 042309 (2018).
  * (33) F. Rozpeedek, T. Schiet, D. Elkouss, A. C. Doherty, and S. Wehner, Optimizing practical entanglement distillation, Phys. Rev. A 97, 062333 (2018).
  * (34) S. Krastanov, V. V. Albert, and L. Jiang, Optimized entanglement purification, Quantum 3, 123123 (2019).
  * (35) X. D. Wu, L. Zhou, W. Zhong, Y. B. Sheng, Purification of the concatenated Greenberger-Horne- Zeilinger state with linear optics, Quan. Inform. Process. 17, UNSP255 (2018).
  * (36) F. F. Du, Y. T. Liu, Z. R. Shi, Y. X. Liang, J. Tang, and J. Liu, Efficient hyperentanglement purification for three-photon systems with the fidelity-robust quantum gates and hyperentanglement link, Opt. Express 27, 27046 (2019).
  * (37) L. Zhou, S. S. Zhang, W. Zhong, and Y. B. Sheng, Multi-copy nested entanglement purification for quantum repeaters, Ann. Phys. 412, 168042 (2020).
  * (38) L. Zhou, W. Zhong, and Y. B. Sheng, Purification of the residual entanglement, Opt. Express 28, 2291-2301 (2020).
  * (39) X. M. Hu, C. X. Huang, Y. B. Sheng, et al. Long-distance entanglement purification for quantum communication, Phys. Rev. Lett. 126, 010503 (2021).
  * (40) I. Marcikic, H. de Riedmatten, W. Tittel, H. Zbinden, and N. Gisin, Long-distance teleportation of qubits at telecommunication wavelengths, Nature 421, 509 (2003).
  * (41) R. T. Thew, S. Tanzilli, W. Tittel, H. Zbinden, and N. Gisin, Experimental investigation of the robustness of partially entangled qubits over 11 km, Phys. Rev. A 66, 062304 (2002).
  * (42) I. Marcikic, H. de Riedmatten, W. Tittel, H. Zbinden, M. Legré and N. Gisin, Distribution of time-bin entangled qubits over 50 km of optical fiber, Phys. Rev. Lett. 93, 180502 (2004).
  * (43) T. Inagaki, N. Matsuda, O. Tadanaga, and H. Takesue, Entanglement distribution over 300 km of fiber, Opt. Express 21, 23241 (2013).
  * (44) R. Valivarthi, M. G. Puigibert, Q. Zhou, G. H. Aguilar, V. B. Verma, F. Marsili, M. D. Shaw, S. W. Nam, D. Oblak, and W. Tittel, Quantum teleportation across a metropolitan fibre network, Nat. Photon. 10, 676 (2016).
  * (45) Q. C. Sun, Y. L. Mao, S. J. Chen, et al. Quantum teleportation with independent sources and prior entanglement distribution over a network, Nat. Photon. 10, 671 (2016).
  * (46) J. T. Barreiro, N. K.Langford, N. A. Peters, and P.G. Kwiat: Generation of hyperentangled photon pairs. Phys. Rev. Lett. 95, 260501 (2005).
  * (47) W. K. Wootters, Entanglement of formation of an arbitrary state of two qubits, Phys. Rev. Lett. 80, 2245-2248 (1998).
  * (48) C. H. Bennett, H. J. Bernstein, S. Popescu, and S. Benjamin, Concentrating partial entanglement by local operations, Phys. Rev. A 53, 2046-2052 (1996).
  * (49) S. Hill and W. K. Wootters, Entanglement of a pair of quantum bits, Phys. Rev. Lett. 78, 5022-5025 (1997).
  * (50) W. J. Munro, A. M. Stephens, S. J. Devitt, K. A. Harrison, and K. Nemoto, Quantum communication without the necessity of quantum memories, Nat. Photon. 6, 777 (2012).


# Kernel-based function learning in dynamic
and non stationary environments

Alberto Giaretta, Mauro Bisiacco and Gianluigi Pillonetto A. Giaretta is with
the Department of Pathology, University of Cambridge, Cambridge, UK. M.
Bisiacco and G. Pillonetto are with the Department of Information Engineering,
University of Padova, Padova, Italy.
Corresponding author: Gianluigi Pillonetto (giapi@dei.unipd.it).

###### Abstract

One central theme in machine learning is function estimation from sparse and
noisy data. An example is supervised learning where the elements of the
training set are couples, each containing an input location and an output
response. In the last decades, a substantial amount of work has been devoted
to design estimators for the unknown function and to study their convergence
to the optimal predictor, also characterizing the learning rate. These results
typically rely on stationary assumptions where input locations are drawn from
a probability distribution that does not change in time. In this work, we
consider kernel-based ridge regression and derive convergence conditions under
non stationary distributions, addressing also cases where stochastic adaption
may happen infinitely often. This includes the important exploration-
exploitation problems where e.g. a set of agents/robots has to monitor an
environment to reconstruct a sensorial field and their movements rules are
continuosuly updated on the basis of the acquired knowledge on the field
and/or the surrounding environment.

###### Index Terms:

kernel-based regularization, generalization, statistical consistency, learning
rate, non stationary sampling distributions

##  1 Introduction

We consider the problem of reconstructing an unknown function $f$, defined
over a set $X$, from noisy outputs $y_{i}$ collected over input locations
$x_{i}$ [17, 30, 21]. A typical measurements model is

$y_{i}=\mu(x_{i})+\nu_{i},\quad i=1,\ldots,n$ (1)

where the errors $\nu_{i}$ are zero-mean random variables and $\mu$ is also
called the regression function. Given any $x\in X$, it represents the optimal
predictor of future data in the mean squared sense. In supervised learning,
the input locations are also seen as random variables and the couples
$\\{x_{i},y_{i}\\}_{i=1}^{n}$ are realizations from a (typically unknown)
probability distribution. This particular version of the problem is also known
as _nonparametric regression under random design_ in statistical literature
[27].
Many forms of regularization have been studied in the literature for
supervised learning. Examples include spectral regularization methods, like
early stopping and boosting [32, 8, 1, 5], and kernel-based regularization
[27, 22] which will be the focus of this paper. Within this framework, the
function $f$ is assumed to belong to a Reproducing Kernel Hilbert Space (RKHS)
$\mathcal{H}$, a particular Hilbert space associated with positive-definite
kernels [2, 12]. Adopted estimators try to balance data fit and a regularizer
built using the RKHS norm. They assume the form [15]

$\hat{\mu}_{n}=\arg\min_{f\in\mathcal{H}}\
\mathcal{J}(f(x_{1}),f(x_{2}),\ldots,f(x_{n}),\|f\|_{\mathcal{H}})$ (2)

with $J$ monotonically increasing w.r.t. the last argument and
$\|f\|_{\mathcal{H}}$ typically enforces smooth solutions. Such formulation
includes as special cases support vector machines [29, 11, 14] and kernel
ridge regression [15, 27]. In particular, this last instance, known in the
literature also as regularization nework or regularized least squares [23],
will be the focus of this paper. It arises when quadratic losses are used to
measure the discrepancy between the data $y_{i}$ and the predictions
$f(x_{i})$.
Kernel-based estimators (2) have been widely studied in the literature, with
many years of theoretical developments. One central theme is the derivation of
conditions under which $\hat{\mu}_{n}$ converges to the regression function
$f$ as the data set size $n$ grows to infinity. The literature on this subject
is enormous and we cite e.g. [28, 18, 16, 19, 31, 32, 3, 13, 7, 5] where
convergence rates and generalization properties of kernel-based estimates are
obtained.
A common feature of all of the above mentioned works is that the sampling
distribution $p$ of the input locations is assumed time-invariant. Hence, the
input locations $x_{i}$ form a stationary stochastic process. An extension can
be found in [25] where $p$ is replaced with a convergent sequence of
probability measures, so that stationarity of $x_{i}$ holds asymptotically. In
this paper we instead assume that the input locations distribution may vary
freely in time over an arbitrary set $\mathcal{P}$. This point is important in
many engineering applications, e.g. in exploration-exploitation problems and
coverage control where a set of agents has to simultaneously explore the
environment and reconstruct a sensorial field [24, 9, 10, 6, 26]. Note that in
this setting the stochastic mechanism underlying the input locations
establishes how the agents move inside the domain of interest. Hence, it is
convenient to update the movements rules on the basis of the acquired
knowledge. This latter can consist of the current filed estimate, which can
suggest the most interesting areas to monitor, or the agent could also follow
external directives, independent of the field, requiring occasionally to
inspect regions where an event is reported. The time-varying distributions
might be Gaussian whose means and variances change over time on the basis of
such directives.
Under this complex scenario, our aim is to derive conditions that ensure
convergence of kernel-based estimators, in particular regularized least-
squares, to the regression function. This will be obtained through a non
trivial extension of the statistical learning estimates derived in [28]. We
will see that the convex hull $co\mathcal{P}$ of the set $\mathcal{P}$ plays a
special role. In fact, the learning rate is related to smoothness of the
unknown function and absolute summability of some covariances computed over
$co\mathcal{P}$.

The paper is organized as follows. In Section 2, we first recall the specific
form of the kernel-based estimator studied in the paper and state our
assumptions on the unknown function and the data generator. In Section 3, the
main convergence result is reported while Section 4 contains a numerical
experiment. Conclusions then end the paper.

##  2 Preliminaries

###  2.1 Regularized least squares in RKHS

Let $\mathcal{H}$ be the RKHS induced by the Mercer kernel $K:X\times
X\rightarrow{\mathbb{R}}$, with norm denoted by $\|\cdot\|_{\mathcal{H}}$. We
consider kernel ridge regression given by the following specific form of the
estimator (2):

$\hat{\mu}_{t}=\arg\min_{f\in\mathcal{H}}J_{t}(f)\\\ $ (3)

where

$J_{t}(f)=\frac{\sum_{i=1}^{t}\left(y_{i}-f(x_{i})\right)^{2}}{t}+\gamma\|f\|_{\mathcal{H}}^{2}$
(4)

where $\gamma$ is the so called regularization parameter which trades-off
adherence to experimental data and the RKHS norm which promotes smooth
solutions. Differently from (2), we now use $t$ in place of $n$ to denote the
data set size to stress that a dynamic environment is now considered. In fact,
the notation $t$ also indicates the (discrete-time) instant where the last
measurement has been collected. In this setting, the input locations $x_{i}$
evolve in time and generally form a sequence of correlated random variables.

###  2.2 Assumptions

Kernel continuity The kernel $K$ inducing the RKHS $\mathcal{H}$ is assumed to
be Mercer (continuous) and the input space $X$ is a compact set of the
Euclidean space. Hence, there exists basis functions $\phi_{j}$ and positive
scalars $\lambda_{j}$, with $\sum_{j}\lambda_{j}<\infty$, providing the
following absolutely convergent expansion of $K$:

$K(x,a)=\sum_{j=1}^{\infty}\lambda_{j}\phi_{j}(x)\phi_{j}(a).$ (5)

Such decomposition is not unique and does not necessarily arise from Mercer’s
theorem [20][Section 4.2]. We also assume that the kernel admits (at least)
one particular expansion where all the $\phi_{j}$ in (5) are contained in a
ball of the space of continuous functions. This condition is satisfied by the
models commonly adopted in the literature like spline [4], Gaussian [20][Eq.
15] and periodic kernels inducing sine and cosine eigenfunctions [19]. For
interesting discussions around uniform boundedness of eigenfunctions coming
from Mercer’s theorem we also refer the reader to [33].

Regression function smoothness Regularity of $\mu$ is an important condition
entering convergence studies. Following the integral operator theory developed
in [28], it can be stated making use of the important (integral) kernel
operator. To introduce it, let $p$ be a probability density function on $X$
while ${\mathbb{L}}^{2}_{p}$ denotes the Lebesque space with the measure
induced by $p$. Hence, this is the space of real functions
$f:X\rightarrow{\mathbb{R}}$ such that

$\|f\|^{2}_{p}:=\int_{X}f^{2}(a)p(a)da<\infty.$

Then, the kernel operator is
$L_{p}:{\mathbb{L}}^{2}_{p}\rightarrow\mathcal{H}$, and maps any
$f\in{\mathbb{L}}^{2}_{p}$ into $h$ where

$h(x):=L_{p}[f](x)=\int_{X}K(x,a)f(a)p(a)da,\quad x\in X.$ (6)

The level of smoothness of $h$ is now measured computing the norm in
${\mathbb{L}}^{2}_{p}$ of $L_{p}^{-r}[h],\ r>0$. The more we can increase $r$
maintaining finite the norm, the more regular the function $h$ is. Our
assumption on the regression function is then reported below. Beyond
guaranteeing that $\mu\in\mathcal{H}$, it also quantifies its level of
regularity. The key difference w.r.t. previous works is that our setting
requires that the smoothnes condition be connected with all the probability
densities $p$ in the convex hull $co\mathcal{P}$.

######  Assumption 2.1 (smoothness of the target function).

There exists $r$, with $\frac{1}{2}<r\leq 1$, and $\mathcal{A}_{1}$ with
$0<\mathcal{A}_{1}<\infty$, such that

$\sup_{p\in co\mathcal{P}}\|L_{p}^{-r}\mu\|_{p}<\mathcal{A}_{1}.$ (7)

$\blacksquare$

Data generation assumptions We consider a very general framework to describe
the process $\\{x_{i},y_{i}\\}$ in (1) which evolves in time. Each input
location $x_{i}$ is a random vector randomly drawn from a sequence of
probability densities $p_{i}\in\mathcal{P}$. We do not specify any particular
stochastic or deterministic mechanism through which these $p_{i}$ change over
time. We just need an assumption on some covariances. In fact, beyond forming
a non stationary stochastic process, the input locations $x_{i}$ can be also
correlated each other. Hence, a condition on the decay of the covariance
between a class of functions evaluated at different input locations is needed.
In addition, we also need to assume that all the sampling distributions that
can be selected are Borel non degenerate w.r.t. the Lebesgue measure. This
just implies that any selected $p$ allows the agent to visit all the input
space $X$, a minimal condition to have consistency for any possible choice of
$p$. This is summarized below.

######  Assumption 2.2 (Data generation).

The probability densities $p\in\mathcal{P}$ are all Borel non degenerate
w.r.t. the Lebesgue measure. The errors $\nu_{i}$ in (1) are independent of
each other and of the $x_{i}$. In addition, let $g$ be any function satisfying

$\|g\|_{p}<q<\infty,\quad\forall p\in co\mathcal{P}.$

Then, for every time instant $i$, there exists a constant
$\mathcal{A}_{2}<\infty$, dependent on $q$ but independent of $g$, such that

$\sum_{k=0}^{\infty}\left|\text{Cov}(g(x_{i}),g(x_{i+k}))\right|<\mathcal{A}_{2}$

where Cov is the covariance operator.

$\blacksquare$

##  3 The main result

We are now in a position to report our main result. In its statement, the
regularization parameter $\gamma$ becomes a function of $t$ which ensures
statistical consistency of $\hat{\mu}_{t}$ in (3). The learning rate is then
discussed inside the proof.

######  Proposition 3.1.

Let Assumptions 2.1 and 2.2 hold. In addition, let the regularization
parameter $\gamma$ depend on instant $t$ as follows

$\gamma\propto t^{-\alpha},\quad 0<\alpha<\frac{1}{2}.$ (8)

Then, as $t$ goes to infinity, one has

$\sup_{x\in X}|\hat{\mu}_{t}(x)-\mu(x)|\longrightarrow_{p}0$ (9)

where $\longrightarrow_{p}$ denotes convergence in probability.

###  3.1 Proof of the main result

We show that, as $t$ goes to $\infty$, the estimator $\hat{\mu}_{t}$ converges
in probability to $\mu$ in the topology of $\mathcal{H}$ and, hence, in that
of the continuous functions [12].
Some notation is first introduced. For any time instant $t$, let
$S_{t}:\mathcal{H}\rightarrow\mathbb{R}^{t}$ be the sampling operator defined
by $S_{t}(f)=\\{f(x_{i})\\}_{i=1}^{t}$ with its adjoint
$S^{\top}_{t}:\mathbb{R}^{t}\rightarrow\mathcal{H}$ given by
$S^{\top}_{t}c=\sum_{i=1}^{t}c_{i}K(x_{i},\dot{)}$. It is well known, e.g.
from [12], that this permits to formulate the minimizer of (4) as follows

$\hat{\mu}_{t}=\Big{(}\frac{S_{t}^{\top}S_{t}}{t}+\gamma
I\Big{)}^{-1}\frac{S_{t}^{\top}y^{t}}{t}$ (10)

where the vector $y^{t}$ contains the outputs up to instant $t$. We also use

$p_{1},\ldots,p_{t}$

to indicate the first $t$ densities selected from $\mathcal{P}$. Repetitions
could of course be present, like e.g. $p_{1}=p_{2}$. The average density is

$\bar{p}_{t}(x)=\frac{\sum_{i=1}^{t}p_{i}(x)}{t}.$ (11)

The nature of our problem requires now to introduce also a sequence of
Lebesgue spaces which vary over time. In particular, ${\mathbb{L}}^{2}_{t}$ is
the Lebesque space of real functions equipped with the measure induced by
(11). It thus contains all the functions satisfying

$\|f\|^{2}_{t}:=\int_{X}f^{2}(a)\bar{p}_{t}(a)da<\infty.$

Note that, in the description of the space and its norm, to simplify notation
the integer $t$ in the subscript replaces $\bar{p}_{t}$. The same convention
is used also to introduce the sequence of kernel operators which map any
$f\in{\mathbb{L}}^{2}_{t}$ into $h$ where

$h(x):=L_{t}[f](x)=\int_{X}K(x,a)f(a)\bar{p}_{t}(a)da,\quad x\in X.$ (12)

Instead, the operator $L_{p_{i}}$ is defined only by the sampling distribution
at instant $i$, i.e. it maps any $f\in{\mathbb{L}}^{2}_{p_{i}}$ into $h$ where

$h(x):=L_{p_{i}}[f](x)=\int_{X}K(x,a)f(a)p_{i}(a)da,\quad x\in X.$ (13)

The following function plays a key role in the subsequent analysis:

$\bar{\mu}_{t}=\arg\min_{f\in\mathcal{H}}\|f-\mu\|^{2}_{t}+\gamma\|f\|^{2}_{\mathcal{H}}.$
(14)

It is always well-defined since, by assumption, $\mu\in\mathcal{H}$ so that it
is continuous over $X$ and, in turn, belongs to ${\mathbb{L}}^{2}_{t}$ for any
$t$. Note that, differently from the data-free limit function introduced in
[28, eq. 2.1], here $\bar{\mu}_{t}$ is a time-varying function, depending on
the time instant $t$. It could also represent a random function e.g. when the
selection of the sampling distributions $p_{t}$ are regulated by a stochastic
mechanism. In any case, exploiting the same arguments leading to [28, eq.
2.2], the explicit solution of (14) is given by

$\bar{\mu}_{t}=(L_{t}+\gamma I)^{-1}L_{t}\mu.$ (15)

Consider now the following decomposition of the estimation error

$\|\hat{\mu}_{t}-\mu\|_{\mathcal{H}}\leq\left\|\bar{\mu}_{t}-\mu\right\|_{\mathcal{H}}+\left\|\hat{\mu}_{t}-\bar{\mu}_{t}\right\|_{\mathcal{H}}$
(16)

We start analyzing the first term on the RHS of (16). The average density
$\bar{p}_{t}$ varies over time but never escapes from $co\mathcal{P}$. Then,
combining Assumption 2.1 and eq. (3.11) in [28], one obtains the following
bound uniform in $t$:

$\left\|\bar{\mu}_{t}-\mu\right\|_{\mathcal{H}}\leq\gamma^{r-\frac{1}{2}}\|L_{t}^{-r}\mu\|_{t}\leq\gamma^{r-\frac{1}{2}}\mathcal{A}_{1}.$
(17)

To account for the possible stochastic nature of $\bar{\mu}_{t}$, we can also
take the expectation to obtain

${\mathbb{E}}\left\|\bar{\mu}_{t}-\mu\right\|_{\mathcal{H}}\leq\gamma^{r-\frac{1}{2}}\|L_{t}^{-r}\mu\|_{t}\leq\gamma^{r-\frac{1}{2}}\mathcal{A}_{1}.$
(18)

Now, we study
${\mathbb{E}}\left\|\hat{\mu}_{t}-\bar{\mu}_{t}\right\|_{\mathcal{H}}$ which
corresponds to the mean of the second term on the RHS of (16). Combining
(11,13) and (15), one has

$\gamma\bar{\mu}_{t}=L_{t}[\mu-\bar{\mu}_{t}]=\frac{1}{t}\sum_{i=1}^{t}L_{p_{i}}[\mu-\bar{\mu}_{t}],$

while from (10) one has

$\hat{\mu}_{t}-\bar{\mu}_{t}=\Big{(}\frac{S_{t}^{\top}S_{t}}{t}+\gamma
I\Big{)}^{-1}\Big{(}\frac{S_{t}^{\top}y^{t}-S_{t}^{\top}S_{t}\bar{\mu}_{t}-t\gamma\bar{\mu}_{t}}{t}\Big{)}.$

Combining the last two equations, and taking into account the definitions of
$S_{t}$ and of its adjoint $S_{t}^{\top}$, we obtain

$\displaystyle\left\|\hat{\mu}_{t}-\bar{\mu}_{t}\right\|_{\mathcal{H}}$
$\displaystyle\leq\frac{1}{\gamma}\small\left[\left\|\frac{1}{t}\sum_{i=1}^{t}\left((y_{i}-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)-L_{p_{i}}[\mu-\bar{\mu}_{t}](\cdot)\right)\right\|_{\mathcal{H}}\right]$

and this implies

$\displaystyle{\mathbb{E}}\left\|\hat{\mu}_{t}-\bar{\mu}_{t}\right\|_{\mathcal{H}}$
$\displaystyle\leq\frac{1}{\gamma}\small{\mathbb{E}}\left[\left\|\frac{1}{t}\sum_{i=1}^{t}\left((y_{i}-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)-L_{p_{i}}[\mu-\bar{\mu}_{t}](\cdot)\right)\right\|_{\mathcal{H}}\right].$

To obtain the desired bound, we need to consider

${\mathbb{E}}\left[\left\|\frac{1}{t}\sum_{i=1}^{t}\left((y_{i}-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)-L_{p_{i}}[\mu-\bar{\mu}_{t}](\cdot)\right)\right\|_{\mathcal{H}}^{2}\right]$
(21)

where the expectation takes into account all the randomness of the data
$\\{x_{i},y_{i}\\}_{i=1}^{t}$ and possibly also that underlying the operators
$L_{p_{i}}$ since they depend on the choice of $p_{1},\ldots,p_{t}$.
Exploiting the expansion (5), the kernel section centred on $x_{i}$ can be
written as

$K(x_{i},\cdot)=\sum_{j=1}^{\infty}\lambda_{j}\phi_{j}(x_{i})\phi_{j}(\cdot)$

so that one has

$\displaystyle(y_{i}-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)$ $\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}(y_{i}-\bar{\mu}_{t}(x_{i}))\lambda_{j}\phi_{j}(x_{i})\phi_{j}(\cdot)$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}a_{j}(x_{i})\lambda_{j}\phi_{j}(\cdot)$

where we have used the following correspondence

$\displaystyle a_{j}(x_{i})$ $\displaystyle=$
$\displaystyle(y_{i}-\bar{\mu}_{t}(x_{i}))\phi_{j}(x_{i})$ $\displaystyle=$
$\displaystyle(\mu(x_{i})+\nu_{i}-\bar{\mu}_{t}(x_{i}))\phi_{j}(x_{i}).$

Since the noises $\nu_{i}$ have all zero-mean and independent of the input
locations $x_{i}$, and recalling the definition of $L_{p_{i}}$, taking the
expectation we also obtain

$\displaystyle{\mathbb{E}}\left[(y_{i}-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)\right]$
$\displaystyle=$
$\displaystyle{\mathbb{E}}\left[(\mu(x_{i})-\bar{\mu}_{t}(x_{i}))K(x_{i},\cdot)\right]$
$\displaystyle=$ $\displaystyle L_{p_{i}}[\mu-\bar{\mu}_{t}](\cdot)$
$\displaystyle=$
$\displaystyle\sum_{j=1}^{\infty}{\mathbb{E}}[a_{j}(x_{i})]\lambda_{j}\phi_{j}(\cdot).$

So, the terms inside the sum reported in (21) consist of differences between
random functions and their means. Exploiting this result and also the RKHS
norm’s structure, we can now rewrite (21) as follows

$\displaystyle\frac{1}{t^{2}}{\mathbb{E}}\left\|\sum_{i=1}^{t}\sum_{j=1}^{\infty}(a_{j}(x_{i})-{\mathbb{E}}[a_{j}(x_{i})])\lambda_{j}\phi_{j}(\cdot)\right\|_{\mathcal{H}}^{2}=$
$\displaystyle={\mathbb{E}}\left[\sum_{i=1}^{t}\sum_{k=1}^{t}\sum_{j=1}^{\infty}\frac{\lambda_{j}}{t^{2}}\left(a_{j}(x_{i})-{\mathbb{E}}[a_{j}(x_{i})]\right)\left(a_{j}(x_{k})-{\mathbb{E}}[a_{j}(x_{k})]\right)\right]$
$\displaystyle={\mathbb{E}}\left[\sum_{i=1}^{t}\sum_{k=1}^{t}\sum_{j=1}^{\infty}\frac{\lambda_{j}}{t^{2}}\left(\tilde{a}_{j}(x_{i})-{\mathbb{E}}[\tilde{a}_{j}(x_{i})]\right)\left(\tilde{a}_{j}(x_{k})-{\mathbb{E}}[\tilde{a}_{j}(x_{k})]\right)\right]$

where

$\displaystyle\tilde{a}_{j}(x_{i})=(\mu(x_{i})-\bar{\mu}_{t}(x_{i}))\phi_{j}(x_{i})$

and we have still used the fact that the noises are zero-mean and independent
of the input locations. We now obtain an upper bound on the first term present
in the rhs of the above equation. First, evaluating the objective (14) at
$f=\bar{\mu}_{t}$ and $f=0$, one has

$\|\bar{\mu}_{t}-\mu\|_{t}\leq\sqrt{\|\bar{\mu}_{t}-\mu\|^{2}_{t}+\gamma\|\bar{\mu}_{t}\|^{2}_{\mathcal{H}}}$
$\leq\|\mu\|_{t}\leq\sup_{p\in co\mathcal{P}}\|\mu\|_{p}<\infty.$

where the last inequality derives from continuity of the function $\mu$ on the
compact $X$. This, combined with the fact that (by assumption) all the
$\phi_{j}$ are contained in a ball of the space of continuous functions, leads
to the following bound, uniform in $t$ and $j$:

$\|a_{j}(\cdot)\|_{t}\leq M<\infty.$

Such inequality permits to exploit Assumption 2.2 to obtain

$\displaystyle\frac{1}{t^{2}}{\mathbb{E}}\left[\sum_{i=1}^{t}\sum_{k=1}^{t}\sum_{j=1}^{\infty}\lambda_{j}\left(a_{j}(x_{i})-{\mathbb{E}}[a_{j}(x_{i})]\right)\left(a_{j}(x_{k})-{\mathbb{E}}[a_{j}(x_{k})]\right)\right]$
$\displaystyle\leq\sum_{j=1}^{\infty}\frac{\lambda_{j}}{t^{2}}\sum_{i=1}^{t}\sum_{k=1}^{t}\left|{\mathbb{E}}\left[\left(a_{j}(x_{i})-{\mathbb{E}}[a_{j}(x_{i})]\right)\left(a_{j}(x_{k})-{\mathbb{E}}[a_{j}(x_{k})]\right)\right]\right|$
$\displaystyle\leq\frac{2\mathcal{A}_{2}\sum_{j=1}^{\infty}\lambda_{j}}{t}.$

This last result, together with the Jensen’s inequality, leads to

${\mathbb{E}}[\|\hat{\mu}_{t}-\bar{\mu}_{t}\|_{\mathcal{H}}]\leq\frac{\sqrt{2\mathcal{A}_{2}\sum_{j=1}^{\infty}\lambda_{j}}}{\gamma\sqrt{t}}.$
(24)

Combining (24) with (16) and (17), we obtain

$\displaystyle{\mathbb{E}}[\|\hat{\mu}_{t}-\mu\|_{\mathcal{H}}]\leq\gamma^{r-\frac{1}{2}}\mathcal{A}_{1}+\frac{\sqrt{2\mathcal{A}_{2}\sum_{j=1}^{\infty}\lambda_{j}}}{\gamma\sqrt{t}}.$

Using the suggested rule for updating the regularization parameter, i.e.

$\gamma\propto t^{-\alpha},\quad 0<\alpha<\frac{1}{2},$

the convergence rate is

$\min\Big{(}\alpha(r-\frac{1}{2}),\frac{1}{2}-\alpha\Big{)}$

and this completes the proof.

##  4 Numerical Experiment

We consider an experiment where an unknown function $\mu$ has to be
reconstructed by an agent over the interval $[0,10]$ from 3000 input-output
data. Specifically, let $K$ be the Gaussian kernel given by

$K(x,a)=\exp(-(x-a)^{2})$ (25)

and define

$\displaystyle h(x)$ $\displaystyle=$ $\displaystyle\begin{cases}1&0\leq x\leq
2,\\\ 0.3&x\geq 8,\\\ 0&\text{elsewhere.}\end{cases}$ (26)

Then, the regression function is

$\mu(x)=\int_{0}^{10}K(x,a)h(a)da$ (27)

and it is displayed in the right panel of Fig. 1 (black line). The input
locations $x_{i}$ are independently generated adopting different probability
densities. In particular, the set $\mathcal{P}$ contains the three truncated
Gaussians displayed in the left panel of Fig. 1. They regulate the agent’s
movements while the collected output data $y_{i}$ follow (1) with the
$\nu_{i}$ forming a white Gaussian noise of variance $\sigma^{2}=0.01$. The
first density, represented by the green curve in left panel of Fig. 1, is used
to generate the first 1000 input locations, i.e. the set
$\\{x_{i}\\}_{i=1}^{1000}$. The corresponding output data are the green points
in the right panel of the same figure. One can see that this first
distribution allows the agent to explore mainly the left side of the domain.
One can then think that external directives drive the agent towards the right
part of the region. Hence, its movements are regulated by the other two
probability density functions plotted in the left panel of Fig. 1: the input
locations $\\{x_{i}\\}_{i=1001}^{2000}$ are drawn from the blue curve while
the last set $\\{x_{i}\\}_{i=2001}^{3000}$ is generated using the red one. In
this way, other 2000 output samples are collected, visible as blue and red
points in the right panel.
To apply Theorem 3.1, we have first to check that the assumptions reported in
Section 2.2 hold true. Assumption 2.2 is trivially satisfied since the input
locations, even if generated by a nonstationary stochastic process, are all
mutually independent. For what regards Assumption 2.1, from the structure of
the regression function $\mu$, it is easy to obtain

$L_{p}^{-1}[\mu](x)=\frac{h(x)}{p(x)}\qquad\forall p\in co\mathcal{P}.$ (28)

In view of the nature of the set $\mathcal{P}$, it is also immediate to check
that

$0<A\leq p(x)\leq B<\infty\qquad\forall x\in[0,10],p\in co\mathcal{P}.$

This ensures the fullfilment of Assumption 2.1, in particular of (7) with
$r=-1$. The evolution of the average distributions $\bar{p}_{t}$ is displayed
in the left panel of Fig. 2. Note that as the time $t$ increases, such
distribution is able to cover better (more uniformly) the function domain.
Through (28), it is also easy to compute the norms $\|L_{t}^{-1}[\mu]\|_{t}$
which depend on $\bar{p}_{t}$. In fact, one has

$\|L_{t}^{-1}[\mu]\|^{2}_{t}=\int_{0}^{10}\frac{h^{2}(x)}{\bar{p}_{t}(x)}dx$

and the integral can be calculated numerically with high precision. Their
evolution is displayed in the right panel of the same figure where one can see
how their values quickly decrease after the instant $t=1000$, i.e. when the
first sampling distribution is replaced by the second one. In view of (18),
this is related to improvement of the learning rate. This phenomenon is
clearly visible in Fig. 3 which plots function estimates $\hat{\mu}_{t}$, for
$t=1000,2000$ and $3000$, obtained using (3) with the Gaussian kernel (25) and

$\gamma=\frac{\sigma^{2}}{t^{0.25}}.$

Using the first sampling distribution, i.e. up to instant $t=1000$, the
recontruction of the right part of $\mu$ is poor while the sup-norm of the
estimation error goes quickly to zero for $t>1000$, i.e. when the other
sampling distributions are adopted.

Figure 1: Left: Sampling distribution adopted to generate the first set of
data (green curve), the second (blue) and the third (red). Right: Regression
function $\mu$ (black) and the three sets of 1000 output data generated using
the sampling distributions displayed in the left panel.

Figure 2: Left: Average probability density $\bar{p}_{t}$ at four different
time instants $t$. Right: Norms $\|L_{t}^{-1}[\mu]\|^{2}_{t}$ as a function of
$t$. Smaller values improve the learning rate.
Figure 3: Regression function $\mu$ (black) and estimates obtained at time
instants $t=1000,2000,3000$.

##  5 Conclusions

In many real applications, agents are distributed in an environment with the
aim of reconstructing a sensorial field. Ofen, it can be convenient to update
on-line their movements rules e.g. to exploit the acquired knowledge on the
unknown function or to follow external directives that have detected
significant events in specific regions. These tasks, which include also the
important exploration-exploitation problems, go beyond standard machine
learning since they require to apply supervised learning in dynamic and non
stationary settings. This problem has been here faced through the analysis of
kernel ridge regression with input locations drawn from sampling distributions
that may freely change in time. Our main result thus provides conditions which
ensure convergence to the optimal predictor and learning rates in rather
general settings, including situations where stochastic adaptation may occur
infinitely often.

## References

  * [1] A. Aravkin, G. Bottegal, and G. Pillonetto, “Boosting as a kernel-based method,” _Machine Learning_ , vol. 108, no. 11, pp. 1951 – 1974, 2019.
  * [2] N. Aronszajn. Theory of reproducing kernels. Trans. of the American Mathematical Society, 68:337–404, 1950.
  * [3] F. Bauer, S. Pereverzev, and L. Rosasco.  On regularization algorithms in learning theory.  Journal of Complexity, 23(1):52–72, 2007.
  * [4] B. Bell and G. Pillonetto, “Estimating parameters and stochastic functions of one variable using nonlinear measurement models,” _Inverse problems_ , vol. 20, no. 3, pp. 627–646, 2004.
  * [5] G. Blanchard and N. Mücke.  Optimal rates for regularization of statistical inverse learning problems.  Found Comput Math, 18:971-1013, 2018.
  * [6] F. Bullo, J. Cortes, and S. Martinez, _Distributed Control of Robotic Networks_. Applied Mathematics Series, Princenton University Press, 2009.
  * [7] A. Caponnetto and E. De Vito.  Optimal rates for the regularized least-squares algorithm.  Found Comput Math, 7:331–368, 2007.
  * [8] A. Caponnetto and Y. Yao.  Cross-validation based adapttion for regularization operators in learning theory.  Analysis and Applications, 08(02):161–183.
  * [9] J. Choi and R. Horowitz, “Learning coverage control of mobile sensing agents in one-dimensional stochastic environments,” _Automatic Control, IEEE Transactions on_ , vol. 55, no. 3, pp. 804–809, March 2010.
  * [10] J. Cortes, S. Martinez, T. Karatas, and F. Bullo, “Coverage control for mobile sensing networks,” _Automatica_ , vol. 20, no. 2, pp. 243–255, 2004.
  * [11] C. Cortes and V. Vapnik.  Support-vector networks.  Mach. Learn., 20(3):273–297, 1995.
  * [12] F. Cucker and S. Smale.  On the mathematical foundations of learning.  Bulletin of the American mathematical society, 39:1–49, 2001.
  * [13] F. Cucker and S. Smale.  Best choices for regularization parameters in learning theory: On the bias-variance problem.  Found Comput Math, 2:413–428, 2002.
  * [14] H. Drucker, C.J.C. Burges, L. Kaufman, A. Smola, and V. Vapnik.  Support vector regression machines.  In Advances in Neural Information Processing Systems, 1997.
  * [15] T. Evgeniou, M. Pontil, and T. Poggio.  Regularization networks and support vector machines.  Advances in Computational Mathematics, 13:1–50, 2000.
  * [16] F. Girosi, M. Jones, and T. Poggio.  Regularization theory and neural networks architectures.  Neural Computation, 7(2):219–269, 1995.
  * [17] T. J. Hastie, R. J. Tibshirani, and J. Friedman.  The Elements of Statistical Learning. Data Mining, Inference and Prediction.  Springer, Canada, 2001.
  * [18] L. Lo Gerfo, L. Rosasco, F. Odone, E. De Vito, and A. Verri.  Spectral algorithms for supervised learning.  Neural Computation, 20:1873–1897, 2008.
  * [19] S. Mendelson and J. Neeman.  Regularization in kernel learning.  The Annals of Statistics, 38(1):526 – 565, 2010.
  * [20] H.Q. Minh and P. Niyogi and Y. Yao, “Mercer’s Theorem, Feature Maps, and Smoothing,” in _Learning Theory. COLT 2006. Lecture Notes in Computer Science_ , vol. 4005, Springer, 2006.
  * [21] G. Pillonetto, T. Chen, A. Chiuso, G. De Nicolao, and L. Ljung.  Regularized System Identification.  Springer, 2022.
  * [22] G. Pillonetto and L. Ljung.  Full Bayesian identification of linear dynamic systems using stable kernels.  Proceedings of the National Academy of Sciences USA (PNAS), 2023.
  * [23] T. Poggio and F. Girosi. Networks for approximation and learning. In Proceedings of the IEEE, volume 78, pages 1481–1497, 1990\.
  * [24] M. Schwager, D. Rus, and J.J. Slotine, “Decentralized, adaptive coverage control for networked robots,” _Int. J. Rob. Res._ , vol. 28, no. 3, pp. 357–375, Mar. 2009.
  * [25] S. Smale and D.X. Zhou, “Online learning with Markov sampling,” _Analysis and Applications_ , vol. 07, no. 01, pp. 87–113, 2009.
  * [26] M. Todescato and A. Carron and R. Carli and G. Pillonetto and L. Schenato, “Multi-Robots Gaussian Estimation and Coverage Control: from Client-Server to Peer-to-Peer Architectures,” _Automatica_ , vol. 80, pp. 284–294, 2017.
  * [27] B. Schölkopf and A. J. Smola.  Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond.  (Adaptive Computation and Machine Learning). MIT Press, 2001.
  * [28] S. Smale and D.X. Zhou.  Learning theory estimates via integral operators and their approximations.  Constructive Approximation, 26:153–172, 2007.
  * [29] V. Vapnik.  The nature of Statistical Learning Theory.  Springer, 1997.
  * [30] G. Wahba.  Spline models for observational data.  SIAM, Philadelphia, 1990.
  * [31] C. Wang and D.X. Zhou.  Optimal learning rates for least squares regularized regression with unbounded sampling.  Journal of Complexity, 27(1):55 – 67, 2011.
  * [32] Y. Yao, L. Rosasco, and A. Caponnetto.  On early stopping in gradient descent learning.  Constr Approx, 26:289–315, 2007.
  * [33] D.X. Zhou, “The covering number in learning theory,” _Journal of Complexity_ , vol. 18, no. 3, pp. 739–767, 2002.