How to transform graph states using single-qubit operations

Abstract

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. This question is of interest for effective routing or state
preparation decisions in a quantum network or distributed quantum
processor and also in the design of quantum repeater schemes and quantum
error-correction codes. 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, which was previously not known. We also show that
the problem remains NP-complete even if |G) is restricted to be the
GHZ-state. However, we also provide efficient algorithms for two
situations of practical interest. Our results make use of the insight
that deciding whether a graph state |G) can be transformed to another
graph state |G) is equivalent to a known decision problem in graph
theory, namely the problem of deciding whether a graph G' is a
vertex-minor of a graph G. The computational complexity of the
vertex-minor problem was prior to this paper an open question in graph
theory. We prove that the vertex-minor problem is NP-complete by
relating it to a new decision problem on 4-regular graphs which we call
the semi-ordered Eulerian tour problem.