The complexity of the vertex-minor problem

A graph H is a vertex-minor of a graph G if it can be reached from G by the successive application of local complementations and vertex deletions. Vertex-minors have been the subject of intense study in graph theory over the last decades and have found applications in other fields such as quantum information theory. Therefore it is natural to...

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

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...

Transforming graph states using single-qubit operations

Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements...