Synchronous linear constraint system games. (English) Zbl 1460.91058
Summary: Mathematical models of quantum mechanics can be studied and distinguished using nonlocal games. We discuss a class of nonlocal games called synchronous linear constraint system (syncLCS) games. We unify two algebraic approaches to studying syncLCS games and relate these games to nonlocal games played on graphs, known as graph isomorphism games. In more detail, syncLCS games are nonlocal games that verify whether or not two players share a solution to a given system of equations. Two algebraic objects associated with these games encode information about the existence of perfect strategies. They are called the game algebra and the solution group. Here, we show that these objects are essentially the same, i.e., the game algebra is a suitable quotient of the group algebra of the solution group. We also demonstrate that syncLCS games are equivalent to graph isomorphism games on a pair of graphs parameterized by the linear system.
©2021 American Institute of Physics
©2021 American Institute of Physics
MSC:
| 91A81 | Quantum games |
| 81P40 | Quantum coherence, entanglement, quantum correlations |
| 91A43 | Games involving graphs |
| 91A05 | 2-person games |
References:
| [1] | Atserias, A.; Mančinska, L.; Roberson, D. E.; Šámal, R.; Severini, S.; Varvitsiotis, A., Quantum and non-signalling graph isomorphisms, J. Comb. Theory, Ser. B, 136, 289-328 (2019) · Zbl 1414.05197 · doi:10.1016/j.jctb.2018.11.002 |
| [2] | Brannan, M.; Chirvasitu, A.; Eifler, K.; Harris, S.; Paulsen, V.; Su, X.; Wasilewski, M., Bigalois extensions and the graph isomorphism game, Commun. Math. Phys., 375, 3, 1777-1809 (2019) · Zbl 1443.91086 · doi:10.1007/s00220-019-03563-9 |
| [3] | Cleve, R.; Hoyer, P.; Toner, B.; J. Watrous, Consequences and limits of nonlocal strategies, 236-249 (2004), IEEE |
| [4] | Cleve, R.; Liu, L.; Slofstra, W., Perfect commuting-operator strategies for linear system games, J. Math. Phys., 58, 1, 012202 (2017) · Zbl 1355.81048 · doi:10.1063/1.4973422 |
| [5] | Cleve, R.; Mittal, R., Characterization of binary constraint system games, 320-331 (2014), Springer · Zbl 1364.91015 |
| [6] | Helton, J. W.; Meyer, K. P.; Paulsen, V. I.; Satriano, M., Algebras, synchronous games and chromatic numbers of graphs, New York J. Math., 25, 328-361 (2019) · Zbl 1410.05069 |
| [7] | Ji, Z.; Natarajan, A.; Vidick, T.; Wright, J.; H., Yuen, MIP^* = RE (2020) |
| [8] | Kim, S.-J.; Paulsen, V.; Schafhauser, C., A synchronous game for binary constraint systems, J. Math. Phys., 59, 3, 032201 (2018) · Zbl 1384.81018 · doi:10.1063/1.4996867 |
| [9] | Lupini, M.; Mančinska, L.; Paulsen, V. I.; Roberson, D. E.; Scarpa, G.; Severini, S.; Todorov, I. G.; Winter, A., Perfect strategies for non-local games, Math. Phys., Anal. Geom., 23, 1, 7 (2020) · Zbl 1436.91021 · doi:10.1007/s11040-020-9331-7 |
| [10] | Ortiz, C. M.; Paulsen, V. I., Quantum graph homomorphisms via operator systems, Linear Algebra Appl., 497, 23-43 (2016) · Zbl 1353.46041 · doi:10.1016/j.laa.2016.02.019 |
| [11] | Paulsen, V. I.; Severini, S.; Stahlke, D.; Todorov, I. G.; Winter, A., Estimating quantum chromatic numbers, J. Funct. Anal., 270, 6, 2188-2222 (2016) · Zbl 1353.46043 · doi:10.1016/j.jfa.2016.01.010 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
