13. – 18. Oktober 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)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


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 der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.