Graph Isomorphism as

Hidden Subgroup
Problem
Omar Shehab
[email protected]

1/ 33

Outline

Group theory review

The hidden subgroup problem

Classes of HSP

An example of Abelian HSP

GI as HSP

2/ 33

Group Theory Review

Definition
A group G is a finite or infinite set of elements with a binary
operation a.k.a. group operation . Any group has following four
fundamental properties.
I
I
I

Closure: If A, B G , then A B G .
Associativity: If A, B, C G , (A B) C = A (B C ).
Identity: There is an identity element e such that
A G : e A = A e = A.
Inverse: There must be an inverse of each element.
Therefore, for each element A G , the set contains an
element B = A1 such that A A1 = A1 A = e.
3/ 33

continued...

Definition
A subgroup H G satisfies the four group requirements.
I

The order, |H|, of any subgroup, H of a group G must be a

divisor of |G |.

Let H with elements hi be the a subgroup of a group G . If an

element x G , 6 H, then x hi for i = 1, 2, . . . constitute the
left coset of the subgroup H with respect to x.

4/ 33

The Hidden Subgroup Problem

Definition
Find the subgroup H of periods of a function f : G S under the
promise that f is strictly periodic, that is, for all x, y G ,
f (x) = f (y ) y = xh for some h H.
In other words 1 ,
Given: G : group, S: set, f : G S via an oracle.
Promise: Subgroup H 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 .
1

Taken from Graph isomorphism, the hidden subgroup problem and

identifying quantum states by Pranab Sen
5/ 33

Classes of HSP

Abelian hidden subgroup problem

I
I

Integer factoring
Simons problem

Non-abelian hidden subgroup problem

I

Dihedral hidden subgroup problem

Symmetric hidden subgroup problem

Lattice problems
Graph isomorphism problems

6/ 33

Simons Problem

Definition
Suppose2 we are given a function f : {0, 1}n {0, 1}m , with
m n, and we are promised that either f is 1 to 1, or there
exists a non-trivial s, such that
x 6= x 0 (f (x)) = f (x 0 ) x 0 = x s, where denotes bitwise
exclusive-or. We wish to determine which of these conditions holds
for f , and in the second case, to find s.

Verbatim from Simons paper.

7/ 33

Simons Problem as HSP

Definition
Suppose we are given a function f : {0, 1}n {0, 1}m , with m n,
and we are promised that either f is 1 to 1, or there exists a
non-trivial h, such that x 6= x 0 (f (x)) = f (x 0 ) x 0 = x h,
where denotes bitwise exclusive-or. We wish to determine which
of these conditions holds for f , and in the second case, to find h.
Given: G = ({0, 1}n , ): group, S = {0, 1}m : set, f : G S via
an oracle.
Promise: Subgroup h H 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 .
8/ 33

Example : Simons problem for Z/2, n = 3

Subgroups are closed under inverses and the group operation.
G = S = {x|x {0, 1} , |x| 3}
= {000, 001, 010, 011, 100, 101, 110, 111}

(1)

and let the blackbox be,

f (000) 7 111, f (001) 7 101
f (010) 7 111, f (011) 7 101
f (100) 7 010, f (101) 7 001
f (110) 7 010, f (111) 7 001
Find H.
9/ 33

(2)

(We pretend that we havent seen this slide!)

Obviously, the non-trivial period is 010.

f (000) 7 111, f (001) 7 101

f (010) = f (000 010) 7 111
f (011) = f (001 010) 7 101
f (100) 7 010, f (101) 7 001
f (110) = f (100 010) 7 010
f (111) = f (101 010) 7 001

10/ 33

(3)

The Promises are Kept!

I
I

H = {000, 010}. So, Promise 1, |H| |G | = 2 < 8 is kept.

Promise 2, that f is constant on the left cosets of H, is kept.
I
I
I
I

f
f
f
f

(000) = 111 = f
(001) = 101 = f
(100) = 010 = f
(101) = 001 = f

(010) X
(011) X
(110) X
(111) X

Promise 3, that f is distinct on different cosets, is kept. 111,

101, 010 and 001 are all distinct.

This is an Abelian HSP problem because the operation is

commutative.

11/ 33

Example: Graph Isomorphism (GI) Problem

Definition
Let 3 V (G ) be the vertex set of a simple graph and E (G ) its edge
set. Then a graph isomorphism from a simple graph G to a simple
graph H is a bijection f : V (G ) V (H) such that
(u, v ) E (G ) (f (u) , f (v )) E (H).

Verbatim from (West 2000).

12/ 33

A Case of Graph Isomorphism

I

A and B are two undirected graphs with n = 4 vertices labeled

1, 2, 3 and 4 4 .

They may be described by two 4 4 adjacency matrices

respectively.

The ij-th entry of an adjacency matrix is 1 iff the graph has an

edge joining vertices i and j. Rest of the entries are zeros.

We assume a graph will always have at most one edge joining

two vertices.

This is a special case of the exposition from (Jozsa 2000)

13/ 33

Isomorphic Graphs

0
1

1
1

1
0
1
0

1
1
0
1

1
0

1
0

0
1

1
1

14/ 33

1
0
0
1

1
0
0
1

1
1

1
0

Permutations

P4 is the group of all permutations of n = 4 symbols 1, 2, 3

and 4.

A and B are isomorphic if P4 operates on A to produce

B.

Such
a permutation
is,


1 2 3 4
1 2 4 3

15/ 33

Symmetry Group of a Graph



1 2 3 4
Pick two permutations, 1 =
and
2 1 3 4


1 2 3 4
2 =
. 1 2 and 2 1 , operating on A,
1 4 3 2
separately, produces two very different graph. So, symmetric groups
are non-abelian i.e. group operations are non-commutative.

16/ 33

Non-abelianness of Graph Permutation

17/ 33

The Question

Can we detect the isomorphism of any two graph defined on n

vertices in poly (n) steps?

18/ 33

A Bigger Space
I

C is the disjoint union of A and B.

V (C ) = 2 n = 2 4 = 8.

The vertices are labeled as 1, . . . , n, n + 1, . . . 2n = 1, . . . 8 .

19/ 33

Symmetry Group of C
I

The permutation group on 2n vertices is P2n , in our case, P8 .

For our example, any permutation will be a 8 2 matrix.

A symmetric group, K , on the new graph C will be a subgroup

of P8 P8 i.e. K P8 P8 .
Any symmetric permutation on C (because of the disjoint
union)

case 1: either separately permutes the vertices {1, 2, 3, 4} and

{5, 6, 7, 8},
case 2: or swaps these two sets of vertices.

20/ 33

Subgroups in P2n
I

Let, H = P4 P4 .

The elements of H are ordered pairs of vertices of A and B .

The group operation is as usual composition of permutation.

If case 1 is true, K H.

Let be the special permutation i.e. involution. So, = 1

and 2 = e.

So, we could define a group on 2n = 8 vertices as {{e, } , }.

Any nontrivial group operation on H, H, will just swap the
vertices in the ordered pairs.

So, if case 2 is true, K H.

21/ 33

Verification

Claim 1:If A and B are isomorphic exactly half of the

members of K are in H and half are in H.

Claim 2:If A and B are not isomorphic then K H

22/ 33

Claim 1:
I
I
I

I
I

K
2

H, K2 H

Let A and B be the two graphs we previously seen.

K is the symmetric group over A B.
K contains all the ordered pairs of elements from P4 and P4
respectively.
By definition, all such ordered pairs are in H.
Being a symmetric group, K also has the previously mentioned
ordered pairs in reverse order.
The involution can generate each of those reversed pairs by
operating on individual elements of H respectively.
So, these two sets of ordered pairs are equal in number and
constitutes K .

23/ 33

Claim 2: K H
Redefine A and B.

I
I
I
I

The symmetric group, K is defined over A B = C .

The vertices will be relabeled to 1 . . . 8.
Every element of K separately permutes {1, 2, 3, 4} and
{5, 6, 7, 8}. So, K H.
Any swap operation on K will destroy the symmetry. So,
K 6 H.
24/ 33

The Ambient Group, G

Let G = H H.

H is a subgroup.

is a coset of H.

25/ 33

GI as HSP

Definition
Find the symmetric hidden subgroup G on the disjoint union of two
graphs, A and B, each of n vertices, in the permutation group P2n
by querying an oracle, f : P2n P2n .

26/ 33

Break

Thank you!

27/ 33

Example: Graph Isomorphism (GI) Problem

Definition
Let 5 V (G ) be the vertex set of a simple graph and E (G ) its edge
set. Then a graph isomorphism from a simple graph G to a simple
graph H is a bijection f : V (G ) V (H) such that
(u, v ) E (G ) (f (u) , f (v )) E (H).

Verbatim from (West 2000).

28/ 33

A Case of Graph Isomorphism

I

A and B are two undirected graphs with n = 4 vertices labeled

1, 2, 3 and 4 6 .

They may be described by two 4 4 adjacency matrices

respectively.

The ij-th entry of an adjacency matrix is 1 iff the graph has an

edge joining vertices i and j. Rest of the entries are zeros.

We assume a graph will always have at most one edge joining

two vertices.

This is a special case of the exposition from (Jozsa 2000)

29/ 33

Isomorphic Graphs
1

6
0 1 1
1 0 0
1 1 0

0 1 0
1 0 1
0 1 0

30/ 33

The group

P2n P2n is the permutation group of 2n symbols. The first

(second) n symbols correspond to the vertices of G1 (G2 ). For our
example, we consider S6 hence it is non-abelian.

31/ 33

The sub group

K P2n P2n is the set of all permutations of the vertex set

which leaves the edge set the same. So, K is a symmetry group.

32/ 33

Promise 1

K P2n P2n

33/ 33

Questions and Answers

Thank you!

34/ 33