December 8, 2022

Transforming graph states to Bell-pairs is NP-Complete

Critical to the construction of large scale quantum networks and a future 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.

Researchers at TU Delft and QuTech have focused 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 they studied 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.

They have proved that this problem is NP-Complete.

Read more.