There has been some efforts to attack graph isomorphism problem using quantum random walk of hard-core bosons (symmetric but no double occupancy). Symmetric power of adjacency matrix, which seemed promising, was proved to be incomplete for general graphs in this paper by Amir Rahnamai Barghi and Ilya Ponomarenko. Other similar approach was also refuted in this paper by Jamie Smith. In both of these papers, they use the idea of coherent configuration (schemes) and alternative but equivalent formulation of cellular algebra (matrix subalgebra indexed by a finite set -here vertex set- closed under point-wise multiplication, complex conjugate transpose, and containing Identity matrix I and all-one matrix J) respectively to provide necessary counter arguments.

I find it very difficult to follow those arguments and even if I follow individual arguments vaguely I do not understand the core idea. I would like to know if the essence of the arguments can be explained in generic terms -may be at the cost of slight rigour- without using the language of scheme theory or cellular algebra.


1 Answer 1


You can do much better than checking all n! permutations when brute forcing a solution, http://oeis.org/A186202 The grail is showing that you can't do much better than that, or exploiting the fact that most graphs have no symmetry in them and using this to speed calculation.

  • 2
    $\begingroup$ The paper of yours referenced from OEIS shows a bound on the size of a set $S \subseteq S_n$ such that $S$ intersects every nontrivial subgroup of $S_n$. I'm probably just being slow here, but how does having such a set help you solve either a) the hidden subgroup problem for $S_n$ or b) graph isomorphism (a special case of (a))? $\endgroup$ Nov 29, 2012 at 23:46
  • 1
    $\begingroup$ If you test one nontrivial permutation from each prime cycle you have checked every possible subgroup of Sn. It is still huge. Also, it is for checking graph automorphism which is "easier" than isomorphism. $\endgroup$ Nov 30, 2012 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.