How to transform graph states using single-qubit operations: computational complexity and algorithms

Understand

Graph states are ubiquitous in quantum information with diverse applications ranging from quantum network protocols to measurement based quantum computing.

• Here we consider the question whether one graph (source) state can be transformed into another graph (target) state, using a specific set of quantum operations (LC+LPM+CC): single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits.
• We first show that deciding whether a graph state |G> can be transformed into another graph state |G'> using LC+LPM+CC is NP-Complete, even if |G'> is restricted to be the GHZ-state.
• However, we also provide efficient algorithms for two situations of practical interest: 1.