Quantum algorithm for the Boolean hidden shift problem

Understand

The hidden shift problem is a natural place to look for new separations between classical and quantum models of computation.

• One advantage of this problem is its flexibility, since it can be defined for a whole range of functions and a whole range of underlying groups.
• In a way, this distinguishes it from the hidden subgroup problem where more stringent requirements about the existence of a periodic subgroup have to be made.
• And yet, the hidden shift problem proves to be rich enough to capture interesting features of problems of algebraic, geometric, and combinatorial flavor.