Document Open Access Logo

Higher-Order Causal Theories Are Models of BV-Logic

Authors Will Simmons , Aleks Kissinger

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2022.80.pdf
  • Filesize: 0.79 MB
  • 14 pages

Document Identifiers

Author Details

Will Simmons
  • Department of Computer Science, University of Oxford, Oxford, UK
  • Cambridge Quantum, Terrington House, 13-15 Hills Road, Cambridge, UK
Aleks Kissinger
  • Department of Computer Science, University of Oxford, Oxford, UK

Funding

  • Simmons, Will: was supported by Cambridge Quantum (Quantinuum Ltd).
  • Kissinger, Aleks: acknowledges support from Grant No. 61466 from the John Templeton Foundation as part of the QISS project. The opinions expressed in this publication are those of the authors and do not necessarily reflect the views of the John Templeton Foundation.

Acknowledgements

The authors would like to thank Alessio Guglielmi for posing the question of modelling BV-logic within Caus[𝒞], as well as Chris Barrett, Lutz Straßburger, and members of the quantum group at University of Oxford for useful discussions.

Cite As Get BibTex

Will Simmons and Aleks Kissinger. Higher-Order Causal Theories Are Models of BV-Logic. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.80

Abstract

The Caus[-] construction takes a compact closed category of basic processes and yields a *-autonomous category of higher-order processes obeying certain signalling/causality constraints, as dictated by the type system in the resulting category. This paper looks at instances where the base category C satisfies additional properties yielding an affine-linear structure on Caus[𝒞] and a substantially richer internal logic. While the original construction only gave multiplicative linear logic, here we additionally obtain additives and a non-commutative, self-dual sequential product yielding a model of Guglielmi’s BV logic. Furthermore, we obtain a natural interpretation for the sequential product as "A can signal to B, but not vice-versa", which sits as expected between the non-signalling tensor and the fully-signalling (i.e. unconstrained) par. Fixing matrices of positive numbers for 𝒞 recovers the BV category structure of probabilistic coherence spaces identified by Blute, Panangaden, and Slavnov, restricted to normalised maps. On the other hand, fixing the category of completely positive maps gives an entirely new model of BV consisting of higher order quantum channels, encompassing recent work in the study of quantum and indefinite causal structures.

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum computation theory
  • Theory of computation → Linear logic
  • Theory of computation → Categorical semantics
Keywords
  • Causality
  • linear logic
  • categorical logic
  • probabilistic coherence spaces
  • quantum channels

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ämin Baumeler, Adrien Feix, and Stefan Wolf. Maximal incompatibility of locally classical behavior and global causal order in multiparty scenarios. Physical Review A - Atomic, Molecular, and Optical Physics, 90(4):42106, October 2014. URL: https://doi.org/10.1103/PhysRevA.90.042106.
  2. Alessandro Bisio and Paolo Perinotti. Theoretical framework for higher-order quantum theory. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 475(2225), May 2019. URL: https://doi.org/10.1098/rspa.2018.0706.
  3. Richard Blute, Prakash Panangaden, and Sergey Slavnov. Deep inference and probabilistic coherence spaces. Applied Categorical Structures, 2012. URL: https://doi.org/10.1007/s10485-010-9241-0.
  4. Richard F. Blute, Ivan T. Ivanov, and Prakash Panangaden. Discrete quantum causal dynamics. International Journal of Theoretical Physics, 42(9):2025-2041, September 2003. URL: https://doi.org/10.1023/A:1027335119549.
  5. Paulo J. Cavalcanti, John H. Selby, Jamie Sikora, and Ana Belén Sainz. Simulating all multipartite non-signalling channels via quasiprobabilistic mixtures of local channels in generalised probabilistic theories. arxiv.org, 2022. URL: http://arxiv.org/abs/2204.10639.
  6. G Chiribella, G. M. D'Ariano, and P. Perinotti. Quantum circuit architecture. Physical Review Letters, 101(6), August 2008. URL: https://doi.org/10.1103/PhysRevLett.101.060401.
  7. Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Theoretical framework for quantum networks. Physical Review A, 80(2):022339, August 2009. URL: https://doi.org/10.1103/PhysRevA.80.022339.
  8. Giulio Chiribella, Giacomo Mauro D'Ariano, and Paolo Perinotti. Probabilistic theories with purification. Physical Review A, 81(6):062348, June 2010. URL: https://doi.org/10.1103/PhysRevA.81.062348.
  9. Giulio Chiribella, Giacomo Mauro D'Ariano, Paolo Perinotti, and Benoit Valiron. Quantum computations without definite causal structure. Physical Review A, 88(2):022318, August 2013. URL: https://doi.org/10.1103/PhysRevA.88.022318.
  10. Bob Coecke and Aleks Kissinger. Picturing Quantum Processes. Cambridge University Press, March 2017. URL: https://doi.org/10.1017/9781316219317.
  11. Alessio Guglielmi. A system of interaction and structure. ACM Transactions on Computational Logic, 2007. URL: https://doi.org/10.1145/1182613.1182614.
  12. Gus Gutoski. Properties of Local Quantum Operations with Shared Entanglement. Quantum Information and Computation, 9(9-10):0739-0764, May 2008. URL: http://arxiv.org/abs/0805.2209.
  13. Gus Gutoski and John Watrous. Toward a general theory of quantum games. Proceedings of the Annual ACM Symposium on Theory of Computing, pages 565-574, 2007. URL: https://doi.org/10.1145/1250790.1250873.
  14. Timothée Hoffreumon and Ognyan Oreshkov. Projective characterization of higher-order quantum transformations. arxiv.org, 2022. URL: http://arxiv.org/abs/2206.06206.
  15. Robin Houston. Finite products are biproducts in a compact closed category. Journal of Pure and Applied Algebra, 2008. URL: https://doi.org/10.1016/j.jpaa.2007.05.021.
  16. Martin Hyland and Andrea Schalk. Glueing and orthogonality for models of linear logic. In Theoretical Computer Science, volume 294, pages 183-231, 2003. URL: https://doi.org/10.1016/S0304-3975(01)00241-9.
  17. Aleks Kissinger, Matty Hoban, and Bob Coecke. Equivalence of relativistic causal structure and process terminality. CoRR, August 2017. URL: http://arxiv.org/abs/1708.04118.
  18. Aleks Kissinger and Sander Uijlen. Picturing indefinite causal structure. In Electronic Proceedings in Theoretical Computer Science, EPTCS, volume 236, pages 87-94, January 2017. URL: https://doi.org/10.4204/EPTCS.236.6.
  19. Aleks Kissinger and Sander Uijlen. A categorical semantics for causal structure. Logical Methods in Computer Science, 2019. URL: https://doi.org/10.23638/LMCS-15(3:15)2019.
  20. Paul-André Melliès. Categorical Semantics of Linear Logic, 2009. URL: https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/categorical-semantics-of-linear-logic.pdf.
  21. Lê Thành Dũng Nguyên and Lutz Straßburger. BV and Pomset Logic Are Not the Same. In Leibniz International Proceedings in Informatics, LIPIcs, volume 216, pages 1-32, 2022. URL: https://doi.org/10.4230/LIPIcs.CSL.2022.32.
  22. Ognyan Oreshkov, Fabio Costa, and Časlav Brukner. Quantum correlations with no causal order. Nature Communications, 3(1):1-8, October 2012. URL: https://doi.org/10.1038/ncomms2076.
  23. Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, March 1994. URL: https://doi.org/10.1007/BF02058098.
  24. Christian Retoré. Pomset logic: A non-commutative extension of classical linear logic. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 1210, pages 300-318, 1997. URL: https://doi.org/10.1007/3-540-62688-3_43.
  25. P. Selinger. A survey of graphical languages for monoidal categories, 2011. URL: https://doi.org/10.1007/978-3-642-12821-9_4.
  26. Will Simmons and Aleks Kissinger. Higher-order causal theories are models of BV-logic. arxiv.org, 2022. URL: http://arxiv.org/abs/2205.11219.
  27. Matt Wilson and Giulio Chiribella. Causality in Higher Order Process Theories. Electronic Proceedings in Theoretical Computer Science, 343:265-300, July 2021. URL: https://doi.org/10.4204/eptcs.343.12.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact