00989nas a2200133 4500008004100000245005500041210005500096260001500151520057900166100002300745700002600768700002400794856003700818 2007 eng d00aQuantum algorithms for hidden nonlinear structures0 aQuantum algorithms for hidden nonlinear structures c2007/05/213 a 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.
1 aChilds, Andrew, M.1 aSchulman, Leonard, J.1 aVazirani, Umesh, V. uhttp://arxiv.org/abs/0705.2784v1