Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

One of the major challenges in the theory of quantum computation is to develop new quantum algorithms. Much of the work on this question has focused on the nonabelian hidden subgroup problem (HSP), attempting to extend Shor's solution of the abelian HSP, the backbone of his efficient quantum algorithm for factoring integers. Unfortunately, these efforts have met with only limited success. In this talk, I will describe an alternative way of generalizing the success of Shor's algorithm. Shor's algorithm can be used to find hidden linear structures, so a natural generalization is to find hidden structures of higher degree. In particular, I will describe two problems involving hidden quadratic structures that can be solved efficiently by a quantum computer, but not by a classical computer. This talk is based on joint work with Leonard Schulman and Umesh Vazirani.