Algebraic Methods in Quantum and Classical Models of Computation

Summary

In the past fifteen years, we have seen several surprising results in computational complexity based on algebraic techniques, including

• Barrington's Theorem used noncommutative groups to show that majority can be computed by bounded-width branching programs.
• Razborov and Smolensky used low-degree polynomials over small fields to give lower bounds on the size of small depth circuits.
• Toda's theorem showing that the polynomial-time hierarchy reduces to the permanent uses many algebraic properties of polynomials.
• Research in interactive proofs a rely on the structure of the zeros of low-degree polynomials.
• The work on probabilistically checkable proofs that led to hardness of approximation results in addition to building on the interactive proof work, require algebraic techniques for testing whether a function is close to a low-degree polynomial.

In the past few years there has been a surge of interest in quantum computation, a model defined using quantum mechanics. The quantum computation model is inherently algebraic as it is defined by unitary linear transformations. Indeed many of the important results on quantum computation require algebraic techniques. Shor's famous algorithm for factoring efficiently on a quantum computer relies heavily on the algebraic structure of the groups Z^m and can be seen as a special case of the hidden subgroup problem for abelian groups. Also realizing that the acceptance probability for quantum decision trees can be expressed as a low-degree polynomial gives many interesting lower bounds for that model.

Consider the graph isomorphism question which is a special case of the hidden subgroup problem for general groups. It remains open whether the graph isomorphism problem has an efficient quantum algorithm. We have seen several results on the classical complexity of graph isomorphism based on the structure of the isomorphism group. For example, one can show a bounded-round proof system for graph nonisomorphism which gives strong evidence that graph isomorphism is not NP-complete. Perhaps some of the classical ideas can be used to help settle the quantum complexity of graph isomorphism.

The seminar brought together leading researchers using algebraic techniques from both the quantum computation area and those studying classical models. Combining these groups of researchers leads to a greater understanding of the computational power of both quantum and classical models of computation through new applications of algebraic techniques.