Published: 28th December 2014
DOI: 10.4204/EPTCS.172
ISSN: 2075-2180

EPTCS 172

Proceedings of the 11th workshop on
Quantum Physics and Logic
Kyoto, Japan, 4-6th June 2014

Edited by: Bob Coecke, Ichiro Hasuo and Prakash Panangaden

Preface
Bob Coecke, Ichiro Hasuo and Prakash Panangaden
Invited Presentation: Denotational Semantics and Quantum Topology
Masahito Hasegawa
Invited Presentation: Dilation of states and processes in operational-probabilistic theories
Giulio Chiribella
1
Invited Presentation: Quantum Set Theory Extending the Standard Probabilistic Interpretation of Quantum Theory (Extended Abstract)
Masanao Ozawa
15
Terminality implies non-signalling
Bob Coecke
27
On monogamy of non-locality and macroscopic averages: examples and preliminary results
Rui Soares Barbosa
36
Tensors, !-graphs, and non-commutative quantum structures
Aleks Kissinger and David Quick
56
Depicting qudit quantum mechanics and mutually unbiased qudit theories
André Ranchin
68
Qutrit Dichromatic Calculus and Its Universality
Quanlong Wang and Xiaoning Bian
92
Reflections on the PBR Theorem: Reality Criteria & Preparation Independence
Shane Mansfield
102
Stochastic Relational Presheaves and Dynamic Logic for Contextuality
Kohei Kishida
115
QPEL: Quantum Program and Effect Language
Robin Adams
133
A Kochen-Specker system has at least 22 vectors (extended abstract)
Sander Uijlen and Bas Westerbaan
154
Semantics for a Quantum Programming Language by Operator Algebras
Kenta Cho
165
Observational Equivalence Using Schedulers for Quantum Processes
Kazuya Yasuda, Takahiro Kubota and Yoshihiko Kakutani
191
On Gács' quantum algorithmic entropy
Toru Takisaka
204
The dagger lambda calculus
Philip Atzemoglou
217
Complexity of Grammar Induction for Quantum Types
Antonin Delpeuch
236
A Study of Entanglement in a Categorical Framework of Natural Language
Dimitri Kartsaklis and Mehrnoosh Sadrzadeh
249
Belief propagation in monoidal categories
Jason Morton
262
Abstract structure of unitary oracles for quantum algorithms
William Zeng and Jamie Vicary
270
The ZX-calculus is incomplete for quantum mechanics
Christian Schröder de Witt and Vladimir Zamdzhiev
285
The ZX-calculus is complete for the single-qubit Clifford+T group
Miriam Backens
293
Mixed quantum states in higher categories
Chris Heunen, Jamie Vicary and Linde Wester
304
A 2-Categorical Analysis of Complementary Families, Quantum Key Distribution and the Mean King Problem
Krzysztof Bar and Jamie Vicary
316

Preface

This volume contains the proceedings of the 11th International Workshop on Quantum Physics and Logic (QPL 2014), which was held June 4--6, 2014 at Kyoto University.

The goal of the QPL workshop series is to bring together researchers working on mathematical foundations of quantum physics, quantum computing and spatio-temporal causal structures, and in particular those that use logical tools, ordered algebraic and category-theoretic structures, formal languages, semantic methods and other computer science methods for the study of physical behavior in general. Over the past few years, there has been growing activity in these foundational approaches, together with a renewed interest in the foundations of quantum theory, which complement the more mainstream research in quantum computation. Earlier workshops in this series, with the same acronym under the name "Quantum Programming Languages", were held in Ottawa (2003), Turku (2004), Chicago (2005), and Oxford (2006). The first QPL under the new name Quantum Physics and Logic was held in Reykjavik (2008), followed by Oxford (2009 and 2010), Nijmegen (2011), Brussels (2012) and Barcelona (2013).

This edition of the workshop attracted 53 submissions. We wish to thank all their authors for their interest in QPL 2014. After careful discussions, the Program Committee selected 32 papers for presentation at the workshop. This volume contains papers corresponding to a selection of the contributed talks. Each submission was refereed by at least two reviewers, who delivered detailed and insightful comments and suggestions. The Program Chairs thank all the Program Committee Members and all the additional reviewers for their excellent service.

The workshop program was enriched by three invited lectures:

The workshop enjoyed partial support from Research Institute for Mathematical Sciences (RIMS), Kyoto University; from the EPSRC Network on Structures at the Interface of Physics and Computer Science (EP/I03596X/1); and the Support Center for Advanced Telecommunications Technology Research (SCAT).

October 2014
Bob Coecke
Ichiro Hasuo
Prakash Panangaden

Workshop Organization

Program Chairs

Bob Coecke (Oxford), Ichiro Hasuo (Tokyo), Prakash Panangaden (McGill)

Program Committee

Dan Browne (UCL), Giulio Chiribella (Tsinghua), Ross Duncan (Strathclyde), Simon Gay (Glasgow), Chris Heunen (Oxford), Matty Hoban (ICFO), Bart Jacobs (Nijmegen), Viv Kendon (Leeds), Simon Perdrix (CNRS Grenoble), Mehrnoosh Sadrzadeh (QMUL), Peter Selinger (Dalhousie), Rob Spekkens (Perimeter), Bas Spitters (Nijmegen), Jamie Vicary (Oxford & CQT Singapore), Mingsheng Ying (UTS Sydney & Tsinghua)

Steering Committee

Bob Coecke (Oxford), Prakash Panangaden (McGill), Peter Selinger (Dalhousie)

Local Organizers

Ichiro Hasuo (Tokyo), Naohiko Hoshino (Kyoto), Yoshihiko Kakutani (Tokyo), Susumu Nishimura (Kyoto)

Additional Reviewers

Daisuke Bekki, Paul Busch, Kentaro Honda, Matthew Leifer, Timothy Proctor, Francisco Rios, and Michael Westmoreland


Denotational Semantics and Quantum Topology

Masahito Hasegawa (Research Institute for Mathematica Sciences, Kyoto University)

In last two decades, traced monoidal categories [9] have found many important applications in theoretical computer science, especially in the area of semantics of logic and computation. The notion of trace nicely captures various forms of feedback or iteration [2] and circular or recursive structure [5, 14], which have been extensively studied in denotational semantics for more than 40 years. Moreover, there is a canonical way of constructing a ribbon category [15] (tortile monoidal categories [13]) from any traced monoidal category called Int-construction [9] which captures the key aspect of Geometry of Interaction [1, 4], that is, an abstract implementation of bi-directional information flow using feedback. A wide range of semantic models of programming languages as well as proof systems have been obtained using Int-construction [4, 7, 12].

On the other hand, since a free ribbon category is equivalent to the category of (oriented framed) tangles [13, 16], each ribbon category gives rise to an invariant of tangles in a functorial way [16]. (This situation can be compared with the role of cartesian closed categories in denotational semantics: a free cartesian closed category is equivalent to the term model of the simply typed lambda calculus.) In particular, many important ribbon categories arise as the categories of linear representations of quantum groups [3] or ribbon Hopf algebras, and they give so-called quantum invariants of (oriented framed) tangles. In this way, ribbon categories play key roles in the development of quantum topology [15, 16].

However, despite the importance of traced monoidal categories and ribbon categories in denotational semantics and quantum topology, there were not much interaction between these two areas. Specifically, we had no non-trivial example of traced monoidal categories or ribbon categories which are interesting for both of denotational semantics and quantum topology.

In this talk, we give an overview of our recent attempts to fill this gap between denotational semanntics and quantum topology. Namely, we start with some familiar monoidal categories used in denotational semantics, and try to find a well-behaved, non-trivial Hopf algebras in these categories which play the role of quantum groups in quantum topology. In some categories such as Rel of sets and binary relations, this approach works very much like the case of linear representations of quantum groups and gives rise to braided monoidal categories which can provide semantics of programs and invariants of tangles at the same time [6]. On the other hand, recently Kenji Maillard [11] has shown that there is no Hopf algebra in the compact closed category of Conway games [8]. This result suggests that it is quite hard (if not impossible) to obtain braided monoidal categories of sequential games by this approach. We also have some negative result for the categories of domains. Thus it is not always possible to literally copy the ideas of quantum topology in denotational semantics.

As of writing this, all our results are of purely mathematical nature, and we are yet to find concrete computational applications. A promising direction would be that of topological quantum computation [10], for which modular tensor categories [15] (certain class of well-behaved ribbon categories) play the central role. It would be interesting to see if our approach would provide a way of relating program semantics with topological quantum computation, like a compilation scheme for (quantum or classical) programs into a topological quantum computing architecture.

References

  1. S. Abramsky, E. Haghverdi & P.J. Scott (2002): Geometry of Interaction and linear combinatory algebras. Mathematical Structures in Computer Science 12, pp. 625–665, doi:10.1017/S0960129502003730.
  2. S. Bloom & Z. Ésik (1993): Iteration Theories. Springer-Verlag, doi:10.1007/978-3-642-78034-9.
  3. V.G. Drinfel'd (1987): Quantum groups. In: Proceedings of 1986 International Congress of Mathematicians, pp. 798–820. Available at http://www.mathunion.org/ICM/ICM1986.1/Main/icm1986.1.0798.0820.ocr.pdf.
  4. J.-Y. Girard (1989): Geometry of Interaction I: interpretation of system F. In: Logic Colloquium 88, Elsevier, pp. 221–260.
  5. M. Hasegawa (1999): Models of Sharing Graphs: A Categorical Semantics of let and letrec. Springer-Verlag, doi:10.1007/978-1-4471-0865-8. Originally published as Ph.D. thesis, ECS-LFCS-97-360, University of Edinburgh, 1997.
  6. M. Hasegawa (2012): A quantum double construction in Rel. Mathematical Structures in Computer Science 22(4), pp. 618–650, doi:10.1017/S0960129511000703. Available at http://hdl.handle.net/2433/159905.
  7. I. Hasuo & N. Hoshino (2011): Semantics of higher-order quantum computation via Geometry of Interaction. In: LICS 2011, IEEE Press, pp. 237–246, doi:10.1109/LICS.2011.26.
  8. A. Joyal (1977): Remarques sur la théorie des jeux á deux personnes. Gazette des Sciences Mathématiques du Québec 1, pp. 46–52.
  9. A. Joyal, R. Street & D. Verity (1996): Traced monoidal categories. Mathematical Proceedings of the Cambridge Philosophical Society 119(3), pp. 447–468, doi:10.1017/S0305004100074338.
  10. A. Kitaev (2003): Fault-tolerant quantum computation by anyons. Annals of Physics 303(1), pp. 3–20, doi:10.1016/S0003-4916(02)00018-0. Available at http://arxiv.org/abs/quant-ph/9707021.
  11. K. Maillard (2013): Looking for the lost Hopf monoids. Report of Internship at RIMS in Kyoto University, ENS Paris.
  12. Ulrich Schöpp (2013): On interaction, continuations and defunctionalization. In: TLCA 2013, Lecture Notes in Computer Science 7941, Springer-Verlag, pp. 205–220, doi:10.1007/978-3-642-38946-7.
  13. M.-C. Shum (1994): Tortile tensor categories. Journal of Pure and Applied Algebra 93, pp. 57–110, doi:10.1016/0022-4049(92)00039-T.
  14. G. Ştefănescu (2000): Network Algebra. Springer-Verlag, doi:10.1007/978-1-4471-0479-7.
  15. V.G. Turaev (1994): Quantum Invariants of Knots and 3-Manifolds. de Gruyter.
  16. D.N. Yetter (2001): Functorial Knot Theory. World Scientific, doi:10.1142/9789812810465.