Transforming graph states to Bell-pairs is NP-Complete

Abstract

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 comment21 pages, 8 figures

References in corpus (9)

• Persistent entanglement in arrays of interacting particles
• Entanglement Distillation between Solid-State Quantum Network Nodes
• Graphical description of the action of local Clifford transformations on graph states
• Exact Topological Quantum Order in D=3 and Beyond: Branyons and Brane-Net Condensates
• Quantum network routing and local complementation
• Classical simulation versus universality in measurement based quantum computation
• An efficient algorithm to recognize local Clifford equivalence of graph states
• Transforming graph states using single-qubit operations
• Analysis of Measurement-based Quantum Network Coding over Repeater Networks under Noisy Conditions

Cited by in corpus (15)

• Complex Quantum Networks: a Topical Review
• Optimized Quantum Networks
• Influence of noise in entanglement-based quantum networks
• Limitations of nearest-neighbour quantum networks
• Extracting GHZ states from linear cluster states
• Sharp complexity phase transitions generated by entanglement
• Counting single-qubit Clifford equivalent graph states is #P-Complete
• Generating $k$ EPR-pairs from an $n$-party resource state
• Catalytic Transformation from Computationally Universal to Strictly Universal Measurement-Based Quantum Computation
• The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
• Demonstration of teleportation across a quantum network code
• Localizing multipartite entanglement with local and global measurements
• Task Concurrency and Compatibility in Measurement-Based Quantum Networks
• Polynomial-time Extraction of Entanglement Resources
• Efficient decoding of stabilizer code by single-qubit local operations and classical communication