20200903
How to transform graph states using singlequbit operations: computational complexity and algorithms
Publication
Publication
Quantum Science and Technology , Volume 5  Issue 4 p. 045016
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): singlequbit Clifford operations(LC), singlequbit 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 errorcorrection codes. We first show that deciding whether a graph stateG〉can be transformed into another graph stateG′〉using LC+LPM+CC is NPcomplete, which was previously not known. We also show that the problem remains NPcomplete even ifG′〉is restricted to be the GHZstate. However, we also provide efficient algorithms for two situations of practical interest. Our results make use of the insight that deciding whether a graph stateG〉can be transformed to another graph stateG′〉is equivalent to a known decision problem in graph theory, namely the problem of deciding whether a graph G′ is a vertexminor of a graph G. The computational complexity of the vertexminor problem was prior to this paper an open question in graph theory. We prove that the vertexminor problem is NPcomplete by relating it to a new decision problem on 4regular graphs which we call the semiordered Eulerian tour problem.
Additional Metadata  

, ,  
doi.org/10.1088/20589565/aba763  
Quantum Science and Technology  
Dahlberg, A, Helsen, J, & Wehner, S.D.C. (2020). How to transform graph states using singlequbit operations: computational complexity and algorithms. Quantum Science and Technology, 5(4). doi:10.1088/20589565/aba763
