1
$\begingroup$

The Simon's 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 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?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Joshua Grochow Nov 4 '15 at 23:10
  • $\begingroup$ @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. $\endgroup$ – Omar Shehab Nov 5 '15 at 3:35
  • 1
    $\begingroup$ As far as I can tell, what you said agrees with what I said... $\endgroup$ – Joshua Grochow Nov 5 '15 at 3:44
  • $\begingroup$ @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? $\endgroup$ – Omar Shehab Nov 5 '15 at 3:47
  • 1
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Nov 5 '15 at 4:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.