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 JanDisplayed time zone: London change
13:40 - 15:00 | |||
13:40 20mTalk | 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 20mTalk | 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 20mTalk | 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 20mTalk | Enriched Presheaf Model of Quantum FPC POPL |