How would HSP with $S_N$ work when the automorphism subgroup is (almost) equal to the symmetric group?

The graph isomorphism problem can be reduced to a case of the hidden subgroup problem, with the group $$S_N$$ and the function $$f \colon \pi \mapsto \pi(G)$$ where $$G$$ is some graph, and $$\pi \in S_N$$.

The hidden subgroup is the group $$Aut(G)$$; the group of automorphisms on $$G$$.

But consider the following adjacency matrix

$$\begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix}$$

In this graph, every node is indistinguishable, so the automorphism group is equal to the symmetric group: $$Aut(G) = S_N$$.

This is an issue. Two graphs are isomorphic if their disjoint union has an automorphism that exchanges their nodes and edges. But running the HSP on the above example of $$G$$ gives us the full $$S_N$$ "subgroup" as an output. This group has $$N!$$ entries, meaning that we would have to search through all $$N!$$ entries until we find an automorphism that swaps the components of the graphs. But this is clearly $$O(N!)$$ time.

Graph isomorphism is thought to be intractable on quantum computers, yes. But I don't think this is the reason. So how would an algorithm alleviate this?

• There are two graphs in the Graph Isomorphism Problem and you form the wreath product between them IIRC - here you've only given one graph $G$. But then, surely it's even classically easy to tell whether a graph on $n$ vertices is (isomorphic to) the complete graph $K_n$, isn't it? Commented May 5, 2023 at 0:41
• Well, I guess your adjacency matrix is the complete graph *with self loops. But still I’d guess it’s easy to find out whether a test graph is isomorphic thereto. Just look at the spectrum of the adjacency matrix. I doubt there’s anything isospectral thereto. Commented May 5, 2023 at 2:29
• @MarkS I think I may understand what you're saying. The graphs generated by "combining" two subgraphs that we want to check the isomorphic-ness of can only have a polynomial number of elements in the automorphism group? Whereas I provided a graph that cannot be generated by "combining" two subgraphs. I don't see how this is necessarily true though. Commented May 5, 2023 at 2:53

TL;DR: We do not need to inspect all the elements of the hidden subgroup $${\mathcal H}=Aut(G)$$. We only need to inspect the elements of the generating set that HSP subroutine has found. An efficient HSP subroutine will return a generating set whose size is polynomial in $$\log|\mathcal{H}|$$. Finally, note that $$\log N!=O(N\log N)$$, so even if $$Aut(G)\simeq S_N$$, we still need to inspect a number of permutations that is polynomial in $$N$$.

Background

For any finite set $$A$$, let $$S_A$$ denote the group of all permutations of $$A$$. If $$G=(V,E)$$ with $$E\subset V\times V$$ is a graph and $$\pi\in S_V$$ a permutation of its vertices, then set $$\pi(G)=(V,\pi(E))$$ where $$\pi(E)=\{(\pi(u),\pi(v))\,|\,(u,v)\in E\}$$. Finally, let $$Aut(G)\subset S_V$$ denote the subgroup of $$S_V$$ consisting of vertex permutations $$\pi$$ that fix $$G$$, i.e. $$\pi(G)=G$$.

In the Graph Isomorphism (GI) decision problem we are given two graphs $$G_1=(V,E_1)$$ and $$G_2=(V,E_2)$$ with $$N$$ vertices and are asked to determine whether they are isomorphic, i.e. if there exists a permutation $$\pi\in S_V$$ such that $$G_1=\pi(G_2)$$.

In the Hidden Subgroup Problem (HSP) we are given a group $${\mathcal G}$$ and a function $$f:{\mathcal G}\to X$$ to some set $$X$$ which hides$$^1$$ an unknown subgroup $${\mathcal H}$$ of $${\mathcal G}$$ and are asked to provide a generating set for $${\mathcal H}$$. There is a subtlety here. Many generating sets for a large group are themselves large, after all $${\mathcal G}$$ is a generating set for $${\mathcal G}$$. However, an efficient HSP subroutine by definition outputs a generating set whose size is polynomial in $$\log|\mathcal{G}|$$. This is always possible since, by group theory, every group $${\mathcal G}$$ has a generating set with at most $$\log_2|{\mathcal G}|$$ generators$$^2$$.

Reduction

Imagine that we have a magic computer that solves the HSP for permutation groups. We will use it to solve GI for two connected$$^3$$ graphs $$G_1$$ and $$G_2$$ as follows. First, create the disjoint union $$G=(W,E)$$ where $$W=V\sqcup V=V_1\cup V_2$$ and $$E=E_1\sqcup E_2$$. Next, run the HSP solver on the magic computer with $$\mathcal{G}:=S_W$$, $$X$$ the set of graphs with vertices in $$W$$ and $$f:\mathcal{G}\to X$$ defined by $$f(\pi):=\pi(G)$$. It is an exercise in the application of definitions to show that $$f$$ hides $$Aut(G)$$. Therefore, our magic computer returns a set $$\mathcal{S}$$ that generates $$Aut(G)$$.

Now, suppose that every generator $$\sigma\in\mathcal{S}$$ maps $$V_1$$ to $$V_1$$. Then it is impossible to use the generators to construct a permutation that sends a $$v\in V_1$$ to $$w\in V_2$$. Consequently, in this case, every $$\pi\in Aut(G)$$ maps $$V_1$$ to $$V_1$$ and $$V_2$$ to $$V_2$$. Therefore, $$G_1$$ is not isomorphic to $$G_2$$. Conversely, if there is a generator $$\sigma\in\mathcal{S}$$ that sends $$v\in V_1$$ to $$w\in V_2$$, then $$\sigma$$ necessarily maps $$V_1$$ to $$V_2$$ and $$V_2$$ to $$V_1$$. Therefore, $$G_1$$ is isomorphic to $$G_2$$.

Complexity

Thus, we only need to inspect the effect of every $$\sigma\in\mathcal{S}$$ on every element of $$v\in V_1$$ in order to determine whether $$G_1$$ and $$G_2$$ are isomorphic. Obviously, $$V_1$$ has size polynomial in $$N$$. However, $$\mathcal{S}$$ has size polynomial in $$\log|Aut(G)|\leqslant\log|S_N|=\log N!=O(N\log N)$$, so $$\mathcal{S}$$ also has size polynomial in $$N$$. We conclude that the cost of classical post-processing is also polynomial in $$N$$.

Remarks

Note that the reduction above means that the HSP subroutine will never be invoked on a complete graph. After all, $$G$$ is disconnected! Nevertheless, $$Aut(G)$$ may be $$S_N$$. Still, as the argument above shows, the complexity of the classical post-processing remains polynomial.

$$^1$$ Function $$f:G\to X$$ hides $$H$$ if $$f$$ is constant on each coset of $$H$$ and injective on every transversal.
$$^2$$ See e.g. $$A2.1.1$$ on page $$611$$ in Nielsen & Chuang for proof.
$$^3$$ Fun exercise: What goes wrong if $$G_1$$ and $$G_2$$ are not connected? How to fix the issue?