Quantum Protocol Zoo - User contributions [en]

Distributing Graph States Over Arbitrary Quantum Networks

2022-01-06T18:04:21Z

189.120.189.205: Edit by Lucas: Corrections and suggestions from our last talk - Removed Kaushik's name

This protocol [https://arxiv.org/abs/1811.05445 (1)] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute this states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realized by the protocol.

'''Tags:'''[[:Category:Specific Task|Specific Task]], [[Entanglement Routing]]

==Assumptions==
* Perfect distribution of Bell pairs occurring at perfectly synchronized times.
* Perfect node local computation.
* Ignore the cost of classical communications.
* Ignore processing time of local quantum processor.
* Ignore the cost of quantum memory.

==Outline==
The protocol [https://arxiv.org/abs/1811.05445 (1)] aims to distribute multipartite entangled states that are represented by graph states over fixed networks of arbitrary topology. They first introduce a protocol to distribute GHZ states that considering the assumptions takes a single time step and is optimal in terms of the Bell pair used. Their second protocol is a generalization of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps than the optimal distributing protocol for the worst case scenario.

In this protocol a quantum network is represented as a graph
'''upload image qn_distributing.svg here'''


The physical distribution of graph states are represented as graph operations ignoring
local corrections.

To distribute a '''GHZ states''' over all the nodes of an arbitrary set <math>W</math> of the network nodes we have two steps:

# Find a minimal tree covering all the nodes of <math>W</math> using the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem].
#* Minimal tree is a subgraph connecting all the nodes in <math>W</math> with the minimum number of edges.
# Apply an operation called Star Expansion on the leaves of the tree from the previous step.


To distribute an '''Arbitrary Graph State''' we realize multiple iterations of the protocol above.
After that we make measurements on the participating nodes to generate the arbitrary graph state we want.



==Requirements==
*'''Network Stage:''' [[Category: Quantum Memory Network Stage]][[:Category: Quantum Memory Network Stage| Quantum Memory]]
* Nodal Clifford Operations.

==Notation==
* <math>b=</math>qubit in the center of the star graph.
* <math>A=</math>Node of the network which contains a qubit <math>a_0 \in A \cap N_b</math> (neighborhood of b).
* <math>|A|</math> number of nodes of A.
* <math>a_i \in A</math>, <math>i > 0</math> Represents each of the qubits of <math>A</math> that constitutes a Bell pair with a qubit <math>c_i</math> in another node of the network.

==Properties==
* The optimality of the protocol depends on the network topology and the wanted graph state to distribute.
* Analysing the consumption of Bell pair between nodes and considering the worst case scenario that is to entangle each qubit with the opposite one over a line network we have the following upper bounds:
{| class="wikitable"
|-
! Distribute
! Cost
! Bound
|-
|rowspan="2"| N-GHZ
| EPR
| <math>N-1</math>
|-
| T
| <math>1</math>
|-
|rowspan="2"| Arbitrary Graph State
| EPR
| <math>\left\lfloor \frac{N}{2} \right\rfloor^2</math>
|-
| T
| <math>\left\lfloor \frac{N}{2} \right\rfloor</math>
|-
|}

==Protocol Description==
'''Graph Operations:'''
* '''Vertex Deletion.''' Removes one vertex and all the associated edges from the graph.
** Implemented by the Pauli Measurement of the relevant qubit in the ''Z basis''.
* '''Local Complementation.''' Inverts the subgraph induced by the neighborhood <math>N_a</math> of the concerned vertex <math>a</math>.
** Implemented by the quantum operator <math>U_a^\tau = e^{-i \frac{\pi}{4}X_a} \bigotimes_{b \in N_a} e^{i \frac{\pi}{4}Z_b}</math> acting on the qubits <math>a \cup N_a</math>.
* '''Edge Addition.''' Add an edge between two nonadjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Edge Deletion.''' Delete an edge between two adjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Entanglement Swapping.'''
** Implemented by applying ''controlled-Z'' gate followed by two single qubit ''Y-measurement''.

===GHZ State Distribution Protocol===
'''Input'''
* N-GHZ state: <math>|\text{N-GHZ}\rangle = (|0\rangle^{\otimes N}+|1\rangle^{\otimes N})/\sqrt{2}</math>.
* That is locally equivalent to: <math>(|0\rangle|+\rangle^{\otimes N-1}+|1\rangle|-\rangle^{\otimes N-1})/\sqrt{2}</math> that is called a star graph '''upload image star_graph_distributing.svg here'''



* Arbitrary set <math>W</math> of the network nodes.
** Assuming that the network topology is already given to us.

'''Output'''
* N-GHZ state distributed over <math>W</math>.

'''GHZ-Distribution Algorithm'''
# Find a minimal tree covering all the nodes of <math>W</math>
# <math>l</math> is a random leaf from the tree of step 1.
# For <math>j=1</math> to <math>|W| - 1</math>:
## Let <math>A</math> be any unprocessed node of <math>W</math> such as <math>l \notin A</math>.
## Apply the Start Expansion Algorithm on node <math>A</math> with <math>l</math> as <math>b</math> the center of the star.

'''Start Expansion Algorithm'''
This routine uses the Bell pairs of the node <math>A</math> to add the edges <math>(b,c_i)</math> to the graph state, as well as the edge <math>(b, a_0)</math> ''iff'' <math>A \in W</math>.

# All the qubits <math>a_i, i \geq 0</math> of <math>A</math> are linked using Controlled-Z operations between all possible pairs.
# Local complementation is applied to the qubit <math>a_0</math> linked to <math>b</math>.
# If <math>A \notin W</math>:
## Remove <math>a_0</math> and all the edges within <math>A</math> by <math>Z</math>-measuring it
## Else (when <math>A \in W</math>):
###Keep <math>a_0</math> and apply Controlled-Z gates to remove all edges within <math>A</math>.
#Apply a <math>Y</math>-measurement on all the other qubits <math>a_i \in A</math>, <math>i>0</math> creating the desired Start Graph.

===Arbitrary Graph State Distribution Protocol===
To distribute an arbitrary graph state we first distribute the edge-decorated complete graph state. From this graph we can construct any other graph state by measuring each edge-qubit with a:
* ''Z measurement'' to delete this vertex and its edges
or a
* ''Y measurement'' to delete the vertex but keep the edges.

'''Input'''
* Arbitrary graph state to distribute
* Arbitrary set <math>W</math> of the <math>k</math> participating nodes.
'''Output'''
* Arbitrary graph state distributed over <math>W</math>.

'''Arbitrary Graph State Distribution Algorithm'''
# Solve the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem] on the network for the <math>k</math> nodes.
#* Each one of the nodes of this tree has an central leaf <math>l_n</math>, <math>1 \leq n \leq k</math>.
# For <math>j=1</math> to <math>k</math>:
## Distribute a (k-1-j)-GHZ state on the node of <math>l_j</math> using the [[Distributing Graph States Over Arbitrary Quantum Networks#Protocol Description|GHZ-Distribution Algorithm ]].
## Delete vertices from the tree in order to have the covering tree for the set <math>W \setminus \{l_j\}</math>.
# For each one of the <math>k</math> nodes apply local operations to generate the edge-decorated graph state.
# For each one of the <math>k</math> nodes construct the desired arbitrary state by applying <math>Z</math> and <math>Y</math> measurements.

==Further Information==
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
* [http://dx.doi.org/10.1088/1367-2630/18/5/053036 Epping et all (2016)] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
* [http://dx.doi.org/10.1103/PhysRevA.86.042304 Cuquet and Calsamiglia (2012)] and [http://dx.doi.org/10.1103/PhysRevLett.104.050501 Matsuzaki et al (2010)] Present decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
* [http://dx.doi.org/10.1038/s41534-019-0191-6 Hahn et all (2019)] Studies the possible transformations of an already shared graph-state, with a single-qubit per location.
* [http://dx.doi.org/10.1088/1367-2630/ab05f7 Pirker and Dür (2019)] Includes a protocol very similar to the one presented in this page, but the modeling of the network is different, as well as the optimized metrics. They describe a hierarchical network stack and use it to provide robustness against router or sub-network failures, which is not presented in this work.

==References==
# [https://arxiv.org/abs/1811.05445 Meignant, Markham and Grosshans (2019)]


<div style='text-align: right;'>''Contributed by Lucas Arenstein during the QOSF Mentorship Program''</div>
<div style='text-align: right;'>''Mentor: Shraddha Singh</div>

Distributed Routing in a Quantum Internet

2022-01-06T18:03:46Z

189.120.189.205: Edit by Lucas: Corrections and suggestions from our last talk - Removed Kaushik's name

This [https://arxiv.org/abs/1907.11630 example protocol (1)] implements the task of [[Entanglement Routing]]. They develop routing protocols considering different types of path discovery algorithm considering a: '''continuous''' model in which entanglement between a subset of the nodes is produced continuously in the background and an '''on-demand''' model where entanglement production start when a request is made. Their protocols work on any network topology but are analyzed in the ring, grid and recursively generated network topology. Their quantum repeater nodes have local state information of the other nodes states.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].
==Assumptions==

* Each quantum repeater node is equipped with:
** Quantum memories that can store a small number of qubits for some predefined time.
** Entanglement sources.
** Ability to perform Entanglement Swapping between any pair of qubits of the network
** Classical computing resources and communication interface.
* Each quantum repeater node is aware of the overall network topology and have local state information of the other nodes states.

==Outline==

In [https://arxiv.org/abs/1907.11630 (1)] they develop routing algorithms with the goal of minimizing the latency of the network to serve a request to create entanglement between two distant nodes in the network. They consider two models for the operation of the quantum network: a '''continuous''' model, in which entanglement between a subset of the nodes is
produced continuously in the background that in principle allows the rapid creation of entanglement between distant nodes using the already pre-generated entanglement pairs and a '''on-demand''' model, where entanglement production does not commence before a request is made. Their distributed routing algorithm is studied considering three different path discovery algorithms: Modified Greedy Routing, Local Best Effort Routing and NoN Local Best Effort Routing. All of these strategies are simulated on the ring, grid and recursively generated network topology.

==Notation==

* Quantum network with topology described by two graphs:
* A '''physical''' graph <math>G_{ph}=(V,E_{ph})</math>
** <math>V</math> represent quantum repeater nodes that can hold a small number of qubits.
** <math>E_{ph}</math> correspond to physical communication channels between nodes.
* A '''virtual''' graph <math>\mathcal{G}=(V,\mathcal{E})</math>
** <math>\mathcal{E}</math> represent ''virtual links'', nodes that are not physically connected but share entanglement.
* <math>D</math> is a <math>|V|\times|V|</math> matrix representing the demands
** <math>D_{i,j}</math> denotes the number of entangled links the source node <math>i \in V</math> wants to share with destination node <math>j \in V</math> at a specific point in time.
* <math>cap</math> denotes the maximum number of entangled links any two neighbour nodes <math>u</math> and <math>v</math> can share simultaneously.
* The ''average latency (AL)'' is defined as:
* <math>AL = \frac{1}{|D|} \sum_{i,j} T_{A,i,j}</math>, where
** <math>|D|</math> denotes the number of non-zero entries in <math>D</math>
** <math>T_{A,i,j}</math> denotes the latency that a routing algorithm <math>\mathcal{A}</math> takes to distribute <math>D_{i,j}</math> entangled link between the nodes <math>i</math> and <math>j</math>.




==Protocol Description==

* All of the three routing algorithms are used as a subroutine (<math>\mathbf{PathDisc}</math>) of '''Algorithm 1'''.
* The entire routing procedure between any two nodes can be subdivided into following three phases:
# Path discovery phase.
# Entanglement reservation phase.
# Entanglement distribution phase.

'''Algorithm 1''' - Distributed Routing Algorithm <math>(s, e, \mathcal{G}, D, cap)</math>
# <math>round = \lceil \frac{D_{s,e}}{cap} \rceil</math>
# <math>i = 1</math>
# '''while''' <math> i \leq round</math> '''do'''
## <math>CommPath_{s,e} = \mathbf{PathDisc}(s, e, \mathcal{G}, D_{s,e})</math>
## <math>CommPath_{s,e} = \{ s=u_0, u_1,...,u_{d-1} = e\}</math>
## '''if''' in <math>CommPath_{s,e}</math> some of the neighbour nodes do not have enough entangled links '''then'''
### Generate all the missing links
## '''else'''
### <math>j=1</math>
### '''while''' <math>j \leq d-2</math> '''do'''
#### <math>EntSwap(u_0,u_j,j_{j+1})</math>
#### j = j + 1
### dem = dem - cap
### i = i + 1

* During the path discovery phase (<math>\mathbf{PathDisc}</math>) each node decides the next hop on the basis of the physical graph topology and the information it has about the shared entangled links with its neighbours.
* In this phase given a demand <math>D_{v,e}</math> if <math>v</math> is an optimal neighbour of <math>u</math> to reach a destination node <math>e</math> then the routing algorithm has three options:
** (1) Select the path via <math>v</math> and generate sufficient amount of links between <math>u, v</math> - see '''Algorithm 2 - Modified Greedy'''
** (2) Try to select another neighbour with whom it already shares enough amount of entangled links - see '''Algorithm 3 - Local Best Effort'''
** (3) (2) + Assume that the quantum repeater nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph - see '''Algorithm 4 - NoN Local Best Effort'''.

==Properties==

* Various simulations of these protocols are presented in [https://arxiv.org/abs/1907.11630 (1)] comparing the [https://dl.acm.org/doi/abs/10.1145/335305.335325 classical greedy routing algorithm] and algorithms 2, 3 and 4 considering the continuous and on-demand model of the network with multiple sources of destinations pairs in the Ring and Grid topology.

* The main differences between the approaches in [https://arxiv.org/abs/1801.02020 2] and [https://arxiv.org/abs/1610.05238 3], and this paper is that in this model they put an upper bound on the distance (relative to the physical graph) of a pre-shared entangled link and put an upper bound on the storage time of the entangled link in a quantum memory making the model more realistic.

==Further Information==

* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)] introduce and formalize some of the concepts presented in this work.
* In [[Routing Entanglement in the Quantum Internet]] Pant et al., proposed a greedy multi-path routing algorithm for distributing entanglement between a source destination pair in a network. Multi-path routing algorithms are useful for sharing entangled links between a source destination pair. However, this type of approach is not scalable for a larger network with multiple demands.

==References==
# [https://arxiv.org/abs/1907.11630 Chakraborty et al. (2019)]
# [https://arxiv.org/abs/1801.02020 Gyongyosi and Imre (2018)]
# [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)]


<div style='text-align: right;'>''Contributed by Lucas Arenstein during the QOSF Mentorship Program''</div>
<div style='text-align: right;'>''Mentor: Shraddha Singh</div>

Routing Entanglement in the Quantum Internet

2022-01-06T18:03:14Z

189.120.189.205: Edit by Lucas: Corrections and suggestions from our last talk - Removed Kaushik's name

This [https://www.nature.com/articles/s41534-019-0139-x 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 ﬂow with global or local state information of the other quantum repeater nodes and a protocol for multipath routing of simultaneous entanglement ﬂows with repeaters with local state information.

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|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 <math>K</math> Source-Destination pairs.

==Outline==

In [https://www.nature.com/articles/s41534-019-0139-x.pdf (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 ﬂow:
** 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 ﬂows:
** 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 ﬂows of entanglement.

==Notation==

Quantum network with topology described by a graph <math>G(V,E)</math>:
* Each of the <math>N=|V|</math> nodes is equipped with a quantum repeater.
* Each of the <math>M=|E|</math> edges is a lossy optical channel of range <math>L_i</math> (km) and power transmissivity <math>\eta_i \propto e^{-\alpha L_i}</math>, <math>i \in E</math> and <math>\alpha</math> depends on the material of the channel.
* <math>K</math> Source-Destination pairs <math>(A_j, B_j)</math>, <math>1 \leq j \leq k</math> situated at (not necessarily distinct) nodes in <math>V</math>.
Considering this graph<math>G</math> we adopt the following notation for the repeater network.
* Each node <math>v \in V</math> is a repeater.
* Each edge <math>e \in E</math> is a physical link connecting two repeater nodes.
* <math>S(e) \in \mathbb{Z}^+</math> is an integer edge weight corresponding to the number of parallel channel across edge <math>e</math>.
* <math>\mathcal{N}(v)</math> is the set of neighbor edges of <math>v</math>
* <math>d(v) = |\mathcal{N}(v)|</math> is the degree of node <math>v</math>.
* <math>\sum_{e \in \mathcal{N}(v)} S(e)</math> is the number of memories at node <math>v</math>.
* <math>d_A</math> distance of a node to the node A, using the <math>\mathbb{L}^2</math> 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 <math>T \geq 1</math> time slot before the stored qubit completely decoheres.
* Each time slot <math>t</math>, <math>t=1,2,... </math> is divided into 2 phases:
* '''External Phase:'''
** Each of the <math>S(e)</math> pairs of memories across and edge <math>e</math> attempts to establish an EPR pair.
*:- An entanglement attempt across any one of the <math>S(e)</math> parallel links across edge <math>e</math> succeeds with probability <math>p_0(e) \sim \eta(e)</math>, where <math>\eta(e) \sim e^{-\alpha L_e}</math> 
*:- The probability that one or more ebits are established across an edge <math>e</math> is <math>p(e)=1-(1-p_0)^{S(e)}</math>.
*:- Assuming <math>S(e)=S,</math> give us <math>p(e)=p,</math> <math>\forall e \in E</math>.
** Using two-way classical communication over an edge , neighboring repeater nodes  learn which of the S(e) (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 <math>q</math>.

At the end of one time-slot a along a path comprising of <math>k</math> edges (and thus <math>(k-1)</math> repeater nodes) one ebit is successfully shared between the end points of the path with probability <math>p^k q^{k-1}</math>.

The maximum number of ebits that can be shared between node <math>a</math> and node <math>b</math> after one time-slot is <math>min\{d(a), d(b)\}</math>, assuming <math>S</math> 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 <math>K</math>.

===Multipath Routing of a Single Entanglement Flow===
'''Input:''' <math>K=1</math>, Source-Destination pair <math>(A_1, B_1)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math>.

====Protocol for Entanglement Routing with Global Link-state Information====
After the External Phase
# <math>m = 1</math>
# <math>G_m</math> = Subgraph induced by the successful external links and the repeater nodes after the external phase.
# While (True):
## <math>S_m</math> = shortest path in <math>G_m</math> connecting <math>A_1</math> with <math>B_1</math>.
## If <math>S_m</math> is empty: Break While Loop.
## Else:
### Set <math>L_m</math> as the length of <math>S_m</math>.
### Try connecting all internal links along the nodes of <math>S_m</math> <br />//successfully generating an ebit between <math>A_1</math> and <math>B_1</math> with probability <math>q^{L_m - 1}</math>
## <math>G_{m+1}</math> = <math>G_m -</math> all external and internal links of <math>S_m</math>.
## <math>m = m + 1.</math>

====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
# For every repeater except <math>A_1</math> and <math>B_1</math>: <br /> Let <math>u</math> be the node of this iteration.
## If less than one of the neighboring external links is successful: <br />Then no internal links are attempted since this repeater node can not be part of a path from <math>A_1</math> to <math>B_1</math>.
## Else If two or more neighboring external links are successful: <br />Then let <math>v</math> be the node linked to <math>u</math> with the smallest <math>d_{A_1}</math> and <math>w</math> be the node linked to <math>u</math> with the smallest <math>d_{B_1}</math>. <br /> Attempt a BSM on node <math>u</math> on the memories connected to <math>v</math> and <math>w</math>.
### Else If four neighboring external links are successful: <br /> Then attempt a BSM on node <math>u</math> on the remaining memories disconsidering the two memories from the previous step.

===Protocol for Simultaneous Entanglement Flows with Link-state Information===
'''Input:''' <math>K=2</math>, Source-Destination pairs <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

This situation motivates the '''Multi-ﬂow 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 ﬂows.
** 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 ﬂows.
** Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle <math>\theta</math> 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 (<math>K=1</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> the entanglement generation rate will depend only linearly on the transmissivity <math>\eta</math> of a single link in the network.
* Maximum rate regions simultaneously achievable by the entanglement flows (<math>K \geq 2</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> this protocol signiﬁcantly exceeds the ones that each repeater node makes BSM decisions by simply time-sharing between catering to the individual ﬂows.

==Further Information==


* [https://arxiv.org/abs/1601.00966 Pirandola (2016)] analyzed entanglement-generation capacities of repeater networks assuming ideal repeater nodes and argued that for a single ﬂow the maximum entanglement-generation rate <math>R_1</math> reduces to the classical max-ﬂow min-cut problem.
* [https://arxiv.org/abs/1606.00135 Azuma and Kato (2016)] looked at an "aggregated" protocol in which the repeater protocols run in parallel.
* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)] developed routing protocols on speciﬁc 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.
* [https://arxiv.org/abs/quant-ph/0612167 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:
[https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.81.5932 Briegel et al. (1998)], [https://arxiv.org/abs/0809.3629 Jiand et al. (2008)] and [https://www.nature.com/articles/srep20463 Muralidharan et al. (2016)].
==References==

# [https://www.nature.com/articles/s41534-019-0139-x Pant et al. (2019)]


<div style='text-align: right;'>''Contributed by Lucas Arenstein during the QOSF Mentorship Program''</div>
<div style='text-align: right;'>''Mentor: Shraddha Singh</div>

Entanglement Routing

2022-01-06T18:02:07Z

189.120.189.205: Edit by Lucas: Corrections and suggestions from our last talk.

==Functionality Description==
Entanglement routing allows a quantum network to generate long distance entanglement between two or multiple nodes. A Quantum router is a device used to transmit quantum information over long distances along a quantum network using entanglement swapping between routers. As quantum information transmissivity decays exponentially in function of the distance, quantum routers are needed to successfully establish entangled states between any nodes on the quantum network.

There are entanglement routing protocols that are specifically designed for certain network topology e.g: linear, rings, spheres, grids, recursively generated network or for networks with arbitrary topology.

The main goal of entanglement routing is to develop efficient routing protocols to enable long distance entanglement.

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].





==Use Case==
*No classical analogue.

==Protocols==

* Almost all of the protocols within this functionality are in the [[:Category: Quantum Memory Network Stage|Quantum Memory Network Stage]].
Entanglement routing protocol:
* [[Routing Entanglement in the Quantum Internet]]
* [[Distributed Routing in a Quantum Internet]]

Related protocol:
* [[Distributing Graph States Over Arbitrary Quantum Networks]]

==Properties==

* Entanglement routing assumes the presence of:
** Classical and quantum communication physical channels.
** Quantum repeater nodes.
* Quantum repeater nodes:
** Contain qubits that in the short and medium term are applicable to only basic operations i.e, Bell State Measurements to pairs of neighborhood nodes allowing the Entanglement Swapping operation.
** Have global (all the network) or local (just neighborhood) information on the state of other nodes.
* Some protocols consider fault-tolerant operations on the nodes but other use [https://en.wikipedia.org/wiki/Entanglement_distillation Entanglement Distillation] or Error Corrections schemes on the repeater nodes [https://www.nature.com/articles/s41534-021-00438-7 5].

==Further Information==

All of the approaches below were based on the specific structure of the physical graphs and manipulation of multi-partite entangled states. However, with current day technologies, these solutions are very difficult to realize in practice.

* Distributing entanglement in a simple chain network:
** For a review: [https://ieeexplore.ieee.org/document/7010905 Munro et al. (2015)]
** [https://arxiv.org/abs/0705.4128 Meter et al. (2009)]
** [https://arxiv.org/abs/0808.2972 Goebel et al. (2008)]
** [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.81.5932 Briegel et al. (1998)]

* Distributing entanglement from a percolation theory point of view:
** [https://arxiv.org/abs/1209.5303 Perseguers et al. (2013)]
** [https://www.nature.com/articles/nphys549 Acín et al. (2007)]
** [https://arxiv.org/abs/0906.1622 Broadfoot et al. (2009)]

* Distributing Entanglements in a noisy network using the concept of quantum network coding:

** [https://arxiv.org/abs/0910.4074 Fowler et al. (2010)]
** [https://arxiv.org/abs/0910.1459 Perseguers (2010)]
** [https://arxiv.org/abs/1202.4077 Cavalcanti and Kwek (2012)]
** [https://arxiv.org/abs/1202.1016 Mazurek et al. (2014)]

The routing approaches below are based on classical techniques and these are arguably more likely to be implemented with the near future quantum technology.
In all of these approaches, first, the nodes discover a path from a source to a destination and then distribute the entangled links along the path. The difference between these approaches comes from the path selection algorithms.
* [https://ieeexplore.ieee.org/document/8068178 Caleffi (2017)]
* [https://arxiv.org/abs/1801.02020 Gyongyosi and Imre (2018)]
* [https://arxiv.org/abs/1206.5655 Meter et al. (2013)]
* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)]

Example of optimization metrics of Entanglement Routing Protocols:
* In [[Routing Entanglement in the Quantum Internet]] their goal is to maximize the rate regions simultaneously achievable by the entanglement flows
* In [[Distributed Routing in a Quantum Internet]] their objective is to minimize the latency of the network to serve a request to create entanglement between two distant nodes in the network.
* In [https://ieeexplore.ieee.org/document/9210823 Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach - Chakraborty et al. (2020)] they consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs.

Other Works:
* In [https://arxiv.org/abs/1601.00966 Capacities of repeater-assisted quantum communications - Pirandola (2016)] analyzed entanglement-generation capacities of repeater networks assuming ideal repeater nodes and argued that for a single ﬂow the maximum entanglement-generation rate <math>R_1</math> reduces to the classical max-ﬂow min-cut problem.
* In [https://arxiv.org/abs/1510.08863 Fundamental Limits of Repeaterless Quantum Communications - Pirandola et al. (2015)] provides precise and general benchmarks for quantum repeaters.

==References==
# [https://arxiv.org/abs/1610.05238 Schoute et al. Shortcuts to Quantum Network Routing (2016)]
# [https://arxiv.org/abs/1907.11630 Chakraborty et al. (2019)] - [[Distributed Routing in a Quantum Internet]]
# [https://www.nature.com/articles/s41534-019-0139-x Pant et al. Routing entanglement in the quantum internet (2019)] - [[Routing Entanglement in the Quantum Internet]]
# [https://dl.acm.org/doi/10.1145/3387514.3405853 Shi and Qian, Concurrent Entanglement Routing for Quantum Networks: Model and Designs (2020)]
# [https://www.nature.com/articles/s41534-021-00438-7 Rozpędek et al. Quantum repeaters based on concatenated bosonic and discrete-variable quantum codes (2021)]


<div style='text-align: right;'>''Contributed by Lucas Arenstein during the QOSF Mentorship Program''</div>
<div style='text-align: right;'>''Mentor: Shraddha Singh - Reviewer: Kaushik Chakraborty </div>

Protocol Library

2022-01-06T13:31:16Z

189.120.189.205: Edit by Lucas: Just changed the order of 2 protocols on the entanglement routing functionality

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="7"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Auth-QFT-Auth Scheme for Quantum Authentication]]
|-
|[[Unitary Design Scheme for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|rowspan="4"|[[Verification of Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of NP-complete problems]]
|-
|[[Verification of Sub-Universal Quantum Computation]]
|-
|[[Classical Verification of Universal Quantum Computation]]
|-
|rowspan="5"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
|[[Practical Quantum Electronic Voting]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="3"|[[Entanglement Routing]]||[[Distributed Routing in a Quantum Internet]]
|-
|[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]
|-
|rowspan="1"|[[Quantum Conference Key Agreement]]||[[Anonymous Conference Key Agreement using GHZ states]]
|-

Entanglement Routing

2021-12-22T19:49:28Z

189.120.189.205: Added more papers on the further information section based on our talk with Kaushik from his "Distributed Routing in a Quantum Internet" paper. To do: add something from Pirandola

==Functionality Description==
Entanglement routing allows a quantum network to generate long distance entanglement between two or multiple nodes. As quantum information transmissivity decays exponentially in function of the distance, quantum routers are needed to successfully establish entangled states between any nodes on a quantum network.

The main goal of entanglement routing is to develop efficient routing protocols to enable long distance entanglement.

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].





==Use Case==
*No classical analogue.

==Protocols==

* All the protocols within this functionality are in the [[:Category: Quantum Memory Network Stage|Quantum Memory Network Stage]].
* There are entanglement routing protocols that are specifically designed for certain network topology e.g: linear, rings, spheres, grids, recursively generated network or for networks with arbitrary topology.
* Quantum repeater nodes have global (all the network) or local (just neighborhood) information on the state of other nodes.

==Properties==

* Entanglement routing assumes the presence of:
** Classical and quantum communication physical channels.
** Quantum repeater nodes.
* Quantum repeater nodes:
** Contain qubits that in the short and medium term are applicable to only basic operations i.e, Bell State Measurements to pairs of neighborhood nodes allowing the Entanglement Swapping operation.
* Some protocols consider fault-tolerant operations on the nodes but other use [https://en.wikipedia.org/wiki/Entanglement_distillation Entanglement Distillation] or Error Corrections schemes on the repeater nodes [https://www.nature.com/articles/s41534-021-00438-7 5].

==Further Information==




All of the approaches below were based on the specific structure of the physical graphs and manipulation of multi-partite entangled states. However, with current day technologies, these solutions are very difficult to realize in practice.

* Distributing entanglement in a simple chain network:
** For a review: [https://ieeexplore.ieee.org/document/7010905 Munro et al. (2015)]
** [https://arxiv.org/abs/0705.4128 Meter et al. (2009)]
** [https://arxiv.org/abs/0808.2972 Goebel et al. (2008)]
** [https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.81.5932 Briegel et al. (1998)]

* Distributing entanglement from a percolation theory point of view:
** [https://arxiv.org/abs/1209.5303 Perseguers et al. (2013)]
** [https://www.nature.com/articles/nphys549 Acín et al. (2007)]
** [https://arxiv.org/abs/0906.1622 Broadfoot et al. (2009)]

* Distributing Entanglements in a noisy network using the concept of quantum network coding:

** [https://arxiv.org/abs/0910.4074 Fowler et al. (2010)]
** [https://arxiv.org/abs/0910.1459 Perseguers (2010)]
** [https://arxiv.org/abs/1202.4077 Cavalcanti and Kwek (2012)]
** [https://arxiv.org/abs/1202.1016 Mazurek et al. (2014)]

The routing approaches below are based on classical techniques and these are arguably more likely to be implemented with the near future quantum technology.
In all of these approaches, first, the nodes discover a path from a source to a destination and then distribute the entangled links along the path. The difference between these approaches comes from the path selection algorithms.
* [https://ieeexplore.ieee.org/document/8068178 Caleffi (2017)]
* [https://arxiv.org/abs/1801.02020 Gyongyosi and Imre (2018)]
* [https://arxiv.org/abs/1206.5655 Meter et al. (2013)]
* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)]

Example of optimization metrics of Entanglement Routing Protocols:
* In [[Routing Entanglement in the Quantum Internet]] their goal is to maximize the rate regions simultaneously achievable by the entanglement flows
* In [[Distributed Routing in a Quantum Internet]] their objective is to minimize the latency of the network to serve a request to create entanglement between two distant nodes in the network.
* In [https://ieeexplore.ieee.org/document/9210823 Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach - Chakraborty et al. (2020)] they consider the problem of optimizing the achievable EPR-pair distribution rate between multiple source-destination pairs.

==References==
# [https://arxiv.org/abs/1610.05238 Schoute et al. Shortcuts to Quantum Network Routing (2016)]
# [https://arxiv.org/abs/1907.11630 Chakraborty et al. (2019)] - [[Distributed Routing in a Quantum Internet]]
# [https://www.nature.com/articles/s41534-019-0139-x Pant et al. Routing entanglement in the quantum internet (2019)] - [[Routing Entanglement in the Quantum Internet]]
# [https://dl.acm.org/doi/10.1145/3387514.3405853 Shi and Qian, Concurrent Entanglement Routing for Quantum Networks: Model and Designs (2020)]
# [https://www.nature.com/articles/s41534-021-00438-7 Rozpędek et al. Quantum repeaters based on concatenated bosonic and discrete-variable quantum codes (2021)]

<div style='text-align: right;'>''contributed by Shraddha Singh and Lucas Arenstein''</div>

Protocol Library

2021-12-22T19:04:04Z

189.120.189.205: Added the Distributed Routing in a Quantum Internet hyperlink

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="5"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|rowspan="4"|[[Verification of Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of NP-complete problems]]
|-
|[[Verification of Sub-Universal Quantum Computation]]
|-
|[[Classical Verification of Universal Quantum Computation]]
|-
|rowspan="5"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
|[[Practical Quantum Electronic Voting]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="3"|[[Entanglement Routing]]||[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributed Routing in a Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]

Distributed Routing in a Quantum Internet

2021-12-22T19:02:06Z

189.120.189.205: First version of the page made by Lucas.

This [https://arxiv.org/abs/1907.11630 example protocol (1)] implements the task of [[Entanglement Routing]]. They develop routing protocols considering different types of path discovery algorithm considering a: '''continuous''' model in which entanglement between a subset of the nodes is produced continuously in the background and an '''on-demand''' model where entanglement production start when a request is made. Their protocols work on any network topology but are analyzed in the ring, grid and recursively generated network topology. Their quantum repeater nodes have local state information of the other nodes states.


'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].
==Assumptions==

* Each quantum repeater node is equipped with:
** Quantum memories that can store a small number of qubits for some predefined time.
** Entanglement sources.
** Ability to perform Entanglement Swapping between any pair of qubits of the network
** Classical computing resources and communication interface.
* Each quantum repeater node is aware of the overall network topology and have local state information of the other nodes states.

==Outline==

In [https://arxiv.org/abs/1907.11630 (1)] they develop routing algorithms with the goal of minimizing the latency of the network to serve a request to create entanglement between two distant nodes in the network. They consider two models for the operation of the quantum network: a '''continuous''' model, in which entanglement between a subset of the nodes is
produced continuously in the background that in principle allows the rapid creation of entanglement between distant nodes using the already pre-generated entanglement pairs and a '''on-demand''' model, where entanglement production does not commence before a request is made. Their distributed routing algorithm is studied considering three different path discovery algorithms: Modified Greedy Routing, Local Best Effort Routing and NoN Local Best Effort Routing. All of these strategies are simulated on the ring, grid and recursively generated network topology.

==Notation==

* Quantum network with topology described by two graphs:
* A '''physical''' graph <math>G_{ph}=(V,E_{ph})</math>
** <math>V</math> represent quantum repeater nodes that can hold a small number of qubits.
** <math>E_{ph}</math> correspond to physical communication channels between nodes.
* A '''virtual''' graph <math>\mathcal{G}=(V,\mathcal{E})</math>
** <math>\mathcal{E}</math> represent ''virtual links'', nodes that are not physically connected but share entanglement.
* <math>D</math> is a <math>|V|\times|V|</math> matrix representing the demands
** <math>D_{i,j}</math> denotes the number of entangled links the source node <math>i \in V</math> wants to share with destination node <math>j \in V</math> at a specific point in time.
* <math>cap</math> denotes the maximum number of entangled links any two neighbour nodes <math>u</math> and <math>v</math> can share simultaneously.
* The ''average latency (AL)'' is defined as:
* <math>AL = \frac{1}{|D|} \sum_{i,j} T_{A,i,j}</math>, where
** <math>|D|</math> denotes the number of non-zero entries in <math>D</math>
** <math>T_{A,i,j}</math> denotes the latency that a routing algorithm <math>\mathcal{A}</math> takes to distribute <math>D_{i,j}</math> entangled link between the nodes <math>i</math> and <math>j</math>.




==Protocol Description==

* All of the three routing algorithms are used as a subroutine (<math>\mathbf{PathDisc}</math>) of '''Algorithm 1'''.
* The entire routing procedure between any two nodes can be subdivided into following three phases:
# Path discovery phase.
# Entanglement reservation phase.
# Entanglement distribution phase.

'''Algorithm 1''' - Distributed Routing Algorithm <math>(s, e, \mathcal{G}, D, cap)</math>
# <math>round = \lceil \frac{D_{s,e}}{cap} \rceil</math>
# <math>i = 1</math>
# '''while''' <math> i \leq round</math> '''do'''
## <math>CommPath_{s,e} = \mathbf{PathDisc}(s, e, \mathcal{G}, D_{s,e})</math>
## <math>CommPath_{s,e} = \{ s=u_0, u_1,...,u_{d-1} = e\}</math>
## '''if''' in <math>CommPath_{s,e}</math> some of the neighbour nodes do not have enough entangled links '''then'''
### Generate all the missing links
## '''else'''
### <math>j=1</math>
### '''while''' <math>j \leq d-2</math> '''do'''
#### <math>EntSwap(u_0,u_j,j_{j+1})</math>
#### j = j + 1
### dem = dem - cap
### i = i + 1

* During the path discovery phase (<math>\mathbf{PathDisc}</math>) each node decides the next hop on the basis of the physical graph topology and the information it has about the shared entangled links with its neighbours.
* In this phase given a demand <math>D_{v,e}</math> if <math>v</math> is an optimal neighbour of <math>u</math> to reach a destination node <math>e</math> then the routing algorithm has two options:
** (1) Select the path via <math>v</math> and generate sufficient amount of links between <math>u, v</math> - see '''Algorithm 2 - Modified Greedy'''
** (2) Vertex <math>u</math> try to select another neighbour with whom it already shares enough amount of entangled links - see '''Algorithm 3 - Local Best Effort'''

* Analyzing Algorithm 3 under the assumption that the quantum repeater nodes have information about its neighbours as well as the neighbours of the neighbours in the virtual graph is '''Algorithm 4 - NoN Local Best Effort'''.

==Properties==

* Various simulations of these protocols are presented in [https://arxiv.org/abs/1907.11630 (1)] comparing the [https://dl.acm.org/doi/abs/10.1145/335305.335325 classical greedy routing algorithm] and algorithms 2, 3 and 4 considering the continuous and on-demand model of the network with multiple sources of destinations pairs in the Ring and Grid topology.

* The main differences between the approaches in [https://arxiv.org/abs/1801.02020 2] and [https://arxiv.org/abs/1610.05238 3], and this paper is that in this model they put an upper bound on the distance (relative to the physical graph) of a pre-shared entangled link and put an upper bound on the storage time of the entangled link in a quantum memory making the model more realistic.

==Further Information==

* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)] introduce and formalize some of the concepts presented in this work.
* In [[Routing Entanglement in the Quantum Internet]] Pant et al., proposed a greedy multi-path routing algorithm for distributing entanglement between a source destination pair in a network. Multi-path routing algorithms are useful for sharing entangled links between a source destination pair. However, this type of approach is not scalable for a larger network with multiple demands.

==References==
# [https://arxiv.org/abs/1907.11630 Chakraborty et al. (2019)]
# [https://arxiv.org/abs/1801.02020 Gyongyosi and Imre (2018)]
# [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)]

<div style='text-align: right;'>''contributed by Lucas Arenstein''</div>

Routing Entanglement in the Quantum Internet

2021-12-20T18:51:05Z

189.120.189.205: Updated the terminology to match/agree with the newest protocol page I'm doing (I will finish the new one in the next couple of days)

This [https://www.nature.com/articles/s41534-019-0139-x 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 ﬂow with global or local state information of the other quantum repeater nodes and a protocol for multipath routing of simultaneous entanglement ﬂows with repeaters with local state information.

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|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 <math>K</math> Source-Destination pairs.

==Outline==

In [https://www.nature.com/articles/s41534-019-0139-x.pdf (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 ﬂow:
** 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 ﬂows:
** 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 ﬂows of entanglement.

==Notation==

Quantum network with topology described by a graph <math>G(V,E)</math>:
* Each of the <math>N=|V|</math> nodes is equipped with a quantum repeater.
* Each of the <math>M=|E|</math> edges is a lossy optical channel of range <math>L_i</math> (km) and power transmissivity <math>\eta_i \propto e^{-\alpha L_i}</math>, <math>i \in E</math> and <math>\alpha</math> depends on the material of the channel.
* <math>K</math> Source-Destination pairs <math>(A_j, B_j)</math>, <math>1 \leq j \leq k</math> situated at (not necessarily distinct) nodes in <math>V</math>.
Considering this graph<math>G</math> we adopt the following notation for the repeater network.
* Each node <math>v \in V</math> is a repeater.
* Each edge <math>e \in E</math> is a physical link connecting two repeater nodes.
* <math>S(e) \in \mathbb{Z}^+</math> is an integer edge weight corresponding to the number of parallel channel across edge <math>e</math>.
* <math>\mathcal{N}(v)</math> is the set of neighbor edges of <math>v</math>
* <math>d(v) = |\mathcal{N}(v)|</math> is the degree of node <math>v</math>.
* <math>\sum_{e \in \mathcal{N}(v)} S(e)</math> is the number of memories at node <math>v</math>.
* <math>d_A</math> distance of a node to the node A, using the <math>\mathbb{L}^2</math> 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 <math>T \geq 1</math> time slot. After this time the stored qubit completely decoheres.
* Each time slot <math>t</math>, <math>t=1,2,... </math> is divided into 2 phases:
* '''External Phase:'''
** Each of the <math>S(e)</math> pairs of memories across and edge <math>e</math> attempts to establish an EPR pair.
*:- An entanglement attempt across any one of the <math>S(e)</math> parallel links across edge <math>e</math> succeeds with probability <math>p_0(e) \sim \eta(e)</math>, where <math>\eta(e) \sim e^{-\alpha L_e}</math> is the transmissivity of a lossy optical channel of length <math>L(e)</math>.
*:- The probability that one or more ebits are established across an edge <math>e</math> is <math>p(e)=1-(1-p_0)^{S(e)}</math>.
*:- Assuming <math>S(e)=S,</math> give us <math>p(e)=p,</math> <math>\forall e \in E</math>.
** Using two-way classical communication over edge <math>e(u, v)</math>, neighboring repeater nodes <math>u, v</math> 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 <math>q</math>.

At the end of one time-slot a along a path comprising of <math>k</math> edges (and thus <math>(k-1)</math> repeater nodes) one ebit is successfully shared between the end points of the path with probability <math>p^k q^{k-1}</math>.

The maximum number of ebits that can be shared between node <math>a</math> and node <math>b</math> after one time-slot is <math>min\{d(a), d(b)\}</math>, assuming <math>S</math> 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 <math>K</math>.

===Multipath Routing of a Single Entanglement Flow===
'''Input:''' <math>K=1</math>, Source-Destination pair <math>(A_1, B_1)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math>.

====Protocol for Entanglement Routing with Global Link-state Information====
After the External Phase
# <math>m = 1</math>
# <math>G_m</math> = Subgraph induced by the successful external links and the repeater nodes after the external phase.
# While (True):
## <math>S_m</math> = shortest path in <math>G_m</math> connecting <math>A_1</math> with <math>B_1</math>.
## If <math>S_m</math> is empty: Break While Loop.
## Else:
### Set <math>L_m</math> as the length of <math>S_m</math>.
### Try connecting all internal links along the nodes of <math>S_m</math> <br />//successfully generating an ebit between <math>A_1</math> and <math>B_1</math> with probability <math>q^{L_m - 1}</math>
## <math>G_{m+1}</math> = <math>G_m -</math> all external and internal links of <math>S_m</math>.
## <math>m = m + 1.</math>

====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
# For every repeater except <math>A_1</math> and <math>B_1</math>: <br /> Let <math>u</math> be the node of this iteration.
## If less than one of the neighboring external links is successful: <br />no internal links are attempted since this repeater node can not be part of a path from <math>A_1</math> to <math>B_1</math>.
## If two or more neighboring external links are successful: <br /> Let <math>v</math> be the node linked to <math>u</math> with the smallest <math>d_{A_1}</math> and <math>w</math> be the node linked to <math>u</math> with the smallest <math>d_{B_1}</math>. <br /> Attempt a BSM on node <math>u</math> on the memories connected to <math>v</math> and <math>w</math>.
### If four neighboring external links are successful: <br /> Attempt a BSM on node <math>u</math> on the remaining memories disconsidering the two memories from the previous step.

===Protocol for Simultaneous Entanglement Flows with Link-state Information===
'''Input:''' <math>K=2</math>, Source-Destination pairs <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

This situation motivates the '''Multi-ﬂow 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 ﬂows.
** 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 ﬂows.
** Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle <math>\theta</math> 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 (<math>K=1</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> the entanglement generation rate will depend only linearly on the transmissivity <math>\eta</math> of a single link in the network.
* Maximum rate regions simultaneously achievable by the entanglement flows (<math>K \geq 2</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> this protocol signiﬁcantly exceeds the ones that each repeater node makes BSM decisions by simply time-sharing between catering to the individual ﬂows.

==Further Information==


* [https://arxiv.org/abs/1601.00966 Pirandola (2016)] analyzed entanglement-generation capacities of repeater networks assuming ideal repeater nodes and argued that for a single ﬂow the maximum entanglement-generation rate <math>R_1</math> reduces to the classical max-ﬂow min-cut problem.
* [https://arxiv.org/abs/1606.00135 Azuma and Kato (2016)] looked at an "aggregated" protocol in which the repeater protocols run in parallel.
* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)] developed routing protocols on speciﬁc 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.
* [https://arxiv.org/abs/quant-ph/0612167 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:
[https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.81.5932 Briegel et al. (1998)], [https://arxiv.org/abs/0809.3629 Jiand et al. (2008)] and [https://www.nature.com/articles/srep20463 Muralidharan et al. (2016)].
==References==

# [https://www.nature.com/articles/s41534-019-0139-x Pant et al. (2019)]

<div style='text-align: right;'>''*contributed by Lucas Arenstein''</div>

Entanglement Routing

2021-12-11T16:50:38Z

189.120.189.205: Add some references and their correspondence to the network topology.

Routing Entanglement in the Quantum Internet

2021-12-11T16:34:41Z

189.120.189.205: Added the introduction, a small edit in the protocol description, the Properties and Further Information section.

This [https://www.nature.com/articles/s41534-019-0139-x 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 ﬂow with global or local state information of the other quantum repeater nodes and a protocol for multipath routing of simultaneous entanglement ﬂows with repeaters with local state information.

'''Tags:''' [[:Category: Multi Party Protocols|Multi Party]], [[:Category: Specific Task|Specific Task]].



==Assumptions==

* Each network repeater node 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 network repeater node is aware of the overall network topology, as well as the locations of the <math>K</math> Source-Destination pairs.

==Outline==

In [https://www.nature.com/articles/s41534-019-0139-x.pdf 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 ﬂow:
** 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 ﬂows:
** 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 ﬂows of entanglement.

==Notation==

Quantum network with topology described by a graph <math>G(V,E)</math>:
* Each of the <math>N=|V|</math> nodes is equipped with a quantum repeater.
* Each of the <math>M=|E|</math> edges is a lossy optical channel of range <math>L_i</math> (km) and power transmissivity <math>\eta_i \propto e^{-\alpha L_i}</math>, <math>i \in E</math> and <math>\alpha</math> depends on the material of the channel.
* <math>K</math> Source-Destination pairs <math>(A_j, B_j)</math>, <math>1 \leq j \leq k</math> situated at (not necessarily distinct) nodes in <math>V</math>.
Considering this graph<math>G</math> we adopt the following notation for the repeater network.
* Each node <math>v \in V</math> is a repeater.
* Each edge <math>e \in E</math> is a physical link connecting two repeater nodes.
* <math>S(e) \in \mathbb{Z}^+</math> is an integer edge weight corresponding to the number of parallel channel across edge <math>e</math>.
* <math>\mathcal{N}(v)</math> is the set of neighbor edges of <math>v</math>
* <math>d(v) = |\mathcal{N}(v)|</math> is the degree of node <math>v</math>.
* <math>\sum_{e \in \mathcal{N}(v)} S(e)</math> is the number of memories at node <math>v</math>.
* <math>d_A</math> distance of a node to the node A, using the <math>\mathbb{L}^2</math> 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 <math>T \geq 1</math> time slot. After this time the stored qubit completely decoheres.
* Each time slot <math>t</math>, <math>t=1,2,... </math> is divided into 2 phases:
* '''External Phase:'''
** Each of the <math>S(e)</math> pairs of memories across and edge <math>e</math> attempts to establish an EPR pair.
*:- An entanglement attempt across any one of the <math>S(e)</math> parallel links across edge <math>e</math> succeeds with probability <math>p_0(e) \sim \eta(e)</math>, where <math>\eta(e) \sim e^{-\alpha L_e}</math> is the transmissivity of a lossy optical channel of length <math>L(e)</math>.
*:- The probability that one or more ebits are established across an edge <math>e</math> is <math>p(e)=1-(1-p_0)^{S(e)}</math>.
*:- Assuming <math>S(e)=S,</math> give us <math>p(e)=p,</math> <math>\forall e \in E</math>.
** Using two-way classical communication over edge <math>e(u, v)</math>, neighboring repeater nodes <math>u, v</math> 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 <math>q</math>.

At the end of one time-slot a along a path comprising of <math>k</math> edges (and thus <math>(k-1)</math> repeater nodes) one ebit is successfully shared between the end points of the path with probability <math>p^k q^{k-1}</math>.

The maximum number of ebits that can be shared between node <math>a</math> and node <math>b</math> after one time-slot is <math>min\{d(a), d(b)\}</math>, assuming <math>S</math> 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 <math>K</math>.

===Multipath Routing of a Single Entanglement Flow===
'''Input:''' <math>K=1</math>, Source-Destination pair <math>(A_1, B_1)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math>.

====Protocol for Entanglement Routing with Global Link-state Information====
After the External Phase
# <math>m = 1</math>
# <math>G_m</math> = Subgraph induced by the successful external links and the repeater nodes after the external phase.
# While (True):
## <math>S_m</math> = shortest path in <math>G_m</math> connecting <math>A_1</math> with <math>B_1</math>.
## If <math>S_m</math> is empty: Break While Loop.
## Else:
### Set <math>L_m</math> as the length of <math>S_m</math>.
### Try connecting all internal links along the nodes of <math>S_m</math> <br />//successfully generating an ebit between <math>A_1</math> and <math>B_1</math> with probability <math>q^{L_m - 1}</math>
## <math>G_{m+1}</math> = <math>G_m -</math> all external and internal links of <math>S_m</math>.
## <math>m = m + 1.</math>

====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
# For every repeater except <math>A_1</math> and <math>B_1</math>: <br /> Let <math>u</math> be the node of this iteration.
## If less than one of the neighboring external links is successful: <br />no internal links are attempted since this repeater node can not be part of a path from <math>A_1</math> to <math>B_1</math>.
## If two or more neighboring external links are successful: <br /> Let <math>v</math> be the node linked to <math>u</math> with the smallest <math>d_{A_1}</math> and <math>w</math> be the node linked to <math>u</math> with the smallest <math>d_{B_1}</math>. <br /> Attempt a BSM on node <math>u</math> on the memories connected to <math>v</math> and <math>w</math>.
### If four neighboring external links are successful: <br /> Attempt a BSM on node <math>u</math> on the remaining memories disconsidering the two memories from the previous step.

===Protocol for Simultaneous Entanglement Flows with Link-state Information===
'''Input:''' <math>K=2</math>, Source-Destination pairs <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

This situation motivates the '''Multi-ﬂow 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 ﬂows.
** 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 ﬂows.
** Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle <math>\theta</math> 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 (<math>K=1</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> the entanglement generation rate will depend only linearly on the transmissivity <math>\eta</math> of a single link in the network.
* Maximum rate regions simultaneously achievable by the entanglement flows (<math>K \geq 2</math>).
*:- Above a (percolation) threshold determined by <math>p</math> and <math>q</math> this protocol signiﬁcantly exceeds the ones that each repeater node makes BSM decisions by simply time-sharing between catering to the individual ﬂows.

==Further Information==


* [https://arxiv.org/abs/1601.00966 Pirandola (2016)] analyzed entanglement-generation capacities of repeater networks assuming ideal repeater nodes and argued that for a single ﬂow the maximum entanglement-generation rate <math>R_1</math> reduces to the classical max-ﬂow min-cut problem.
* [https://arxiv.org/abs/1606.00135 Azuma and Kato (2016)] looked at an "aggregated" protocol in which the repeater protocols run in parallel.
* [https://arxiv.org/abs/1610.05238 Schoute et al. (2016)] developed routing protocols on speciﬁc 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.
* [https://arxiv.org/abs/quant-ph/0612167 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:
[https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.81.5932 Briegel et al. (1998)], [https://arxiv.org/abs/0809.3629 Jiand et al. (2008)] and [https://www.nature.com/articles/srep20463 Muralidharan et al. (2016)].
==References==

# [https://www.nature.com/articles/s41534-019-0139-x Pant et al. (2019)]

<div style='text-align: right;'>''*contributed by Lucas Arenstein''</div>

Distributing Graph States Over Arbitrary Quantum Networks

2021-12-11T12:37:55Z

189.120.189.205: Added the properties part. I'm going to send the images by email/slack

Under construction [https://arxiv.org/abs/1811.05445 Meignant, Markham and Grosshans (2019)]

'''Tags:'''[[:Category:Specific Task|Specific Task]]

==Assumptions==
* Perfect distribution of Bell pairs occurring at perfectly synchronized times.
* Perfect node local computation.
* Ignore the cost of classical communications.
* Ignore processing time of local quantum processor.
* Ignore the cost of quantum memory.

==Outline==
The protocol [https://arxiv.org/abs/1811.05445 1] aims to distribute multipartite entangled states that are represented by graph states over fixed networks of arbitrary topology. They first introduce a protocol to distribute GHZ states that considering the assumptions takes a single time step and is optimal in terms of the Bell pair used. Their second protocol is a generalization of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps than the optimal distributing protocol for the worst case scenario.

In this protocol a quantum network is represented as a graph
'''upload image qn_distributing.svg here'''


The physical distribution of graph states are represented as graph operations ignoring
local corrections.

To distribute a '''GHZ states''' over all the nodes of an arbitrary set <math>W</math> of the network nodes we have two steps:

# Find a minimal tree covering all the nodes of <math>W</math> using the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem].
#* Minimal tree is a subgraph connecting all the nodes in <math>W</math> with the minimum number of edges.
# Apply an operation called Star Expansion on the leaves of the tree from the previous step.


To distribute an '''Arbitrary Graph State''' we realize multiple iterations of the protocol above.
After that we make measurements on the participating nodes to generate the arbitrary graph state we want.



==Requirements==
*'''Network Stage:''' [[Category: Quantum Memory Network Stage]][[:Category: Quantum Memory Network Stage| Quantum Memory]]
* Nodal Clifford Operations.

==Notation==
* <math>b=</math>qubit in the center of the star graph.
* <math>A=</math>Node of the network which contains a qubit <math>a_0 \in A \cap N_b</math> (neighborhood of b).
* <math>|A|</math> number of nodes of A.
* <math>a_i \in A</math>, <math>i > 0</math> Represents each of the qubits of <math>A</math> that constitutes a Bell pair with a qubit <math>c_i</math> in another node of the network.

==Properties==
* The optimality of the protocol depends on the network topology and the wanted graph state to distribute.
* Analysing the consumption of Bell pair between nodes and considering the worst case scenario that is to entangle each qubit with the opposite one over a line network we have the following upper bounds:
{| class="wikitable"
|-
! Distribute
! Cost
! Bound
|-
|rowspan="2"| N-GHZ
| EPR
| <math>N-1</math>
|-
| T
| <math>1</math>
|-
|rowspan="2"| Arbitrary Graph State
| EPR
| <math>\left\lfloor \frac{N}{2} \right\rfloor^2</math>
|-
| T
| <math>\left\lfloor \frac{N}{2} \right\rfloor</math>
|-
|}

==Protocol Description==
'''Graph Operations:'''
* '''Vertex Deletion.''' Removes one vertex and all the associated edges from the graph.
** Implemented by the Pauli Measurement of the relevant qubit in the ''Z basis''.
* '''Local Complementation.''' Inverts the subgraph induced by the neighborhood <math>N_a</math> of the concerned vertex <math>a</math>.
** Implemented by the quantum operator <math>U_a^\tau = e^{-i \frac{\pi}{4}X_a} \bigotimes_{b \in N_a} e^{i \frac{\pi}{4}Z_b}</math> acting on the qubits <math>a \cup N_a</math>.
* '''Edge Addition.''' Add an edge between two nonadjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Edge Deletion.''' Delete an edge between two adjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Entanglement Swapping.'''
** Implemented by applying ''controlled-Z'' gate followed by two single qubit ''Y-measurement''.

===GHZ State Distribution Protocol===
'''Input'''
* N-GHZ state: <math>|\text{N-GHZ}\rangle = (|0\rangle^{\otimes N}+|1\rangle^{\otimes N})/\sqrt{2}</math>.
* That is locally equivalent to: <math>(|0\rangle|+\rangle^{\otimes N-1}+|1\rangle|-\rangle^{\otimes N-1})/\sqrt{2}</math> that is called a star graph '''upload image star_graph_distributing.svg here'''



* Arbitrary set <math>W</math> of the network nodes.
** Assuming that the network topology is already given to us.

'''Output'''
* N-GHZ state distributed over <math>W</math>.

'''GHZ-Distribution Algorithm'''
# Find a minimal tree covering all the nodes of <math>W</math>
# <math>l</math> is a random leaf from the tree of step 1.
# For <math>j=1</math> to <math>|W| - 1</math>:
## Let <math>A</math> be any unprocessed node of <math>W</math> such as <math>l \notin A</math>.
## Apply the Start Expansion Algorithm on node <math>A</math> with <math>l</math> as <math>b</math> the center of the star.

'''Start Expansion Algorithm'''
This routine uses the Bell pairs of the node <math>A</math> to add the edges <math>(b,c_i)</math> to the graph state, as well as the edge <math>(b, a_0)</math> ''iff'' <math>A \in W</math>.

# All the qubits <math>a_i, i \geq 0</math> of <math>A</math> are linked using Controlled-Z operations between all possible pairs.
# Local complementation is applied to the qubit <math>a_0</math> linked to <math>b</math>.
# If <math>A \notin W</math>:
## Remove <math>a_0</math> and all the edges within <math>A</math> by <math>Z</math>-measuring it
## Else (when <math>A \in W</math>):
###Keep <math>a_0</math> and apply Controlled-Z gates to remove all edges within <math>A</math>.
#Apply a <math>Y</math>-measurement on all the other qubits <math>a_i \in A</math>, <math>i>0</math> creating the desired Start Graph.

===Arbitrary Graph State Distribution Protocol===
To distribute an arbitrary graph state we first distribute the edge-decorated complete graph state. From this graph we can construct any other graph state by measuring each edge-qubit with a:
* ''Z measurement'' to delete this vertex and its edges
or a
* ''Y measurement'' to delete the vertex but keep the edges.

'''Input'''
* Arbitrary graph state to distribute
* Arbitrary set <math>W</math> of the <math>k</math> participating nodes.
'''Output'''
* Arbitrary graph state distributed over <math>W</math>.

'''Arbitrary Graph State Distribution Algorithm'''
# Solve the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem] on the network for the <math>k</math> nodes.
#* Each one of the nodes of this tree has an central leaf <math>l_n</math>, <math>1 \leq n \leq k</math>.
# For <math>j=1</math> to <math>k</math>:
## Distribute a (k-1-j)-GHZ state on the node of <math>l_j</math> using the [[Distributing Graph States Over Arbitrary Quantum Networks#Protocol Description|GHZ-Distribution Algorithm ]].
## Delete vertices from the tree in order to have the covering tree for the set <math>W \setminus \{l_j\}</math>.
# For each one of the <math>k</math> nodes apply local operations to generate the edge-decorated graph state.
# For each one of the <math>k</math> nodes construct the desired arbitrary state by applying <math>Z</math> and <math>Y</math> measurements.

==Further Information==
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
* [http://dx.doi.org/10.1088/1367-2630/18/5/053036 Epping et all (2016)] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
* [http://dx.doi.org/10.1103/PhysRevA.86.042304 Cuquet and Calsamiglia (2012)] and [http://dx.doi.org/10.1103/PhysRevLett.104.050501 Matsuzaki et al (2010)] Present decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
* [http://dx.doi.org/10.1038/s41534-019-0191-6 Hahn et all (2019)] Studies the possible transformations of an already shared graph-state, with a single-qubit per location.
* [http://dx.doi.org/10.1088/1367-2630/ab05f7 Pirker and Dür (2019)] Includes a protocol very similar to the one presented in this page, but the modeling of the network is different, as well as the optimized metrics. They describe a hierarchical network stack and use it to provide robustness against router or sub-network failures, which is not presented in this work.

==References==
# [https://arxiv.org/abs/1811.05445 Meignant, Markham and Grosshans (2019)]

<div style='text-align: right;'>''*contributed by Lucas Arenstein''</div>

Entanglement Routing

2021-12-09T22:33:52Z

189.120.189.205: First sketch of this functionality by Lucas

Protocol Library

2021-12-09T22:33:52Z

189.120.189.205: Add a protocol page to the Entanglement Routing Functionality

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="5"|[[Authentication of Quantum Messages]]||[[Purity Testing based Quantum Authentication]]
|-
|[[Polynomial Code based Quantum Authentication]]
|-
|[[Clifford Code for Quantum Authentication]]
|-
|[[Trap Code for Quantum Authentication]]
|-
|[[Naive approach using Quantum Teleportation]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[Copy Protection of Compute and Compare Programs]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="2"|[[Entanglement Routing]]||[[Routing Entanglement in the Quantum Internet]]
|-
|[[Distributing Graph States Over Arbitrary Quantum Networks]]

Routing Entanglement in the Quantum Internet

2021-12-03T21:28:58Z

189.120.189.205: First version of the page made by Lucas. I still need to add some parts and make another good review of everything.

==Assumptions==

* Each network repeater node 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 network repeater node is aware of the overall network topology, as well as the locations of the <math>K</math> Source-Destination pairs.

==Outline==

In [https://www.nature.com/articles/s41534-019-0139-x.pdf 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 ﬂow:
** 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 ﬂows:
** 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 ﬂows of entanglement.

==Notation==

Quantum network with topology described by a graph <math>G(V,E)</math>:
* Each of the <math>N=|V|</math> nodes is equipped with a quantum repeater.
* Each of the <math>M=|E|</math> edges is a lossy optical channel of range <math>L_i</math> (km) and power transmissivity <math>\eta_i \propto e^{-\alpha L_i}</math>, <math>i \in E</math> and <math>\alpha</math> depends on the material of the channel.
* <math>K</math> Source-Destination pairs <math>(A_j, B_j)</math>, <math>1 \leq j \leq k</math> situated at (not necessarily distinct) nodes in <math>V</math>.
Considering this graph<math>G</math> we adopt the following notation for the repeater network.
* Each node <math>v \in V</math> is a repeater.
* Each edge <math>e \in E</math> is a physical link connecting two repeater nodes.
* <math>S(e) \in \mathbb{Z}^+</math> is an integer edge weight corresponding to the number of parallel channel across edge <math>e</math>.
* <math>\mathcal{N}(v)</math> is the set of neighbor edges of <math>v</math>
* <math>d(v) = |\mathcal{N}(v)|</math> is the degree of node <math>v</math>.
* <math>\sum_{e \in \mathcal{N}(v)} S(e)</math> is the number of memories at node <math>v</math>.
* <math>d_A</math> distance of a node to the node A, using the <math>\mathbb{L}^2</math> norm.
* An ebit represents a maximally entangled qubit.





==Properties==



==Protocol Description==


* All of the three protocols below assume that time is slotted and each memory can hold a qubit perfectly for <math>T \geq 1</math> time slot. After this time the stored qubit completely decoheres.
* Each time slot <math>t</math>, <math>t=1,2,... </math> is divided into 2 phases:
* '''External Phase:'''
** Each of the <math>S(e)</math> pairs of memories across and edge <math>e</math> attempts to establish an EPR pair.
*:- An entanglement attempt across any one of the <math>S(e)</math> parallel links across edge <math>e</math> succeeds with probability <math>p_0(e) \sim \eta(e)</math>, where <math>\eta(e) \sim e^{-\alpha L_e}</math> is the transmissivity of a lossy optical channel of length <math>L(e)</math>.
** Using two-way classical communication over edge <math>e(u, v)</math>, neighboring repeater nodes <math>u, v</math> 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 <math>q</math>.

At the end of one time-slot a along a path comprising of <math>k</math> edges (and thus <math>(k-1)</math> repeater nodes) one ebit is successfully shared between the end points of the path with probability <math>p^k q^{k-1}</math>.

The maximum number of ebits that can be shared between node <math>a</math> and node <math>b</math> after one time-slot is <math>min\{d(a), d(b)\}</math>, assuming <math>S</math> 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 <math>K</math>.

===Multipath Routing of a Single Entanglement Flow===
'''Input:''' <math>K=1</math>, Source-Destination pair <math>(A_1, B_1)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math>.

====Protocol for Entanglement Routing with Global Link-state Information====
After the External Phase
# <math>m = 1</math>
# <math>G_m</math> = Subgraph induced by the successful external links and the repeater nodes after the external phase.
# While (True):
## <math>S_m</math> = shortest path in <math>G_m</math> connecting <math>A_1</math> with <math>B_1</math>.
## If <math>S_m</math> is empty: Break While Loop.
## Else:
### Set <math>L_m</math> as the length of <math>S_m</math>.
### Try connecting all internal links along the nodes of <math>S_m</math> <br />//successfully generating an ebit between <math>A_1</math> and <math>B_1</math> with probability <math>q^{L_m - 1}</math>
## <math>G_{m+1}</math> = <math>G_m -</math> all external and internal links of <math>S_m</math>.
## <math>m = m + 1.</math>

====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
# For every repeater except <math>A_1</math> and <math>B_1</math>: <br /> Let <math>u</math> be the node of this iteration.
## If less than one of the neighboring external links is successful: <br />no internal links are attempted since this repeater node can not be part of a path from <math>A_1</math> to <math>B_1</math>.
## If two or more neighboring external links are successful: <br /> Let <math>v</math> be the node linked to <math>u</math> with the smallest <math>d_{A_1}</math> and <math>w</math> be the node linked to <math>u</math> with the smallest <math>d_{B_1}</math>. <br /> Attempt a BSM on node <math>u</math> on the memories connected to <math>v</math> and <math>w</math>.
### If four neighboring external links are successful: <br /> Attempt a BSM on node <math>u</math> on the remaining memories disconsidering the two memories from the previous step.

===Protocol for Simultaneous Entanglement Flows with Link-state Information===
'''Input:''' <math>K=2</math>, Source-Destination pairs <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

'''Output:''' Quantum network with ebits shared between the end points of <math>(A_1, B_1)</math> and <math>(A_2, B_2)</math>.

This situation motivates the '''Multi-ﬂow 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 ﬂows.
** 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 ﬂows.
** Considering the square-grid topology the two spatial regions are divided by two crossing lines with an angle <math>\theta</math> between them (forming a hourglass shape).
** For each one of this regions we apply the Protocol for Entanglement Routing with Local Link-state Information.

==Further Information==


==References==


<div style='text-align: right;'>''*contributed by Lucas Arenstein''</div>

Distributing Graph States Over Arbitrary Quantum Networks

2021-11-20T14:07:07Z

189.120.189.205: First version of this page. I still need to add the introduction, properties, images and make another good review of everything.

Under construction [https://arxiv.org/abs/1811.05445 Meignant, Markham and Grosshans (2019)]

'''Tags:'''[[:Category:Specific Task|Specific Task]]

==Assumptions==
* Perfect distribution of Bell pairs occurring at perfectly synchronized times.
* Perfect node local computation.
* Ignore the cost of classical communications.
* Ignore processing time of local quantum processor.
* Ignore the cost of quantum memory.

==Outline==
The protocol [https://arxiv.org/abs/1811.05445 1] aims to distribute multipartite entangled states that are represented by graph states over fixed networks of arbitrary topology. They first introduce a protocol to distribute GHZ states that considering the assumptions takes a single time step and is optimal in terms of the Bell pair used. Their second protocol is a generalization of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps than the optimal distributing protocol for the worst case scenario.

In this protocol a quantum network is represented as a graph
''upload image here''


The physical distribution of graph states are represented as graph operations ignoring
local corrections.

To distribute a '''GHZ states''' over all the nodes of an arbitrary set <math>W</math> of the network nodes we have two steps:

# Find a minimal tree covering all the nodes of <math>W</math> using the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem].
#* Minimal tree is a subgraph connecting all the nodes in <math>W</math> with the minimum number of edges.
# Apply an operation called Star Expansion on the leaves of the tree from the previous step.


To distribute an '''Arbitrary Graph State''' we realize multiple iterations of the protocol above.
After that we make measurements on the participating nodes to generate the arbitrary graph state we want.



==Requirements==
*'''Network Stage:''' [[Category: Quantum Memory Network Stage]][[:Category: Quantum Memory Network Stage| Quantum Memory]]
* Nodal Clifford Operations.

==Notation==
* <math>b=</math>qubit in the center of the star graph.
* <math>A=</math>Node of the network which contains a qubit <math>a_0 \in A \cap N_b</math> (neighborhood of b).
* <math>|A|</math> number of nodes of A.
* <math>a_i \in A</math>, <math>i > 0</math> Represents each of the qubits of <math>A</math> that constitutes a Bell pair with a qubit <math>c_i</math> in another node of the network.

==Protocol Description==
'''Graph Operations:'''
* '''Vertex Deletion.''' Removes one vertex and all the associated edges from the graph.
** Implemented by the Pauli Measurement of the relevant qubit in the ''Z basis''.
* '''Local Complementation.''' Inverts the subgraph induced by the neighborhood <math>N_a</math> of the concerned vertex <math>a</math>.
** Implemented by the quantum operator <math>U_a^\tau = e^{-i \frac{\pi}{4}X_a} \bigotimes_{b \in N_a} e^{i \frac{\pi}{4}Z_b}</math> acting on the qubits <math>a \cup N_a</math>.
* '''Edge Addition.''' Add an edge between two nonadjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Edge Deletion.''' Delete an edge between two adjacent vertices.
** Implemented by applying a ''controlled-Z'' between the desired nodes.
* '''Entanglement Swapping.'''
** Implemented by applying ''controlled-Z'' gate followed by two single qubit ''Y-measurement''.

===GHZ State Distribution Protocol===
'''Input'''
* N-GHZ state: <math>|\text{N-GHZ}\rangle = (|0\rangle^{\otimes N}+|1\rangle^{\otimes N})/\sqrt{2}</math>.
* That is locally equivalent to: <math>(|0\rangle|+\rangle^{\otimes N-1}+|1\rangle|-\rangle^{\otimes N-1})/\sqrt{2}</math> that is called a star graph '''link to star graph'''



* Arbitrary set <math>W</math> of the network nodes.
** Assuming that the network topology is already given to us.

'''Output'''
* N-GHZ state distributed over <math>W</math>.

'''GHZ-Distribution Algorithm'''
# Find a minimal tree covering all the nodes of <math>W</math>
# <math>l</math> is a random leaf from the tree of step 1.
# For <math>j=1</math> to <math>|W| - 1</math>:
## Let <math>A</math> be any unprocessed node of <math>W</math> such as <math>l \notin A</math>.
## Apply the Start Expansion Algorithm on node <math>A</math> with <math>l</math> as <math>b</math> the center of the star.

'''Start Expansion Algorithm'''
This routine uses the Bell pairs of the node <math>A</math> to add the edges <math>(b,c_i)</math> to the graph state, as well as the edge <math>(b, a_0)</math> ''iff'' <math>A \in W</math>.

# All the qubits <math>a_i, i \geq 0</math> of <math>A</math> are linked using Controlled-Z operations between all possible pairs.
# Local complementation is applied to the qubit <math>a_0</math> linked to <math>b</math>.
# If <math>A \notin W</math>:
## Remove <math>a_0</math> and all the edges within <math>A</math> by <math>Z</math>-measuring it
## Else (when <math>A \in W</math>):
###Keep <math>a_0</math> and apply Controlled-Z gates to remove all edges within <math>A</math>.
#Apply a <math>Y</math>-measurement on all the other qubits <math>a_i \in A</math>, <math>i>0</math> creating the desired Start Graph.

===Arbitrary Graph State Distribution Protocol===
To distribute an arbitrary graph state we first distribute the edge-decorated complete graph state. From this graph we can construct any other graph state by measuring each edge-qubit with a:
* ''Z measurement'' to delete this vertex and its edges
or a
* ''Y measurement'' to delete the vertex but keep the edges.

'''Input'''
* Arbitrary graph state to distribute
* Arbitrary set <math>W</math> of the <math>k</math> participating nodes.
'''Output'''
* Arbitrary graph state distributed over <math>W</math>.

'''Arbitrary Graph State Distribution Algorithm'''
# Solve the [https://en.wikipedia.org/wiki/Steiner_tree_problem Steiner Tree Problem] on the network for the <math>k</math> nodes.
#* Each one of the nodes of this tree has an central leaf <math>l_n</math>, <math>1 \leq n \leq k</math>.
# For <math>j=1</math> to <math>k</math>:
## Distribute a (k-1-j)-GHZ state on the node of <math>l_j</math> using the [[Distributing Graph States Over Arbitrary Quantum Networks#Protocol Description|GHZ-Distribution Algorithm ]].
## Delete vertices from the tree in order to have the covering tree for the set <math>W \setminus \{l_j\}</math>.
# For each one of the <math>k</math> nodes apply local operations to generate the edge-decorated graph state.
# For each one of the <math>k</math> nodes construct the desired arbitrary state by applying <math>Z</math> and <math>Y</math> measurements.

==Further Information==
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
* [http://dx.doi.org/10.1088/1367-2630/18/5/053036 Epping et all (2016)] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
* [http://dx.doi.org/10.1103/PhysRevA.86.042304 Cuquet and Calsamiglia (2012)] and [http://dx.doi.org/10.1103/PhysRevLett.104.050501 Matsuzaki et al (2010)] Present decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
* [http://dx.doi.org/10.1038/s41534-019-0191-6 Hahn et all (2019)] Studies the possible transformations of an already shared graph-state, with a single-qubit per location.
* [http://dx.doi.org/10.1088/1367-2630/ab05f7 Pirker and Dür (2019)] Includes a protocol very similar to the one presented in this page, but the modeling of the network is different, as well as the optimized metrics. They describe a hierarchical network stack and use it to provide robustness against router or sub-network failures, which is not presented in this work.

==References==
# [https://arxiv.org/abs/1811.05445 Meignant, Markham and Grosshans (2019)]

<div style='text-align: right;'>''*contributed by Lucas Arenstein''</div>

Protocol Library

2021-11-20T11:18:13Z

189.120.189.205:

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="1"|[[Authentication of Quantum Messages]]||[[Polynomial Code based Quantum Authentication]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[-]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]
|-
|rowspan="1"|[[Entanglement Routing]]||[[Distributing Graph States Over Arbitrary Quantum Networks]]

Protocol Library

2021-11-09T15:59:34Z

189.120.189.205:

{| class="wikitable"
!width="40%"|Functionality
!width="60%"|Protocols
|-
|rowspan="2"|[[Anonymous Transmission]]||[[GHZ-based Quantum Anonymous Transmission]]
|-
|[[Verifiable Quantum Anonymous Transmission]]
|-
|rowspan="1"|[[Authentication of Classical Messages]]||[[Uncloneable Encryption]]
|-
|rowspan="1"|[[Authentication of Quantum Messages]]||[[Polynomial Code based Quantum Authentication]]
|-
||[[Byzantine Agreement]]||[[Fast Quantum Byzantine Agreement]]
|-
||[[Bit Commitment]]||[[Quantum Bit Commitment]]
|-
|rowspan="2"|[[Coin Flipping]]||[[Quantum Strong Coin Flipping]]
|-
|[[Quantum Weak Coin Flipping]]
|-
|[[Copy Protection]]||[[-]]
|-
|rowspan="8"|[[Quantum Digital Signature|(Quantum) Digital Signature]] |||[[Gottesman and Chuang Quantum Digital Signature]]
|-
|[[Prepare and Measure Quantum Digital Signature]]
|-
|[[Measurement Device Independent Quantum Digital Signature (MDI-QDS)]]
|-
|[[Arbitrated Quantum Digital Signature]]
|-
|[[Blind Delegation of Quantum Digital Signature]]
|-
|[[Designated Verifiable Quantum Signature]]
|-
|[[Limited Delegation of Quantum Digital Signature]]
|-
|[[Quantum Proxy Signature]]
|-
||[[Entanglement Verification]]||[[Multipartite Entanglement Verification]]
|-
||[[Fingerprinting]]||[[Quantum Fingerprinting]]
|-
|[[Quantum Identity Authentication]]||[[-]]
|-
|rowspan="4"|[[Quantum Key Distribution|(Quantum) Key Distribution]]||[[BB84 Quantum Key Distribution]]
|-
|[[Measurement Device Independent Quantum Key Distribution (MDI-QKD)]]
|-
|[[Device-Independent Quantum Key Distribution]]
|-
|[[Continuous-Variable Quantum Key Distribution (CV-QKD)]]
|-
||[[Leader Election]]||[[Quantum Leader Election]]
|-
|rowspan="4"|[[Quantum Money|(Quantum) Money]]||[[Quantum Cheque]]
|-
|[[Quantum Coin]]
|-
|[[Quantum Token]]
|-
|[[Wiesner Quantum Money]]
|-
||[[Oblivious Transfer]]||[[Quantum Oblivious Transfer]]
|-
|rowspan="10"| [[(Symmetric) Private Information Retrieval]] ||[[Multi-Database Classical Symmetric Private Information Retrieval with Quantum Key Distribution]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Coded Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval for Communicating and Colluding Servers]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval in the Visible Setting for a Quantum Database]]
|-
|[[Multi-Database Quantum Symmetric Private Information Retrieval without Shared Randomness]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model]]
|-
|[[Single-Database Quantum Private Information Retrieval in the Honest Server Model and in the Blind Setting for a Quantum Database]]
|-
|[[Single-Database Quantum Private Information Retrieval with Prior Shared Entanglement in the Honest Server Model]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Oblivious Key Distribution]]
|-
|[[Quantum Private Queries Protocol Based on Quantum Random Access Memory]]
|-
|rowspan="2"| [[Quantum Secret Sharing|Secret Sharing]] ||[[Quantum Secret Sharing using GHZ States]]
|-
|[[Verifiable Quantum Secret Sharing]]
|-
|rowspan="5"| [[Secure Client- Server Delegated Quantum Computation]] ||[[Classical Fully Homomorphic Encryption for Quantum Circuits]]
|-
|[[Measurement-Only Universal Blind Quantum Computation]]
|-
| [[Prepare-and-Send Quantum Fully Homomorphic Encryption]]
|-
|[[Prepare-and-Send Universal Blind Quantum Computation]]
|-
|[[Pseudo-Secret Random Qubit Generator (PSQRG)]]
|-
|rowspan="3"|[[Secure Verifiable Client-Server Delegated Quantum Computation]]||[[Prepare-and-Send Verifiable Universal Blind Quantum Computation]]
|-
|[[Measurement-Only Verifiable Universal Blind Quantum Computation]]
|-
|[[Prepare-and-Send Verifiable Quantum Fully Homomorphic Encryption]]
|-
|rowspan="2"|[[Secure Delegated Classical Computation]]||[[Secure Client-Server Classical Delegated Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Secure Multi-Party Delegated Computation]]||[[Secure Multiparty Delegated Quantum Computation]]
|-
|[[Secure Multiparty Delegated Classical Computation]]
|-
|rowspan="2"|[[Teleportation|(Quantum) Teleportation]]||[[Quantum Teleportation|State Teleporation]]
|-
|[[Gate Teleporation]]
|-
|[[Verification of Universal Quantum Computation]]||[[Interactive Proofs for Quantum Computation|Quantum Prover Interactive Proofs]]
|-
|[[Verification of Sub-Universal Quantum Computation]]||[[-]]
|-
|[[Verification of NP-complete problems]]||[[-]]
|-
|[[Classical Verification of Universal Quantum Computation]]||[[-]]
|-
|rowspan="4"|[[Quantum Electronic Voting]]||[[Dual Basis Measurement Based Protocol]]
|-
|[[Travelling Ballot Based Protocol]]
|-
|[[Distributed Ballot Based Protocol]]
|-
|[[Quantum voting based on conjugate coding]]
|-
||-||[[Weak String Erasure]]
|-
||-||[[Distributing Graph States Over Arbitrary Quantum Networks]]

Distributing Graph States Over Arbitrary Quantum Networks

2021-11-07T18:08:35Z

189.120.189.205: Created page with "To do [https://arxiv.org/abs/1811.05445]"

To do [https://arxiv.org/abs/1811.05445]