The definition of the Hidden Subgroup Problem (HSP) is as follows (according to a lecture series by Pranab Sen),

Let $G$ be a group, $S$ a set and $f : G \to S$ a function. We are given an oracle for a reversible version of $f$ , $F(f) : |x\rangle |s\rangle \mapsto |x\rangle|s \oplus f (x)\rangle$, where the first and second registers denote elements of $G$ and $S$ respectively, and the operation $\oplus$ is a bitwise XOR of binary strings. The function $f$ satisfies the promise that there exists a subgroup $H \le G$, called the hidden subgroup, such that $f$ is constant on the left cosets of $H$ and distinct on distinct cosets. The aim is to find a generating set for $H$ by making queries to $F(f)$. In other words,

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 \in G$, $f(x) = f(y) \iff y = xh$ for some $h \in H$.

I would like to confirm whether I understand the definition right. 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\} $$

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, $S = \left\{111, 101, 010, 001 \right\}$ and $H = \left\{ 010\right\}$. Unfortunately when I try to work out the behavior of the oracle, $F\left(f\right)$, it doesn't make sense.

Here solving the HSP means determining the set $H$ given the following oracle, $F\left(f\right)$,

$$ F\left(f \right) : |x\rangle |s\rangle \mapsto |x\rangle|s \oplus f\left(x\right)\rangle\\ |000\rangle |111\rangle \mapsto |000\rangle |111 \oplus f\left(000\right)\rangle =|000\rangle |111 \oplus 111\rangle = |000\rangle |000\rangle \\ |001\rangle |101\rangle \mapsto |001\rangle |101 \oplus f\left(001\right)\rangle =|001\rangle|101 \oplus101\rangle = |001\rangle|000\rangle\\ \ldots\\ \ldots $$

Is the right register is being mapped to the right value? Could anyone please verify?

UPDATE: A supplementary question is why the definition doesn't work for right cosets?


Indeed the right register is being mapped to the right value in the two examples you have shown. But that is not the point of the reversible oracle F(f). F(f) is used because a quantum circuit only has unitary operations and f itself may not be a permutation whereas F(f) will always be. In your example, the range of f has size four whereas the domain has size 8, so f is not a permutation.

In the HSP problem, usually the right register of F(f) is initialised to zero. So the two examples you gave would become |000> |000> \mapsto |000> |111>, |001> |000> \mapsto |001> |101>.

You can define HSP for right cosets too. The same results (adapted suitably) will also hold. The point is that, in general, for non-abelian groups, a function f: G -> S either has a hidden subgroup according to the left definition or a hidden subgroup according to the right definition, but not both.

  • 1
    $\begingroup$ Velcome to the site! $\endgroup$ – kjetil b halvorsen Jun 4 '14 at 8:16

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.