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

Axel Dahlberg, Jonas Helsen, Stephanie Wehner

Research output: Contribution to journalArticleScientificpeer-review

23 Downloads (Pure)

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.

Original languageEnglish
Article number045016
Number of pages61
JournalQuantum Science and Technology
Volume5
Issue number4
DOIs
Publication statusPublished - 2020

Keywords

  • Complexity
  • Graph states
  • Local operations

Fingerprint

Dive into the research topics of 'How to transform graph states using single-qubit operations: Computational complexity and algorithms'. Together they form a unique fingerprint.

Cite this