# Negative results on identical particles approach to Graph Isomorphism (GI) problem

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.

• 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))? – Joshua Grochow Nov 29 '12 at 23:46