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 paperby 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.
Negative results on identical particles approach to Graph Isomorphism (GI) problem
cc.complexity theory;graph theory;graph algorithms;graph isomorphism
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.