Quantum Computing Stack Exchange is a question and answer site for engineers, scientists, programmers, and computing professionals interested in quantum computing. It only takes a minute to sign up.
Sign up to join this community
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.
TL;DR: The general version of the Hidden Subgroup Problem (abelian or otherwise) is not in NP, because it is an oracle problem.
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.
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$.
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.
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.
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}$.
