TOP
Search the Dagstuhl Website
Looking for information on the websites of the individual seminars? - Then please:
Not found what you are looking for? - Some of our services have separate websites, each with its own search option. Please check the following list:
Schloss Dagstuhl - LZI - Logo
Schloss Dagstuhl Services
Seminars
Within this website:
External resources:
  • DOOR (for registering your stay at Dagstuhl)
  • DOSA (for proposing future Dagstuhl Seminars or Dagstuhl Perspectives Workshops)
Publishing
Within this website:
External resources:
dblp
Within this website:
External resources:
  • the dblp Computer Science Bibliography


Dagstuhl Seminar 18381

Quantum Programming Languages

( Sep 16 – Sep 21, 2018 )


Permalink
Please use the following short url to reference this page: https://www.dagstuhl.de/18381

Organizers

Contact


Schedule

Motivation

Quantum computing is getting real. Several laboratories around the world are implementing hardware platforms and there is a likely possibility within the next 2-3 years some of those will scale into the 50-100 qubit range. While research on the theoretical side of the field addressed fundamental questions such as how to best leverage this new model of computation for algorithmic applications, a topic that has received significantly less attention is how to actually program quantum computers. To take advantage of the immense computing power offered by quantum computers as they come online in the coming years, software tools will be essential. We want these tools to be available, efficient and reliable, so that we can quickly and reliably reap the positive benefits that quantum computers have to offer.

It is clear that quantum programming will require tools for automatically generating large-scale circuits and for synthesizing circuits from elementary fault-tolerant gates which then can be carried out by a future quantum computer. However, it is less clear what the best way will be to go about these challenging issues. Questions that are within the scope for this Dagstuhl Seminar include the following:

  • How can we program a quantum computer?What are the basic structures that a language should support and how can a compiler help a user develop abstract/high-level reasoning about algorithms?
  • How do we model the underlying instruction set? As currently the underlying hardware is quickly evolving, how can we best model a fault-tolerant quantum computer?
  • How to compile and optimize quantum programs? Automatic translation of high-level programs into circuits will be key to program quantum computers. How to design good tools for this?
  • How can we program near-term devices? Near-term quantum computers are likely to only have a few hundred noisy qubits, rather than a few thousand fault-tolerant ones. What are the best ways to make use of such a device? How would one program in such a highly constrained setting?
  • How to we test and verify quantum programs? Given that it is hard for classical computers to simulate the time evolution of a quantum computer, how can we ascertain correctness of a circuit?

Progress on these questions requires diverse skill sets from different research communities. We aim at bringing together researchers from quantum computing, mathematical foundations of programming languages, implementation of programming languages, and formal verification. We anticipate a vibrant exchange of novel ideas, to tackle important problems such as the analysis of quantum algorithms for real-world computational problems, compiler optimizations, reversible computing, and fault-tolerant quantum computing.

We expect that the Seminar will help to further establish quantum programming languages and circuit synthesis and optimization as a rapidly evolving research area in the intersection of quantum computing and programming languages.

Copyright Michele Mosca, Martin Roetteler, and Peter Selinger

Summary

This report documents the program and the outcomes of Dagstuhl Seminar 18381 "Quantum Programming Languages".

The aim of the seminar was to bring together researchers from quantum computing-in particular those focusing on quantum algorithms and quantum error correction-and classical programming languages. Open questions that were of interest to this group include new methods for circuit synthesis and optimization, compiler optimizations and rewriting, embedded languages versus non-embedded languages, implementations of type systems and error reporting for quantum languages, techniques for verifying the correctness of quantum programs, and new techniques for compiling efficient circuits and protocols for fault-tolerant questions and their 2D layout.

Quantum computing is getting real. Several laboratories around the world are implementing hardware platforms. For instance, systems based on superconducting qubits, such as those at IBM, Google, Intel, the University of Maryland, ionQ, and Rigetti are now scaling into the 50-150 qubit range.

While research on the theoretical side of the field addressed fundamental questions such as how to best leverage this new model of computation for algorithmic applications, a topic that has received significantly less attention is how to actually program quantum computers. To take advantage of the immense computing power offered by quantum computers as they come online in the coming years, software tools will be essential. We want these tools to be available, efficient and reliable, so that we can quickly and reliably reap the positive benefits that quantum computers have to offer.

It is clear that quantum programming will require tools for automatically generating large-scale circuits and for synthesizing circuits from elementary fault-tolerant gates which then can be carried out by a future quantum computer. However, it is less clear what the best way will be to go about these challenging issues. Questions that were discussed at the seminar include the following:

  • How can we program a quantum computer? What are the basic structures that a language should support and how can a compiler help a user develop abstract/high-level reasoning about algorithms?
  • How do we model the underlying instruction set? As currently the underlying hardware is quickly evolving, how can we best model a fault-tolerant quantum computer?
  • How to compile and optimize quantum programs? Automatic translation of high-level programs into circuits will be key to program quantum computers. How to design good tools for this?
  • How to we test and verify quantum programs? Given that it is hard for classical computers to simulate the time evolution of a quantum computer, how can we ascertain correctness of a circuit?

The seminar brought together some 44 researchers with diverse skill sets from quantum computing, mathematical foundations of programming languages, implementation of programming languages, and formal verification. The seminar consisted of 23 talks, as well as a number of vibrant discussion sessions and a software demonstration session. The sessions where:

  • Wine Cellar discussion, moderated by Sabine Glesner. This was our first discussion session. We discussed the questions raised by Sabine Glesner during her talk: Why do we need quantum programming languages? Which ``killer applications'' would make quantum programming languages successful? What are appropriate abstractions from quantum hardware? What are theoretical models for quantum computing?
  • Discussion session on Debugging, moderated by Rodney Van Meter. This session focused on what are appropriate debugging techniques for quantum computing. The issue arises because the most common classical debugging technique, setting break points and examining the program state, cannot be applied in the context of quantum computing.
  • Discussion session on Challenge Problems for Quantum Computing, moderated by Earl Campbell. In this session, we discussed coming up with well-defined problems with some success quantifier for quantum computation, similar to the successful SAT competitions.
  • Group survey session on a Bird's Eye View on Quantum Languages, moderated by Robert Rand. In this session, the group compiled a list of all quantum programming languages and toolkits we are currently aware of, and classified them according to various criteria, for example, whether the languages are imperative or functional, whether the computational paradigm is circuit generation or Knill's QRAM model, whether the language is high-level or assembly, whether it supports type-safety and/or verification, etc.
  • Group survey session on Tools for Quantum Optimization, moderated by Matthew Amy. In this session, the group compiled a list of available tools for optimization of quantum circuits.
  • Group discussion on Opportunities for Education and Outreach, moderated by Rodney Van Meter. The discussion centered on new opportunities for public outreach and education that are enabled by the emergence of new quantum tools.
  • Software demonstration session, moderated by Martin Roetteler. In this session, 10 researchers gave rapid demonstrations, of a about 10 minutes each, of various software tools they have designed.

Most of the participants rated the seminar as a success. We managed to connect researchers from different communities, and engaged in a vibrant exchange of novel ideas, and started to tackle important problems such as the analysis of quantum algorithms for real-world computational problems, compiler optimizations, reversible computing, and fault-tolerant quantum computing.

Copyright Michele Mosca, Martin Roetteler, and Peter Selinger

Participants
  • Matthew Amy (University of Waterloo, CA) [dblp]
  • Sébastien Bardin (CEA LIST, FR) [dblp]
  • Xiaoning Bian (Dalhousie University - Halifax, CA) [dblp]
  • Earl Campbell (University of Sheffield, GB) [dblp]
  • Andrew Cross (IBM TJ Watson Research Center - Yorktown Heights, US) [dblp]
  • Olivia Di Matteo (University of Waterloo, CA) [dblp]
  • Austin G. Fowler (Google Research - Mountain View, US) [dblp]
  • Frank Fu (Dalhousie University - Halifax, CA)
  • Vlad Gheorghiu (University of Waterloo, CA) [dblp]
  • Sabine Glesner (TU Berlin, DE) [dblp]
  • Robert Glück (University of Copenhagen, DK) [dblp]
  • Christopher Granade (Microsoft Corporation - Redmond, US) [dblp]
  • Markus Grassl (Max Planck Institute for the Science of Light, DE) [dblp]
  • Thomas Häner (ETH Zürich, CH) [dblp]
  • Shih-Han Hung (University of Maryland - College Park, US) [dblp]
  • Nader Khammassi (TU Delft, NL) [dblp]
  • Vadym Kliuchnikov (Microsoft Corporation - Redmond, US) [dblp]
  • Sriram Krishnamoorthy (Pacific Northwest National Lab. - Richland, US) [dblp]
  • Andrew John Landahl (Sandia National Labs - Albuquerque, US)
  • Albertus Johannis Lindenhovius (Tulane University - New Orleans, US)
  • Michael W. Mislove (Tulane University - New Orleans, US) [dblp]
  • Michele Mosca (University of Waterloo, CA) [dblp]
  • Beatrice Nash (MIT - Cambridge, US)
  • Jennifer Paykin (Galois - Portland, US) [dblp]
  • Robert Rand (University of Maryland - College Park, US) [dblp]
  • Mathys Rennela (CWI - Amsterdam, NL) [dblp]
  • Francisco Rios (Dalhousie University - Halifax, CA) [dblp]
  • Martin Roetteler (Microsoft Corporation - Redmond, US) [dblp]
  • Neil Julien Ross (Dalhousie University - Halifax, CA) [dblp]
  • Bruno Schmitt Antunes (EPFL - Lausanne, CH)
  • Peter Selinger (Dalhousie University - Halifax, CA) [dblp]
  • Mathias Soeken (EPFL - Lausanne, CH) [dblp]
  • Damian Steiger (ETH Zürich, CH) [dblp]
  • Rainer Steinwandt (Florida Atlantic University - Boca Raton, US) [dblp]
  • Benoit Valiron (Centrale Supelec - Orsay, FR) [dblp]
  • Rodney Van Meter (Keio University - Yokohama, JP) [dblp]
  • Michael Walter (University of Amsterdam, NL) [dblp]
  • Robert Wille (Johannes Kepler Universität Linz, AT) [dblp]
  • Shigeru Yamashita (Ritsumeikan University - Shiga, JP) [dblp]
  • Mingsheng Ying (University of Technology - Sydney, AU) [dblp]
  • Vladimir Zamdzhiev (LORIA - Nancy, FR) [dblp]
  • Margherita Zorzi (University of Verona, IT) [dblp]
  • Alwin Zulehner (Johannes Kepler Universität Linz, AT) [dblp]
  • Paolo Zuliani (Newcastle University, GB) [dblp]

Classification
  • data structures / algorithms / complexity
  • programming languages / compiler

Keywords
  • quantum computing
  • reversible computing
  • functional programming
  • compilers
  • verification