  We introduce the Shifted Legendre Symbol Problem and some variants along with
efficient quantum algorithms to solve them. The problems and their algorithms
are different from previous work on quantum computation in that they do not
appear to fit into the framework of the Hidden Subgroup Problem. The classical
complexity of the problem is unknown despite the various results on the
irregularity of Legendre Sequences.

Quantum Physics;Computational Complexity;Number Theory