Document Open Access Logo

The Quantum Monad on Relational Structures

Authors Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, Octavio Zapata

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2017.35.pdf
  • Filesize: 0.57 MB
  • 19 pages

Document Identifiers

Author Details

Samson Abramsky
Rui Soares Barbosa
Nadish de Silva
Octavio Zapata

Cite As Get BibTex

Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata. The Quantum Monad on Relational Structures. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.MFCS.2017.35

Abstract

Homomorphisms between relational structures play a central role in finite model theory, constraint satisfaction, and database theory. A central theme in quantum computation is to show how quantum resources can be used to gain advantage in information processing tasks. In particular, non-local games have been used to exhibit quantum advantage in boolean constraint satisfaction, and to obtain quantum versions of graph invariants such as the chromatic number. We show how quantum strategies for homomorphism games between relational structures can be viewed as Kleisli morphisms for a quantum monad on the (classical) category of relational structures and homomorphisms. We use these results to exhibit a wide range of examples of contextuality-powered quantum advantage, and to unify several apparently diverse strands of previous work.

Subject Classification

Keywords
  • non-local games
  • quantum computation
  • monads

Metrics

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

References

  1. Samson Abramsky, Rui Soares Barbosa, Giovanni Carù, Nadish de Silva, Kohei Kishida, and Shane Mansfield. Minimum quantum resources for strong non-locality, 2017. To appear in Proceedings of the 12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017). Available as arXiv:1705.09312 [quant-ph]. Google Scholar
  2. Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield. Contextuality, cohomology and paradox. In Stephan Kreutzer, editor, 24th EACSL Annual Conference on Computer Science Logic (CSL 2015), volume 41 of Leibniz International Proceedings in Informatics (LIPIcs), pages 211-228. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CSL.2015.211.
  3. Samson Abramsky, Rui Soares Barbosa, and Shane Mansfield. Contextual fraction as a measure of contextuality, 2017. To appear in Physical Review Letters. Available as arXiv:1705.07918 [quant-ph]. Google Scholar
  4. Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics, 13(11):113036, 2011. URL: http://dx.doi.org/10.1088/1367-2630/13/11/113036.
  5. Samson Abramsky and Bob Coecke. A categorical semantics of quantum protocols. In Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LiCS 2004), pages 415-425, 2004. URL: http://dx.doi.org/10.1109/LICS.2004.1319636.
  6. Samson Abramsky and Bob Coecke. Categorical quantum mechanics. In Kurt Engesser, Dov M. Gabbay, and Daniel Lehmann, editors, Handbook of quantum logic and quantum structures: Quantum logic, pages 261-323. Elsevier, 2009. URL: http://dx.doi.org/10.1016/B978-0-444-52869-8.50010-4.
  7. Samson Abramsky, Anuj Dawar, and Pengming Wang. The pebbling comonad in finite model theory, 2017. To appear in Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LiCS 2017). Available as arXiv:1704.05124 [cs.LO]. Google Scholar
  8. Albert Atserias, Laura Mančinska, David E Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis. Quantum and non-signalling graph isomorphisms, 2016. Available as arXiv:1611.09837 [quant-ph]. Google Scholar
  9. Bruce Blackadar. Operator algebras: Theory of C^*-algebras and von Neumann algebras, volume 122 of Encyclopaedia of Mathematical Sciences. Springer, 2006. URL: http://dx.doi.org/10.1007/3-540-28517-2.
  10. Adán Cabello, José M. Estebaranz, and Guillermo Garcí a-Alcaine. Bell-Kochen-Specker theorem: A proof with 18 vectors. Physics Letters A, 212(4):183-187, 1996. URL: http://dx.doi.org/10.1016/0375-9601(96)00134-X.
  11. Peter J. Cameron, Ashley Montanaro, Michael W. Newman, Simone Severini, and Andreas Winter. On the quantum chromatic number of a graph. Electronic Journal of Combinatorics, 14(1):R81, 2007. Google Scholar
  12. Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58(1):012202, 2017. URL: http://dx.doi.org/10.1063/1.4973422.
  13. Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Part I (ICALP 2014), pages 320-331. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_27.
  14. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28(1):57-104, 1998. URL: http://dx.doi.org/10.1137/S0097539794266766.
  15. Daniel M. Greenberger, Michael A. Horne, and Anton Zeilinger. Going beyond Bell’s theorem. In Menas Kafatos, editor, Bell’s theorem, quantum theory, and conceptions of the universe, volume 37 of Fundamental Theories of Physics, pages 69-72. Kluwer, 1989. URL: http://dx.doi.org/10.1007/978-94-017-0849-4_10.
  16. Teiko Heinosaari, Daniel Reitzner, and Peter Stano. Notes on joint measurability of quantum observables. Foundations of Physics, 38(12):1133-1147, 2008. URL: http://dx.doi.org/10.1007/s10701-008-9256-7.
  17. Pavol Hell and Jaroslav Nešetřil. Graphs and homomorphisms, volume 28 of Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, 2004. URL: http://dx.doi.org/10.1093/acprof:oso/9780198528173.001.0001.
  18. William Helton, Kyle P. Meyer, Vern I. Paulsen, and Matthew Satriano. Algebras, synchronous games and chromatic numbers of graphs, 2017. Available as arXiv:1703.00960 [math.OA]. Google Scholar
  19. Peter Heywood and Michael L. G. Redhead. Nonlocality and the Kochen-Specker paradox. Foundations of physics, 13(5):481-499, 1983. URL: http://dx.doi.org/10.1007/BF00729511.
  20. Bart Jacobs. Convexity, duality and effects. In Cristian S. Calude and Vladimiro Sassone, editors, Proceedings of 6th IFIP TC 1/WG 2.2 International Conference on Theoretical Computer Science (TCS 2010), pages 1-19. Springer, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15240-5_1.
  21. Zhengfeng Ji. Binary constraint system games and locally commutative reductions, 2013. Available as arXiv:1310.3794 [quant-ph]. Google Scholar
  22. Simon Kochen and Ernst P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Google Scholar
  23. Anders Kock. Monads on symmetric monoidal closed categories. Archiv der Mathematik, 21(1):1-10, 1970. URL: http://dx.doi.org/10.1007/BF01220868.
  24. Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences, 61(2):302-332, 2000. URL: http://dx.doi.org/10.1006/jcss.2000.1713.
  25. Leonid Libkin. Elements of finite model theory. Texts in Theoretical Computer Science. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-662-07003-1.
  26. Saunders Mac Lane. Categories for the working mathematician, volume 5 of Graduate Texts in Mathematics. Springer, 1971. URL: http://dx.doi.org/10.1007/978-1-4757-4721-8.
  27. Laura Mančinska and David E Roberson. Quantum homomorphisms. Journal of Combinatorial Theory, Series B, 118:228-267, 2016. URL: http://dx.doi.org/10.1016/j.jctb.2015.12.009.
  28. N. David Mermin. Quantum mysteries revisited. American Journal of Physics, 58(8):731-734, 1990. URL: http://dx.doi.org/10.1119/1.16503.
  29. N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65(27):3373-3376, Dec 1990. URL: http://dx.doi.org/10.1103/PhysRevLett.65.3373.
  30. Stefan Milius, Dirk Pattinson, and Lutz Schröder. Generic trace semantics and graded monads. In Lawrence S. Moss and Pawel Sobocinski, editors, 6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015), volume 35 of Leibniz International Proceedings in Informatics (LIPIcs), pages 253-269. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.CALCO.2015.253.
  31. Ryan O'Donnell. Analysis of boolean functions. Cambridge University Press, 2014. URL: http://dx.doi.org/10.1017/CBO9781139814782.
  32. Gert K. Pedersen. Analysis now, volume 118 of Graduate Texts in Mathematics. Springer, 1989. URL: http://dx.doi.org/10.1007/978-1-4612-1007-8.
  33. Sandu Popescu and Daniel Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379-385, 1994. URL: http://dx.doi.org/10.1007/BF02058098.
  34. David E. Roberson. Variations on a theme: Graph homomorphisms. PhD thesis, University of Waterloo, 2013. Google Scholar
  35. Volkher B. Scholz and Reinhard F. Werner. Tsirelson’s problem, 2008. Available as arXiv:0812.4305 [math-ph]. Google Scholar
  36. William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games, 2016. Available as arXiv:1606.03140 [quant-ph]. Google Scholar
  37. Boris Tsirelson. Bell inequalities and operator algebras, 2006. Pre-print. Google Scholar
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