{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:04:40Z","timestamp":1773479080342,"version":"3.50.1"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"POPL","license":[{"start":{"date-parts":[[2019,1,2]],"date-time":"2019-01-02T00:00:00Z","timestamp":1546387200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100011199","name":"FP7 Ideas: European Research Council","doi-asserted-by":"publisher","award":["ERC-2010-AdG_20100224"],"award-info":[{"award-number":["ERC-2010-AdG_20100224"]}],"id":[{"id":"10.13039\/100011199","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005304","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-10-LABX-0070"],"award-info":[{"award-number":["ANR-10-LABX-0070"]}],"id":[{"id":"10.13039\/501100005304","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2019,1,2]]},"abstract":"<jats:p>Quantum programming languages permit a hardware independent, high-level description of quantum algo rithms. In particular, the quantum lambda-calculus is a higher-order programming language with quantum primitives, mixing quantum data and classical control. Giving satisfactory denotational semantics to the quantum lambda-calculus is a challenging problem that has attracted significant interest in the past few years. Several models have been proposed but for those that address the whole quantum \u03bb-calculus, they either do not represent the dynamics of computation, or they lack the compositionality one often expects from denotational models.<\/jats:p>\n          <jats:p>In this paper, we give the first compositional and interactive model of the full quantum lambda-calculus, based on game semantics. To achieve this we introduce a model of quantum games and strategies, combining quantum data with a representation of the dynamics of computation inspired from causal models of concurrent systems. In this model we first give a computationally adequate interpretation of the affine fragment. Then, we extend the model with a notion of symmetry, allowing us to deal with replication. In this refined setting, we interpret and prove adequacy for the full quantum lambda-calculus. We do this both from a sequential and a parallel interpretation, the latter representing faithfully the causal independence between sub-computations.<\/jats:p>","DOI":"10.1145\/3290345","type":"journal-article","created":{"date-parts":[[2019,1,4]],"date-time":"2019-01-04T13:33:51Z","timestamp":1546608831000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Game semantics for quantum programming"],"prefix":"10.1145","volume":"3","author":[{"given":"Pierre","family":"Clairambault","sequence":"first","affiliation":[{"name":"University of Lyon, France \/ CNRS, France \/ ENS Lyon, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"De Visme","sequence":"additional","affiliation":[{"name":"University of Lyon, France \/ ENS Lyon, France \/ CNRS, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Glynn","family":"Winskel","sequence":"additional","affiliation":[{"name":"University of Cambridge, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,1,2]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2930"},{"key":"e_1_2_2_2_1","volume-title":"11th International Workshop, CSL \u201997, Annual Conference of the EACSL","author":"Abramsky Samson","year":"1997","unstructured":"Samson Abramsky and Guy McCusker . 1997 . Call-by-Value Games. In Computer Science Logic , 11th International Workshop, CSL \u201997, Annual Conference of the EACSL , Aarhus, Denmark , August 23-29, 1997, Selected Papers. 1\u201317. Samson Abramsky and Guy McCusker. 1997. Call-by-Value Games. In Computer Science Logic, 11th International Workshop, CSL \u201997, Annual Conference of the EACSL, Aarhus, Denmark, August 23-29, 1997, Selected Papers. 1\u201317."},{"key":"e_1_2_2_3_1","volume-title":"Concurrent Games and Full Completeness. In 14th Annual IEEE Symposium on Logic in Computer Science","author":"Abramsky Samson","year":"1999","unstructured":"Samson Abramsky and Paul-Andr\u00e9 Melli\u00e8s . 1999 . Concurrent Games and Full Completeness. In 14th Annual IEEE Symposium on Logic in Computer Science , Trento, Italy , July 2-5, 1999. 431\u2013442. Samson Abramsky and Paul-Andr\u00e9 Melli\u00e8s. 1999. Concurrent Games and Full Completeness. In 14th Annual IEEE Symposium on Logic in Computer Science, Trento, Italy, July 2-5, 1999. 431\u2013442."},{"key":"e_1_2_2_4_1","volume-title":"Interleavings in Concurrent Game Semantics. In 27th International Conference on Concurrency Theory, CONCUR 2016","author":"Castellan Simon","year":"2016","unstructured":"Simon Castellan and Pierre Clairambault . 2016 . Causality vs . Interleavings in Concurrent Game Semantics. In 27th International Conference on Concurrency Theory, CONCUR 2016 , August 23-26, 2016, Qu\u00e9bec City, Canada. 32:1\u201332:14. Simon Castellan and Pierre Clairambault. 2016. Causality vs. Interleavings in Concurrent Game Semantics. In 27th International Conference on Concurrency Theory, CONCUR 2016, August 23-26, 2016, Qu\u00e9bec City, Canada. 32:1\u201332:14."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209187"},{"key":"e_1_2_2_6_1","volume-title":"Games and Strategies as Event Structures. LMCS 13, 3","author":"Castellan Simon","year":"2017","unstructured":"Simon Castellan , Pierre Clairambault , Silvain Rideau , and Glynn Winskel . 2017. Games and Strategies as Event Structures. LMCS 13, 3 ( 2017 ). Simon Castellan, Pierre Clairambault, Silvain Rideau, and Glynn Winskel. 2017. Games and Strategies as Event Structures. LMCS 13, 3 (2017)."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2603088.2603141"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.31"},{"key":"e_1_2_2_9_1","unstructured":"Simon Castellan Pierre Clairambault and Glynn Winskel. 2016. Concurrent Hyland-Ong Games. (2016). https:\/\/arxiv.org\/abs\/1409.7542.  Simon Castellan Pierre Clairambault and Glynn Winskel. 2016. Concurrent Hyland-Ong Games. (2016). https:\/\/arxiv.org\/abs\/1409.7542."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.34"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009859"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2011.01.005"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02273-9_9"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1571-0661(04)80078-1"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129506005378"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90045-4"},{"key":"e_1_2_2_17_1","volume-title":"Studies in Logic and the Foundations of Mathematics.","author":"Girard Jean-Yves","unstructured":"Jean-Yves Girard . 1989. Geometry of interaction 1: Interpretation of System F . In Studies in Logic and the Foundations of Mathematics. Vol. 127 . Elsevier , 221\u2013260. Jean-Yves Girard. 1989. Geometry of interaction 1: Interpretation of System F. In Studies in Logic and the Foundations of Mathematics. Vol. 127. Elsevier, 221\u2013260."},{"key":"e_1_2_2_18_1","volume-title":"Quantum cryptography. Reviews of modern physics 74, 1","author":"Gisin Nicolas","year":"2002","unstructured":"Nicolas Gisin , Gr\u00e9goire Ribordy , Wolfgang Tittel , and Hugo Zbinden . 2002. Quantum cryptography. Reviews of modern physics 74, 1 ( 2002 ), 145. Nicolas Gisin, Gr\u00e9goire Ribordy, Wolfgang Tittel, and Hugo Zbinden. 2002. Quantum cryptography. Reviews of modern physics 74, 1 (2002), 145."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237866"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/788021.788970"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2016.10.010"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00039-0"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2917"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00241-9"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100074338"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2013.36"},{"key":"e_1_2_2_28_1","volume-title":"Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky - Essays Dedicated to Samson Abramsky on the Occasion of His 60th Birthday. 178\u2013194.","author":"Malherbe Octavio","unstructured":"Octavio Malherbe , Philip Scott , and Peter Selinger . 2013. Presheaf Models of Quantum Computation: An Outline . In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky - Essays Dedicated to Samson Abramsky on the Occasion of His 60th Birthday. 178\u2013194. Octavio Malherbe, Philip Scott, and Peter Selinger. 2013. Presheaf Models of Quantum Computation: An Outline. In Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky - Essays Dedicated to Samson Abramsky on the Occasion of His 60th Birthday. 178\u2013194."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2005.6"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2012.58"},{"key":"e_1_2_2_31_1","volume-title":"Asynchronous Games: Innocence Without Alternation. In CONCUR 2007 - Concurrency Theory, 18th International Conference, CONCUR 2007, Lisbon, Portugal, September 3-8, 2007, Proceedings. 395\u2013411","author":"Melli\u00e8s Paul-Andr\u00e9","year":"2007","unstructured":"Paul-Andr\u00e9 Melli\u00e8s and Samuel Mimram . 2007 . Asynchronous Games: Innocence Without Alternation. In CONCUR 2007 - Concurrency Theory, 18th International Conference, CONCUR 2007, Lisbon, Portugal, September 3-8, 2007, Proceedings. 395\u2013411 . Paul-Andr\u00e9 Melli\u00e8s and Samuel Mimram. 2007. Asynchronous Games: Innocence Without Alternation. In CONCUR 2007 - Concurrency Theory, 18th International Conference, CONCUR 2007, Lisbon, Portugal, September 3-8, 2007, Proceedings. 395\u2013411."},{"key":"e_1_2_2_32_1","doi-asserted-by":"crossref","unstructured":"Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.  Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.","DOI":"10.1119\/1.1463744"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535838.2535879"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129597002375"},{"key":"e_1_2_2_35_1","volume-title":"ICALP\u201999 (LNCS)","author":"Power John","unstructured":"John Power and Hayo Thielecke . 1999. Closed Freyd- and kappa-categories . In ICALP\u201999 (LNCS) , Vol. 1644 . Springer . John Power and Hayo Thielecke. 1999. Closed Freyd- and kappa-categories. In ICALP\u201999 (LNCS), Vol. 1644. Springer."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.13"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129504004256"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129506005238"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2008.04.022"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of an Advanced Course, Bad Honnef, 8.-19","author":"Winskel Glynn","year":"1986","unstructured":"Glynn Winskel . 1986 . Event Structures. In Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II , Proceedings of an Advanced Course, Bad Honnef, 8.-19 . September 1986. 325\u2013392. Glynn Winskel. 1986. Event Structures. In Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, Bad Honnef, 8.-19. September 1986. 325\u2013392."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2007.02.022"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-012-0235-6"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2013.09.024"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290345","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3290345","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:58:04Z","timestamp":1750208284000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3290345"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,1,2]]},"references-count":43,"journal-issue":{"issue":"POPL","published-print":{"date-parts":[[2019,1,2]]}},"alternative-id":["10.1145\/3290345"],"URL":"https:\/\/doi.org\/10.1145\/3290345","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,1,2]]},"assertion":[{"value":"2019-01-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}