Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2508.18024 · IEEE International Conference on Quantum Computing and Engineering (QCE)

Polynomial-Time Extraction of Entanglement Resources

Si‐Yi Chen, Angela Sara Cacciapuoti, Marcello Caleffi

Published Aug 30, 2025• 0 citations
arXivHTMLPDF

Abstract

The extraction of EPR pairs and$n$-qubits GHZ states among remote nodes in quantum networks constitutes the resource primitives for end-to-end and on-demand communications. However, the Bell-VM problem, which determines whether a given graph state can be transformed into a set of Bell pairs on specific vertices (not necessarily remote), is known to be NP-complete. In this paper, we extend this problem, not only by focusing on nodes remote within generic graph states, but also by determining the number of extractable$n$-qubit remote GHZ states - beside the number of remote EPR pairs. The rationale for tackling the extraction of GHZ states among remote nodes, rather than solely remote EPR pairs, is that a GHZ state enables the dynamic extraction of an EPR pair between any pair of nodes sharing the state. This, in turn, implies the ability of accommodating the traffic requests on-the-fly. Specially, we propose a polynomial-time algorithm for solving the aforementioned NP-complete problem. Our results demonstrate that the proposed algorithm is able to effectively adapt to generic graph states for extracting entanglement resources across remote nodes.

DOI
10.1109/qce65121.2025.00130

Related papers

On the Efficient Extraction of Entangled Resources

Si-Yi Chen, Angela Sara Cacciapuoti, Marcello Caleffi

In the Quantum Internet, multipartite entanglement enables a rich and dynamic overlay topology, referred to as artificial topology, upon the physical one, that can be exploited for communication purposes. In fact, the ability to extractn-qubits GHZ states and EPR pairs from the original multipartite entangled state constitutes the resource primitives for end-to-end and on-demand quantum communications. Thus, in this paper, we theoretically determine upper and lower bounds for the number of extractablen-qubits GHZ states and EPR pairs involving nodes remote in the artificial topology, as well as the achievable sizenof remote GHZ states. The theoretical analysis is then complemented by the proposal of a novel algorithm, which provides in polynomial-time a heuristic solution to the above problem. This is remarkable, since the theoretical problem is NP-complete. The performance analysis demonstrates the proposed algorithm is able to effectively manipulate the original and arbitrary graph state for extracting entanglement resources across remote nodes.

arXiv:2504.10186•IEEE Transactions on Communications•Jan 1, 2026•0 citations

Transforming graph states to Bell-pairs is NP-Complete

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Critical to the construction of large scale quantum networks, i.e. a quantum internet, is the development of fast algorithms for managing entanglement present in the network. One fundamental building block for a quantum internet is the distribution of Bell pairs between distant nodes in the network. Here we focus on the problem of transforming multipartite entangled states into the tensor product of bipartite Bell pairs between specific nodes using only a certain class of local operations and classical communication. In particular we study the problem of deciding whether a given graph state, and in general a stabilizer state, can be transformed into a set of Bell pairs on specific vertices using only single-qubit Clifford operations, single-qubit Pauli measurements and classical communication. We prove that this problem is NP -Complete.

arXiv:1907.08019•Quantum•Oct 22, 2020•27 citations

Distributing Graph States Across Quantum Networks

Alexander Fischer, Don Towsley

Graph states form an important class of multipartite entangled quantum states. We propose a new approach for distributing graph states across a quantum network. We consider a quantum network consisting of nodes—quantum computers within which local operations are free—and EPR pairs shared between nodes that can continually be generated. We prove upper bounds for our approach on the number of EPR pairs consumed, completion time, and amount of classical communication required, all of which are equal to or better than that of prior work [10]. We also reduce the problem of minimizing the completion time to distribute a graph state using our approach to a network flow problem having polynomial time complexity.

arXiv:2009.10888•IEEE International Conference on Quantum Computing and Engineering (QCE)•Oct 1, 2021•27 citations

Topology-Dependent Enhancement of Entanglement Extraction in Repeater Graph States

Poramat Chianvichai, Poramet Pathumsoot, Naphan Benchasattabuse +3 more

Quantum repeaters are essential for establishing long-distance quantum communication to overcome the exponential decay of entanglement due to photon loss. Traditional repeater architectures rely on physical quantum memory, which introduces decoherence and poses significant practical implementation challenges. The repeater graph state (RGS) architecture offers a promising memory-less alternative that is inherently resilient to photon losses. A key challenge in implementing RGS lies in the requirement for highly efficient graph state generators and complex qubit measurement. In this work, we aim to investigate the strategies for extracting the maximum number of Bell pairs from the RGS structure via its qubit connection to resolve the well-known bottleneck problem of RGS in which only a single Bell pair can be extracted from a complete bipartite graph state. From simulations, we observe that the maximum number of extracted Bell pairs depends on its connection topology, where the Bell-pair yield tends to be maximal at low to moderate edge densities. As the number of network hops increases, the RGS must be equipped with higher inner-qubit connectivity to maintain a sufficient yield of extractable Bell pairs. Thus, the expected resource requirement shifts toward the use of RGSs with higher inner-qubit connectivity.

quant-pharXiv:2609.03496•International Conference on Quantum Communications, Networking, and Computing (QCNC)•Sep 4, 2026•0 citations

A resource- and computationally-efficient protocol for multipartite entanglement distribution in Bell-pair networks

S. Siddardha Chelluri, Sumeet Khatri, Peter van Loock

Abstract Multipartite entangled states, such as Greenberger–Horne–Zeilinger (GHZ) states, are important resources in multiparty quantum networking tasks. We consider protocols for generating such states from networks of Bell pairs and local operations and classical communication. We present a computationally-efficient protocol for generating GHZ states that is also efficient with respect to the number of consumed Bell pairs, (local) gates, and Bell-pair sources. Our protocol: (1) requires O ( N ) gates in a network with N nodes, independent of the network topology; (2) has time complexity O ( N 2 ), avoiding the Steiner tree and any other computationally-hard problem; (3) maintains a near-optimal number of consumed Bell pairs. Numerically, our protocol outperforms those based on (approximate) Steiner trees with respect to the number of gates and Bell-pair sources. We prove that the minimal Bell-pair source cost is given by solving the graph-theoretic dominating set problem, and we demonstrate numerically that our protocol is nearly optimal for this quantity. Finally, we analytically characterize the impact of noisy Bell pairs and gates on the fidelity of the distributed GHZ states.

arXiv:2412.04252•npj Quantum Information•Jul 7, 2026•1 citation

Quantum network routing and local complementation

F. Hahn, Anna Pappa, J. Eisert

Abstract Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.

arXiv:1805.04559•npj Quantum Information•Sep 6, 2019•109 citations
The extraction of EPR pairs andnnn-qubits GHZ states among remote nodes in quantum networks constitutes the resource primitives for end-to-end and on-demand communications. However, the Bell-VM problem, which determines whether a given graph state can be transformed into a set of Bell pairs on specific vertices (not necessarily remote), is known to be NP-complete. In this paper, we extend this problem, not only by focusing on nodes remote within generic graph states, but also by determining the number of extractablennn-qubit remote GHZ states - beside the number of remote EPR pairs. The rationale for tackling the extraction of GHZ states among remote nodes, rather than solely remote EPR pairs, is that a GHZ state enables the dynamic extraction of an EPR pair between any pair of nodes sharing the state. This, in turn, implies the ability of accommodating the traffic requests on-the-fly. Specially, we propose a polynomial-time algorithm for solving the aforementioned NP-complete problem. Our results demonstrate that the proposed algorithm is able to effectively adapt to generic graph states for extracting entanglement resources across remote nodes.
In the Quantum Internet, multipartite entanglement enables a rich and dynamic overlay topology, referred to as artificial topology, upon the physical one, that can be exploited for communication purposes. In fact, the ability to extractn-qubits GHZ states and EPR pairs from the original multipartite entangled state constitutes the resource primitives for end-to-end and on-demand quantum communications. Thus, in this paper, we theoretically determine upper and lower bounds for the number of extractablen-qubits GHZ states and EPR pairs involving nodes remote in the artificial topology, as well as the achievable sizenof remote GHZ states. The theoretical analysis is then complemented by the proposal of a novel algorithm, which provides in polynomial-time a heuristic solution to the above problem. This is remarkable, since the theoretical problem is NP-complete. The performance analysis demonstrates the proposed algorithm is able to effectively manipulate the original and arbitrary graph state for extracting entanglement resources across remote nodes.
Critical to the construction of large scale quantum networks, i.e. a quantum internet, is the development of fast algorithms for managing entanglement present in the network. One fundamental building block for a quantum internet is the distribution of Bell pairs between distant nodes in the network. Here we focus on the problem of transforming multipartite entangled states into the tensor product of bipartite Bell pairs between specific nodes using only a certain class of local operations and classical communication. In particular we study the problem of deciding whether a given graph state, and in general a stabilizer state, can be transformed into a set of Bell pairs on specific vertices using only single-qubit Clifford operations, single-qubit Pauli measurements and classical communication. We prove that this problem is NP -Complete.
Graph states form an important class of multipartite entangled quantum states. We propose a new approach for distributing graph states across a quantum network. We consider a quantum network consisting of nodes—quantum computers within which local operations are free—and EPR pairs shared between nodes that can continually be generated. We prove upper bounds for our approach on the number of EPR pairs consumed, completion time, and amount of classical communication required, all of which are equal to or better than that of prior work [10]. We also reduce the problem of minimizing the completion time to distribute a graph state using our approach to a network flow problem having polynomial time complexity.
Quantum repeaters are essential for establishing long-distance quantum communication to overcome the exponential decay of entanglement due to photon loss. Traditional repeater architectures rely on physical quantum memory, which introduces decoherence and poses significant practical implementation challenges. The repeater graph state (RGS) architecture offers a promising memory-less alternative that is inherently resilient to photon losses. A key challenge in implementing RGS lies in the requirement for highly efficient graph state generators and complex qubit measurement. In this work, we aim to investigate the strategies for extracting the maximum number of Bell pairs from the RGS structure via its qubit connection to resolve the well-known bottleneck problem of RGS in which only a single Bell pair can be extracted from a complete bipartite graph state. From simulations, we observe that the maximum number of extracted Bell pairs depends on its connection topology, where the Bell-pair yield tends to be maximal at low to moderate edge densities. As the number of network hops increases, the RGS must be equipped with higher inner-qubit connectivity to maintain a sufficient yield of extractable Bell pairs. Thus, the expected resource requirement shifts toward the use of RGSs with higher inner-qubit connectivity.
Abstract Multipartite entangled states, such as Greenberger–Horne–Zeilinger (GHZ) states, are important resources in multiparty quantum networking tasks. We consider protocols for generating such states from networks of Bell pairs and local operations and classical communication. We present a computationally-efficient protocol for generating GHZ states that is also efficient with respect to the number of consumed Bell pairs, (local) gates, and Bell-pair sources. Our protocol: (1) requires O ( N ) gates in a network with N nodes, independent of the network topology; (2) has time complexity O ( N 2 ), avoiding the Steiner tree and any other computationally-hard problem; (3) maintains a near-optimal number of consumed Bell pairs. Numerically, our protocol outperforms those based on (approximate) Steiner trees with respect to the number of gates and Bell-pair sources. We prove that the minimal Bell-pair source cost is given by solving the graph-theoretic dominating set problem, and we demonstrate numerically that our protocol is nearly optimal for this quantity. Finally, we analytically characterize the impact of noisy Bell pairs and gates on the fidelity of the distributed GHZ states.
Abstract Quantum communication between distant parties is based on suitable instances of shared entanglement. For efficiency reasons, in an anticipated quantum network beyond point-to-point communication, it is preferable that many parties can communicate simultaneously over the underlying infrastructure; however, bottlenecks in the network may cause delays. Sharing of multi-partite entangled states between parties offers a solution, allowing for parallel quantum communication. Specifically for the two-pair problem, the butterfly network provides the first instance of such an advantage in a bottleneck scenario. In this paper, we propose a more general method for establishing EPR pairs in arbitrary networks. The main difference from standard repeater network approaches is that we use a graph state instead of maximally entangled pairs to achieve long-distance simultaneous communication. We demonstrate how graph-theoretic tools, and specifically local complementation, help decrease the number of required measurements compared to usual methods applied in repeater schemes. We examine other examples of network architectures, where deploying local complementation techniques provides an advantage. We finally consider the problem of extracting graph states for quantum communication via local Clifford operations and Pauli measurements, and discuss that while the general problem is known to be NP-complete, interestingly, for specific classes of structured resources, polynomial time algorithms can be identified.