Quantum algorithms for hidden nonlinear structures
arXiv:0705.2784 · doi:10.1109/FOCS.2007.18
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 (8)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Algorithms Revisited
- Reversing quantum dynamics with near-optimal quantum and classical fidelity
- Quantum Search on Bounded-Error Inputs
- A Quantum Algorithm for the Hamiltonian NAND Tree
- Tradeoffs in the Quantum Search Algorithm
- Hidden Subgroup States are Almost Orthogonal
- How many copies are needed for state discrimination?
Cited by in corpus (26)
- Universal computation by quantum walk
- Quantum walks: a comprehensive review
- On the relationship between continuous- and discrete-time quantum walk
- Quantum algorithms for algebraic problems
- Review on Quantum Walk Computing: Theory, Implementation, and Application
- Quantum Computation Beyond the Circuit Model
- A lower bound on the probability of error in quantum state discrimination
- Quantum state revivals in quantum walks on cycles
- Quantum algorithms to solve the hidden shift problem for quadratics and for functions of large Gowers norm
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Limitations on the simulation of non-sparse Hamiltonians
- Hidden Symmetry Subgroup Problems
- Quantum Snake Walk on Graphs
- Quantum Walk Search through Potential Barriers
- Efficient Quantum Algorithm for Hidden Quadratic and Cubic Polynomial Function Graphs
- Efficient Quantum Algorithm for Identifying Hidden Polynomials
- Quantum algorithms for abelian difference sets and applications to dihedral hidden subgroups
- On solving systems of diagonal polynomial equations over finite fields
- Quantum algorithm for the Boolean hidden shift problem
- Quantum algorithms for shifted subset problems
- Unbounded quantum-classical separation in sample complexity for sphere center finding
- Polynomial time quantum algorithms for certain bivariate hidden polynomial problems
- Quantum Algorithms Using the Curvelet Transform
- Quantum algorithms for highly non-linear Boolean functions
- On quantum computation of Kloosterman sums
- Quantum binary field inversion: improved circuit depth via choice of basis representation