Promises in the hidden subgroup formulation of graph isomorphism problem

Question

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.

Answer 1

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.)