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: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

quant-phSubmitted Oct 3, 2026• Announced Oct 6, 2026• 0 citations
arXivHTMLPDF

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.

Little sign of AI-generated textAI use disclosed
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!

Related papers

Violations of Bell inequalities as lower bounds on the communication cost of nonlocal correlations

Stefano Pironio

To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension $d>~3$ where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.

arXiv:quant-ph/0304176•Physical Review A•Dec 4, 2003•70 citations

The cost of classically simulating quantum communication is as high as it could be

Riccardo Castellano, Pavel Sekatski, Nicolas Brunner

A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary $d$-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for $d\geq 4$, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.

quant-pharXiv:2610.19060•Oct 15, 2026•1 citation

Tensor norms and the classical communication complexity of nonlocal quantum measurement

Yaoyun Shi

Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•4 citations

Classical simulation of quantum entanglement without local hidden variables

Serge Massar, Dave Bacon, Nicolas J. Cerf +1 more

Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario is that a bipartite measurement is given from a set of possibilities and the goal is to find a classical scheme that reproduces exactly the correlations that arise when an actual quantum system is measured. Previous results have shown that, using local hidden variables, a finite amount of communication suffices to simulate the correlations for a Bell state. We extend this in a number of ways. First, we show that, when the communication is merely required to be finite on average, Bell states can be simulated without any local hidden variables. More generally, we show that arbitrary positive operator valued measurements on systems of n Bell states can be simulated with ${O(n2}^{n})$ bits of communication on average (again, without local hidden variables). On the other hand, when the communication is required to be absolutely bounded, we show that a finite number of bits of local hidden variables is insufficient to simulate a Bell state. This latter result is based on an analysis of the nondeterministic communication complexity of the NOT-EQUAL function, which is constant in the quantum model and logarithmic in the classical model.

arXiv:quant-ph/0009088•Physical Review A•Apr 16, 2001•83 citations

Non-local games and communication complexity with noisy entanglement

Srijita Kundu, Olivier Lalonde

We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an $Ω(n)$ two-way communication lower bound for distilling $n$ EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.

quant-pharXiv:2609.05122•Sep 7, 2026•2 citations

Classical Communication Cost of a Bipartite Quantum Channel Assisted by Non-Signaling Correlations

Chengkai Zhu, Xuanqiang Zhao, Xin Wang

Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot $ε$-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.

arXiv:2408.02506•IEEE Transactions on Information Theory•May 9, 2025•1 citation
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 nnn parallel Magic-Square-winning correlations, we prove a lower bound of nlog⁡2(3/2)n\log_2(3/2)nlog2​(3/2) bits and give a one-way communication protocol that attains this rate asymptotically. For the quantum correlation maximally winning the nnn-copy of the Clauser--Horne--Shimony--Holt nonlocal game, we obtain an input-average lower bound of approximately 0.04627n0.04627n0.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.
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 mmm-symbol message is charged log⁡2m\log_2mlog2​m 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/α)\log_2(1/\alpha)log2​(1/α), 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 ∑iΦωc(wi)\sum_i\Phi_{\omega_c}(w_i)∑i​Φωc​​(wi​), where wiw_iwi​ is the marginal winning probability, ωc\omega_cωc​ the classical value, and Φωc(w)=Dbin(w∥ωc)\Phi_{\omega_c}(w)=D_{\mathrm{bin}}(w\|\omega_c)Φωc​​(w)=Dbin​(w∥ωc​) above the classical value and zero otherwise.
For nnn Magic Square correlations, the lower bound is nlog⁡2(3/2)≈0.584963nn\log_2(3/2)\approx0.584963nnlog2​(3/2)≈0.584963n bits. A one-way covering construction, combined with shared-random output relabeling, achieves this plus O(log⁡n)O(\log n)O(logn), determining the asymptotic rate for both average and worst-case costs, with or without interaction. For nnn product Tsirelson CHSH correlations, the two-way average-cost lower bound is approximately 0.04627385n0.04627385n0.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.
To reproduce in a local hidden variables theory correlations that violate Bell inequalities, communication must occur between the parties. We show that the amount of violation of a Bell inequality imposes a lower bound on the average communication needed to produce these correlations. Moreover, for every probability distribution there exists an optimal inequality for which the degree of violation gives the minimal average communication. As an example, to produce using classical resources the correlations that maximally violate the Clauser-Horne-Shimony-Holt inequality, $\sqrt{2}\ensuremath{-}1\ensuremath{\simeq}0.4142$ bits of communication are necessary and sufficient. For Bell tests performed on two entangled states of dimension d> 3d>~3d> 3 where each party has the choice between two measurements, our results suggest that more communication is needed to simulate outcomes obtained from certain nonmaximally entangled states than maximally entangled ones.
A long-standing open question is to characterize the classical communication cost of simulating the correlations arising from measurements on finite-dimensional quantum systems. We consider this question in the prepare-and-measure scenario. First we construct a classical simulation model involving a finite average number of bits of one-way communication that simulates exactly the correlations arising from arbitrary ddd-dimensional quantum states and arbitrary measurements. Second, we show that no classical simulation protocol involving a finite average message dimension can exist for d≥4d\geq 4d≥4, hence strengthening a recent result of de Gois, Santos and Vieira. Our first result relies on a more general simulation theorem which can be applied to certain continuous variable (i.e. infinite-dimensional) quantum systems, and even beyond quantum theory, e.g. to generalized probabilistic theories. In particular, we show that multimode Gaussian states of bounded average energy and general Gaussian measurements admit an exact classical simulation with a finite expected number of bits. Overall, our results show that the classical simulation cost of quantum communication is essentially as high as it could be.
Nonlocality is at the heart of quantum information processing. In this paper we investigate the minimum amount of classical communication required to simulate a nonlocal quantum measurement. We derive general upper bounds, which in turn translate to systematic classical simulations of quantum communication protocols.As a concrete application, we prove that any quantum communication protocol with shared entanglement for computing a Boolean function can be simulated by a classical protocol whose cost does not depend on the amount of the shared entanglement. This implies that if the cost of communication is a constant, quantum and classical protocols, with shared entanglement and shared coins, respectively, compute the same class of functions.Furthermore, we describe a new class of efficient quantum communication protocols based on fast quantum algorithms. While some of them have efficient classical simulations by our method, others appear to be good candidates for separating quantum v.s. classical protocols, and quantum protocols with v.s. without shared entanglement.Yet another application is in the context of simulating quantum correlations using local hidden variable models augmented with classical communications. We give a constant cost, approximate simulation of quantum correlations when the number of correlated variables is a constant, while the dimension of the entanglement and the number of possible measurements can be arbitrary.Our upper bounds are expressed in terms of some tensor norms on the measurement operator. Those norms capture the nonlocality of bipartite operators in their own way and may be of independent interest and further applications.
Recent work has extended Bell's theorem by quantifying the amount of communication required to simulate entangled quantum systems with classical information. The general scenario is that a bipartite measurement is given from a set of possibilities and the goal is to find a classical scheme that reproduces exactly the correlations that arise when an actual quantum system is measured. Previous results have shown that, using local hidden variables, a finite amount of communication suffices to simulate the correlations for a Bell state. We extend this in a number of ways. First, we show that, when the communication is merely required to be finite on average, Bell states can be simulated without any local hidden variables. More generally, we show that arbitrary positive operator valued measurements on systems of n Bell states can be simulated with O(n2n){O(n2}^{n})O(n2n) bits of communication on average (again, without local hidden variables). On the other hand, when the communication is required to be absolutely bounded, we show that a finite number of bits of local hidden variables is insufficient to simulate a Bell state. This latter result is based on an analysis of the nondeterministic communication complexity of the NOT-EQUAL function, which is constant in the quantum model and logarithmic in the classical model.
We study the impact of noise on the theories of quantum nonlocality and entanglement-assisted communication complexity. We consider non-local games and entanglement-assisted communication complexity in a model where Alice and Bob may share arbitrarily many noisy EPR pairs. We study four noise models: depolarizing noise, unital noise, biased reset noise, and erasure noise. Our results are as follows: 1. We upper bound the value of the CHSH game under all these noise models in terms of the noise parameter, without any assumptions on the measurements used in the strategy. 2. We prove a parallel repetition theorem for general non-local games under all noise models except biased reset noise; we prove an improved parallel repetition theorem for unique games. Our parallel repetition rate is smaller than the quantum parallel repetition rate for CHSH in a nontrivial noise regime. 3. Using our unique-game parallel repetition theorem and a relation defined by the CHSH game, we prove a separation between communication complexity with noisy vs noiseless entanglement. This implies an Ω(n)Ω(n)Ω(n) two-way communication lower bound for distilling nnn EPR pairs from noisy EPR pairs, in the same nontrivial noise regime. 4. We show that any interactive entanglement-assisted communication protocol can be simulated by an SMP communication protocol with noisy shared randomness, with an exponential blowup in communication. This generalizes a known result on the simulation of noiseless shared randomness with noisy shared randomness. 5. We show a polynomial lower bound on the number of copies of noisy EPR pairs required to compute the Equality function with constant communication, under all four noise models. The previous result gives a matching upper bound, and moreover, this answers an open question in the literature on whether logarithmically many noisy shared bits suffice for communication.
Understanding the classical communication cost of simulating a quantum channel is a fundamental problem in quantum information theory, which becomes even more intriguing when considering the role of non-locality in quantum information processing. This paper investigates the bidirectional classical communication cost of simulating a bipartite quantum channel assisted by non-signalling correlations, which are permitted across the spatial dimension between the two parties. By introducing non-signalling superchannels, we present lower and upper bounds on the one-shot εεε-error one-way classical communication cost of a bipartite channel via its smooth max-relative entropy of one-way classical communication, and establish that the asymptotic exact cost is given by its max-relative entropy of one-way classical communication. For the bidirectional scenario, we derive semidefinite programming (SDP) formulations for the one-shot exact bidirectional classical communication cost via non-signalling bipartite superchannels. We further introduce a channel's bipartite conditional min-entropy as an efficiently computable lower bound on the asymptotic cost of bidirectional classical communication. Our results in both one-shot and asymptotic settings provide lower bounds on the entanglement-assisted simulation cost in scenarios where entanglement is available to the two parties. Moreover, we propose a seesaw-based algorithm to compute an upper bound on the minimum simulation error via local operations and shared entanglement, which provides valuable insights into the relationship between non-signalling bipartite superchannels and more physically realizable protocols. Numerical experiments demonstrate the effectiveness of our bounds in estimating communication costs for various quantum channels, showing that our bounds can be tight in different scenarios.