One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem

Abstract

The quantum Fourier transform (QFT) is central to many quantum algorithms, yet its necessity is not always well understood. We re-examine its role in canonical query problems. The Deutsch-Jozsa algorithm requires neither a QFT nor a domain group structure. In contrast, the Bernstein-Vazirani problem is an instance of the hidden subgroup problem (HSP), where the hidden subgroup has either index $1$ or $2$, and the Bernstein-Vazirani algorithm exploits this promise to solve the problem with a single query. Motivated by these insights, we introduce the index-$q$ HSP: determine whether a hidden subgroup $H\le G$ has index $1$ or $q$, and, when possible, identify $H$. We present a single-query algorithm that always distinguishes index $1$ from $q$, for any choice of abelian structure on the oracle's codomain. Moreover, with suitable pre- and post-oracle unitaries (inverse-QFT/QFT over $G$), the same query exactly identifies $H$ under explicit minimal conditions: $G/H$ is cyclic of order $q$, and the output alphabet is equipped, up to affine relabeling, with a compatible $\mathbb{Z}/q\mathbb{Z}$ structure. These conditions hold automatically for $q\in \left\{2,3\right\}$, giving unconditional single-query identification in these cases. In contrast, the Shor-Kitaev sampling approach cannot guarantee exact recovery from a single sample. Our results sharpen the landscape of one-query quantum solvability for abelian HSPs.

25 pages