POPL 2024
Sun 14 - Sat 20 January 2024 London, United Kingdom
Thu 18 Jan 2024 14:40 - 15:00 at Kelvin Lecture - Quantum Computing Chair(s): Oded Padon

Selinger gave a superoperator model of a first-order quantum programming language and proved that it is fully definable and hence fully abstract. This paper proposes an extension of the superoperator model to higher-order programs based on modules over superoperators or, equivalently, enriched presheaves over the category of superoperators. The enriched presheaf category can be easily proved to be a model of intuitionistic linear logic with cofree exponential, from which one can cave out a model of classical linear logic by a kind of bi-orthogonality construction. Although the structures of an enriched presheaf category is usually rather complex, we proved that a morphism can be expressed simply as a matrix of completely positive maps in a sufficiently large subcategory of the enriched presheaf category, which subsumes the classical model. The model inherits many desirable properties from the superoperator model such as $\omega$CPO-enrichment. Interestingly it has a sufficient structure to interpret arbitrary recursive types. We introduce \emph{Quantum FPC}, a quantum $\lambda$-calculus with recursive types, and prove that our model is a fully abstract model of Quanutm FPC.

Thu 18 Jan

Displayed time zone: London change

13:40 - 15:00
Quantum ComputingPOPL at Kelvin Lecture
Chair(s): Oded Padon VMware Research
13:40
20m
Talk
With a Few Square Roots, Quantum Computing is as Easy as Pi
POPL
Jacques Carette McMaster University, Chris Heunen University of Edinburgh, Robin Kaarsgaard University of Southern Denmark, Amr Sabry Indiana University
Pre-print
14:00
20m
Talk
Quantum Bisimilarity via Barbs and Contexts: Curbing the Power of Non-Deterministic Observers
POPL
Lorenzo Ceragioli IMT Lucca, Italy, Fabio Gadducci University of Pisa, Giuseppe Lomurno University of Pisa, Italy, Gabriele Tedeschi University of Pisa, Italy
14:20
20m
Talk
SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog CompilationRemote
POPL
Yuxiang Peng University of Maryland, Jacob Young University of Maryland, Pengyu Liu Tsinghua University, Xiaodi Wu University of Maryland
14:40
20m
Talk
Enriched Presheaf Model of Quantum FPC
POPL
Takeshi Tsukada Chiba University, Kazuyuki Asada Tohoku University