What is the hidden subgroup in Deutsch-Jozsa?

Question

It is noted by several sources (e.g. this paper) that the problem solved by the Deutsch-Jozsa (DJ) algorithm is an instance of the Hidden Subgroup Problem (HSP). However, I fail to see this for $n>2$.

For DJ to be an instance of the HSP, we need the possible oracles to implement functions $ f: G \rightarrow X $ from a group $G$ to a set $X$, such that $f$ "hides" an unknown subgroup $ H \subset G $. The oracles in DJ implement functions from $ \left\{ 0,1 \right\}^n $ to $ \left\{0,1 \right\} $, that are promised to be either constant or balanced (where "balanced" means "yields $0$ on exactly one half of its inputs). Thus, $G$ should be a group with the underlying set $ \left\{ 0,1 \right\}^n $, and we identify $X$ with $ \left\{0,1 \right\} $. Moreover, we can consider only subgroups $H$ with index $1$ or $2$, since a function with codomain of size $m$ cannot hide a subgroup with index larger than $m$.

Now, clearly any constant function hides the subgroup $H = G$; but I cannot think of any group structure for $G$, such that any balanced function on $G$ would hide some subgroup $H$. For this to happen, the fibers $ f^{-1} \left( \left\{0\right\}\right) $ and $ f^{-1} \left( \left\{ 1 \right\}\right) $ must be the cosets of some index-$2$ subgroup $H$, but clearly this is not always the case. For example, consider $n=3$. If $G = (\mathbb{Z}_2)^3$, then the following subset of size $4 = 2^3/2$ that contains the identity element $000$ is a subgroup: $$ H = \left\{ 000, 001, 110, 111 \right\} \tag{1}$$ but the following subset of size $4$ that includes the identity is not a subgroup: $$ H = \left\{ 000, 001, 010, 100 \right\} \tag{2}$$ For $ n \leq 2 $ we do not have this problem, as any subset of $ (\mathbb{Z}_2)^n $ of size $ 2^n/2 $ that contains the identity is indeed a subgroup. Am I missing anything?

Answer 1

Thinking about this some more, for the Deutsch-Jozsa problem I don't think the parent group $G$ is $n$ copies of $\mathbb Z_2$, but is rather $\mathbb Z/(2^n\mathbb Z)$. That is, the parent group is the additive group of integers modulo $2^n$.

If $f$ is constant, then $H=G$, while if $f$ is balanced, then $H=\mathbb Z/(2^{n-1}\mathbb Z)$.

But if $f$ is balanced then there is an unknown and unspecified permutation or bijection between the input strings $\{0,1\}^n$ and the integers $\{0,1,\ldots,2^n-1\}$. In that case we don't know (or don't even care) what the specific fibers of $f^{-1}(\{0\})$ or $f^{-1}(\{1\})$ are; we just know that there is some mapping between these fibers and one half of $\{0,1,\ldots,2^n-1\}$.

---

Page 241 of Mike and Ike gives a nice table and recognizes that Deutsch's problem $(n=1)$ has, as the parent group, $(\mathbb Z_2,\oplus)$, but doesn't give a corresponding entry for the Deutsch-Jozsa problem $(n\gt 1)$. Indeed on page 247 they refer to Jozsa's 1997 article "Quantum Algorithms and the Fourier Transform" (arxiv link to Jozsa's article), and assert that Jozsa was among the first to:

explicitly provide a uniform description of the Deutsch–Jozsa, Simon, and Shor algorithms in terms of the hidden subgroup problem (emphasis added).

Jozsa's 1997 article does describe the difference between Deutsch's problem $(n=1)$ and the Deutsch-Jozsa problem $(n\gt 1)$ very nicely, but does not clearly explain the particular groups of relevance in the $(n\gt 1)$ case, apart from suggesting that the group $G$ (he calls it $B$) is $(\mathbb Z_2)^n$, which, as you explained in your question, may not be correct.

So, I guess the literature might have been silent about the question in the title, at least up until then?