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?

  • $\begingroup$ Perhaps if you can find a BQP-complete problem, it might be so… Can HHL be rephrased as a hidden subgroup problem? HHL is from 2010, and is BQP-complete, unlike the others you mention. $\endgroup$ Aug 17, 2022 at 22:11
  • $\begingroup$ HHL: given $A$ and $b$, find $x$ such that $Ax=b$. As a hidden subgroup: find the kernel (a subgroup of vectors) of the matrix $[A | -b]$. $\endgroup$
    – Sam Jaques
    Aug 18, 2022 at 7:03
  • 1
    $\begingroup$ @SamJaques very interesting - can you expand on that? What does the notation $[A\vert -b]$ mean? Is that a group itself? And under what operation- matrix multiplication? What is hidden? I have some ideas about your statement, but not positive. The kernel maps to $\mathbb 1$? Most quantum algorithms return an NP certificate - as generators of the hidden subgroup. But HHL doesn’t have a certificate that’s classically verifiable. If HHL could be reframed as a BQP-complete HSP, would that answer in the affirmative Lomomaco and Kauffman? $\endgroup$ Aug 18, 2022 at 11:22
  • $\begingroup$ I mean concatenation of matrices (not sure if there is a standard notation for that, sorry), so if $A$ is $n\times n$ then $[A|-b]$ is an $n\times(n+1)$ matrix where $-b$ is the last column. The group would be $\mathbb{C}^{n+1}$ under addition, where the kernel is the one-dimensional subspace spanned by $(x, 1)$. I guess HHL doesn't really solve this hidden subgroup problem, since it gives you $\vert x\rangle$, not $x$ itself. $\endgroup$
    – Sam Jaques
    Aug 18, 2022 at 11:43
  • 4
    $\begingroup$ Did We Overgeneralize to the Hidden Subgroup Problem? a blog post by @‪Dave Bacon $\endgroup$ Aug 23, 2022 at 5:53

1 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.


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