Quantum Programming and Circuits Workshop synopsis
During the period of June 8 - June 11 2015, the Institute for Quantum Computing hosted the ``Quantum Programming and Circuits Workshop". The workshop constituted a rare opportunity of bringing together researchers from both quantum computing and classical programming languages.
As quantum computing researchers continue to strive to build a universal quantum computer, there is already a large number of important problems that have to solved for a successful implementation of such a machine.
An important topic tackled by the workshop was related to building tools for automation and verification of large quantum circuits and corresponding quantum ``programs". In particular, given an abstract specification of a quantum algorithm, it is of paramount importance to be able to come up with an as small as possible quantum circuit that implements the algorithm, and to make sure such an implementation is optimal with respect to some desired measure.
Some highlights from this area were the talks of Krysta Svore, Microsoft Research: ``Efficient Synthesis of Universal Probabilistic Quantum Circuits", David Gosset, Caltech: ``Exact synthesis of single-qubit unitaries over Clifford cyclotomic gate sets", Vadym Kliuchnikov, Microsoft Research: "A framework for exact synthesis", Peter Sarnak, Princeton University and IAS: "The Solovay-Kitaev theorem and Golden Gates".
Another topic of interest is the simulation of quantum computers by classical computers and the application of classical programming language theory and compiler theory therein. The talks of Dave Wecker, Microsoft Research: "LIQUi|>: Simulation and compilation of quantum algorithms", Blake Johnson, BBN: "Quantum Gate Language: A machine language for quantum processors", Vlad Gheorghiu, IQC: "Quantum++ - A modern C++ quantum computing library", Benoit Valiron, Universite Paris Diderot: "Quipper: A Scalable Quantum Programming Language", Margaret Martonosi, Princeton University: "Language, Compiler, and Optimization Issues in Quantum Computing" were dedicated to this topic.
Other topics covered by the workshop were related to 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. Some of the talks covering these areas were given by William Zeng, University of Oxford: "Diagrammatic methods for the specification and verification of quantum algorithms", Robert Gluck, University of Copenhagen: "Elements of reversible programming languages", Alexis De Vos, Universiteit Gent: "From classical circuits to quantum circuits", Tetsuo Yokoyama, Nanzan University: "On the theory of reversible flowchart languages", Alex Bocharov, Microsoft Research: "Mathematics of efficient topological quantum circuits", Shigeru Yamashita, Ritsumeikan University: "Reduction of computational steps for topological quantum circuits".
Currently, only very few opportunities exist to bring together researchers from all these somewhat disjoint but nevertheless extremely important sub-fields of quantum information theory as well classical programming languages theory. The workshop was one of the first that, in our opinion, successfully attempted to do so and allowed a fruitful exchange of ideas across these topics during a vibrant 4 days period.