Routing Entanglement in the Quantum Internet

This example protocol (1) implements the task of Entanglement Routing considering different scenarios. All of the protocols presented are applicable to quantum networks with arbitrary topology but their analysis is only concerned with the 2D grid network. They develop protocols for multipath routing of a single entanglement flow with global or local state information of the other quantum repeater nodes and a protocol for multipath routing of simultaneous entanglement flows with repeaters with local state information.

Tags: Multi Party, Specific Task.

Assumptions

• Each quantum repeater node is equipped with:
  • Quantum memories that can hold a qubit perfectly for some predefined time.
  • Entanglement sources.
  • Ability to perform Bell state measurements between any pair of locally-held qubits.
  • Classical computing resources and communication interface.
• Each quantum repeater node is aware of the overall network topology, as well as the locations of the $K$ Source-Destination pairs.

Outline

In (1) they develop and analyze routing protocols for generating maximally entangled qubits (ebits) simultaneously between single or multiple pairs of senders and receivers in a quantum network by exploiting multiple paths in the network. They introduce protocols for quantum repeater nodes in the following scenarios:

• Multipath routing of a single entanglement flow:
  • Considering nodes with global link-state information (the state of every link is known to every repeater in the network and can be used).
  • Considering nodes with local link-state information (a link knows the states of it neighbors).
• Multipath routing of simultaneous entanglement flows:
  • Considering nodes with local link-state information.

All of the protocols above considering their characteristics are divided in two phases with the objective of creating an unbroken end-to-end connection between the source and destination nodes. The external and the internal phase which occur in this order.

• External phase: each pair of memories (neighboring repeaters) across an edge attempts to establish a shared entangled (EPR) pair.
• Internal phase: BSMs are attempted within each memory (repeater node) based on the successes and failures of the neighboring links in the external phase.

The high-level objective is: Considering the assumptions of quantum and classical operations at each of the repeater nodes of the underlying network, what operations should be performed at the repeater to achieve maximum entanglement-generation rate for one sender and receiver or achieve maximum rate region for multiple flows of entanglement.

Notation

Quantum network with topology described by a graph Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G(V,E)} :

• Each of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N=|V|} nodes is equipped with a quantum repeater.
• Each of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle M=|E|} edges is a lossy optical channel of range $L_{i}$ (km) and power transmissivity $\eta _{i}\propto e^{-\alpha L_{i}}$, $i\in E$ and $\alpha$ depends on the material of the channel.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} Source-Destination pairs $(A_{j},B_{j})$, $1\leq j\leq k$ situated at (not necessarily distinct) nodes in $V$.

Considering this graph$G$ we adopt the following notation for the repeater network.

• Each node $v\in V$ is a repeater.
• Each edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e \in E} is a physical link connecting two repeater nodes.
• $S(e)\in \mathbb {Z} ^{+}$ is an integer edge weight corresponding to the number of parallel channel across edge $e$.
• ${\mathcal {N}}(v)$ is the set of neighbor edges of $v$
• $d(v)=|{\mathcal {N}}(v)|$ is the degree of node $v$.
• $\sum _{e\in {\mathcal {N}}(v)}S(e)$ is the number of memories at node $v$.
• Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_A} distance of a node to the node A, using the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{L}^2} norm.
• An ebit represents a maximally entangled qubit.

Protocol Description

• All of the three protocols below assume that time is slotted and each memory can hold a qubit perfectly for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T \geq 1} time slot. After this time the stored qubit completely decoheres.
• Each time slot Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t} , Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle t=1,2,... } is divided into 2 phases:
• External Phase:
  • Each of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(e)} pairs of memories across and edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} attempts to establish an EPR pair.

  - An entanglement attempt across any one of the Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(e)} parallel links across edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} succeeds with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_0(e) \sim \eta(e)} , where $\eta (e)\sim e^{-\alpha L_{e}}$ is the transmissivity of a lossy optical channel of length Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L(e)} .

  - The probability that one or more ebits are established across an edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(e)=1-(1-p_0)^{S(e)}} .

  - Assuming Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S(e)=S,} give us Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p(e)=p,} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \forall e \in E} .

  • Using two-way classical communication over edge Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e(u, v)} , neighboring repeater nodes $u,v$ learn which of the S(e) parallel links (if any) succeeded in the external phase, in a given time slot.

• Internal Phase:
  • BSMs are attempted locally at each repeater node between pairs of qubit memories based on the success and failure of the neighboring links in the external phase.

  - These BSM attempts are called internal links, i.e., links between memories internal to a repeater node.

  - Each of these internal-link attempts succeed with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} .

At the end of one time-slot a along a path comprising of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} edges (and thus $(k-1)$ repeater nodes) one ebit is successfully shared between the end points of the path with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^k q^{k-1}} .

The maximum number of ebits that can be shared between node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} and node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} after one time-slot is Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle min\{d(a), d(b)\}} , assuming Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S} is the same over all edges.

The protocols described below focus on finding the optimal strategy for each repeater node in order to decide which locally held qubits to attempt BSMs during the internal phase of a time slot. Based on the outcomes of the external phase and considering global or local link-state knowledge and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} .

Multipath Routing of a Single Entanglement Flow

Input: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=1} , Source-Destination pair Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_1, B_1)} .

Output: Quantum network with ebits shared between the end points of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_1, B_1)} .

Protocol for Entanglement Routing with Global Link-state Information

After the External Phase

1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = 1}
2. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_m} = Subgraph induced by the successful external links and the repeater nodes after the external phase.
3. While (True):
   1. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_m} = shortest path in Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_m} connecting Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} with Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_1} .
   2. If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_m} is empty: Break While Loop.
   3. Else:
      1. Set Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle L_m} as the length of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_m} .
      2. Try connecting all internal links along the nodes of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_m}
         //successfully generating an ebit between Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_1} with probability Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q^{L_m - 1}}
   4. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_{m+1}} = Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_m -} all external and internal links of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_m} .
   5. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = m + 1.}

Protocol for Entanglement Routing with Local Link-state Information

Knowledge of success and failure of the External Phase is communicated only to the two repeater nodes connected by the link. Repeater nodes need to decide on which pair(s) of memories BSMs should be attempted (which internal links to attempt), based only on information about the states of external links adjacent to them.

After the External Phase

1. For every repeater except Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_1} :
   Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} be the node of this iteration.
   1. If less than one of the neighboring external links is successful:
      no internal links are attempted since this repeater node can not be part of a path from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle B_1} .
   2. If two or more neighboring external links are successful:
      Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} be the node linked to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} with the smallest Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{A_1}} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} be the node linked to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} with the smallest Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_{B_1}} .
      Attempt a BSM on node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} on the memories connected to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle w} .
      1. If four neighboring external links are successful:
         Attempt a BSM on node Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle u} on the remaining memories disconsidering the two memories from the previous step.

Protocol for Simultaneous Entanglement Flows with Link-state Information

Input: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=2} , Source-Destination pairs Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_1, B_1)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_2, B_2)} .

Output: Quantum network with ebits shared between the end points of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_1, B_1)} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (A_2, B_2)} .

This situation motivates the Multi-flow Spatial-division rule which divides the the network between two spatial regions corresponding to the two flows.

• When the shortest path connecting the two source-destination pairs do not cross the network is divided between two spatial regions corresponding to the two flows.
  • For each one of this regions we apply the Protocol for Entanglement Routing with Local Link-state Information.

• When the shortest path connecting the two source-destination pairs do cross the network is divided between two spatial regions corresponding to the two flows.
  • Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \theta} between them (forming a hourglass shape).
  • For each one of this regions we apply the Protocol for Entanglement Routing with Local Link-state Information.

Properties

• The goal of the optimal repeater strategy is to achieve:
  • Maximum entanglement generation rate for a single sender and receiver (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K=1} ).

  - Above a (percolation) threshold determined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} the entanglement generation rate will depend only linearly on the transmissivity Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \eta} of a single link in the network.

• Maximum rate regions simultaneously achievable by the entanglement flows (Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K \geq 2} ).

  - Above a (percolation) threshold determined by Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} this protocol significantly exceeds the ones that each repeater node makes BSM decisions by simply time-sharing between catering to the individual flows.

Further Information

• Pirandola (2016) analyzed entanglement-generation capacities of repeater networks assuming ideal repeater nodes and argued that for a single flow the maximum entanglement-generation rate Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle R_1} reduces to the classical max-flow min-cut problem.
• Azuma and Kato (2016) looked at an "aggregated" protocol in which the repeater protocols run in parallel.
• Schoute et al. (2016) developed routing protocols on specific network topologies and found scaling laws as functions on the number of qubits in the memories at nodes, and the time and space consumed by the routing algorithms, under lossless and noiseless assumptions.
• Acín et al. (2006) have considered the problem of entanglement percolation where neighboring nodes share a perfect lossless pure state.

There is an extensive literature of quantum networks analyzing repeaters in a linear chain for example: Briegel et al. (1998), Jiand et al. (2008) and Muralidharan et al. (2016).

References

1. Pant et al. (2019)

*contributed by Lucas Arenstein