Graph states are a particular class of entangled quantum states, that play essential roles in distributed quantum computing and quantum communication. In both cases, graph states are usually used as resources for a specific set of quantum computers to share information. Therefore, distributing a graph state across a quantum network is an important problem. Currently, we do not have an efficient method for generating Einstein-Podolsky-Rosen(EPR) pairs on demand. Hence EPR pairs needed to distribute graph states are critical resources, and it is important to design distribution algorithms that reduce the need for such resources. Meignant et al. [1] presented the edge-decorated complete graph algorithm that uses n(n – 1)/2 number of EPR pairs to distribute the given graph state, where n is number of node in the network. Fischer et al [2] proposed the Graph State Transfer (GST) algorithm, which consumes fewer EPR pairs. However, GST requires an unbounded amount of memory at each node and preparation of the entire graph state in a single network node. In this poster, we present an integer programming formulation that removes these two assumptions. The model accounts for both the topology of the quantum network and memory constraints at each network node. Meanwhile, we propose a greedy algorithm to solve the problem.
Graph states are a particular class of entangled quantum states, that play essential roles in distributed quantum computing and quantum communication. In both cases, graph states are usually used as resources for a specific set of quantum computers to share information. Therefore, distributing a graph state across a quantum network is an important problem. Currently, we do not have an efficient method for generating Einstein-Podolsky-Rosen(EPR) pairs on demand. Hence EPR pairs needed to distribute graph states are critical resources, and it is important to design distribution algorithms that reduce the need for such resources. Meignant et al. [1] presented the edge-decorated complete graph algorithm that uses n(n – 1)/2 number of EPR pairs to distribute the given graph state, where n is number of node in the network. Fischer et al [2] proposed the Graph State Transfer (GST) algorithm, which consumes fewer EPR pairs. However, GST requires an unbounded amount of memory at each node and preparation of the entire graph state in a single network node. In this poster, we present an integer programming formulation that removes these two assumptions. The model accounts for both the topology of the quantum network and memory constraints at each network node. Meanwhile, we propose a greedy algorithm to solve the problem.
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.
The quantum internet will extend today's networks with a capability no classical infrastructure can offer: the distribution of entanglement between distant nodes. That single resource underlies services provably beyond classical reach, such as secure communication against computationally unbounded adversaries, blind delegated computation on remote quantum servers, and entangled networks of atomic clocks. Most of these services require a single multipartite state shared among several nodes at once — for the most part a graph state: one qubit per vertex of a graph, one entangling interaction per edge. This Thesis addresses the distribution of one such state: given an arbitrary network of entanglement switches, deliver the m-qubit path graph state, in the order the application requests, to m single-qubit end nodes — the weakest client model in the literature. Prior protocols support arbitrary topologies or such minimal end nodes, never both. The strongest of them are also centralized: the construction and the memory demand concentrate at a single node. The Thesis takes the opposite approach: a distributed protocol. The Path Graph State Distribution (PathGSD) protocol grows the target state one end node at a time behind a single reference qubit that walks a classically planned route, the shortest ordered Steiner walk. The work is partitioned among the switches, which coordinate only through entanglement and classical messages; no single node ever builds or stores the whole state. The design is deliberately simple, guided by engineering principles, and the simplicity pays at scale: planning is polynomial and completes in seconds on a network of 22,500 switches, where the closest optimization-based alternatives face exponential blow-up. Correctness is proved in the graph-state measurement calculus; a memory-reuse discipline and a parallel multi-domain execution mode complete the protocol. The protocol is implemented as communicating discrete-event processes on the QuantumSavory simulator, validated against exact theoretical expectations, and evaluated against the strongest available baselines: the star-specific Piecemaker and Factory protocols, simulated under noise, and the Graph State Transfer (GST) algorithm's proved cost expressions, evaluated exactly on arbitrary topologies. PathGSD consumes fewer Einstein-Podolsky-Rosen (EPR) pairs than the exact GST baseline on every single-domain family tested, keeps switch memory constant in the network size where the centralized baseline's grows, matches the star-specific protocols on their home topology, and reaches measured speed-ups of up to 1.9× when two administrative domains execute in parallel.
In recent years, quantum communication and quantum computing have become strategic technologies of great importance to countries around the world, with profound implications for individuals, businesses, and even nations. Among these, graph states are a very important class of multi-particle entangled states, playing a crucial role in fields such as quantum secret sharing, measurement-based quantum computing, and quantum metrology. However, the distribution of graph states faces the following challenges: existing quantum communication networks designed for single-qubit transmission cannot effectively accomplish graph state distribution tasks, and current methods for graph state distribution lack consideration of node resources, making it difficult to complete graph state distribution in some cases.We conduct research on cross-node graph states distribution methods in quantum communication networks under limited resource constraints. To address the issue that current quantum communication networks cannot handle graph states and other multi-particle entangled states, a graph state distribution method is proposed. This method combines local operations and classical communication to meet the distribution requirements for graph states, which are multi-particle entangled states. Additionally, to solve the problem of limited quantum resources at individual nodes, we proposed a graph states segmentation method. This method divides a complete graph state into subgraphs for distribution and subsequently integrates them, enabling graph state distribution services in a broader range of resource scenarios.
Quantum networks are important for quantum communication and consist of entangled states that are essential for many tasks such as quantum teleportation, quantum key distribution, quantum sensing and quantum error correction. Graph states are a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterised byasystem of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyse resource usage for our algorithm and show it to match or be improved in the number of qubits, bits for classical communication and EPR pairs utilised, as compared to prior work. The number of local operations is efficient, and the resource consumption for our approach scales linearly in the number of vertices. This presents a quadratic improvement in completion time for several classes of graph states represented by dense graphs, and implies a potential for improved fidelity in the presence of noise. Common classes of graph states are classified along with the optimal time for their distribution using subgraph complementations. We also provide a framework to similarly find the optimal sequence of operations to distribute an arbitrary graph state, and prove upper bounds along with providing approximate greedy algorithms.
Quantum networks are important for quantum communication, enabling tasks such as quantum teleportation, quantum key distribution, quantum sensing, and quantum error correction, often utilizing graph states, a specific class of multipartite entangled states that can be represented by graphs. We propose a novel approach for distributing graph states across a quantum network. We show that the distribution of graph states can be characterized by a system of subgraph complementations, which we also relate to the minimum rank of the underlying graph and the degree of entanglement quantified by the Schmidt-rank of the quantum state. We analyze resource usage for our algorithm and show that it improves on the number of qubits, bits for classical communication, and EPR pairs utilized, as compared to prior work. In fact, the number of local operations and resource consumption for our approach scales linearly in the number of vertices. This produces a quadratic improvement in completion time for several classes of graph states represented by dense graphs, which translates into an exponential improvement by allowing parallelization of gate operations. This leads to improved fidelities in the presence of noisy operations, as we show through simulation in the presence of noisy operations. We classify common classes of graph states, along with their optimal distribution time using subgraph complementations. We find a sequence of subgraph complementation operations to distribute an arbitrary graph state which we conjecture is close to the optimal sequence, and establish upper bounds on distribution time along with providing approximate greedy algorithms.
Graph states are a class of important multiparty entangled quantum states, of which Bell pairs are the special case. Realizing a robust and fast distribution of arbitrary graph states in the downstream layer of the quantum network is essential for enabling large-scale quantum networks. To address this, we propose a novel quantum network protocol, called P2PGSD, inspired by the classical Peer-to-Peer network. This protocol efficiently implements general graph state distribution in the network layer, demonstrating significant advantages in resource efficiency and scalability, particularly for sparse graph states. An explicit mathematical model for the general graph state distribution problem has also been constructed, above which the intractability for a wide class of resource minimization problems is proved and the optimality of the existing algorithms is discussed. Moreover, we leverage the space-time quantum network for memory management in network challenges, drawing inspiration from special relativity. We suggest a universal quantum distributed computation framework to exploit the strengths of our protocols, as confirmed by numerical simulations that reveal up to a 50% enhancement for general sparse graph states. This work marks a significant step toward resource-efficient multiparty entanglement distribution for diverse network topologies.