Commutative diagram for hidden subgroup representation of graph automorphism

52 Views Asked by At

The hidden subgroup representation of the graph automorphism problem is defined in the section 10.2 of QUANTUM ALGORITHMS FOR PROBLEMS IN NUMBER THEORY, ALGEBRAIC GEOMETRY, AND GROUP THEORY. It is as follows.

enter image description here

I would like to define the the problem as follows.

For a graph $\Gamma$ with $n$ vertices, a map $\varphi : S_{n} \to > \text{Mat}\left(\mathbb{C}, N \right)$ ($\text{Mat}\left(\mathbb{C}, N > \right)$ is the algebra of all $N \times N$ matrices over the complex numbers $\mathbb{C}$) from the group $S_{n}$ is said to have hidden subgroup structure if there exists a subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$, called a hidden subgroup, an injection $\ell_\varphi : S_{n}/\text{Aut}\left(\Gamma\right) \to > \text{Mat}\left(\mathbb{C}, N \right)$, called a hidden injection, such that the diagram

enter image description here

is commutative, where $S_{n}/\text{Aut}\left(\Gamma\right)$ denotes the collection of right cosets of $\text{Aut}\left(\Gamma\right)$ in $S_{n}$, and where $\nu : S_{n}/\text{Aut}\left(\Gamma\right)$ is the natural map of $S_{n}$ onto $S_{n}/\text{Aut}\left(\Gamma\right)$. We refer to the group $S_{n}$ as the ambient group and to the set $\text{Mat}\left(\mathbb{C}, N \right)$ as the target set.

The hidden subgroup version of the graph automorphism problem is to determine a hidden subgroup $\text{Aut}\left(\Gamma\right)$ of $S_{n}$ with the promise that $\text{Aut}\left(\Gamma\right)$ is either trivial or maintain a particular order depending on the type of $\Gamma$.

Is my way of defining graph automorphism capturing the whole idea?