Constant-time solution to Simon's decision problem with the known subgroup range in quantum computer
Chien-Yuan Chen, Chih-Cheng Hsueh · Computational intelligence · 2007
Simon's algorithm can determine whether the function f is bijective or periodic by using the polynomial-function evaluations. Simon's algorithm is more efficient than classical algorithms which require exponential function evaluations. In this paper, we assume that the range of the periodic function is a known subgroup. We further find an integer b orthogonal to the range. According to b, we can construct a quantum algorithm to determine whether f is bijective or periodic in only one function evaluation.