October 13 – 18 , 2002, Dagstuhl Seminar 02421

Algebraic Methods in Quantum and Classical Models of Computation


Harry Buhrman (CWI – Amsterdam, NL)
Lance Fortnow (University of Chicago, US)
Thomas Thierauf (FH Aalen, DE)

For support, please contact

Dagstuhl Service Team


List of Participants
Dagstuhl-Seminar-Report 357


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 Zm 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.

Dagstuhl Seminar Series


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.