Abstract
A game-semantics foundation for quantum computation is presented. It draws on two lines of work: for its temporal dynamics, on concurrent games and strategies, based on event structures; for its quantum interactions, on the mathematical foundations of positive operators and completely positive maps. The two lines are married in the definition of quantum concurrent strategy, obtained via an operator generalisation of the conditions on a probabilistic concurrent strategy. The result is a compact-closed (bi)category of quantum games, whose finite configurations carry finite dimensional Hilbert spaces, and quantum strategies, whose finite configurations carry operators.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
The use of subdensity rather than density operators, where \(\mathrm{tr}(\rho )=1\), is natural in quantum systems which may stick with a non-trivial probability.
- 2.
A Scott-open subset of configurations is upwards-closed w.r.t. inclusion and such that if it contains the union of a directed subset S of configurations then it contains an element of S. A continuous valuation is a function w from the Scott-open subsets of \(\,\!{\mathcal C}^\infty (E)\) to [0, 1] which is ((normalised)\(w(\,\!{\mathcal C}^\infty (E)) = 1\); (strict) \(w(\emptyset ) = 0 \); (monotone)\(U \subseteq V \implies w(U)\le w(V)\); (modular)\(w(U \cup V) + w(U\cap V) = w(U) + w(V)\); and (continuous) \(w(\bigcup _{i\in I} U_i) = \mathrm{sup}_{i\in I} w(U_i)\), for directed unions.
- 3.
References
Winskel, G.: Events, causality and symmetry. Comput. J. 54, 42–57 (2011)
Winskel, G.: Distributed games and strategies. Festschrift for pierre-louis curien on the occasion of his 60th birthday (2014, as yet unpublished)
Winskel, G.: Distributed probabilistic and quantum strategies. Electr. Notes Theor. Comput. Sci. 298, 403–425 (2013)
Grabbe, J.: An introduction to quantum game theory. arXiv preprint quant-ph/0506219 (2005)
Pagani, M., Selinger, P., Valiron, B.: Applying quantitative semantics to higher-order quantum computing. In: POPL 2014 (2014)
Delbecque, Y., Panagaden, P.: Game semantics for quantum stores. MFPS XXIV, Electr. Notes Theor. Comput. Sci. 218, 153–170 (2008)
Dal Lago, U., Faggian, C., Valiron, B., Yoshimizu, A.: The geometry of parallelism, classical, probabilistic, and quantum effects. In: POPL 2017 (2017)
Brukner, C.: Quantum causality. Nat. Phys. 10, 259 (2014)
Abramsky, S., Coecke, B.: A categorical semantics of quantum protocols. In: LICS 2004 (2004)
Castellan, S., Clairambault, P., Winskel, G.: The parallel intensionally fully abstract games model of PCF. In: LICS 2015 (2015)
Castellan, S., Clairambault, P., Paquet, H., Winskel, G.: The concurrent game semantics of probabilistic PCF. In: LICS 2018 (2018)
Selinger, P., Valiron, B.: On a fully abstract model for a quantum linear functional language. Electr. Notes Theor. Comput. Sci. 210, 123–137 (2008)
Clairambault, P., de Visme, M., Winskel, G.: Game semantics for quantum programming. In: POPL 2019 (2019)
Joyal, A., Street, R., Verity, D.: Traced monoidal categories. In: Mathematical Proceedings of the Cambridge Philosophical Society (1996)
Selinger, P.: Dagger compact closed categories and completely positive maps: (extended abstract). Electr. Notes Theor. Comput. Sci. 170, 139–163 (2007)
Winskel, G.: Probabilistic and quantum event structures. In: van Breugel, F., Kashefi, E., Palamidessi, C., Rutten, J. (eds.) Horizons of the Mind. A Tribute to Prakash Panangaden. LNCS, vol. 8464, pp. 476–497. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-06880-0_25
Alvarez-Manilla, M., Edalat, A., Saheb-Djahromi, N.: An extension result for continuous valuations. J. LMS 61, 629–640 (2000)
Leifer, M.S., Spekkens, R.W.: Towards a formulation of quantum theory as a causally neutral theory of Bayesian inference. Phys. Rev. 88, 052130 (2013)
Saunders-Evans, L., Winskel, G.: Event structure spans for nondeterministic dataflow. Electr. Notes Theor. Comput. Sci. 175(3), 109–129 (2007)
Selinger, P.: Towards a quantum programming language. Math. Struct. Comput. Sci. 14, 527–586 (2004)
Acknowledgments
We are grateful to the ERC for Advanced Grant ECSYM. Discussions with Frank Roumen and Benoît Valiron have been very helpful.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Clairambault, P., de Visme, M., Winskel, G. (2019). Concurrent Quantum Strategies. In: Thomsen, M., Soeken, M. (eds) Reversible Computation. RC 2019. Lecture Notes in Computer Science(), vol 11497. Springer, Cham. https://doi.org/10.1007/978-3-030-21500-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-21500-2_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-21499-9
Online ISBN: 978-3-030-21500-2
eBook Packages: Computer ScienceComputer Science (R0)