I am going through the talk, Graph isomorphism, the hidden subgroup problem and identifying quantum states, by Pranab Sen. On slide 3, the promise of the problem is defined as follows. Here is the previous related question I have asked.

Promise: Subgroup $H \le G$ such that $f$ is constant on the left cosets of $H$ and distinct on different cosets.

I am trying to follow the definition with an example. Let's take the example of set G where,

$$ G = \left\{x | x \in \left\{0, 1\right\}^*, |x| \le 3 \right\}\\ = \left\{000, 001, 010, 011, 100, 101, 110, 111\right\} $$

We assume, here the group operation is bit-wise XOR, $\oplus$, which is, in this context, convolution. So, for the group, $G$, if there is a subgroup $H$ with elements $h_i$ and an element $x$ of $G$ not in $H$, the left coset is $\left\{x \oplus h_i | i = 1, 2, \ldots \right\}$.

Suppose the period is $010$. With that, let's define $f$ as follows.

$$ f\left(000\right) \mapsto 111\\ f\left(001\right) \mapsto 101\\ f\left(010\right) = f\left(000 \oplus 010\right) \mapsto 111\\ f\left(011\right) = f\left(001 \oplus 010\right)\mapsto 101\\ f\left(100\right) \mapsto 010\\ f\left(101\right) \mapsto 001\\ f\left(110\right) = f\left(100 \oplus 010\right) \mapsto 010\\ f\left(111\right) = f\left(101 \oplus 010\right) \mapsto 001 $$

So, obviously, $H = \left\{ 010\right\}$.

Now we go by all items in the promise.

Promise 1 : $H \le G$

$H \le G$ is true in the sense that $|G| > |H|$.

Promise 2 : $f$ is content on the left cosets of $H$

We need to determine the set of left cosets of $H$ first. To determine the left coset we need to know the elements of $G$ which are not in $H$. There are $7$ such elements, $\left\{000, 001, 011, 100, 101, 110, 111 \right\}$. $|H| = 1$ So, always, $i = 1$.

For, $000 \in G, \notin H $ the left coset is $\left\{000 \oplus 010 \right\} = \left\{010 \right\}$

Because, $|H| = 1$, verification of Promise 2 is trivial. As there is only one element in the hidden group, $f$ over it is always constant.

Promise 3: $f$ is distinct on different cosets

We will have $7$ different cosets. Let $j = 1 \ldots 7$ and be the index of the elements in the set G. So, $x_j \in G$. Let $C_j$ be the coset for $x_j$.

$ \therefore C_1 = \left\{000 \oplus 010 \right\} = \left\{010 \right\} $

$C_2 = \left\{001 \oplus 010 \right\} = \left\{011 \right\}$

$C_3 = \left\{011 \oplus 010 \right\} = \left\{001 \right\}$

$C_4 = \left\{100 \oplus 010 \right\} = \left\{110 \right\}$

$C_5 = \left\{101 \oplus 010 \right\} = \left\{111 \right\}$

$C_6 = \left\{110 \oplus 010 \right\} = \left\{100 \right\}$

$C_7 = \left\{111 \oplus 010 \right\} = \left\{101 \right\}$

Is my understanding correct?


You seem to have forgotten a bit of group theory.

Subgroups are closed under inverses and the group operation. In particular, they contain the identity element. The identity of your eight-element group $G$ is $000$, and $H=\{000,010\}$, so the cardinality of it is $|H|=2$. Furthermore the number of cosets is $[G:H]=|G|/|H|=8/2=4$, and a subgroup is always itself a coset of itself ($H=eH$ where $e\in G$ is the identity). A system of representatives for these cosets (called a transversal) can be read off of the arguments for which you were able to decide the value of the function arbitrarily. This is easy to read off of the table:

  1. $000\oplus H=\{000,010\}$
  2. $001\oplus H=\{001,011\}$
  3. $100\oplus H=\{100,110\}$
  4. $101\oplus H=\{101,111\}$

These are the four cosets. They partition $G$. It is easy to check that $f$ is constant on each coset:

  1. $f(000)=111=f(010) \quad \checkmark$
  2. $f(001)=101=f(011) \quad \checkmark$
  3. $f(100)=010=f(110) \quad \checkmark$
  4. $f(101)=001=f(111) \quad \checkmark$

Finally, note that the four values taken ($111,101,010,001$) are all distinct.

  • $\begingroup$ this was helpful. $\endgroup$ – Omar Shehab Jun 12 '14 at 6:13

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.