<p>The <a href="https://en.wikipedia.org/wiki/Simon%27s_problem" rel="nofollow">Simon's problem</a> involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has the capability to encode the inputs.</p>

<p>The graph isomorphism problem is defined over two input graphs. The <a href="http://arxiv.org/pdf/quant-ph/0012084v1.pdf" rel="nofollow">hidden subgroup representation</a> of the problem involves a function which doesn't take the graphs as inputs. Rather it takes permutation over the vertices as input. Those permutations are agnostic of the input graphs. In the standard method, the first register doesn't have the capability to encode the inputs i.e. the graphs.</p>

<p>Can anyone explain why the HSP representations of these two problem are so different in the sense that in the standard method of an hidden subgroup approach the first register of one of them encodes the inputs but the other doesn't?</p>

CC BY-SA 3.0
2015-11-04T23:10:28.927Z
I'm not sure I understand the question. Simon's problem simply *is* an instance of HSP. Graph isomorphism gets *reduced* to an instance of HSP over the symmetric group. So the register doesn't encode a graph, it encodes the instance of the HSP that the GI instance got transformed into... Does that answer your question?
Joshua Grochow
CC BY-SA 3.0
2015-11-05T03:35:30.517Z
@JoshuaGrochow, I am afraid, the first register doesn't encode the input graphs. It rather encodes the permutations which could be applied to any graphs.
Omar Shehab
CC BY-SA 3.0
2015-11-05T03:44:44.393Z
As far as I can tell, what you said agrees with what I said...
Joshua Grochow
CC BY-SA 3.0
2015-11-05T03:47:38.167Z
@JoshuaGrochow, yes. When we apply the standard method on the HSP representation of the Simon's problem, the first register encodes the set over which the problem is defined i.e. the set of binary strings. But on the other hand, the first register doesn't encode the set over which the graph isomorphism is defined i.e. the set of the two graphs. Why don't we have a HSP representation of GI which, when the standard method is applied on, allows us to encode the input graphs in the first register?
Omar Shehab
CC BY-SA 3.0
2015-11-05T04:20:51.737Z
Because the set of binary strings is a group, and it's that group that is being used in the HSP representation of Simon's problem. But the set of graphs is not (in any particularly natural way that relevant to GI) a group, so any HSP representation of GI must first translate groups into groups somehow, and it is those groups (or rather, their elements) that are represented in the registers of the algorithm for HSP.
Joshua Grochow
CC BY-SA 3.0
2015-11-05T06:14:42.900Z
@JoshuaGrochow, understood. Say we limit to our discussion for the graph isomorphism problem over the permutation cycle graphs (http://math.stackexchange.com/questions/1491568/relation-between-automorphism-group-of-a-permutation-cycle-graph-and-the-cyclic) whose adjacency matrices are invertible. Can we in that case have a HSP representation of this special graph isomorphism problem which allows us to encode the input graphs in the first register?
Omar Shehab
CC BY-SA 3.0
2015-11-05T16:53:07.510Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/31150/discussion-between-joshua-grochow-and-omar-shehab).
Joshua Grochow
<quantum-computing><graph-isomorphism><quantum-information><gr.group-theory>
First register in the hidden subgroup representations of Simon's and graph isomorphism problems
Omar Shehab
# First register in the hidden subgroup representations of Simon's and graph isomorphism problems

(Asked by: username_0 on 2015-11-04)

The [Simon's problem](https://en.wikipedia.org/wiki/Simon%27s_problem) involves a function which takes binary strings as inputs. One seeks to find the period of the function which acts on those inputs. In the standard method, the first register has the capability to encode the inputs.

The graph isomorphism problem is defined over two input graphs. The [hidden subgroup representation](http://arxiv.org/pdf/quant-ph/0012084v1.pdf) of the problem involves a function which doesn't take the graphs as inputs. Rather it takes permutation over the vertices as input. Those permutations are agnostic of the input graphs. In the standard method, the first register doesn't have the capability to encode the inputs i.e. the graphs.

Can anyone explain why the HSP representations of these two problem are so different in the sense that in the standard method of an hidden subgroup approach the first register of one of them encodes the inputs but the other doesn't?

**Tags:** quantum-computing, graph-isomorphism, quantum-information, gr.group-theory

> **Comments:**
> **username_1**: I'm not sure I understand the question. Simon's problem simply *is* an instance of HSP. Graph isomorphism gets *reduced* to an instance of HSP over the symmetric group. So the register doesn't encode a graph, it encodes the instance of the HSP that the GI instance got transformed into... Does that answer your question?  
> **username_0**: @JoshuaGrochow, I am afraid, the first register doesn't encode the input graphs. It rather encodes the permutations which could be applied to any graphs.  
> **username_1**: As far as I can tell, what you said agrees with what I said...  
> **username_0**: @JoshuaGrochow, yes. When we apply the standard method on the HSP representation of the Simon's problem, the first register encodes the set over which the problem is defined i.e. the set of binary strings. But on the other hand, the first register doesn't encode the set over which the graph isomorphism is defined i.e. the set of the two graphs. Why don't we have a HSP representation of GI which, when the standard method is applied on, allows us to encode the input graphs in the first register?  
> **username_1**: Because the set of binary strings is a group, and it's that group that is being used in the HSP representation of Simon's problem. But the set of graphs is not (in any particularly natural way that relevant to GI) a group, so any HSP representation of GI must first translate groups into groups somehow, and it is those groups (or rather, their elements) that are represented in the registers of the algorithm for HSP.  
> **username_0**: @JoshuaGrochow, understood. Say we limit to our discussion for the graph isomorphism problem over the permutation cycle graphs (http://math.stackexchange.com/questions/1491568/relation-between-automorphism-group-of-a-permutation-cycle-graph-and-the-cyclic) whose adjacency matrices are invertible. Can we in that case have a HSP representation of this special graph isomorphism problem which allows us to encode the input graphs in the first register?  
> **username_1**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/31150/discussion-between-joshua-grochow-and-omar-shehab).  

---

## 0 answers

