26. – 31. Juli 2020, Dagstuhl-Seminar 20311

RESCHEDULED Quantum Complexity: Theory and Application

Due to the Covid-19 pandemic, this seminar was rescheduled to 27. Juni – 02. Juli 2021Seminar 21261.


Bill Fefferman (University of Chicago, US)
Sevag Gharibian (Universität Paderborn, DE)
Norbert Schuch (MPI für Quantenoptik – Garching, DE)
Barbara Terhal (TU Delft, NL)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Since the seminal discovery of an efficient quantum integer factorization algorithm by Peter Shor in 1994, the field of Quantum Computation has blossomed into a large-scale international effort to build, test, and study the possibilities that information processing using quantum particles may provide. A central role in these developments has been played by Quantum Complexity Theory, a traditionally theoretical realm of research focusing on such questions as: Which physical properties of Nature can be efficiently computed? Can the behavior of an untrusted or noisy quantum computer be verified? What might constitute convincing evidence of “quantum supremacy” over classical computers?

With the current global hunt for “Noisy Intermediate Scale Quantum (NISQ)” devices able to convincingly outperform classical devices underway, however, the answers to such “traditionally theoretical” questions have taken on important practical relevance. For example, a complexity theoretic understanding of which realistic physical problems are “just hard enough” for classical computers and “easy enough” for quantum computers is the natural starting point for “quantum supremacy” testbeds. With functioning experimental devices in place, one must next convincingly confirm the device is performing as designed, particularly in the presence of noise. Finally, if the aim of such experiments is to cast doubt on the Extended Church-Turing Thesis, then a strong standard of evidence is required; such a standard must be rigorously stated and developed.

Candidate subset of topics for this Dagstuhl Seminar:

  1. Quantum complexity of physical problems — What physical properties involving thermal states, excited states, time evolution of quantum systems, or the study of phases and phase transitions, can be efficiently computed or verified? Which problems can be verified via classical proofs (QCMA) or multiple quantum provers (QMA(2))?
  2. Tractable classes of problems — Which families of “non-universal” Hamiltonians, such as stoquastic Hamiltonians, can be efficiently identified and simulated? What is the difficulty of Hamiltonian problems in realistic settings, such as realistic interactions (e.g. Heisenberg-type couplings), finite temperature, or robustness under small fluctuations?
  3. Verification of quantum computing — What resources are required to verify quantum computing? Can one construct verification protocols without computational or cryptographic assumptions? How can we verify near-term intermediate-scale quantum devices?
  4. Tests of quantum supremacy — Which physical problems do quantum computers have an advantage over classical computers? Can quantum supremacy be demonstrated in a classically verifiable way, e.g. using problems inside NP (as opposed to sampling problems)? How can we verify computational power based on problems outside NP (such as sampling problems)?

Seminar structure: The week-long Dagstuhl Seminar will consist of introductory tutorials, research talks from attendees, a rump session, and plenty of discussion time.

Motivation text license
  Creative Commons BY 3.0 DE
  Bill Fefferman, Sevag Gharibian, Norbert Schuch, and Barbara Terhal

Related Dagstuhl-Seminar


  • Data Structures / Algorithms / Complexity


  • Quantum computation
  • Complexity theory
  • Many-body systems
  • Proof and verification systems
  • Quantum supremacy


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.