Deterministic algorithms for the hidden subgroup problem

The hidden subgroup problem () plays a crucial role in the field of quantum computing, since several celebrated quantum algorithms including Shor's algorithm have a uniform description in the framework of . The problem is as follows: for a finite group and a finite set , given a function and the promise that for any iff for a subgroup , the goal of the decision version is to determine whether is trivial, and the goal of the search version is to find . Nayak (2021) asked whether there exist deterministic algorithms with query complexity for . We answer this problem for Abelian groups, which also extends the main results of Ye et al. (2021), since here the algorithms do not rely on any prior knowledge of .