Revision History for: Distributing Graph States Over Arbitrary Quantum Networks
- 2026-06-07 at 20:07 by kimworrall
implements Entanglement Routing
Introduction
This protocol [1] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute these states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realised by the protocol.
Outline
The protocol 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 generalisation of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps as the optimal distributing protocol for the worst-case scenario.
In this protocol, a quantum network is represented as a graph.
The physical distribution of graph states are represented as graph operations, ignoring local corrections.
To distribute a GHZ state over all the nodes of an arbitrary set $W$ of the network nodes, we have two steps:
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- The minimal tree is a subgraph connecting all the nodes in $W$ 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 realise multiple iterations of the protocol above. After that, we make measurements on the participating nodes to generate the arbitrary graph state we want.
Assumptions
- Perfect distribution of Bell pairs occurring at perfectly synchronized times.
- Perfect node local computation.
- Ignore the cost of classical communications.
- Ignore the processing time of the local quantum processor.
- Ignore the cost of quantum memory.
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 desired graph state to distribute.
- Analysing the consumption of Bell pairs 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:
$$
\\\begin{array}{|c|c|c|}
\\\hline
\\\text{Distribute} & \\\text{Cost} & \\\text{Bound} \\\\\\\\\
\\\hline
\\\text{N-GHZ} & \\\text{EPR} & N – 1 \\\\\\\\\
& \\\text{T} & 1 \\\\\\\\\
\\\hline
\\\text{Arbitrary Graph State} & \\\text{EPR} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor^{2} \\\\\\\\\
& \\\text{T} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor \\\\\\\\\
\\\hline
\\\end{array}
$$Technical 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 neighbourhood $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.
Subroutine 1: GHZ State Distribution
Here we use the protocol “GHZ State Distribution” as a subroutine
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}$. This is called a star graph. - An 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:
- Find a minimal tree covering all the nodes of $W$
- $l$ is a random leaf from the tree of step 1.
- For $j = 1$ to $|W| – 1$:
- Let $A$ be any unprocessed node of $W$ such that $l \\\notin A$.
- Apply the Start Expansion Algorithm on node $A$ with $l$ as $b$ (the centre 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$.- All the qubits $a_i, i \\\geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
- Local complementation is applied to the qubit $a_0$ linked to $b$.
- If $A \\\notin W$:
- Remove $a_0$ and all the edges within $A$ by $Z$-measuring it.
- Else (when $A \\\in W$):
- Keep $a_0$ and apply Controlled-Z gates to remove all edges within $A$.
- Apply a $Y$-measurement on all the other qubits $a_i \\\in A$, $i > 0$, creating the desired Star Graph.
Subroutine 2: Arbitrary Graph State Distribution
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:
- An arbitrary graph state to distribute
- An arbitrary set $W$ of the $k$ participating nodes.
Output: Arbitrary graph state distributed over $W$.
Arbitrary Graph State Distribution Algorithm
- Solve the Steiner Tree Problem on the network for the $k$ nodes.
- Each one of the nodes of this tree has a central leaf $l_n$, $1 \\\leq n \\\leq k$.
- For $j = 1$ to $k$:
- Distribute a $(k – 1 – j)$-GHZ state on the node of $l_j$ using the GHZ-Distribution Algorithm (subroutine 1).
- Delete vertices from the tree in order to have the covering tree for the set $W \\\setminus \\\{l_j\\\}$.
- For each one of the $k$ nodes, apply local operations to generate the edge-decorated graph state.
- For each one of the $k$ nodes, construct the desired arbitrary state by applying $Z$ and $Y$ measurements.
Experimental Implementations
No content has been added to this section, yet!
Further Information
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
- Epping et al. (2016)[2] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
- Cuquet and Calsamiglia (2012)[3] and Matsuzaki et al (2010)[4] present the decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
- Hahn et al. (2019)[5] studied the possible transformations of an already shared graph-state, with a single qubit per location.
- Pirker and Dür (2019)[6] include a protocol very similar to the one presented on this page, but the modelling of the network is different, as well as the optimised 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
–
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- 2025-06-24 at 21:47 by JuliaM
implements Entanglement Routing
Introduction
This protocol [1] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute these states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realised by the protocol.
Outline
The protocol 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 generalisation of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps as the optimal distributing protocol for the worst-case scenario.
In this protocol, a quantum network is represented as a graph.
The physical distribution of graph states are represented as graph operations, ignoring local corrections.
To distribute a GHZ state over all the nodes of an arbitrary set $W$ of the network nodes, we have two steps:
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- The minimal tree is a subgraph connecting all the nodes in $W$ 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 realise multiple iterations of the protocol above. After that, we make measurements on the participating nodes to generate the arbitrary graph state we want.
Assumptions
- Perfect distribution of Bell pairs occurring at perfectly synchronized times.
- Perfect node local computation.
- Ignore the cost of classical communications.
- Ignore the processing time of the local quantum processor.
- Ignore the cost of quantum memory.
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 desired graph state to distribute.
- Analysing the consumption of Bell pairs 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:
$$
\\\begin{array}{|c|c|c|}
\\\hline
\\\text{Distribute} & \\\text{Cost} & \\\text{Bound} \\\\\\\\\
\\\hline
\\\text{N-GHZ} & \\\text{EPR} & N – 1 \\\\\\\\\
& \\\text{T} & 1 \\\\\\\\\
\\\hline
\\\text{Arbitrary Graph State} & \\\text{EPR} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor^{2} \\\\\\\\\
& \\\text{T} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor \\\\\\\\\
\\\hline
\\\end{array}
$$Technical 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 neighbourhood $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.
Subroutine 1: GHZ State Distribution
Here we use the protocol “GHZ State Distribution” as a subroutine
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}$. This is called a star graph. - An 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:
- Find a minimal tree covering all the nodes of $W$
- $l$ is a random leaf from the tree of step 1.
- For $j = 1$ to $|W| – 1$:
- Let $A$ be any unprocessed node of $W$ such that $l \\\notin A$.
- Apply the Start Expansion Algorithm on node $A$ with $l$ as $b$ (the centre 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$.- All the qubits $a_i, i \\\geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
- Local complementation is applied to the qubit $a_0$ linked to $b$.
- If $A \\\notin W$:
- Remove $a_0$ and all the edges within $A$ by $Z$-measuring it.
- Else (when $A \\\in W$):
- Keep $a_0$ and apply Controlled-Z gates to remove all edges within $A$.
- Apply a $Y$-measurement on all the other qubits $a_i \\\in A$, $i > 0$, creating the desired Star Graph.
Subroutine 2: Arbitrary Graph State Distribution
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:
- An arbitrary graph state to distribute
- An arbitrary set $W$ of the $k$ participating nodes.
Output: Arbitrary graph state distributed over $W$.
Arbitrary Graph State Distribution Algorithm
- Solve the Steiner Tree Problem on the network for the $k$ nodes.
- Each one of the nodes of this tree has a central leaf $l_n$, $1 \\\leq n \\\leq k$.
- For $j = 1$ to $k$:
- Distribute a $(k – 1 – j)$-GHZ state on the node of $l_j$ using the GHZ-Distribution Algorithm (subroutine 1).
- Delete vertices from the tree in order to have the covering tree for the set $W \\\setminus \\\{l_j\\\}$.
- For each one of the $k$ nodes, apply local operations to generate the edge-decorated graph state.
- For each one of the $k$ nodes, construct the desired arbitrary state by applying $Z$ and $Y$ measurements.
Experimental Implementations
No content has been added to this section, yet!
Further Information
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
- Epping et al. (2016)[2] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
- Cuquet and Calsamiglia (2012)[3] and Matsuzaki et al (2010)[4] present the decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
- Hahn et al. (2019)[5] studied the possible transformations of an already shared graph-state, with a single qubit per location.
- Pirker and Dür (2019)[6] include a protocol very similar to the one presented on this page, but the modelling of the network is different, as well as the optimised 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
- Meignant, Clément, Damian Markham, and Frédéric Grosshans. “Distributing graph states over arbitrary quantum networks.” Physical Review A 100, no. 5 (2019): 052333.
- Epping, Michael, Hermann Kampermann, and Dagmar Bruß. “Large-scale quantum networks based on graphs.” New Journal of Physics 18, no. 5 (2016): 053036.
- Cuquet, Marti, and John Calsamiglia. “Growth of graph states in quantum networks.” Physical Review A—Atomic, Molecular, and Optical Physics 86, no. 4 (2012): 042304.
- Matsuzaki, Yuichiro, Simon C. Benjamin, and Joseph Fitzsimons. “Probabilistic growth of large entangled states with low error accumulation.” Physical review letters 104, no. 5 (2010): 050501.
- Hahn, Frederik, Anna Pappa, and Jens Eisert. “Quantum network routing and local complementation.” npj Quantum Information 5, no. 1 (2019): 76.
- Pirker, Alexander, and Wolfgang Dür. “A quantum network stack and protocols for reliable entanglement-based networks.” New Journal of Physics 21, no. 3 (2019): 033003.
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- 2025-05-16 at 13:22 by JuliaM
implements Entanglement Routing
Introduction
This protocol [1] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute these states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realised by the protocol.
Outline
The protocol 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 generalisation of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps as the optimal distributing protocol for the worst-case scenario.
In this protocol, a quantum network is represented as a graph.
The physical distribution of graph states are represented as graph operations, ignoring local corrections.
To distribute a GHZ state over all the nodes of an arbitrary set $W$ of the network nodes, we have two steps:
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- The minimal tree is a subgraph connecting all the nodes in $W$ 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 realise multiple iterations of the protocol above. After that, we make measurements on the participating nodes to generate the arbitrary graph state we want.
Assumptions
- Perfect distribution of Bell pairs occurring at perfectly synchronized times.
- Perfect node local computation.
- Ignore the cost of classical communications.
- Ignore the processing time of the local quantum processor.
- Ignore the cost of quantum memory.
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 desired graph state to distribute.
- Analysing the consumption of Bell pairs 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:
$$
\\\begin{array}{|c|c|c|}
\\\hline
\\\text{Distribute} & \\\text{Cost} & \\\text{Bound} \\\\\\\\\
\\\hline
\\\text{N-GHZ} & \\\text{EPR} & N – 1 \\\\\\\\\
& \\\text{T} & 1 \\\\\\\\\
\\\hline
\\\text{Arbitrary Graph State} & \\\text{EPR} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor^{2} \\\\\\\\\
& \\\text{T} & \\\left\\\lfloor \\\frac{N}{2} \\\right\\\rfloor \\\\\\\\\
\\\hline
\\\end{array}
$$Technical 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 neighbourhood $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.
Subroutine 1: GHZ State Distribution
Here we use the protocol “GHZ State Distribution” as a subroutine
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}$. This is called a star graph. - An 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:
- Find a minimal tree covering all the nodes of $W$
- $l$ is a random leaf from the tree of step 1.
- For $j = 1$ to $|W| – 1$:
- Let $A$ be any unprocessed node of $W$ such that $l \\\notin A$.
- Apply the Start Expansion Algorithm on node $A$ with $l$ as $b$ (the centre 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$.- All the qubits $a_i, i \\\geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
- Local complementation is applied to the qubit $a_0$ linked to $b$.
- If $A \\\notin W$:
- Remove $a_0$ and all the edges within $A$ by $Z$-measuring it.
- Else (when $A \\\in W$):
- Keep $a_0$ and apply Controlled-Z gates to remove all edges within $A$.
- Apply a $Y$-measurement on all the other qubits $a_i \\\in A$, $i > 0$, creating the desired Star Graph.
Subroutine 2: Arbitrary Graph State Distribution
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:
- An arbitrary graph state to distribute
- An arbitrary set $W$ of the $k$ participating nodes.
Output: Arbitrary graph state distributed over $W$.
Arbitrary Graph State Distribution Algorithm
- Solve the Steiner Tree Problem on the network for the $k$ nodes.
- Each one of the nodes of this tree has a central leaf $l_n$, $1 \\\leq n \\\leq k$.
- For $j = 1$ to $k$:
- Distribute a $(k – 1 – j)$-GHZ state on the node of $l_j$ using the GHZ-Distribution Algorithm (subroutine 1).
- Delete vertices from the tree in order to have the covering tree for the set $W \\\setminus \\\{l_j\\\}$.
- For each one of the $k$ nodes, apply local operations to generate the edge-decorated graph state.
- For each one of the $k$ nodes, construct the desired arbitrary state by applying $Z$ and $Y$ measurements.
Experimental Implementations
No content has been added to this section, yet!
Further Information
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
- Epping et al. (2016)[2] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
- Cuquet and Calsamiglia (2012)[3] and Matsuzaki et al (2010)[4] present the decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
- Hahn et al. (2019)[5] studied the possible transformations of an already shared graph-state, with a single qubit per location.
- Pirker and Dür (2019)[6] include a protocol very similar to the one presented on this page, but the modelling of the network is different, as well as the optimised 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
- Meignant, Clément, Damian Markham, and Frédéric Grosshans. “Distributing graph states over arbitrary quantum networks.” Physical Review A 100, no. 5 (2019): 052333.
- Epping, Michael, Hermann Kampermann, and Dagmar Bruß. “Large-scale quantum networks based on graphs.” New Journal of Physics 18, no. 5 (2016): 053036.
- Cuquet, Marti, and John Calsamiglia. “Growth of graph states in quantum networks.” Physical Review A—Atomic, Molecular, and Optical Physics 86, no. 4 (2012): 042304.
- Matsuzaki, Yuichiro, Simon C. Benjamin, and Joseph Fitzsimons. “Probabilistic growth of large entangled states with low error accumulation.” Physical review letters 104, no. 5 (2010): 050501.
- Hahn, Frederik, Anna Pappa, and Jens Eisert. “Quantum network routing and local complementation.” npj Quantum Information 5, no. 1 (2019): 76.
- Pirker, Alexander, and Wolfgang Dür. “A quantum network stack and protocols for reliable entanglement-based networks.” New Journal of Physics 21, no. 3 (2019): 033003.
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- 2025-05-16 at 13:21 by Mina Doosti
implements Entanglement Routing
Introduction
This protocol [1] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute these states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realised by the protocol.
Outline
The protocol 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 generalisation of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps as the optimal distributing protocol for the worst-case scenario.
In this protocol, a quantum network is represented as a graph.
The physical distribution of graph states are represented as graph operations, ignoring local corrections.
To distribute a GHZ state over all the nodes of an arbitrary set $W$ of the network nodes, we have two steps:
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- The minimal tree is a subgraph connecting all the nodes in $W$ 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 realise multiple iterations of the protocol above. After that, we make measurements on the participating nodes to generate the arbitrary graph state we want.
Assumptions
- Perfect distribution of Bell pairs occurring at perfectly synchronized times.
- Perfect node local computation.
- Ignore the cost of classical communications.
- Ignore the processing time of the local quantum processor.
- Ignore the cost of quantum memory.
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 desired graph state to distribute.
- Analysing the consumption of Bell pairs 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:
$$
begin{array}{|c|c|c|}
hline
text{Distribute} & text{Cost} & text{Bound} \\\\\\\\\
hline
text{N-GHZ} & text{EPR} & N – 1 \\\\\\\\\
& text{T} & 1 \\\\\\\\\
hline
text{Arbitrary Graph State} & text{EPR} & leftlfloor frac{N}{2} rightrfloor^{2} \\\\\\\\\
& text{T} & leftlfloor frac{N}{2} rightrfloor \\\\\\\\\
hline
end{array}
$$Technical 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 neighbourhood $N_a$ of the concerned vertex $a$.
Implemented by the quantum operator
$U_a^tau = e^{-ifrac{pi}{4}X_a} bigotimes_{b in N_a} e^{ifrac{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.
Subroutine 1: GHZ State Distribution
Here we use the protocol “GHZ State Distribution” as a subroutine
Input:- N-GHZ state: $|text{N-GHZ}rangle = (|0rangle^{otimes N} + |1rangle^{otimes N})/sqrt{2}$
That is locally equivalent to: $(|0rangle |+rangle^{otimes N-1} + |1rangle |-rangle^{otimes N-1})/sqrt{2}$. This is called a star graph. - An 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:
- Find a minimal tree covering all the nodes of $W$
- $l$ is a random leaf from the tree of step 1.
- For $j = 1$ to $|W| – 1$:
- Let $A$ be any unprocessed node of $W$ such that $l notin A$.
- Apply the Start Expansion Algorithm on node $A$ with $l$ as $b$ (the centre 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$.- All the qubits $a_i, i geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
- Local complementation is applied to the qubit $a_0$ linked to $b$.
- If $A notin W$:
- Remove $a_0$ and all the edges within $A$ by $Z$-measuring it.
- Else (when $A in W$):
- Keep $a_0$ and apply Controlled-Z gates to remove all edges within $A$.
- Apply a $Y$-measurement on all the other qubits $a_i in A$, $i > 0$, creating the desired Star Graph.
Subroutine 2: Arbitrary Graph State Distribution
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:
- An arbitrary graph state to distribute
- An arbitrary set $W$ of the $k$ participating nodes.
Output: Arbitrary graph state distributed over $W$.
Arbitrary Graph State Distribution Algorithm
- Solve the Steiner Tree Problem on the network for the $k$ nodes.
- Each one of the nodes of this tree has a central leaf $l_n$, $1 leq n leq k$.
- For $j = 1$ to $k$:
- Distribute a $(k – 1 – j)$-GHZ state on the node of $l_j$ using the GHZ-Distribution Algorithm (subroutine 1).
- Delete vertices from the tree in order to have the covering tree for the set $W setminus {l_j}$.
- For each one of the $k$ nodes, apply local operations to generate the edge-decorated graph state.
- For each one of the $k$ nodes, construct the desired arbitrary state by applying $Z$ and $Y$ measurements.
Experimental Implementations
No content has been added to this section, yet!
Further Information
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
- Epping et al. (2016)[2] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
- Cuquet and Calsamiglia (2012)[3] and Matsuzaki et al (2010)[4] present the decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
- Hahn et al. (2019)[5] studied the possible transformations of an already shared graph-state, with a single qubit per location.
- Pirker and Dür (2019)[6] include a protocol very similar to the one presented on this page, but the modelling of the network is different, as well as the optimised 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
- Meignant, Clément, Damian Markham, and Frédéric Grosshans. “Distributing graph states over arbitrary quantum networks.” Physical Review A 100, no. 5 (2019): 052333.
- Epping, Michael, Hermann Kampermann, and Dagmar Bruß. “Large-scale quantum networks based on graphs.” New Journal of Physics 18, no. 5 (2016): 053036.
- Cuquet, Marti, and John Calsamiglia. “Growth of graph states in quantum networks.” Physical Review A—Atomic, Molecular, and Optical Physics 86, no. 4 (2012): 042304.
- Matsuzaki, Yuichiro, Simon C. Benjamin, and Joseph Fitzsimons. “Probabilistic growth of large entangled states with low error accumulation.” Physical review letters 104, no. 5 (2010): 050501.
- Hahn, Frederik, Anna Pappa, and Jens Eisert. “Quantum network routing and local complementation.” npj Quantum Information 5, no. 1 (2019): 76.
- Pirker, Alexander, and Wolfgang Dür. “A quantum network stack and protocols for reliable entanglement-based networks.” New Journal of Physics 21, no. 3 (2019): 033003.
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- 2025-05-16 at 13:21 by Mina Doosti
implements Entanglement Routing
Introduction
This protocol [1] implements the task of distributing arbitrary graph states over quantum networks of arbitrary topology. The goal is to distribute these states in a way that is most efficient in terms of the number of Bell pairs consumed and the number of operations realised by the protocol.
Outline
The protocol 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 generalisation of the first one and can distribute any arbitrary graph state using at most twice as many Bell pairs and steps as the optimal distributing protocol for the worst-case scenario.
In this protocol, a quantum network is represented as a graph.
The physical distribution of graph states are represented as graph operations, ignoring local corrections.
To distribute a GHZ state over all the nodes of an arbitrary set $W$ of the network nodes, we have two steps:
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.
- The minimal tree is a subgraph connecting all the nodes in $W$ 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 realise multiple iterations of the protocol above. After that, we make measurements on the participating nodes to generate the arbitrary graph state we want.
Assumptions
- Perfect distribution of Bell pairs occurring at perfectly synchronized times.
- Perfect node local computation.
- Ignore the cost of classical communications.
- Ignore the processing time of the local quantum processor.
- Ignore the cost of quantum memory.
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 desired graph state to distribute.
- Analysing the consumption of Bell pairs 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:
$$
begin{array}{|c|c|c|}
hline
text{Distribute} & text{Cost} & text{Bound} \\\\\\\\\
hline
text{N-GHZ} & text{EPR} & N – 1 \\\\\\\\\
& text{T} & 1 \\\\\\\\\
hline
text{Arbitrary Graph State} & text{EPR} & leftlfloor frac{N}{2} rightrfloor^{2} \\\\\\\\\
& text{T} & leftlfloor frac{N}{2} rightrfloor \\\\\\\\\
hline
end{array}
$$Technical 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 neighbourhood $N_a$ of the concerned vertex $a$.
Implemented by the quantum operator
$U_a^tau = e^{-ifrac{pi}{4}X_a} bigotimes_{b in N_a} e^{ifrac{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.
Subroutine 1: GHZ State Distribution
Here we use the protocol “GHZ State Distribution” as a subroutine
Input:- N-GHZ state: $|text{N-GHZ}rangle = (|0rangle^{otimes N} + |1rangle^{otimes N})/sqrt{2}$
That is locally equivalent to: $(|0rangle |+rangle^{otimes N-1} + |1rangle |-rangle^{otimes N-1})/sqrt{2}$. This is called a star graph. - An 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:
- Find a minimal tree covering all the nodes of $W$
- $l$ is a random leaf from the tree of step 1.
- For $j = 1$ to $|W| – 1$:
- Let $A$ be any unprocessed node of $W$ such that $l notin A$.
- Apply the Start Expansion Algorithm on node $A$ with $l$ as $b$ (the centre 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$.- All the qubits $a_i, i geq 0$ of $A$ are linked using Controlled-Z operations between all possible pairs.
- Local complementation is applied to the qubit $a_0$ linked to $b$.
- If $A notin W$:
- Remove $a_0$ and all the edges within $A$ by $Z$-measuring it.
- Else (when $A in W$):
- Keep $a_0$ and apply Controlled-Z gates to remove all edges within $A$.
- Apply a $Y$-measurement on all the other qubits $a_i in A$, $i > 0$, creating the desired Star Graph.
Subroutine 2: Arbitrary Graph State Distribution
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:
- An arbitrary graph state to distribute
- An arbitrary set $W$ of the $k$ participating nodes.
Output: Arbitrary graph state distributed over $W$.
Arbitrary Graph State Distribution Algorithm
- Solve the Steiner Tree Problem on the network for the $k$ nodes.
- Each one of the nodes of this tree has a central leaf $l_n$, $1 leq n leq k$.
- For $j = 1$ to $k$:
- Distribute a $(k – 1 – j)$-GHZ state on the node of $l_j$ using the GHZ-Distribution Algorithm (subroutine 1).
- Delete vertices from the tree in order to have the covering tree for the set $W setminus {l_j}$.
- For each one of the $k$ nodes, apply local operations to generate the edge-decorated graph state.
- For each one of the $k$ nodes, construct the desired arbitrary state by applying $Z$ and $Y$ measurements.
Experimental Implementations
No content has been added to this section, yet!
Further Information
The distribution of multipartite entangled states over quantum networks has also been studied in the following articles:
- Epping et al. (2016)[2] Investigate the creation of a graph state presenting the shape of the network in the presence of noise.
- Cuquet and Calsamiglia (2012)[3] and Matsuzaki et al (2010)[4] present the decomposition of graph states into various building blocks that can be purified and merged to construct graph states over a network.
- Hahn et al. (2019)[5] studied the possible transformations of an already shared graph-state, with a single qubit per location.
- Pirker and Dür (2019)[6] include a protocol very similar to the one presented on this page, but the modelling of the network is different, as well as the optimised 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
- Meignant, Clément, Damian Markham, and Frédéric Grosshans. “Distributing graph states over arbitrary quantum networks.” Physical Review A 100, no. 5 (2019): 052333.
- Epping, Michael, Hermann Kampermann, and Dagmar Bruß. “Large-scale quantum networks based on graphs.” New Journal of Physics 18, no. 5 (2016): 053036.
- Cuquet, Marti, and John Calsamiglia. “Growth of graph states in quantum networks.” Physical Review A—Atomic, Molecular, and Optical Physics 86, no. 4 (2012): 042304.
- Matsuzaki, Yuichiro, Simon C. Benjamin, and Joseph Fitzsimons. “Probabilistic growth of large entangled states with low error accumulation.” Physical review letters 104, no. 5 (2010): 050501.
- Hahn, Frederik, Anna Pappa, and Jens Eisert. “Quantum network routing and local complementation.” npj Quantum Information 5, no. 1 (2019): 76.
- Pirker, Alexander, and Wolfgang Dür. “A quantum network stack and protocols for reliable entanglement-based networks.” New Journal of Physics 21, no. 3 (2019): 033003.
- Find a minimal tree covering all the nodes of $W$ using the Steiner Tree Problem.