Quantum graph state is a special class of nonlocal state among multiple quantum particles, underpinning several nonclassical and promising applications such as quantum computing and quantum secret sharing. Recently, establishing quantum graph states among physically distant nodes has gained increasing popularity owing to its potential in expanding current quantum applications in scale. Existing research on this topic relies on a two-step approach: first distributing low-dimension elementary entanglement to target nodes, and then fusing them into a high-dimension quantum graph state. However, most existing studies focus solely on minimizing costs (e.g., the number of elementary entanglements consumed) to entangle target nodes, while neglecting the structure of the final quantum graph state. This can easily result in weak system entanglement, jeopardizing the graph state under partial measurement or noises. In this paper, we aim to establish any arbitrary quantum graph states of strong entanglement structures at a much lower cost than the state of the art. The method is to search for and establish an alternative state to the target state that is of lowest cost in creation. Subsequently, we transform such an alternative state back to the target state via compressed single-qubit Clifford operations. To verify the performance of our developed algorithm, we conduct comprehensive simulations based on an open dataset containing all graph state structures up to 8 qubits. The results demonstrate fast algorithm convergence, an increased success probability in distributing any graph states, and $53.57\%$ saving in ERP cost compared with the state-of-the-art baseline.
Quantum graph state is a special class of nonlocal state among multiple quantum particles, underpinning several nonclassical and promising applications such as quantum computing and quantum secret sharing. Recently, establishing quantum graph states among physically distant nodes has gained increasing popularity owing to its potential in expanding current quantum applications in scale. Existing research on this topic relies on a two-step approach: first distributing low-dimension elementary entanglement to target nodes, and then fusing them into a high-dimension quantum graph state. However, most existing studies focus solely on minimizing costs (e.g., the number of elementary entanglements consumed) to entangle target nodes, while neglecting the structure of the final quantum graph state. This can easily result in weak system entanglement, jeopardizing the graph state under partial measurement or noises. In this paper, we aim to establish any arbitrary quantum graph states of strong entanglement structures at a much lower cost than the state of the art. The method is to search for and establish an alternative state to the target state that is of lowest cost in creation. Subsequently, we transform such an alternative state back to the target state via compressed single-qubit Clifford operations. To verify the performance of our developed algorithm, we conduct comprehensive simulations based on an open dataset containing all graph state structures up to 8 qubits. The results demonstrate fast algorithm convergence, an increased success probability in distributing any graph states, and 53.57% saving in ERP cost compared with the state-of-the-art baseline.
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.
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 the range of applications opened by quantum technology, often a highly entangled source state is needed as an input for a protocol (target state). The easiest example of such an application is QKD, other examples are quantum secret sharing and measurement based quantum computing. Generating a non-local entangled state is however not trivial. Let us assume that there is an entangled state (source state) present in the network before the start of the protocol. One can ask than whether this source state can be transformed to the target state with only local operations. Local operations usually have a lower error rate compared to non-local operations. As the set of all quantum states increases exponentially, we will restrict ourselves to graph states (quantum states described by a simple graph). This allows one to study the graphs and local operations in a graph theory perspective, instead of in a quantum information perspective. In this thesis we investigate the complexity of deciding equivalence of two graph states under local multi-qubit operations (T-LMQC-equivalent), where T refers to the partition denoting which qubits are on the same device which allows multi-qubit operations. When T consist only of single qubit nodes, this problem reduces to the single qubit Clifford equivalence problem (SQC-EQUIV). It is known that SQC-EQUIV can be solved in O(N^4). On the other side, if all qubits are in the same node, the problem can be solved in O(1) as every source state can be transformed to any graph state on the same vertex set. We will present three algorithms to solve T-LMQC equivalence. The first algorithm solves the problem in general but the running time scales exponentially in the number of multi-qubit nodes and the size of the graph. The other two scale polynomially in the size of the graph, but do not allow for nodes with more than 2 qubits. The remaining question is indeed whether deciding T-LMQC equivalence is an easy (in P) problem or a hard problem (NP-complete).
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.
In quantum computing and quantum information processing, graph states are a specific type of quantum states which are commonly used in quantum networking and quantum error correction. A recurring problem is finding a transformation from a given source graph state to a desired target graph state using only local operations. Recently it has been shown that deciding transformability is already NP-hard. In this paper, we present a CNF encoding for both local and non-local graph state operations, corresponding to one- and two-qubit Clifford gates and single-qubit Pauli measurements. We use this encoding in a bounded-model-checking set-up to synthesize the desired transformation. Additionally, for a completeness threshold on local transformations, we provide an upper bound on the length of the transformation if it exists. We evaluate the approach in two settings: the first is the synthesis of the ubiquitous GHZ state from a random graph state where we can vary the number of qubits, while the second is based on a proposed 14 node quantum network. We find that the approach is able to synthesize transformations for graphs up to 17 qubits in under 30 minutes.
Abstract We propose schemes to extract arbitrary graph states from two-dimensional cluster states by locally manipulating the qubits solely via single-qubit measurements. We introduce graph state manipulation tools that allow one to increase the local vertex degree and to merge subgraphs. We utilize these tools together with the previously introduced zipper scheme that generates multiple edges between distant vertices to extract the desired graph state from a two-dimensional cluster state. We show how to minimize overheads by avoiding multiple edges, and compare with a local manipulation strategy based on measurement-based quantum computation together with transport. These schemes have direct applications in entanglement-based quantum networks, sensor networks, and distributed quantum computing in general.