# Promises in the hidden subgroup formulation of graph isomorphism problem

In the 3rd slide of the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen, the promise of the problem is defined as follows.

Given: $G$: group, $S$: set, $f: G \to S$ via an oracle.

Promise: Subgroup $H \le G$ such that $f$ is constant on the left cosets of $H$ and distinct on different cosets.

Task: Find the hidden subgroup $H$ by querying f.

If we enumerate the promises, there are three of them.

1. $H \le G$.
2. $f$ is constant on the left cosets of $H$.
3. $f$ is distinct on different cosets.

I am trying to understand the promises in the context of hidden subgroup formulation of the graph isomorphism problem.

Let $A$ and $B$ be two simple graphs each of $n$ vertices. The permutation group on $n$ vertices is $\mathcal{P}_n$. Let, $C$ be their disjoint union i.e. $C = A \cup B$. We relabel the vertices as $1, \ldots, n, n+1, \ldots , 2n$. The permutation group on $2n$ vertices is $\mathcal{P}_{2n}$. A symmetric group $K$ on the new graph $C$ will be a subgroup of $\mathcal{P}_{2n}$ i.e. $K \subset \mathcal{P}_{2n}$. Any symmetric permutation on $C$,

1. case 1: either separately permutes the vertices $1 \ldots n$ and $n+1 \ldots 2n$,
2. case 2: or swaps these two sets of vertices.

Let $H = \mathcal{P}_n \times \mathcal{P}_n$. The elements of $H$ are ordered pairs of vertices of $A$ and $B$. If case 1 is true, $K \subset H$. Let $\sigma$ be the special permutation i.e. involution. So, $\sigma = \sigma^{-1}$ and $\sigma^2 = e$. So, we can define a group on $2n$ vertices as $\left\{\left\{e, \sigma\right\}, \circ \right\}$. Any nontrivial group operation on $H$, $\sigma H$, will just swap the vertices in the ordered pairs. So, if case 2 is true, $K \subset \sigma H$. Let $G = H \cup \sigma H$. So, $H$ is a subgroup of $G$ and $\sigma$ is the coset of $H$.

So, I think, the formal statement of the graph isomorphism problem as a hidden subgroup problem is as follows:

Find the symmetric hidden subgroup $H$ on the disjoint union of two graphs, $A$ and $B$, each of $n$ vertices, in the permutation group $\mathcal{P}_{2n}$ by querying an oracle, $f : \mathcal{P}_{2n} \to \mathcal{P}_{2n}$.

If I am correct so far, I would like to identify the three promises we are expecting.

1. $H \le \mathcal{P}_{2n}$
2. $f$ is constant on the left cosets, i.e., $\sigma H$ of $H$. This is trivial as there is only one nontrivial element of $\mathcal{P}_{2n}$ which constitutes the left coset of $H$. So, it is constant.
3. $f$ is distinct on different cosets. This is true too as $e H \ne \sigma H$.

Am I getting it right?

Here is the previous related question I have asked.

First of all, $K$ is the symmetry group of $C$, not "a" "symmetric" group.

Second of all, just because the letter $H$ is used in the statement of the hidden subgroup problem and the letter $H$ is also used for one of the groups in the graph isomorphism problem setup, doesn't mean that the latter is functioning as the former. Indeed, we're supposed to turn the isomorphism problem into a hidden subgroup problem, so the problem needs to depend on what graphs we have, but $H$ does not at all depend on the graphs $A$ and $B$, it only depends on their size $n$. Furthermore, $H$ is already known right from the get-go, whilst the promised subgroup in a hidden subgroup problem is a mystery that we need to find out. That's $K$.

Here, we have

• A subgroup $K\le {\cal P}_{2n}\times{\cal P}_{2n}$ (namely, the symmetry group of $C$: the set of all permutations of the vertex set which leaves the edge set the same).
• A function $f:{\cal P}_{2n}\times{\cal P}_{2n}\to M_{2n\times 2n}$ which sends a permutation of all of the vertices of $C$ to the adjacency matrix of the new graph obtained by keeping the same vertex set but applying the function $f$ to the endpoints of each edge, thereby moving the edges around.
• The function $f$ is constant on cosets of $K$, and distinct on distinct cosets. (Are you able to prove this fact? Argue $f(\alpha)=f(\beta)$ if and only if $\alpha\beta^{-1}\in K$.)

This is the setup of the hidden subgroup problem. By solving it, we find $K$. After we have $K$, we merely need to check if $K\cap\sigma H$ is empty or not: if it's empty, then $A\not\cong B$ are nonisomorphic, whereas if it's not empty, there is an isomorphism $A\cong B$ induced from an element of $K\cap\sigma H$, and this solves the graph isomorphism problem. (As the arxiv paper you linked last time states, we technically don't need to fully solve for $K$ here, only figure out of $K\cap\sigma H$ is empty or not.)

• could you please elaborate the argument that $f(\alpha) = f(\beta) \iff \alpha \beta^{-1} \in K$ little more? Thanks! – Omar Shehab Jun 30 '14 at 19:04
• @Omar Let $G$ act on any set $X$, and pick some $x\in X$. The map $f:G\to Gx$ given by $g\mapsto gx$ is such that $f(\alpha)=f(\beta)$ iff $\alpha,\beta$ represent the same coset of ${\rm Stab}(x)$. Apply that here, with the group $G={\cal P}_{2n}\times{\cal P}_{2n}$, the space $X$ of adjacency matrices of possible graphs on the vertices of $C$, and $x$ the adjacency matrix of the graph $C$ with stabilizer $K$. – blue Jun 30 '14 at 21:54
• @OmarShehab What's that supposed to mean? It's the stabilizer of a single graph's adjacency matrix, or equivalently its edge set. – blue Jun 30 '14 at 23:35
• $kx=x$, that's what stabilization means. It's not just an isomorphic graph, it's the same exact graph. If you want the set of all adjacency matrices of graphs isomorphic to $C$ on the same vertex set, that would be the orbit of $x$ under the action of all of $G$, not $K$. – blue Jul 1 '14 at 2:10
• @Omar You should have known, or researched, or asked, what that meant long before all of this discussion. How is it possible to try to tackle a question over months of time in this amount of depth without knowing what the problem is even asking? Anyway: A function is constant on cosets if its restriction to any coset is a constant function, i.e. $f(a)=f(b)$ whenever $a$ and $b$ are in the same coset. Of course here we are speaking of left cosets. Having distinct values on distinct cosets means $f(a)\ne f(b)$ whenever $a$ and $b$ belong to different (left) cosets. – blue Jan 7 '15 at 2:02