Pre-established entanglement distribution algorithm in quantum networks

Yazi Wang; Xiaosong Yu; Xiaosong Yu; Yongli Zhao; Avishek Nag; Jie Zhang

doi:10.1364/JOCN.465432

Journal of Optical Communications and Networking
Vol. 14,
Issue 12,
pp. 1020-1033
(2022)
•https://doi.org/10.1364/JOCN.465432

Pre-established entanglement distribution algorithm in quantum networks

Yazi Wang, Xiaosong Yu, Yongli Zhao, Avishek Nag, and Jie Zhang

Not Accessible

Your library or personal account may give you access

Get PDF
Email
Share
Get Citation
Copy Citation Text
Yazi Wang, Xiaosong Yu, Yongli Zhao, Avishek Nag, and Jie Zhang, "Pre-established entanglement distribution algorithm in quantum networks," J. Opt. Commun. Netw. 14, 1020-1033 (2022)

Export Citation
- BibTex
- Endnote (RIS)
- HTML
- Plain Text
Citation alert
Save article

Abstract

As the basic principle of quantum networks, quantum entanglement can enable important quantum applications such as teleportation and quantum-key distribution. To realize wide-area quantum communication, entanglement establishment between two remote communication parties is vital, and it requires effective entanglement distribution strategies. Entanglement distribution network models of distributed and centralized entangled pair sources are constructed, based on which two entanglement-distribution algorithms are proposed, i.e., the real-time entanglement distribution (R-TED) algorithm and the pre-established entanglement distribution (P-EED) algorithm, to achieve end-to-end multi-hop entanglement establishment. For the former, the objective is to build long-distance entanglements via hop-by-hop entanglement tentatively and entanglement swapping to finally glue them together. For the latter, which uses pre-established entanglement, entanglements can be established in advance to patch multiple link-level entanglements via entanglement swapping. Simulation results show that as the number of time slots increases, the P-EED algorithm is more efficient and has higher entanglement establishment probability than the R-TED algorithm to establish end-to-end entanglement; while there are fewer memory cells in a quantum memory, such as 10, the R-TED algorithm provides more stable entanglement distribution compared to the P-EED algorithm.

Full Article | PDF Article

Cited By

You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Figures (15)

You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Tables (3)

You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.

Contact your librarian or system administrator
or
Login to access Optica Member Subscription

Notation	Definition
$G (V, E)$	Physical EDN of the distributed EPS topology
$V$	Set of Q-Nodes with $V = {v_{i}}_{i = 1}^{N}$
$E$	Set of fiber links with $E = {e_{i, j}, v_{i}, v_{j} \in V}$
$G (V, E, B)$	Physical EDN of the centralized EPS topology
$V$	Set of Q-Nodes with $V = {v_{i}}_{i = 1}^{N}$
$E$	Set of fiber links with $E = {e_{i, j} \cup e_{s, i}, v_{i}, v_{j} \in V, b_{s} \in B}$
$B$	Set of EPSs with $B = {b_{s}}_{s = 1}^{Z}$
$r (s_{r}, d_{r}, t_{r})$	Quantum request
$s_{r}$	Source Q-Node of quantum request $r$ , $s_{r} \in V$ , $V$
$d_{r}$	Destination Q-Node of quantum request $r$ , $d_{r} \in V$ , $V$
$t_{r}$	Holding time of quantum request $r$
$h_{r}$	Number of hops of quantum request $r$
$R_{s, d}$	Calculated path with the $K$ -shortest-path algorithm for a quantum request
$t$	Entanglement-updating period in a quantum memory (a time slot)
$t_{v_{i}}$	Real-time remaining time of entanglement stored in each memory cell (quantum memory) for Q-Node $v_{i}$ in a time slot $t$
$Q_{c}^{v_{i}}$	Set of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$ with $Q_{c}^{v_{i}} = {q_{1}^{v_{i}}, q_{2}^{v_{i}}, \dots, q_{c}^{v_{i}}}$
$Q_{d}^{v_{i}}$	Set of memory cell storing entanglements in each Q-Node $v_{i}$ with $Q_{d}^{v_{i}} = {q_{1}^{v_{i}}, q_{2}^{v_{i}}, \dots, q_{d}^{v_{i}}}$
${NQ}_{c}^{v_{i}}$	Real-time number of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$
${NQ}_{d}^{v_{i}}$	Real-time number of memory cells storing entanglements in each Q-Node $v_{i}$
$D$	Set of intermediary Q-Nodes in the route $R_{s, d}$ , $D = {d_{1}, d_{2}, \dots, d_{h_{r} - 1}}$ , $\| D \| = h_{r} - 1 D \in V$ , $V$
$Q - R_{s, d}$	Set of Q-Nodes in the path $R_{s, d}$ with $Q - R_{s, d} = {s_{r}, v_{1}, \dots, v_{h_{r} - 1}, d_{r}}$
${NQ}_{c}^{v_{i}} - R_{s, d}$	Set of total number of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$ in the path $R_{s, d}$ with ${NQ}_{c}^{v_{i}} - R_{s, d} = {{NQ}_{c 1}^{s_{r}}, {NQ}_{c 2}^{v_{1}}, \dots, {NQ}_{c h_{r} + 1}^{d_{r}}}$
${NQ}_{d}^{v_{i}} - R_{s, d}$	Set of total number of memory cell storing entanglements in each Q-Node $v_{i}$ in the path $R_{s, d}$ with ${NQ}_{d}^{v_{i}} - R_{s, d} = {{NQ}_{d 1}^{s_{r}}, {NQ}_{d 2}^{v_{1}}, \dots, {NQ}_{d h_{r} + 1}^{d_{r}}}$
$t_{v_{i}} - R_{s, d}$	Set of real-time remaining times of entanglement stored in each quantum memory for Q-Node $v_{i}$ in a time slot $t$ in the path $R_{s, d}$ with $t_{v_{i}} - R_{s, d} = {t_{v_{1}}, t_{v_{2}}, \dots, t_{v_{h_{r} + 1}}}$

Input: $G (V, E)$ , $r (s_{r}, d_{r}, t_{r})$ , $t$ , $Q_{c}^{v_{i}}$ , ${N Q}_{c}^{v_{i}}$
Output: $R$ -TED for each quantum request
1	for each $r (s_{r}, d_{r}, t_{r})$ then
2	Routing computation with *Dijkstra* algorithm;
3	for each computed path $R_{s, d}$ do
4	Add the computed Q-Nodes in a Q-Nodes set
	$Q - R_{s, d}$ ;
5	Compute the number of intermediary Q-Nodes
	$\| D \| \leftarrow h_{r} - 1$ ;
6	Search available memory cells in each Q-Node,
	i.e., source Q-Node $Q_{c 1}^{s_{r}} = {q_{1}^{s_{r}}, q_{2}^{s_{r}}, \dots, q_{c 1}^{s_{r}}}$ ,
	destination Q-Node $Q_{c 2}^{d_{r}} = {q_{1}^{d_{r}}, q_{2}^{d_{r}}, \dots, q_{c 2}^{d_{r}}}$ , and
	intermediary Q-Nodes $Q_{c 3}^{v_{1}} = {q_{1}^{v_{1}}, q_{2}^{v_{1}}, \dots, q_{c 3}^{v_{1}}}, \dots,$
	$Q_{c h_{r} + 1}^{v_{h_{r} - 1}} = {q_{1}^{v_{h_{r} - 1}}, q_{2}^{v_{h_{r} - 1}}, \dots, q_{c h_{r} + 1}^{v_{h_{r} - 1}}};$
7	if $\forall {NQ}_{c}^{v_{i}} - R_{s, d} \geq 2$ then
8	Select available memory cells in each Q-Node with
	*First Fit* algorithm;
9	if $t \geq t_{r}$ then
10	Distribute entangled particle pairs between all
	adjacent Q-Nodes;
11	Store entangled particle pairs in memory cells;
12	Conduct entanglement swapping along the
	path $R_{s, d}$ to patch multiple link-level
	entanglements together;
13	Establish end-to-end entanglement;
14	else
15	Block $r$ ; break;
16	end
17	else
18	Select alternative path $R_{s, d}$ ;
19	Repeat the steps in lines 4–20;
20	end
21	end for
22	for each $r (s_{r}, d_{r}, t_{r})$ release then
23	Free the allocated memory cells;
24	end for
25	end for

Input: $G (V, E, B), r (s_{r}, d_{r}, t_{r})$ , $t$ , $t_{v_{i}}$ , $Q_{d}^{v_{i}}$ , ${N Q}_{d}^{v_{i}}$
Output: $P$ -EED for each quantum request
1	for each $r (s_{r}, d_{r}, t_{r})$ then
2	if $t \geq t_{r}$ then
3	Routing computation with *Dijkstra* algorithm;
4	for each computed path $R_{s, d}$ do
5	Add the computed Q-Nodes in a Q-Node
	set $Q - R_{s, d}$ ;
6	Compute the number of intermediary
	Q-Nodes $\| D \| \leftarrow h_{r} - 1$ ;
7	Search available memory cells in each Q-Node,
	i.e., source Q-Node $Q_{d 1}^{s_{r}} = {q_{1}^{s_{r}}, q_{2}^{s_{r}}, \dots, q_{d 1}^{s_{r}}}$ ,
	destination Q-Node $Q_{d 2}^{d_{r}} = {q_{1}^{d_{r}}, q_{2}^{d_{r}}, \dots, q_{d 2}^{d_{r}}}$ ,
	and intermediary Q-Nodes
	$Q_{c 3}^{v_{1}} = {q_{1}^{v_{1}}, q_{2}^{v_{1}}, \dots, q_{d 3}^{v_{1}}}, \dots,$
	$Q_{d h_{r} + 1}^{v_{h_{r} - 1}} = {q_{1}^{v_{h_{r} - 1}}, q_{2}^{v_{h_{r} - 1}}, \dots, q_{d h_{r} + 1}^{v_{h_{r} - 1}}};$
8	if $\forall t_{v_{i}} - R_{s, d} \geq t_{r}$ and $\forall {NQ}_{d}^{v_{i}} - R_{s, d} \geq 2$ then
9	Select available memory cells in each Q-Node with
	*First Fit* algorithm;
10	Conduct entanglement swapping along the path
	$R_{s, d}$ to patch multiple link-level entanglements
	together;
11	Establish end-to-end entanglement;
12	else
13	Find the unsatisfied memory cells;
14	Re-distribute entangled particle pairs in the
14	unsatisfied memory cells;
15	Store entangled particle pairs in memory cells;
16	Repeat the steps in lines 10 and 11;
17	end
18	end for
19	else
20	Block $r$ ; break;
21	end
22	Free the allocated memory cells;
23	end for

Notation	Definition
$G (V, E)$	Physical EDN of the distributed EPS topology
$V$	Set of Q-Nodes with $V = {v_{i}}_{i = 1}^{N}$
$E$	Set of fiber links with $E = {e_{i, j}, v_{i}, v_{j} \in V}$
$G (V, E, B)$	Physical EDN of the centralized EPS topology
$V$	Set of Q-Nodes with $V = {v_{i}}_{i = 1}^{N}$
$E$	Set of fiber links with $E = {e_{i, j} \cup e_{s, i}, v_{i}, v_{j} \in V, b_{s} \in B}$
$B$	Set of EPSs with $B = {b_{s}}_{s = 1}^{Z}$
$r (s_{r}, d_{r}, t_{r})$	Quantum request
$s_{r}$	Source Q-Node of quantum request $r$ , $s_{r} \in V$ , $V$
$d_{r}$	Destination Q-Node of quantum request $r$ , $d_{r} \in V$ , $V$
$t_{r}$	Holding time of quantum request $r$
$h_{r}$	Number of hops of quantum request $r$
$R_{s, d}$	Calculated path with the $K$ -shortest-path algorithm for a quantum request
$t$	Entanglement-updating period in a quantum memory (a time slot)
$t_{v_{i}}$	Real-time remaining time of entanglement stored in each memory cell (quantum memory) for Q-Node $v_{i}$ in a time slot $t$
$Q_{c}^{v_{i}}$	Set of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$ with $Q_{c}^{v_{i}} = {q_{1}^{v_{i}}, q_{2}^{v_{i}}, \dots, q_{c}^{v_{i}}}$
$Q_{d}^{v_{i}}$	Set of memory cell storing entanglements in each Q-Node $v_{i}$ with $Q_{d}^{v_{i}} = {q_{1}^{v_{i}}, q_{2}^{v_{i}}, \dots, q_{d}^{v_{i}}}$
${NQ}_{c}^{v_{i}}$	Real-time number of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$
${NQ}_{d}^{v_{i}}$	Real-time number of memory cells storing entanglements in each Q-Node $v_{i}$
$D$	Set of intermediary Q-Nodes in the route $R_{s, d}$ , $D = {d_{1}, d_{2}, \dots, d_{h_{r} - 1}}$ , $\| D \| = h_{r} - 1 D \in V$ , $V$
$Q - R_{s, d}$	Set of Q-Nodes in the path $R_{s, d}$ with $Q - R_{s, d} = {s_{r}, v_{1}, \dots, v_{h_{r} - 1}, d_{r}}$
${NQ}_{c}^{v_{i}} - R_{s, d}$	Set of total number of unoccupied memory cells by other quantum requests in each Q-Node $v_{i}$ in the path $R_{s, d}$ with ${NQ}_{c}^{v_{i}} - R_{s, d} = {{NQ}_{c 1}^{s_{r}}, {NQ}_{c 2}^{v_{1}}, \dots, {NQ}_{c h_{r} + 1}^{d_{r}}}$
${NQ}_{d}^{v_{i}} - R_{s, d}$	Set of total number of memory cell storing entanglements in each Q-Node $v_{i}$ in the path $R_{s, d}$ with ${NQ}_{d}^{v_{i}} - R_{s, d} = {{NQ}_{d 1}^{s_{r}}, {NQ}_{d 2}^{v_{1}}, \dots, {NQ}_{d h_{r} + 1}^{d_{r}}}$
$t_{v_{i}} - R_{s, d}$	Set of real-time remaining times of entanglement stored in each quantum memory for Q-Node $v_{i}$ in a time slot $t$ in the path $R_{s, d}$ with $t_{v_{i}} - R_{s, d} = {t_{v_{1}}, t_{v_{2}}, \dots, t_{v_{h_{r} + 1}}}$

Input: $G (V, E)$ , $r (s_{r}, d_{r}, t_{r})$ , $t$ , $Q_{c}^{v_{i}}$ , ${N Q}_{c}^{v_{i}}$
Output: $R$ -TED for each quantum request
1	for each $r (s_{r}, d_{r}, t_{r})$ then
2	Routing computation with *Dijkstra* algorithm;
3	for each computed path $R_{s, d}$ do
4	Add the computed Q-Nodes in a Q-Nodes set
	$Q - R_{s, d}$ ;
5	Compute the number of intermediary Q-Nodes
	$\| D \| \leftarrow h_{r} - 1$ ;
6	Search available memory cells in each Q-Node,
	i.e., source Q-Node $Q_{c 1}^{s_{r}} = {q_{1}^{s_{r}}, q_{2}^{s_{r}}, \dots, q_{c 1}^{s_{r}}}$ ,
	destination Q-Node $Q_{c 2}^{d_{r}} = {q_{1}^{d_{r}}, q_{2}^{d_{r}}, \dots, q_{c 2}^{d_{r}}}$ , and
	intermediary Q-Nodes $Q_{c 3}^{v_{1}} = {q_{1}^{v_{1}}, q_{2}^{v_{1}}, \dots, q_{c 3}^{v_{1}}}, \dots,$
	$Q_{c h_{r} + 1}^{v_{h_{r} - 1}} = {q_{1}^{v_{h_{r} - 1}}, q_{2}^{v_{h_{r} - 1}}, \dots, q_{c h_{r} + 1}^{v_{h_{r} - 1}}};$
7	if $\forall {NQ}_{c}^{v_{i}} - R_{s, d} \geq 2$ then
8	Select available memory cells in each Q-Node with
	*First Fit* algorithm;
9	if $t \geq t_{r}$ then
10	Distribute entangled particle pairs between all
	adjacent Q-Nodes;
11	Store entangled particle pairs in memory cells;
12	Conduct entanglement swapping along the
	path $R_{s, d}$ to patch multiple link-level
	entanglements together;
13	Establish end-to-end entanglement;
14	else
15	Block $r$ ; break;
16	end
17	else
18	Select alternative path $R_{s, d}$ ;
19	Repeat the steps in lines 4–20;
20	end
21	end for
22	for each $r (s_{r}, d_{r}, t_{r})$ release then
23	Free the allocated memory cells;
24	end for
25	end for

Abstract

Cited By

Figures (15)

Tables (3)

Journal of Optical Communications and Networking