Pawel Wocjan

School of Electrical Engineering and Computer Science
University of Central Florida

Efficient quantum algorithm for identifying hidden polynomial function graphs

One of the major challenges for quantum computing is to design new efficient quantum algorithms that significantly outperform their classical counterparts. Much of the research on this challenge has focused on the nonabelian hidden subgroup problem (HSP), which generalizes the central problem (the abelian HSP) solved by Shor's algorithm. Unfortunately, these attempts have met with only limited success and it seems that the general nonabelian HSP could be difficult for quantum computers. Childs, Schulman and Vazirani suggested an alternative way of trying to generalize the success of the abelian HSP. This problem can also be viewed as the problem to determine hidden linear structures. So, why not try to see what types of hidden non-linear structures can also be identified by quantum computers?

In this context, we introduce the Hidden Polynomial Function Graph Problem as a natural generalization of an abelian Hidden Subgroup Problem where rhe subgroups and their cosets correspond to graphs of linear functions over a finite field F_q. For the Hidden Polynomial Function Graph Problem the functions are not restricted to be linear but can also be multivariate polynomial functions of higher degree.

For a fixed number of indeterminates and bounded total degree the Hidden Polynomial Function Graph Problem is hard on a classical computer as its black box query complexity is polynomial in q. In contrast, this problem can be reduced to a quantum state identification problem so that the resulting quantum query complexity does not depend on q. For univariate polynomials we construct a von Neumann measurement for distinguishing these states. We relate the success probability and the implementation of this measurement to certain classical problems involving polynomial equations. We present an efficient algorithm for hidden univariate polynomial functions by establishing that the success probability of the measurement is bounded from below by a constant and that it can be implemented efficiently for fixed degree. These results are obtained with the help of tools from algebraic geometry allowing us to make specific statements about properties of generic morphisms between affine spaces.

This talk is based on the joint work with Tomas Decker and Jan Draisma (http://arxiv.org/abs/0706.1219)

Seminar schedule: http://www.physics.rutgers.edu/qcg/Seminars.html