QUANTUM ALGORITHMS FOR SHIFTED SUBSET PROBLEMS
We consider a recently proposed generalisation of the abelian hidden subgroup problem: the shifted subset problem. The problem is to determine a subset S of some abelian group, given access to quantum states of the form (S + x), for some unknown shift x. We give quantum algorithms to find Hamming spheres and other subsets of the boolean cube {0, 1}(n). The algorithms have time complexity polynomial in n and give rise to exponential separations from classical computation.
quantum algorithms shifted subsets krawtchouk polynomials