Deconstructed Proto-Quipper: A Rational Reconstruction
The Proto-Quipper family of programming languages aims to provide a formal foundation for the Quipper quantum programming language. Unfortunately, Proto-Quipper languages have complex operational semantics: they are inherently effectful, and they rely on set-theoretic operations and fresh name generation to manipulate quantum circuits. This makes them difficult to reason about using standard programming language techniques and, ultimately, to mechanize. We introduce Proto-Quipper-A, a rational reconstruction of Proto-Quipper languages for static circuit generation. It uses a linear $\lambda$-calculus to describe quantum circuits with normal forms that closely correspond to box-and-wire circuit diagrams. Adjoint-logical foundations integrate this circuit language with a linear/non-linear functional language and let us reconstruct Proto-Quipper’s circuit programming abstractions using more primitive adjoint-logical operations. Proto-Quipper-A has a simple call-by-value reduction semantics. To illustrate its tractability as a foundation for Proto-Quipper languages, we prove and mechanize metatheoretic results using standard techniques. We give a logical relations technique to prove normalization of substructural systems, thus avoiding the complexity of existing linear logical relations.
Fri 28 AugDisplayed time zone: Eastern Time (US & Canada) change
16:00 - 17:30 | |||
16:00 30mTalk | Deconstructed Proto-Quipper: A Rational Reconstruction LOPSTR+PPDP Ryan Kavanagh Université du Québec à Montréal, Chuta Sano McGill University, Brigitte Pientka McGill University | ||
16:30 30mTalk | Deriving a Kronecker-Free Functional Quantum Simulator LOPSTR+PPDP Martin Elsman University of Copenhagen Pre-print | ||
17:00 30mPanel | LOPSTR+PPDP Discussion LOPSTR+PPDP | ||