Counting single-qubit Clifford equivalent graph states is #P-complete
Counting single-qubit Clifford equivalent graph states is #P-complete
Graph states, which include for example Bell states, GHZ states and cluster states, form a well-known class of quantum states with applications ranging from quantum networks to error-correction. Deciding whether two graph states are equivalent up to single-qubit Clifford operations is known to be decidable in polynomial time and have …