Distributing Graph States Over Arbitrary Quantum Networks

This protocol (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: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 (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 $W$ of the network nodes we have two steps:

1. Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
   • Minimal tree is a subgraph connecting all the nodes in $W$ with the minimum number of edges.
2. 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: Quantum Memory
• Nodal Clifford Operations.

Notation

• $b=$qubit in the center of the star graph.
• $A=$Node of the network which contains a qubit $a_{0}\in A\cap N_{b}$ (neighborhood of b).
• $|A|$ number of nodes of A.
• $a_{i}\in A$, $i>0$ Represents each of the qubits of $A$ that constitutes a Bell pair with a qubit $c_{i}$ 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:

Distribute	Cost	Bound
N-GHZ	EPR	$N-1$
	T	$1$
Arbitrary Graph State	EPR	$\left\lfloor {\frac {N}{2}}\right\rfloor ^{2}$
	T	$\left\lfloor {\frac {N}{2}}\right\rfloor$

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 $N_{a}$ of the concerned vertex $a$.
  • Implemented by the quantum operator $U_{a}^{\tau }=e^{-i{\frac {\pi }{4}}X_{a}}\bigotimes _{b\in N_{a}}e^{i{\frac {\pi }{4}}Z_{b}}$ acting on the qubits $a\cup N_{a}$.
• 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: $|{\text{N-GHZ}}\rangle =(|0\rangle ^{\otimes N}+|1\rangle ^{\otimes N})/{\sqrt {2}}$.
• That is locally equivalent to: $(|0\rangle |+\rangle ^{\otimes N-1}+|1\rangle |-\rangle ^{\otimes N-1})/{\sqrt {2}}$ that is called a star graph upload image star_graph_distributing.svg here

• Arbitrary set $W$ of the network nodes.
  • Assuming that the network topology is already given to us.

Output

• N-GHZ state distributed over $W$.

GHZ-Distribution Algorithm

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

Start Expansion Algorithm This routine uses the Bell pairs of the node $A$ to add the edges $(b,c_{i})$ to the graph state, as well as the edge $(b,a_{0})$ iff $A\in W$.

1. All the qubits $a_{i},i\geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
2. Local complementation is applied to the qubit $a_{0}$ linked to $b$.
3. If $A\notin W$:
   1. Remove $a_{0}$ and all the edges within $A$ by $Z$-measuring it
   2. Else (when $A\in W$):
      1. Keep $a_{0}$ and apply Controlled-Z gates to remove all edges within $A$.
4. Apply a $Y$-measurement on all the other qubits $a_{i}\in A$, $i>0$ 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 $W$ of the $k$ participating nodes.

Output

• Arbitrary graph state distributed over $W$.

Arbitrary Graph State Distribution Algorithm

1. Solve the Steiner Tree Problem on the network for the $k$ nodes.
   • Each one of the nodes of this tree has an central leaf $l_{n}$, $1\leq n\leq k$.
2. For $j=1$ to $k$:
   1. Distribute a (k-1-j)-GHZ state on the node of $l_{j}$ using the GHZ-Distribution Algorithm .
   2. Delete vertices from the tree in order to have the covering tree for the set $W\setminus \{l_{j}\}$.
3. For each one of the $k$ nodes apply local operations to generate the edge-decorated graph state.
4. For each one of the $k$ nodes construct the desired arbitrary state by applying $Z$ and $Y$ measurements.

Further Information

The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:

• Epping et all (2016) Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
• Cuquet and Calsamiglia (2012) and 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.
• Hahn et all (2019) Studies the possible transformations of an already shared graph-state, with a single-qubit per location.
• 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

1. Meignant, Markham and Grosshans (2019)

Contributed by Lucas Arenstein during the QOSF Mentorship Program

Mentor: Shraddha Singh