Counting single-qubit Clifford equivalent graph states is # P -complete

Axel Dahlberg*, Jonas Helsen, Stephanie Wehner

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

3 Citations (Scopus)
68 Downloads (Pure)


Graph states, which include Bell states, Greenberger-Horne-Zeilinger (GHZ) states, and cluster states, form a well-known class of quantum states with applications ranging from quantum networks to error-correction. Whether two graph states are equivalent up to single-qubit Clifford operations is known to be decidable in polynomial time and has been studied in the context of producing certain required states in a quantum network in relation to stabilizer codes. The reason for the latter is that single-qubit Clifford equivalent graph states exactly correspond to equivalent stabilizer codes. We here consider that the computational complexity of, given a graph state |G«, counting the number of graph states, single-qubit Clifford equivalent to |G«. We show that this problem is #P-complete. To prove our main result, we make use of the notion of isotropic systems in graph theory. We review the definition of isotropic systems and point out their strong relation to graph states. We believe that these isotropic systems can be useful beyond the results presented in this paper.

Original languageEnglish
Article number022202
Number of pages11
JournalJournal of Mathematical Physics
Issue number2
Publication statusPublished - 2020


Dive into the research topics of 'Counting single-qubit Clifford equivalent graph states is # P -complete'. Together they form a unique fingerprint.

Cite this