Background and motivation. 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 first generation of completed "Noisy Intermediate Scale Quantum (NISQ)" experiments already staking quantum supremacy claims, however, the answers to such "traditionally theoretical" questions have taken on an urgent and 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.

Seminar Topics. This seminar covered a range of topics under the broad umbrella of Quantum Complexity Theory, ranging from highly theoretical to experimentally driven. We briefly overview some of these here; further examples and details are in the included talk abstracts.

Theoretical directions. The field of Quantum Complexity Theory is concerned, broadly speaking, with a rigorous mathematical study of the resources required to perform certain computational tasks. To first order, this involves dividing the "computational world" into two buckets: Easy versus hard problems. However, in reality, the complexity landscape is much finer than this. For example, one might ask -- given that problem X has a known efficient quantum algorithm, does there nevertheless exist a faster quantum algorithm for X? This typically falls under the classical area of "fine-grained complexity", which has only recently begun to emerge as having a quantum analogue. Conversely, one may ask -- is problem $X$ hard only when one wishes to have a high precision answer, becoming easy when a larger margin of error is allowed? Classically, this falls under the umbrella of ``hardness of approximation'', and which has seen intense study in the guise of the ``quantum PCP conjecture''. Finally, given that quantum computers are believed more powerful than classical ones, a natural question is: Do there exist computational problems whose difficulty lies strictly between classical and quantum? Here, a natural object of study has been so-called "stoquastic" quantum systems, whose time evolution can often be simulated in practice via randomized (i.e. Monte Carlo) techniques, but which nevertheless appear difficult to classically simulate in the worst case in a rigorous fashion. Recent advances and the state of the art in all of these topics, as well as a number of others, were discussed at the seminar.

Experimentally motivated directions. The recent explosion of the so-called Noisy Intermediate-Scale Quantum (NISQ) computation era has brought many new questions to the forefront of Quantum Complexity Theory. For example, to date, two of the leading frameworks for experimental demonstration of "quantum supremacy" have been random circuit sampling and Boson sampling. On the one hand, much progress has been made closing the remaining gaps in the theoretical hardness proofs for these tasks on classical computers. On the other hand, for experiments that have been conducted, important practical topics such as how to benchmark such experimental random circuit setups have very recently been studied. Moreover, beyond the quest for quantum supremacy lies the next question: What practical applications might NISQ devices already prove useful for? These and related topics were presented and discussed at the seminar.

Participants and program overview. Due to the on-going COVID situation, the seminar was held in hybrid format. This meant that of the 55 total participants joining from 14 countries around the world (from North America to Europe to Asia), 17 were on-site, and 38 were remote. To allow all audience members to participate, a few measures were taken, which arguably worked quite well given the circumstances:

• During each of the seminar's on-site sessions, a Zoom session was projected onto a whiteboard, to which all remote participants were invited. The Zoom participants could see and hear on-site whiteboard and slide presentations, as well as interrupt to ask questions (via the room's loudspeaker system). This made for a reasonably efficient setup in which both on-site and hybrid participants could discuss in real-time. A Slack channel was also set up to ease communication, and by popular request, after talks a virtual Zoom chat room was set up so that the remote participants could also chat amongst themselves.
• To accommodate both types of audience members, a mix of on-site and remote talks were scheduled. On-site talks were typically held in the morning (CEST), allowing remote audience members in Europe Asia to attend. These were held at "standard" times, starting at 9:00 CEST. Remote talks were largely scheduled in the late afternoon and evening (17:00 and 20:00 CEST), this time accessible to North American and European participants.
• Seminar participants Marcel Hinsche (on-site) and James Watson (off-site) graciously offered to act as ``technical help volunteers'' for local and remote participants, ensuring the hybrid setup ran smoothly for both local and remote attendees.

Regarding the remaining program structure, a strong emphasis was placed on plentiful open time for ad-hoc discussion - typically 14:00 to 17:00 was left open expressly for this purpose. A social outing (hike) was organized by participant Dominik Hangleiter on Wednesday afternoon, and a traditional social night in the music room took place on Wednesday evening.

Acknowledgements. The seminar's participants and organizing committee wholeheartedly thank the Schloss Dagstuhl administrative and technical staff, who before, during, and after the seminar were incredibly supportive, professional, and patient with us quantum computer scientists. Many of the seminars participants, both online and off-line, commented very positively of the experience, citing it as a very welcome break to the stress of the on-going COVID pandemic.

Creative Commons BY 4.0

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