Bisynchronous Games and Factorizable Maps

Mizanur Rahaman; Vern I. Paulsen

REVIEW 2 major objections 5 minor 20 references

Bisynchronous Games and Factorizable Maps

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Bisynchronous correlations are trace-form densities on the quantum permutation group.

desk verdict Bisynchronous correlations give a clean trace representation on the quantum permutation group; the core theorems hold, but the abstract's blanket CP/factorizability claim is false as stated. read the letter →

arxiv 1908.03842 v2 pith:Y7G2WRB7 submitted 2019-08-11 quant-ph math.FAmath.OA

Vern I. Paulsen , Mizanur Rahaman This is my paper · ORCID

classification quant-phmath.FAmath.OA MSC 46L1046L3005C6081P45

keywords bisynchronousgamescorrelationssynchronousquantumpermutationgroupmagicunitaryfactorizablemapsgraphisomorphismgametracialstates

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Bisynchronous games are non-local games in which matching questions force matching answers and distinct questions force distinct answers. The paper proves that when the number of questions equals the number of answers, every bisynchronous correlation $p(a,b|x,y)$ is exactly the trace of a product of two entries of a quantum permutation: $p(a,b|x,y)=\tau(u_{x,a}u_{y,b})$ for a tracial state on the quantum permutation group $O(S_n^+)$. It further shows that the completely positive map naturally attached to such a density is factorizable, meaning it can be implemented by a quantum-permutation unitary and an ancilla trace. A sympathetic reader should care because this identifies a clean algebraic object—traces on $O(S_n^+)$—as the carrier of an entire family of correlation densities, and because the same mechanism connects graph isomorphism games to factorizable channels.

What carries the argument

The load-bearing object is the bisynchronous density, equivalently the relations $p(a,b|x,x)=0$ for $a\neq b$ and $p(a,a|x,y)=0$ for $x\neq y$ imposed on a conditional probability density, and the corresponding game-algebra relations $e_{x,a}e_{y,a}=0$ for $x\neq y$. When $|I|=|O|=n$, these relations combine with the synchronous relations to make the projections $\{e_{x,a}\}$ satisfy $\sum_a e_{x,a}=1$ and $\sum_x e_{x,a}=1$, i.e. to form a magic permutation, also called a quantum permutation: a square matrix of projections whose rows and columns each sum to the identity. The quantum permutation group $O(S_n^+)$ is the universal $C^*$-algebra generated by such entries, and the paper's central identity is $p(a,b|x,y)=\tau(u_{x,a}u_{y,b})$, which turns a trace on $O(S_n^+)$ into a bisynchronous correlation and, via $\Phi_p$, into a factorizable map with ancilla $N$: $\Phi_p(X)=\mathrm{id}\otimes\tau_N(u^*(X\otimes 1_N)u)$.

What would settle it

Find a bisynchronous density in $C^{bs}_{qc}(3,3)$ whose entries cannot be written as $\tau(u_{x,a}u_{y,b})$ for any tracial state on $O(S_3^+)$; since the set of such trace evaluations is convex and semidefinite-representable, a concrete counterexample would be a finite matrix violating the feasibility problem. Alternatively, exhibit a local bisynchronous density whose associated map is not a mixed permutation map; Theorem 4.2 predicts no such density exists.

Watch

Extended reading notes

Core claim

The paper's central discovery is that bisynchronicity, in the square case $n=k$, forces the projections of a game's $*$-algebra to assemble into a magic permutation, and every trace on the quantum permutation group produced this way yields a bisynchronous density. Theorem 2.2 states the precise equivalence: $p\in C^{bs}_{qc}(n,n)$ iff $p(a,b|x,y)=\tau(u_{x,a}u_{y,b})$ for a tracial state on $O(S_n^+)$, with parallel characterizations for qa, q, loc, and vectorial correlations using representations of $O(S_n^+)$ into an ultrapower of the hyperfinite II$_1$-factor, a finite-dimensional algebra, an abelian algebra, and a Hilbert space. Theorem 4.1 extends this to maps: for $t\in\{\mathrm{loc},\mathrm{q},\mathrm{qa},\mathrm{qc}\}$, a bisynchronous density in $C^{bs}_t(n,n)$ is exactly one whose associated completely positive map $\Phi_p(E_{x,y})=\sum_{a,b}p(a,b|x,y)E_{a,b}$ is $t$-factorizable via a quantum permutation. The proof mechanism is the trace formula itself, which converts multiplicativity of the density into an ancilla implementation of the channel.

Load-bearing premise

The characterization inherits previously established characterizations of synchronous correlations—the proof leans on those results for qc, qa, q, loc, and vectorial correlations—and on the known equivalence between graph isomorphism and existence of a quantum t-permutation; if any of those prior results is incomplete, the bisynchronous theorems built on them collapse.

Editorial extensions

If this is right

When $n=k$, bisynchronous games with perfect quantum-commuting strategies are exactly those whose densities are trace evaluations on the quantum permutation group, so the theory of such games is a chapter of the theory of $O(S_n^+)$.
For $t\in\{\mathrm{loc},\mathrm{q},\mathrm{qa},\mathrm{qc}\}$, the classes of bisynchronous densities and of $t$-factorizable maps via quantum permutations coincide; in particular, local bisynchronous correlations correspond exactly to mixed permutation maps.
Graph isomorphism $G\sim_t H$ holds if and only if there is a quantum $t$-permutation intertwining the adjacency matrices, and equivalently if and only if there is a $t$-factorizable map $\Phi$ with $\Phi(A_G)=A_H$ and $\Phi^*(A_H)=A_G$.
The fixed-point algebra of the channel $\Phi_p$ equals the commutant of any representing quantum permutation, and this fixed-point algebra is closed under the Schur product.
The flip of a bisynchronous density is again bisynchronous for $t\in\{\mathrm{loc},\mathrm{q},\mathrm{qa},\mathrm{qc},\mathrm{vect}\}$, so the transpose density belongs to the same correlation class.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

One testable extension is the rectangular case $|I|\neq|O|$: the paper's counting argument gives only the necessary condition $n\le k$ for a perfect $C^*$-strategy, and the trace characterization likely needs a non-square quantum-permutation analogue; constructing such an analogue would generalize Theorem 2.2.
The paper's Slofstra-type example suggests a route to factorizable maps that genuinely require infinite-dimensional ancilla: use a graph-isomorphism density that is qa but not q, and check whether the factorizable map it defines admits any finite-dimensional factorization, not just one with quantum-permutation unitary.
Because every synchronous game can be transformed into a bisynchronous game by making players return the question, any structural result for bisynchronous games automatically transfers back to synchronous games whenever the construction preserves the relevant parameters; the obstacle in the paper is that this transform doubles the output set, so the square equality $n=k$ is lost.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Chris,

You asked about the Paulsen–Rahaman bisynchronous games paper. Here is my take.

The genuinely new piece is the bisynchronous condition. Requiring same inputs to force same outputs and different inputs to force different outputs is a natural restriction on synchronous correlations, and it pays off: when n=k, the game algebra becomes a quantum permutation group, and Theorem 2.2 gives trace representations for qc, qa, q, loc, and vect bisynchronous correlations. The qc proof is clean: invoke the [19] synchronous trace theorem, use the bisynchronous condition to annihilate off-diagonal column products, and the GNS representation gives a magic unitary. The vectorial case has a nice column-sum argument. Theorem 4.1 showing that these correlations are t-factorizable via quantum permutations, and conversely, is the other main contribution. The flip game, the orbital algebra section, and the open problems are thoughtful extras.

Now the soft spots. First, the abstract overclaims: it states that every bisynchronous density gives a completely positive map and that these maps are factorizable. That is not true as written. Remark 3.3 produces a bisynchronous nonsignalling density whose Phi_p is not positive, and factorizable maps in this paper are defined only for square maps. The body is careful—Theorem 4.1 restricts to t in {loc,q,qa,qc} and n=k—so it is a writing bug, but a serious one for citation.

Second, the proof architecture leans heavily on prior synchronous characterizations: [19] for qc, [10] for qa/q/loc, [14,15] for vect, and [2, Theorem 4.9] for the graph isomorphism equivalence. Many of those results come from the same community and are not reproved. That is a dependency risk, not circularity. A referee should verify that the cited theorems have no hidden hypotheses. I do not see evidence of a flaw, but the paper is not self-contained.

Third, the converse direction in Theorem 4.1 depends on identifying the map from its matrix units and comparing with the trace formula; that works. Theorem 4.3 imports the quantum t-permutation characterization of graph isomorphism, so it inherits that theorem's standing.

Overall, this is a solid and useful paper. The core math holds up under standard cited results. Fix the abstract, spell out the hypotheses in the body, and it is a good contribution. I would send it to a serious referee. If I worked on synchronous games or factorizable maps, I would cite it.

Best.

Referee Report

2 major / 5 minor

Summary. The paper introduces a new class of synchronous non-local games and correlations, called bisynchronous, which require equal outputs for equal inputs and different outputs for different inputs. For the case of equal numbers of inputs and outputs, the authors prove a characterization: a bisynchronous correlation in C_bs_t(n,n) for t in {qc,qa,q,loc,vect} is of the form p(a,b|x,y) = τ(u_{x,a}u_{y,b}) for a suitable trace and quantum permutation. They then associate to each square bisynchronous density a completely positive map Φ_p and show, for t in {loc,q,qa,qc}, that Φ_p is t-factorizable via a quantum permutation; conversely, every such factorizable map gives a bisynchronous correlation. The paper also connects these maps to the graph isomorphism game, shows that local bisynchronous maps are exactly the mixed permutation maps, and analyzes the fixed-point algebra of Φ_p in terms of the commutant of the quantum permutation.

Significance. The paper's main contribution is an explicit bridge between bisynchronous correlations and traces on the quantum permutation group, extending the existing theory of synchronous correlations. The factorizability result for the associated completely positive maps is a strong structural property with potential applications in quantum information and operator algebras. The central proofs in Theorems 2.2 and 4.1 are coherent: the GNS faithfulness argument, the column-sum computation, and the factorization formula are all checkable and appear correct. The paper also honestly discusses limitations, for example in Remark 4.4. The main reservations are that the abstract overstates the hypotheses of the main theorem and that one step in the graph-isomorphism characterization (Theorem 4.3) is too terse and needs a missing argument.

major comments (2)

[Abstract and Section 1, first paragraph] The statement 'Each bisynchronous density gives rise to a completely positive map and we prove that these maps are factorizable maps' is false as written. Remark 3.3 provides a bisynchronous nonsignalling density on 3 inputs and 3 outputs for which Φ_p is not even positive, and factorizable maps are only defined in the paper for square maps (n=k). Theorem 4.1 correctly restricts to t in {loc,q,qa,qc} and n=k. Please revise the abstract and the introductory sentence to state the precise hypotheses under which the factorizability result holds.
[Theorem 4.3, proof of (3 ⇒ 1)] After deriving the vanishing conditions from Φ(A_G)=A_H and Φ*(A_H)=A_G, the proof immediately concludes 'Hence 1 follows.' It does not explicitly show that these conditions imply the intertwining relation (A_G⊗1)u = u(A_H⊗1) from part (2), nor does it explain how the full graph-isomorphism-game conditions, including inputs from V(H) and cross-graph pairs, are recovered. The missing step is non-trivial: one must pass from τ(e_{x,a}e_{y,b})=0 on edge/non-edge mismatches to the operator equality using the row and column sums of the quantum permutation. Please expand this part of the proof.

minor comments (5)

[Proof of Theorem 2.2] The symbol F(n,n) for the free product of n copies of the cyclic group of order n is used but never defined. Please add a definition or a reference.
[Proof of Theorem 4.3] In the display computing Φ(1), the expression '∑_{x∼y} ∑_{a≠b}' appears to be a typo: the first sum should be over x, not over x∼y.
[Corollary 4.7] The notation 'p ∈ C_b_qc(n,n)' should be 'p ∈ C_bs_qc(n,n)' for consistency with the rest of the paper.
[Proof of Theorem 4.5] The notation is confusing because 'e_{x,y}' is used both for the matrix entries of the quantum permutation and for matrix units. Please disambiguate these uses.
[Throughout] There are several typographical errors, including 'Anatharaman-Delaroche' for 'Anantharaman-Delaroche' and 'Neuamnn' in the proof of Theorem 4.1. A careful proofreading pass is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the bisynchronous trace and factorizability theorems are derived from prior synchronous characterizations, not assumed.

full rationale

The central derivation (Theorem 2.2(1)) is not circular. The paper starts with p in C^bs_qc(n,n), invokes the prior synchronous trace representation from [19] only to obtain p(a,b|x,y)=tau(e_{x,a}e_{y,b}) on C*(F(n,n)); the bisynchronous assumption is then used to prove tau((e_{y,a}e_{x,a})*(e_{x,a}e_{y,a}))=0, and the GNS faithfulness forces u_{x,a}u_{y,a}=0. That is exactly what converts the row-sum relation into a magic permutation and yields the quotient of O(S_n^+). The converse is a direct check. The qa/q/loc analogs inherit the synchronous characterizations of [10], and the vectorial case inherits [14,15]; all are external, parameter-free published theorems whose assumptions do not contain the bisynchronous conclusion, so by the stated independence rule they do not create circularity. Theorem 4.1 is a computation from Theorem 2.2 in one direction and a comparison of matrix coefficients in the other; it introduces no fitted quantity. Theorem 4.3 imports [2, Theorem 4.9] for the graph-isomorphism equivalence and then proves the operator-system implications itself. No equation in the paper reduces to its input by construction, and no fitted parameter is renamed as a prediction. The only flagged issue is a scope/correctness caveat, not circularity: the abstract's unconditional sentence 'Each bisynchronous density ... factorizable' is contradicted by Remark 3.3, where a bisynchronous nonsignalling density gives a non-positive Phi_p; Theorem 4.1 states the correct restriction t in {loc,q,qa,qc} with n=k. Open problems in Section 5 are honest limitations and do not affect the circularity assessment.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper introduces no fitted constants. The central claims rest on previously published characterizations of synchronous correlations and on standard factorizable map theory, all cited. The main new content is the definition of bisynchronous correlations and the observation that with n=k they force quantum permutation structure.

assumptions (5)

domain assumption Every synchronous qc correlation p in C^s_qc(n,k) is represented as p(a,b|x,y)=tau(e_{x,a}e_{y,b}) for a trace tau on C*(F(n,k)).
Invoked in the first line of the proof of Theorem 2.2; the bisynchronous characterization inherits this external theorem from [19].
domain assumption Synchronous qa, q, and loc correlations admit the algebraic representations from Kim-Paulsen-Schafhauser [10] used in Theorem 2.2(2)-(4).
The paper says the proofs are similar and cites [10]; no derivation is repeated, so the result rests on those characterizations.
domain assumption Vectorial synchronous correlations have the representation from [14] and [15] with vectors h_{x,a} satisfying row orthogonality and common sum h.
Used in the proof of Theorem 2.2(5) to show that a bisynchronous vector correlation is a vector permutation.
domain assumption Factorizable maps and their ancillas satisfy the Haagerup-Musat decomposition u = sum_i K_i tensor v_i for Kraus operators K_i of the channel.
Used in Theorem 4.5 to prove that fixed points of Phi_p commute with the implementing quantum permutation.
domain assumption G ~_t H holds if and only if there exists a quantum t-permutation intertwining the adjacency matrices (cited from [2, Theorem 4.9]).
Used without proof as the first equivalence in Theorem 4.3; the rest of the theorem is built on this premise.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bisynchronous Games and Factorizable Maps." pith.science (2026). https://pith.science/paper/Y7G2WRB7

@misc{pith2026190803842,
  author       = {Pith},
  title        = {Pith review of: Bisynchronous Games and Factorizable Maps},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y7G2WRB7}},
  note         = {Machine review of arXiv:1908.03842}
}

read the original abstract

We introduce a new class of non-local games, and corresponding densities, which we call bisynchronous. Bisynchronous games are a subclass of synchronous games and exhibit many interesting symmetries when the algebra of the game is considered. We develop a close connection between these non-local games and the theory of quantum groups which recently surfaced in studies of graph isomorphism games. When the number of inputs is equal to the number of outputs, we prove that a bisynchronous density arises from a trace on the quantum permutation group. Each bisynchronous density gives rise to a completely positive map and we prove that these maps are factorizable maps.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages

[19]

P aulsen, S

V. P aulsen, S. Severini, D. Stahlke, I. Todorov and A. Winter , Estimating quantum chromatic numbers , Journal of Functional Analysis, VOL 270, 2016, DOI = 10.1016/j.jfa.2016.01.010

work page doi:10.1016/j.jfa.2016.01.010 2016
[10]

S.-J. Kim; V. P aulsen and C. Schafhauser , A synchronous game for bi- nary constraint systems , Journal of Mathematical Physics 59, 032201 (2018); doi: 10.1063/1.4996867

work page doi:10.1063/1.4996867 2018
[1]

Atserias; L

A. Atserias; L. Man ˇcinska; D.E. Roberson; R. ˇS´amal; S. Severini and A. V arvitsiotis, Quantum and non-signalling graph isomorphisms , Journal of Combi- natorial Theory, Series B, Volume 136, 2019, Pages 289-328, ISSN 0095-8956

work page 2019
[2]

Michael Brannan; Alexandru Chirvasitu; Kari Eifler; Samue l Harris; Vern P aulsen; Xiaoyu Su and Mateusz W asilewski , Bigalois extensions and the graph isomorphism game , arXiv:1812.11474

work page Pith review arXiv
[3]

Anantharaman-Delaroche , On ergodic theorems for free group actions on non- commutative spaces, Probab

C. Anantharaman-Delaroche , On ergodic theorems for free group actions on non- commutative spaces, Probab. Theory Rel. Fields 135 (2006), 520-546

work page 2006
[4]

Dykema and V

K. Dykema and V. P aulsen , Synchronous correlation matrices and Connes’ em- bedding conjecture, Journal of Mathematical Physics 57 (2016), no. 1, 015214, 1 2 pp

work page 2016
[5]

Haagerup and M

U. Haagerup and M. Musat , Factorization and Dilation Problems for Completely Positive Maps on von Neumann Algebras , Comm. Math. Phys. (2011), vol. 303, 555– 594

work page 2011
[6]

Haagerup and M

U. Haagerup and M. Musat , An Asymptotic Property of Factorizable Completely Positive Maps and the Connes Embedding Problem , Comm. Math. Phys. (2015), vol. 338, 721–752

work page 2015

Show all 20 references

[7]

Z. Ji, A. Natarajan, T. Vidick, J. Wright and H. Yuen , MIP*=RE, 2020, arXiv e-prints , arXiv:2001.04383. 22 V. I. PAULSEN AND M. RAHAMAN

2020 arXiv
[8]

Helton; K.P

J.W. Helton; K.P. Meyer; V. P aulsen and M. Satriano , Algebras, synchronous games and chromatic numbers of graphs , New York Journal of Mathematics, Volume 25 (2019), 328-361

2019
[9]

W Kribs , Quantum channels, wavelets, dilations and representation s of On, Proc

D. W Kribs , Quantum channels, wavelets, dilations and representation s of On, Proc. Edinb. Math. Soc. (2), 46, 2003, 2, 421–433

2003
[11]

Lupini, L

M. Lupini, L. Man ˇcinska, and D.E Roberson Nonlocal Games and Quantum Permutation Groups , 2017, arXiv:1712.01820

2017 arXiv
[12]

Manˇcinska; D

L. Manˇcinska; D. E. Roberson; R. ˇS´amal; S. Severini and A. V arvitsiotis, Re- laxations of Graph Isomorphism , http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.76

2017 doi
[13]

Musat and M

M. Musat and M. Rørdam , Non-closure of quantum correlation matrices and fac- torizable channels that require inﬁnite dimensional ancil la, Communications in Math- ematical Physics (2019), https://doi.org/10.1007/s0022 0-019-03449-w

2019 doi
[14]

Navascu ´es, Y

M. Navascu ´es, Y. Guryanova, M. J. Hoban, and A. Ac ´ın, Almost quantum correlations, Nat.Commun.6(2015), 6288

2015
[15]

Navascu´es, S

M. Navascu´es, S. Pironio, and A. Ac ´ın, A convergent hierarchy of semideﬁnite programs characterizing the set of quantum correlations New J. Phys.10(2008), no. 7, 073013

2008
[16]

Ortiz and V

C. Ortiz and V. P aulsen , Quantum Graph Homomorphisms via Operator Systems , Linear Alg. and Appl., Vol 497, 15 May 2016, 23-43, doi: 10.10 16/j.laa2016.02.019

2016
[17]

Ozaw a, About the Connes embedding conjecture , Japanese Journal of Mathemat- ics, volume 8, number 1, 2013

N. Ozaw a, About the Connes embedding conjecture , Japanese Journal of Mathemat- ics, volume 8, number 1, 2013

2013
[18]

Harris and Satish K

Vern P aulsen, Entanglement and non-locality , unpublished lecture notes written by Samuel J. Harris and Satish K. Pandey, Winter 2016

2016
[20]

Slofstra , The set of quantum correlations is not closed , Forum of Mathematics, Pi, v.7, (2019), E1, 41 pp

W. Slofstra , The set of quantum correlations is not closed , Forum of Mathematics, Pi, v.7, (2019), E1, 41 pp. Institute for Quantum Computing and Department of Pure Math ematics, University of W aterloo, W aterloo, ON, Canada N2L 3G1 Email address : vpaulsen@uwaterloo.ca Dep...

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [19]

P aulsen, S

V. P aulsen, S. Severini, D. Stahlke, I. Todorov and A. Winter , Estimating quantum chromatic numbers , Journal of Functional Analysis, VOL 270, 2016, DOI = 10.1016/j.jfa.2016.01.010

work page doi:10.1016/j.jfa.2016.01.010 2016

[2] [10]

S.-J. Kim; V. P aulsen and C. Schafhauser , A synchronous game for bi- nary constraint systems , Journal of Mathematical Physics 59, 032201 (2018); doi: 10.1063/1.4996867

work page doi:10.1063/1.4996867 2018

[3] [1]

Atserias; L

A. Atserias; L. Man ˇcinska; D.E. Roberson; R. ˇS´amal; S. Severini and A. V arvitsiotis, Quantum and non-signalling graph isomorphisms , Journal of Combi- natorial Theory, Series B, Volume 136, 2019, Pages 289-328, ISSN 0095-8956

work page 2019

[4] [2]

Michael Brannan; Alexandru Chirvasitu; Kari Eifler; Samue l Harris; Vern P aulsen; Xiaoyu Su and Mateusz W asilewski , Bigalois extensions and the graph isomorphism game , arXiv:1812.11474

work page Pith review arXiv

[5] [3]

Anantharaman-Delaroche , On ergodic theorems for free group actions on non- commutative spaces, Probab

C. Anantharaman-Delaroche , On ergodic theorems for free group actions on non- commutative spaces, Probab. Theory Rel. Fields 135 (2006), 520-546

work page 2006

[6] [4]

Dykema and V

K. Dykema and V. P aulsen , Synchronous correlation matrices and Connes’ em- bedding conjecture, Journal of Mathematical Physics 57 (2016), no. 1, 015214, 1 2 pp

work page 2016

[7] [5]

Haagerup and M

U. Haagerup and M. Musat , Factorization and Dilation Problems for Completely Positive Maps on von Neumann Algebras , Comm. Math. Phys. (2011), vol. 303, 555– 594

work page 2011

[8] [6]

Haagerup and M

U. Haagerup and M. Musat , An Asymptotic Property of Factorizable Completely Positive Maps and the Connes Embedding Problem , Comm. Math. Phys. (2015), vol. 338, 721–752

work page 2015