Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1707.01016 · Journal of Mathematical Physics

A synchronous game for binary constraint systems

Se-Jin Kim, Vern I. Paulsen, Christopher P. Schafhauser

Published Mar 1, 2018• 44 citations
arXivHTMLPDF

Abstract

Recently, Slofstra proved that the set of quantum correlations is not closed. We prove that the set of synchronous quantum correlations is not closed, which implies his result, by giving an example of a synchronous game that has a perfect quantum approximate strategy but no perfect quantum strategy. We also exhibit a graph for which the quantum independence number and the quantum approximate independence number are different. We prove new characterisations of synchronous quantum approximate correlations and synchronous quantum spatial correlations. We solve the synchronous approximation problem of Dykema and the second author, which yields a new equivalence of Connes’ embedding problem in terms of synchronous correlations.

DOI
10.1063/1.4996867

Related papers

Synchronous correlation matrices and Connes’ embedding conjecture

Kenneth J. Dykema, Vern Paulsen

In the work of Paulsen et al. [J. Funct. Anal. (in press); preprint arXiv:1407.6918], the concept of synchronous quantum correlation matrices was introduced and these were shown to correspond to traces on certain C*-algebras. In particular, synchronous correlation matrices arose in their study of various versions of quantum chromatic numbers of graphs and other quantum versions of graph theoretic parameters. In this paper, we develop these ideas further, focusing on the relations between synchronous correlation matrices and microstates. We prove that Connes’ embedding conjecture is equivalent to the equality of two families of synchronous quantum correlation matrices. We prove that if Connes’ embedding conjecture has a positive answer, then the tracial rank and projective rank are equal for every graph. We then apply these results to more general non-local games.

arXiv:1503.07207•Journal of Mathematical Physics•Dec 10, 2015•28 citations

Quantum games and synchronicity

Adina Goldberg

In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.

arXiv:2408.15444•Quantum•Jan 14, 2026•0 citations

Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states

Connor Paddock

We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding $*$-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is $*$-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

arXiv:2203.02525•Mar 4, 2022•0 citations

Rounding near-optimal quantum strategies for nonlocal games to strategies using a maximally entangled state

Connor Paddock

We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp. XOR-algebra) yields measurement operators for near-perfect (resp. near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp. near-optimal XOR) quantum strategy is close to a near-perfect (resp. near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.

Journal of Mathematical Physics•Dec 1, 2025•0 citations

THE SET OF QUANTUM CORRELATIONS IS NOT CLOSED

William Slofstra

We construct a linear system nonlocal game which can be played perfectly using a limit of finite-dimensional quantum strategies, but which cannot be played perfectly on any finite-dimensional Hilbert space, or even with any tensor-product strategy. In particular, this shows that the set of (tensor-product) quantum correlations is not closed. The constructed nonlocal game provides another counterexample to the ‘middle’ Tsirelson problem, with a shorter proof than our previous paper (though at the loss of the universal embedding theorem). We also show that it is undecidable to determine if a linear system game can be played perfectly with a finite-dimensional strategy, or a limit of finite-dimensional quantum strategies.

arXiv:1703.08618•Forum of Mathematics Pi•Jan 1, 2019•177 citations

Almost synchronous quantum correlations

Thomas Vidick

The study of quantum correlation sets initiated by Tsirelson in the 1980s and originally motivated by questions in the foundations of quantum mechanics has more recently been tied to questions in quantum cryptography, complexity theory, operator space theory, group theory, and more. Synchronous correlation sets introduced by Paulsen et al. [J. Funct. Anal. 270, 2188–2222 (2016)] are a subclass of correlations that has proven particularly useful to study and arises naturally in applications. We show that any correlation that is almost synchronous, in a natural ℓ1 sense, arises from a state and measurement operators that are well-approximated by a convex combination of projective measurements on a maximally entangled state. This extends a result of Paulsen et al. [J. Funct. Anal. 270, 2188–2222 (2016)] that applies to exactly synchronous correlations. Crucially, the quality of approximation is independent of the dimension of the Hilbert spaces or of the size of the correlation. Our result allows one to reduce the analysis of many classes of nonlocal games, including rigidity properties, to the case of strategies using maximally entangled states that are generally easier to manipulate.

arXiv:2103.02468•Journal of Mathematical Physics•Feb 1, 2022•10 citations
Recently, Slofstra proved that the set of quantum correlations is not closed. We prove that the set of synchronous quantum correlations is not closed, which implies his result, by giving an example of a synchronous game that has a perfect quantum approximate strategy but no perfect quantum strategy. We also exhibit a graph for which the quantum independence number and the quantum approximate independence number are different. We prove new characterisations of synchronous quantum approximate correlations and synchronous quantum spatial correlations. We solve the synchronous approximation problem of Dykema and the second author, which yields a new equivalence of Connes’ embedding problem in terms of synchronous correlations.
In the work of Paulsen et al. [J. Funct. Anal. (in press); preprint arXiv:1407.6918], the concept of synchronous quantum correlation matrices was introduced and these were shown to correspond to traces on certain C*-algebras. In particular, synchronous correlation matrices arose in their study of various versions of quantum chromatic numbers of graphs and other quantum versions of graph theoretic parameters. In this paper, we develop these ideas further, focusing on the relations between synchronous correlation matrices and microstates. We prove that Connes’ embedding conjecture is equivalent to the equality of two families of synchronous quantum correlation matrices. We prove that if Connes’ embedding conjecture has a positive answer, then the tracial rank and projective rank are equal for every graph. We then apply these results to more general non-local games.
In the flavour of categorical quantum mechanics, we extend nonlocal games to allow quantum questions and answers, using quantum sets (special symmetric dagger Frobenius algebras) and the quantum functions of Musto, Reutter, and Verdon. Equations are presented using a diagrammatic calculus for tensor categories. To this quantum question and answer setting, we extend the standard definitions, including strategies, correlations, and synchronicity, and we use these definitions to extend results about synchronicity. We extend the graph homomorphism (isomorphism) game to quantum graphs, and show it is synchronous (bisynchronous) and connect its perfect (bi)strategies to quantum graph homomorphisms (isomorphisms). Our extended definitions agree with the existing quantum games literature, except in the case of synchronicity.
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗*∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp.~XOR-algebra) yields measurement operators for near-perfect (resp.~near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp.~near-optimal XOR) quantum strategy is close to a near-perfect (resp.~near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗*∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.
We establish approximate rigidity results for several well-known families of nonlocal games. In particular, we show that near-perfect quantum strategies for boolean constraint system (BCS) games are approximate representations of the corresponding BCS algebra. Likewise, for the class of XOR nonlocal games, we show that near-optimal quantum strategies are approximate representations of the corresponding ∗-algebra associated with optimal quantum values for the game. In both cases, the approximate representations are with respect to the normalized Hilbert-Schmidt norm and independent of the Hilbert space or quantum state employed in the strategy. We also show that approximate representation of the BCS (resp. XOR-algebra) yields measurement operators for near-perfect (resp. near-optimal) quantum strategies where the players employ a maximally entangled state in the game. As a corollary, every near-perfect BCS (resp. near-optimal XOR) quantum strategy is close to a near-perfect (resp. near-optimal) quantum strategy using a maximally entangled state. Lastly, we establish that every synchronous algebra is ∗-isomorphic to a certain BCS algebra called the SynchBCS algebra. This allows us to apply our BCS rigidity results to the class of synchronous games as well.
We construct a linear system nonlocal game which can be played perfectly using a limit of finite-dimensional quantum strategies, but which cannot be played perfectly on any finite-dimensional Hilbert space, or even with any tensor-product strategy. In particular, this shows that the set of (tensor-product) quantum correlations is not closed. The constructed nonlocal game provides another counterexample to the ‘middle’ Tsirelson problem, with a shorter proof than our previous paper (though at the loss of the universal embedding theorem). We also show that it is undecidable to determine if a linear system game can be played perfectly with a finite-dimensional strategy, or a limit of finite-dimensional quantum strategies.
The study of quantum correlation sets initiated by Tsirelson in the 1980s and originally motivated by questions in the foundations of quantum mechanics has more recently been tied to questions in quantum cryptography, complexity theory, operator space theory, group theory, and more. Synchronous correlation sets introduced by Paulsen et al. [J. Funct. Anal. 270, 2188–2222 (2016)] are a subclass of correlations that has proven particularly useful to study and arises naturally in applications. We show that any correlation that is almost synchronous, in a natural ℓ1 sense, arises from a state and measurement operators that are well-approximated by a convex combination of projective measurements on a maximally entangled state. This extends a result of Paulsen et al. [J. Funct. Anal. 270, 2188–2222 (2016)] that applies to exactly synchronous correlations. Crucially, the quality of approximation is independent of the dimension of the Hilbert spaces or of the size of the correlation. Our result allows one to reduce the analysis of many classes of nonlocal games, including rigidity properties, to the case of strategies using maximally entangled states that are generally easier to manipulate.