Is the phase-estimation a specific case of the Hidden Subgroup Problem?

Question

I read Nielsen & Chuang and I have difficulties understanding the links between the Hidden Subgroup Problem and the Phase Estimation.

In Exercise 5.14 (Section 5.3.1 "Application: order-finding"), they show that the order-finding problem, for a $x \in \mathbb{Z}/N\mathbb{Z}$ can be seen both as a phase estimation problem (where $V(|y\rangle) = |xy\rangle$ that led to the use of the function $|k\rangle|y\rangle \rightarrow |k\rangle|V^k(y)\rangle$) and as a particular case of the Hidden Subgroup Problem (to find the period of $f(k)=x^k$, which lead to the use of the function $U_f(|x\rangle|y\rangle)=|x\rangle|y\oplus f(x)\rangle=|x\rangle|y\oplus x^k\rangle$.

My question is: are these two approaches related in a more general situation? For example, could the phase estimation problem be seen as a special case of the Hidden Subgroup Problem?

Answer 1

I would say "No, the quantum phase-estimation algorithm (QPE), in all its glory, is not just an embodiment of, or should not be limited to, the hidden subgroup problem (HSP)", at least because I can think of examples where we use QPE without any clear relation to any HSP.

As an example, the QMA-completeness proof of the local Hamiltonian problem has two parts - showing that Hamiltonian is QMA-hard, and showing that it is in QMA. The first part is usually the tricky one with proofs similar to those of the Cook-Levin theorem, but the second one implicitly uses QPE without any clear relation to any Hidden Subgroup Problem.

That is, if we are given a state $|\psi\rangle$ that is promised to be an eigenstate of some local Hamiltonian $\mathcal H$ where we know how to simulate $U=\exp(-i\mathcal H t)$, and we wish to determine its eigenvalue, if we can run controlled versions of $U$ then we measure the phase of $|\psi\rangle$ with respect to $U$, and hence the energy $\lambda$ with respect to $\mathcal H$. It's not clear where, if anywhere, is any subgroup in the above problem.

Another example would be that of the HHL algorithm, which uses the QPE as a black-box for access to $\mathcal H$. It's really not clear where there is an HSP inside of the HHL problem.

One thing that is maybe not emphasized enough is that the precision in the QPE as applied to the abelian HSP is exponential because the abelian HSP can be fast-forwarded, e.g. with modular exponentiation. But most often, e.g. in HHL, we only have polynomial precision from the QPE as we need to actively execute controlled versions of $U$ many times. I think this distinction is really pretty and related to time-energy uncertainty in some problems.

If anything I would say that QPE is more general than HSP, rather than the other way around, but there's some type mixing here as QPE is a subroutine while HSP is a problem.

Alternatively, however, another question that may be relevant is here, which links to a paper by Lomonaco and Kauffman. That paper suggests that many algorithms (including Grover's) can be recast as a form of the HSP. As some comments note it's interesting to ask whether HHL, which at its heart is eigenvalue surgery based on the QPE, can be recast as an instance of HSP.