Quantum Algorithms for Hidden Nonlinear Structures

Attempts to find new quantum algorithms that outperform classical computation have focused primarily on the nonAbelian hidden subgroup problem, which generalizes the central problem solved by Shor's factoring algorithm. We suggest an alternative generalization, namely to problems of finding hidden nonlinear structures over finite fields. We give examples of two such problems that can be solved efficiently by a quantum computer, but not by a classical computer. We also give some positive results on the quantum query complexity of finding hidden nonlinear structures.

Authors

• Andrew M. Childs
• Leonard J. Schulman
• Umesh V. Vazirani

Keywords

• Quantum computing
• Polynomials
• Interference
• Fourier transforms
• Computer science
• USA Councils
• Galois fields
• Vectors
• Quantum mechanics
• Level set
• Hidden Structure
• Quantum Algorithms
• Finite Field
• Classical Computer
• Hidden Problem
• Fourier Transform
• Complex Problems
• Black Box
• Algebra
• Efficient Algorithm
• Finite Set
• Quantum State
• Sphere Of Radius
• Abelian Group
• Unit Sphere
• Subset Of Points
• Sum Of Exponentials
• Hidden Object
• Black-box Function