2000/11/15 by Wim van Dam, van Dam, Wim, Sean Hallgren +1
Computer Science · Mathematics · Physics and Astronomy · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #FOS: Physical sciences #Number Theory (math.NT) #Quantum Physics (quant-ph) #cs.CC #math.NT #quant-ph
paper · pdf · doi:10.48550/arxiv.quant-ph/0011067
LaTeX2e, 15 pages
arxiv created 2001/01/04 · arxiv updated 2009/11/30
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.