July 26 – 31 , 2020, Dagstuhl Seminar 20311

RESCHEDULED Quantum Complexity: Theory and Application

Due to the Covid-19 pandemic, this seminar was rescheduled to June 27 – July 2 , 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)

For support, please contact

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