We revisit the finite Abelian hidden subgroup problem (AHSP) from a mathematical perspective and make the following contributions. First, by employing amplitude amplification, we present an exact quantum algorithm for the finite AHSP, our algorithm is more concise than the previous exact algorithm and applies to any finite Abelian group. Second, utilizing the Chinese Remainder Theorem, we propose a distributed exact quantum algorithm for finite AHSP, which requires fewer qudits, lower quantum query complexity, and no quantum communication. We further show that our distributed approach can be extended to certain classes of non-Abelian groups. Finally, we develop a parallel exact classical algorithm for finite AHSP with reduced query complexity; even without parallel execution, the total number of queries across all nodes does not exceed that of the original centralized algorithm under mild conditions.
We present deterministic algorithms for the Hidden Subgroup Problem. The first algorithm, for abelian groups, achieves the same asymptotic worst-case query complexity as the optimal randomized algorithm, namely~$ \Order(\sqrt{ n}\, ),wheren$ is the order of the group. The analogous algorithm for non-abelian groups comes within a~logn factor of the optimal randomized query complexity. The best known randomized algorithm for the Hidden Subgroup Problem has \emph{expected\/} query complexity that is sensitive to the input, namely~$ \Order(\sqrt{ n/m}\, ),wherem$ is the order of the hidden subgroup. In the first version of this article~\cite[Sec.~5]{Nayak21-hsp-classical}, we asked if there is a deterministic algorithm whose query complexity has a similar dependence on the order of the hidden subgroup. Prompted by this question, Ye and Li~\cite{YL21-hsp-classical} present deterministic algorithms for \emph{abelian\/} groups which solve the problem with~$ \Order(\sqrt{ n/m }\, )$ queries, and find the hidden subgroup with~$ \Order( \sqrt{ n (\log m) / m} + \log m ) $ queries. Moreover, they exhibit instances which show that in general, the deterministic query complexity of the problem may be~$\order(\sqrt{ n/m } \,)$, and that of \emph{finding\/} the entire subgroup may also be~$\order(\sqrt{ n/m } \,)$ or even~$\upomega(\sqrt{ n/m } \,) $.}We present a different deterministic algorithm for the Hidden Subgroup Problem that also has query complexity~$ \Order(\sqrt{ n/m }\, )$ for abelian groups. The algorithm is arguably simpler. Moreover, it works for non-abelian groups, and has query complexity~$ \Order(\sqrt{ (n/m) \log (n/m) }\,) $ for a large class of instances, such as those over supersolvable groups. We build on this to design deterministic algorithms to find the hidden subgroup for all abelian and some non-abelian instances, at the cost of a~logm multiplicative factor increase in the query complexity.
In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use O(log(∣G∣)/ε) copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using O(log(∣G/H∣)/ε) forward and inverse queries, and prove a matching Ω(log(∣G/H∣)/ε) lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, Θ(log(∣G/H∣)/ε) copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in ε genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.