2025/10/12 by Te'eni, Amit, Oz, Yaron, Cohen, Eliahu
#FOS: Physical sciences #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2510.10538
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 ≤ 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 admits a faithful, compatible group structure. These conditions hold automatically for q ∈ \ 2,3 \, 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.