# What is the complexity of hidden subgroup problems?

It is often stated that some of the "hidden subgroup problems" can be efficiently solved by quantum computers if the group is abelian, while no efficient algorithm is known for the non-abelian case. The problems of the first case include factorization which is in NP (more precisely, there is a decision problem related to factorization that is in NP).

I would like to know if there is a general formulation of the abelian hidden subgroup problems as NP problems.

• Are you asking whether the abelian hidden subgroup problem is in NP - that is, are you asking whether a polynomial certificate always exists for the abelian hidden subgroup problem? Or are you asking something more subtle? Feb 13, 2022 at 23:52
• I'm not asking about anything subtle! Rather, I see that the papers are quite cautious about this point, and always speak of "some" of the HSP problems rather than about all of them. So I suspect that there can be some subtlety there, which prevents the formulation as NP problem. Maybe a non-polynomial size certificate. Feb 14, 2022 at 8:06

TL;DR: The general version of the Hidden Subgroup Problem (abelian or otherwise) is not in NP, because it is an oracle problem.

## Background: $$\text{NP}$$

Recall that a language $$L\subset \bigcup_{k=0}^\infty\{0,1\}^k$$ belongs to $$\text{NP}$$ if there exists a deterministic Turing machine $$M_L$$ such that for every binary string $$x\in L$$ there exists a polynomial-size certificate $$w$$ with the property that the pair $$(x,w)$$ makes $$M_L$$ halt in polynomial time and answer "YES" and for every binary string $$x\notin L$$ all pairs $$(x,w)$$ make $$M_L$$ halt in polynomial time and answer "NO".

This definition has two important consequences. First, $$\text{NP}$$ is a class of decision problems. Second, $$\text{NP}$$ is a class of problems described as data on the input tape of a Turing machine. In particular, it excludes problems specified via access to an oracle.

## Hidden Subgroup Problem

We say that a function $$f:G\to X$$ from a finitely generated group $$G$$ to a finite set $$X$$ hides the subgroup $$H$$ of $$G$$ if $$f(g_1)=f(g_2)\iff g_1g_2^{-1}\in H$$. The Hidden Subgroup Problem $$\text{HSP}$$ is the following: given access to an oracle for $$f$$, find a set $$S_H\subset G$$ that generates the hidden subgroup $$H$$.

Clearly, $$\text{HSP}$$ is not in $$\text{NP}$$, because it is not a decision problem and because it is specified as an oracle for $$f$$.

## Decision variant

We can easily remedy the first issue by defining the decision variant $$\text{HSP}_D$$ of the Hidden Subgroup Problem as the following: given access to an oracle for $$f$$, determine whether $$H$$ is trivial.

## Oracles

However, we cannot turn $$\text{HSP}$$ into a problem that may be directly described on the input tape of a Turing machine without losing generality. Instead, we can ask a different question that captures the same overall intention as the original. Namely, we can ask whether $$\text{HSP}_D$$ belongs to the analogue of $$\text{NP}$$ for oracle problems. In other words, we can ask whether there exists easily checkable certificate that $$H$$ is a non-trivial subgroup of $$G$$.

I don't know whether this is the case for the general Hidden Subgroup Problem. However, consider the promise problem $$\text{HSP}^h$$ which is the same as $$\text{HSP}$$ except for the additional assumption that $$X$$ is a group and $$f$$ a group homomorphism. We can show that its decision variant $$\text{HSP}_D^h$$ has certificates that we can verify using a polynomial number of oracle queries.

## $$\text{HSP}_D^h$$ has polynomially verifiable certificates

Suppose $$f$$ hides $$H\subset G$$. Note that $$H$$ is normal since it is the kernel of $$f$$. Let $$S_H$$ be a generating set of $$H$$ and $$S_{G/H}$$ a generating set of $$G/H$$. We can assume that $$|S_H|\le\log|H|$$ and $$|S_{G/H}|\le\log|G/H|$$ (see e.g. $$A2.1.1$$ on page $$611$$ in Nielsen & Chuang). The pair $$(S_H,S_{G/H})$$ is our certificate. Indeed, $$f$$ hides $$H$$ if and only if $$f(h)=e$$ for all $$h\in S_H$$ and $$f(g)\ne e$$ for all $$g\in S_{G/H}$$ where $$e$$ is the identity element of the group $$X$$. Moreover, by Lagrange theorem, the above test requires mere $$|S_H|+|S_{G/H}|\le\log|G|$$ invocations of the oracle.

In fact, the above certificate works for both positive and negative instances of $$\text{HPS}_D^h$$. Therefore, we have shown that $$\text{HPS}_D^h$$ belongs to the oracle analogue of $$\text{NP}\cap\text{co-NP}$$. Interestingly, factoring is known to be in $$\text{NP}\cap\text{co-NP}$$.

• Nice application of Lagrange's theorem! If the group is infinite then it's a bit more complicated as to whether there is even a polynomial-sized certificate - see, e.g., slide 14 of Kuperberg's slidedeck. (I understand like 5% of that though). Feb 14, 2022 at 22:09
• @Mark S True. I avoid the difficulty by assuming that $G$ is finitely generated (and on slide 14 $G=(\mathbb{Q}, +)$ which is not finitely generated). Also, note that the slides discuss time complexity whereas I only consider query complexity (number of invocations of the oracle $f$). This allows me to ignore issues surrounding efficient encoding of group elements and checking that a given set generates the group it is supposed to. The latter is not easy in general, but doesn't require the oracle, i.e. it is the sort of issue that affects time complexity but is neglected by query complexity. Feb 15, 2022 at 0:40
• In this very clear explanation, a delimited set of HSPs is formulated and it is shown that it lies in the intersection of the oracle-analogues of NP and coNP. To investigate the opposite case: are you aware of any pathologically complex case, which lies outside (the oracle-analogue) of NP, or at least in NP but outside coNP? Feb 16, 2022 at 13:52
• I don't know, but here are some thoughts: Suppose we don't expect the certificate to enable us to verify that the set $H$ is subgroup of $G$. IOW, we treat HSP as a promise problem where we're guaranteed that $H$ is subgroup (as is done for example here). In that case, a pair of non-identity elements $(g, h)$ such that $f(h)=f(e)\ne f(g)$ is sufficient to prove that $H$ is non-trivial. Thus, the promise problem is always in the NP analogue for oracle problems. In this view, the question reduces to whether we can evaluate the promise. Hope this helps! Feb 16, 2022 at 18:49
• @AdamZalcman - The query complexity HSP for $(\mathbb{Q},+)$ is also bad, because the NP-hardness result relativizes. The same is true for HSP for a free group with two generators, which is finitely generated. Apr 1 at 17:20