Exercises are from QUANTUM COMPUTING: A GENTLE INTRODUCTION, by Eleanor Rieffel and Wolfgang Polak, published by The MIT Press.

$\def\abs#1{|#1|}\def\i{\mathbf {i}}\def\ket#1{|{#1}\rangle}\def\bra#1{\langle{#1}|}\def\braket#1#2{\langle{#1}|{#2}\rangle}\mathbf{Exercise\ B.1}$

Let $G$ and $H$ be finite graphs. A map $f:G\to H$ is a *graph isomorphism* if it is one-to-one and $f(g_1)$ and $f(g_2)$ have an edge between them if and only if $g_1$ and $g_2$ do. An *automorphism* of $G$ is a graph isomorphism from $G$ to itself, $f:G\to G$. A graph automorphism of $G$ is a permutation of its vertices.

The *graph isomorphism problem* is to find an efficient algorithm for determining whether there is an isomorphism

between two graphs or not.

a) Show that the set $\mathrm{Aut}(G)$ of automorphisms of a graph $G$ forms a group, a subgroup of the permutation group $S_n$, where $n = |G|$.

b) Two graphs $G_1$ and $G_2$ are isomorphic if there exists at least one automorphism in $\mathrm{Aut}(G_1\cup G_2) < S^{2n}$ that maps nodes of $G_1$ to $G_2$ and vice versa. Show that if $G_1$ and $G_2$ are non-isomorphic connected graphs, then $\mathrm{Aut}(G_1\cup G_2) = \mathrm{Aut}(G_1) \times \mathrm{Aut}(G_2)$.

c) Show that if $\mathrm{Aut}(G_1\cup G_2)$ is strictly bigger than $\mathrm{Aut}(G_1) \times \mathrm{Aut}(G_2)$, then there must be an element of $\mathrm{Aut}(G_1\cup G_2)$ that swaps $G_1$ and $G_2$.

d) Express the graph isomorphism problem as a hidden subgroup problem.

$\mathbf{Exercise\ B.2}$

Write out the algorithm that solves Simon's problem using the hidden subgroup framework of Section B.3.

$\mathbf{Exercise\ B.3}$

Write out an algorithm that finds the period of a function using the hidden subgroup framework of Section B.3.

$\mathbf{Exercise\ B.4}$

Find an efficient algorithm that solves the discrete logarithm problem.