Editing Distributing Graph States Over Arbitrary Quantum Networks


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'''
<!--[[File:qn_distributing.svg]]-->

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.
<!-- Put Link to Star Expansion -->


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.
<!-- ==Properties== -->
<!-- Put the cost of distributing, upper bounds etc -->

==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'''

<!--[[File:star_graph_distributing.svg]]-->

* 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)]

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