4
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Welcome to QCSE! You might like the following PowerPoint from Oliveira. On page 37 it's noted that Deutsch's problem has the underlying group $\mathbb Z_2$ but on page 42 the Deutsch-Jozsa problem is left as an exercise. $\endgroup$ Sep 9 at 18:27
  • $\begingroup$ @MarkSpinelli thanks... I guess I'll try to email Oliveira. I'll post here if I find a solution. $\endgroup$
    – smitke6
    Sep 9 at 18:51

1 Answer 1

1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ I agree that we don't need to know or care about the specific fibers of $ f^{-1} (\{0\}) $ or $ f^{-1} (\{1\}) $. What I am having trouble with is bijection between $G$ and the set of input strings being unknown and unspecified. If this is the case, then literally any subset of $\{0,1\}^n$ of a size that divides $2^n$ could be a subgroup. It seems that such an assumption would take away any meaning of the HSP. This would also differ from the assumptions in any other known instance of the HSP. $\endgroup$
    – smitke6
    Sep 10 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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