20200207
Counting singlequbit Clifford equivalent graph states is #ℙcomplete
Publication
Publication
Journal of Mathematical Physics , Volume 61  Issue 2 p. 022202
Graph states, which include Bell states, GreenbergerHorneZeilinger (GHZ) states, and cluster states, form a wellknown class of quantum states with applications ranging from quantum networks to errorcorrection. Whether two graph states are equivalent up to singlequbit 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 singlequbit 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, singlequbit Clifford equivalent to G⟩. We show that this problem is #ℙ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.
Additional Metadata  

doi.org/10.1063/1.5120591  
Journal of Mathematical Physics  
Dahlberg, A, Helsen, J, & Wehner, S.D.C. (2020). Counting singlequbit Clifford equivalent graph states is #ℙcomplete. Journal of Mathematical Physics, 61(2). doi:10.1063/1.5120591
