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 nlog2(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.
Related
- Quantifying and Bounding Spatiotemporal Correlations in Quantum Noise
- Bounding Classical and Quantum Correlations in Bayesian Networks with Quasiprobabilities
- The cost of classically simulating quantum communication is as high as it could be
- An Unbounded Separation of Almost-Quantum and Commuting-Operator Correlations in Zero-Error Communication
- Infectious behaviour: Simulating the effects of communication and social influence on pathogen transmission in crowds
BibTeX
@misc{chen2026bounding,
title = {{Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations}},
author = {Kai-Siang Chen and Gelo Noel M. Tabia and Bo-An Tsai and Swati Kumari and Yeong-Cherng Liang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.04648},
eprint = {2610.04648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.04648},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations
AU - Kai-Siang Chen
AU - Gelo Noel M. Tabia
AU - Bo-An Tsai
AU - Swati Kumari
AU - Yeong-Cherng Liang
PY - 2026
DA - 2026/10/03
PB - arXiv
DO - 10.48550/arxiv.2610.04648
UR - https://arxiv.org/abs/2610.04648
AB - 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 nlog_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.
ER -