Exercises for Appendix B

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.