Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

Abstract:Bell nonlocal correlations cannot be reproduced by local hidden-variable models without communication, making classical communication cost a natural quantitative measure of nonlocality. Although finite communication always suffices to simulate any correlation in a fixed finite Bell scenario, determining the minimum amount needed to (exactly) simulate any given nonlocal correlation remains challenging, especially in the average-cost setting. Here, we derive lower bounds on input-average communication cost from nonlocal games, allowing variable-length, fully interactive two-way protocols. When applied to parallel games, these bounds yield explicit finite quantum correlations for which the exact simulation cost exceeds any prescribed finite input-average communication budget. For $n$ parallel Magic-Square-winning correlations, we prove a lower bound of $n\log_2(3/2)$ bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the $n$-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately $0.04627n$ bits for exact simulation. Finally, we formulate a hierarchy of lower bounds and complementary upper bounds using deterministic correlations up to chosen communication costs. Both recover the exact input-average cost at their final levels, and if the bounds agree at lower levels, their common value yields the exact input-average cost without needing to consider all communication strategies.

10+10 pages, 2 figures, 2 tables; Comments are welcome!

arXiv:2610.04648 [quant-ph]

(or arXiv:2610.04648v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.04648 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.