Quantum algorithms for hidden nonlinear structures

Abstract

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.

13 pages

References in corpus (1)

• A Quantum Algorithm for the Hamiltonian NAND Tree

Cited by in corpus (6)

• Universal computation by quantum walk
• Quantum Computation Beyond the Circuit Model
• Efficient Quantum Algorithm for Identifying Hidden Polynomials
• Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
• Quantum algorithms for shifted subset problems
• Quantum Algorithms Using the Curvelet Transform