arXiv:2610.04648
Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations
Kai-Siang Chen, Gelo Noel M. Tabia, Bo-An Tsai, Swati Kumari, Yeong-Cherng Liang
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.
AI Summary
The paper studies the classical communication needed to simulate finite quantum correlations exactly, averaging communication over a specified input distribution and shared randomness while allowing variable-length, fully interactive two-way protocols. An $m$-symbol message is charged $\log_2m$ bits. Two nonlocal-game bounds are developed. For perfect-winning games, the rectangle method and a transcript-entropy bound give cost at least $\log_2(1/\alpha)$, where $\alpha$ is the largest winning-rectangle probability. Multiplicativity of $\alpha$ under parallel repetition yields linear finite-copy bounds. For imperfect winning with independent Alice–Bob inputs, an information-theoretic argument gives cost at least $\sum_i\Phi_{\omega_c}(w_i)$, where $w_i$ is the marginal winning probability, $\omega_c$ the classical value, and $\Phi_{\omega_c}(w)=D_{\mathrm{bin}}(w\|\omega_c)$ above the classical value and zero otherwise. For $n$ Magic Square correlations, the lower bound is $n\log_2(3/2)\approx0.584963n$ bits. A one-way covering construction, combined with shared-random output relabeling, achieves this plus $O(\log n)$, determining the asymptotic rate for both average and worst-case costs, with or without interaction. For $n$ product Tsirelson CHSH correlations, the two-way average-cost lower bound is approximately $0.04627385n$ bits. A complementary LP hierarchy uses deterministic correlations grouped by communication cost, with matching restricted-decomposition upper bounds; both recover the exact cost at their final levels. Numerical examples use only the first level and small scenarios. Finite-copy Magic Square costs remain largely open, hierarchy enumeration becomes expensive, and the explicit parallel constructions grow exponentially in scenario size with the communication budget. Simulation error, detector loss, and finite-statistics certification remain future directions.
The authors used ChatGPT-5.6 Sol and ChatGPT-6 Astra to assist with proof ideas, checks of mathematical arguments, and revisions to the writing.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 10+10 pages, 2 figures, 2 tables; Comments are welcome!