Efficient Quantum Algorithms for Shifted Quadratic Character Problems

Abstract

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.

LaTeX2e, 15 pages

References in corpus (4)

• Quantum Algorithms Revisited
• Quantum measurements and the Abelian Stabilizer Problem
• Quantum Algorithms for Weighing Matrices and Quadratic Residues
• The Hidden Subgroup Problem and Eigenvalue Estimation on a Quantum Computer

Cited by in corpus (10)

• Exponential algorithmic speedup by quantum walk
• Quantum Data Fitting
• The Hidden Subgroup Problem - Review and Open Problems
• Efficient Quantum Algorithms for Estimating Gauss Sums
• Quantum Computation Beyond the Circuit Model
• Sharp Quantum vs. Classical Query Complexity Separations
• Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation
• Quantum Fourier Transform Over Galois Rings
• Control-target inversion property on Abelian groups
• Distribution of Interference in the Presence of Decoherence