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.

Creative Commons BY 3.0 DE

Bill Fefferman, Sevag Gharibian, Norbert Schuch, and Barbara Terhal