Are all quantum algorithms hidden subgroup algorithms?

Question

I am reading the paper "Quantum Hidden Subgroup Algorithms: An Algorithmic Toolkit" by Samuel Lomonaco and Louis Kauffman from the book, "Mathematics of Quantum Computation and Quantum Technology." See also, this arxiv link.

The authors suggest that all quantum algorithms may be hidden subgroup algorithms in the sense that they all find hidden symmetries, i.e., hidden subgroups. Indeed, quantum hidden subgroup (QHS) algorithms encompass Deutsch-Jozsa, Simon's, Shor's factoring algorithm, and more.

The authors suggest of the following meta-procedure for quantum algorithm development:

1. Meta-Step 1: Explicitly state the problem to be solved.

2. Meta-Step 2: Rephrase the problem as a hidden symmetry.

3. Meta-Step 3: Create a quantum algorithm to find the hidden symmetry.

The authors leaves the reader with the questions: "Can this meta-procedure be made more explicit?"

This is article is from 2008. Have their been any developments in the past 15 years building on this idea, or proving that all quantum algorithms are indeed hidden subgroup algorithms?

Answer 1

Currently, I am reviewing some literature on this topic. This is still an open problem if we talk about general Hidden subgroup problem (say, g-HSP), including both abelian and non-abelian cases.

An alternative reformulation of the problem makes it more approachable (and sound). This goes as follows:

If a classical computer ($P$ or $BPP$) has access to a g-HSP solver (as an oracle), can it solve all the problems in $BQP$?

Or, does $BQP\subseteq BPP^{(g-HSP)}$ hold true?

This is considered too broad/complex to attack due to the diverse nature of g-HSP problems. For example, some g-HSP problems are in BQP (i.e., finite abelian HSP). But some are conjectured to be outside BQP, such as (a version of) shortest vector problem; it is NP-hard [Ajtai, 1998].

As pointed out by @Mark Spinelli, we need to know whether we have a BQP-complete in g-HSP. One of the crucial results in this line of reasoning is due to Scott Aaronson (2006) [see cstheory.se post]. This is restricted to the abelian HSP (say, a-HSP) case. It says any a-HSP solver is (most likely) not powerful enough to solve a BQP-complete problem. Or, $BQP \not\subset BPP^{(a-HSP)}$ is probably true.