Quantum Complexity: Theory and Application
( 27. Jun – 02. Jul, 2021 )
- Bill Fefferman (University of Chicago, US)
- Sevag Gharibian (Universität Paderborn, DE)
- Norbert Schuch (Universität Wien, AT)
- Barbara Terhal (TU Delft, NL)
- Shida Kunz (für wissenschaftliche Fragen)
- Annette Beyer (für administrative Fragen)
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:
- 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))?
- 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?
- 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?
- 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.
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.
- Simon Apers (Free University of Brussels, BE)
- Sergio Boixo (Google - Venice, US) [dblp]
- Harry Buhrman (CWI - Amsterdam, NL) [dblp]
- Libor Caha (IBM Research-Zurich, CH) [dblp]
- Jens Eisert (FU Berlin, DE) [dblp]
- Lior Eldar (IL) [dblp]
- Sevag Gharibian (Universität Paderborn, DE) [dblp]
- Dominik Hangleiter (University of Maryland - College Park, US)
- Marcel Hinsche (FU Berlin, DE)
- Marios Ioannou (FU Berlin, DE)
- Robert König (TU München, DE) [dblp]
- Maris Ozols (University of Amsterdam, NL) [dblp]
- Dorian Rudolph (Universität Paderborn, DE) [dblp]
- Norbert Schuch (Universität Wien, AT) [dblp]
- Barbara Terhal (TU Delft, NL) [dblp]
- Frank Verstraete (Ghent University, BE) [dblp]
- Petra Wolf (Universität Trier, DE) [dblp]
- Scott Aaronson (University of Texas - Austin, US) [dblp]
- Dorit Aharonov (The Hebrew University of Jerusalem, IL) [dblp]
- Anurag Anshu (University of California - Berkeley, US)
- Itai Arad (Technion - Haifa, IL) [dblp]
- Johannes Bausch (University of Cambridge, GB) [dblp]
- Adam Bouland (Stanford University, US) [dblp]
- Sergey Bravyi (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
- Michael Bremner (University of Technology - Sydney, AU) [dblp]
- Andrew Childs (University of Maryland - College Park, US) [dblp]
- Toby Cubitt (University College London, GB) [dblp]
- Abhinav Deshpande (University of Maryland - College Park, US) [dblp]
- Bill Fefferman (University of Chicago, US) [dblp]
- András Gilyén (Caltech - Pasadena, US) [dblp]
- David Gosset (University of Waterloo, CA) [dblp]
- Alex Grilo (Sorbonne University - Paris, FR)
- Sandy Irani (University of California - Irvine, US)
- Stacey Jeffery (CWI - Amsterdam, NL) [dblp]
- Elham Kashefi (University of Edinburgh, GB) [dblp]
- Joel David Klassen (Phasecraft - London, GB) [dblp]
- Robin Kothari (Microsoft Corporation - Redmond, US) [dblp]
- Richard Küng (Johannes Kepler Universität Linz, AT)
- Urmila Mahadev (California Institute of Technology - Pasadena, US) [dblp]
- Milad Marvian (University of New Mexico, US)
- Rewad Mezher (University of Edinburgh, GB)
- Tomoyuki Morimae (Kyoto University, JP) [dblp]
- Ramis Movassagh (IBM Research - Boston, US) [dblp]
- Daniel Nagaj (Slovak Academy of Sciences - Bratislava, SK)
- Harumichi Nishimura (Nagoya University, JP) [dblp]
- David Pérez García (Complutense University of Madrid, ES) [dblp]
- Stephen Piddock (University of Bristol, GB) [dblp]
- Jamie Sikora (Virginia Polytechnic Institute - Falls Church, US)
- Maarten Stroeks (University of Cambridge, GB)
- Aarthi Sundaram (MicrosoftMicrosoft Quantum - Redmond, US) [dblp]
- Yuki Takeuchi (NTT - Kyoto, JP) [dblp]
- Ewin Tang (University of Washington - Seattle, US)
- Thomas Vidick (Caltech - Pasadena, US)
- James Watson (University College London, GB)
- Justin Yirka (University of Texas - Austin, US) [dblp]
- data structures / algorithms / complexity
- Quantum computation
- complexity theory
- many-body systems
- proof and verification systems
- quantum supremacy