If the graph isomorphism problem can't be solved in polynomial time, do spin-networks in loop quantum gravity violate the Church-Turing thesis? To determine whether or not two graphs are isomorphic (labelled in the case of spin networks, but this doesn't change anything essential) is conjectured to be unsolvable in polynomial time in the worst case scenario. It may or may not be solvable in polynomial time using quantum computers. To compute using spin-networks, we have to determine whether or not two components describe the same network when summing up over quantum states and computing bra-ket norms.