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

Lower Bounds on the Communication Complexity of Binary Local Quantum Measurement Simulation

Adrian Kosowski, Markiewicz, Marcin

Published Oct 8, 2013• 0 citations
arXivHTMLPDF

Abstract

We consider the problem of the classical simulation of quantum measurements in the scenario of communication complexity. Regev and Toner (2007) have presented a 2-bit protocol which simulates one particular correlation function arising from binary projective quantum measurements on arbitrary state, and in particular does not preserve local averages. The question of simulating other correlation functions using a protocol with bounded communication, or preserving local averages, has been posed as an open one. Within this paper we resolve it in the negative: we show that any such protocol must have unbounded communication for some subset of executions. In particular, we show that for any protocol, there exist inputs for which the random variable describing the number of communicated bits has arbitrarily large variance.

DOI
10.48550/arxiv.1310.2217

Related papers

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•0 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•82 citations

Bounding Two-Way Average Communication Cost of Simulating Quantum Correlations

Kai-Siang Chen, Gelo Noel M. Tabia, Bo-An Tsai +2 more

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.

quant-pharXiv:2610.04648•Oct 6, 2026•0 citations

Lower bound on the communication cost of simulating bipartite quantum correlations

Tamás Vértesi, Erika Bene

Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.

arXiv:0904.1390•Physical Review A•Dec 8, 2009•15 citations

Classical Cost of Transmitting a Qubit

Martin J. Renner, Armin Tavakoli, Marco Túlio Quintino

We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation. In addition, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state.

arXiv:2207.02244•Physical Review Letters•Mar 22, 2023•16 citations

The communication cost of simulating POVMs over maximally entangled qubits

Ricard Ravell Rodríguez

In [Toner and Bacon, Phys. Rev. Lett. 91, 187904 (2003)], $1$ bit of communication was proven to be enough to simulate the statistics of local projective measurements over the maximally entangled state. Ever since then, the question of whether $1$ bit is also enough for the case of generalized measurements has been open. In this thesis, we retort to inefficiency-resistant Bell functionals, a powerful technique to prove lower bounds communication complexity, to numerically study this question. The results obtained suggest that, indeed, as is the case with projective measurements, $1$ bit of communication suffices to simulate POVMs over maximally entangled qubits.

•Sep 9, 2019•0 citations
We consider the problem of the classical simulation of quantum measurements in the scenario of communication complexity. Regev and Toner (2007) have presented a 2-bit protocol which simulates one particular correlation function arising from binary projective quantum measurements on arbitrary state, and in particular does not preserve local averages. The question of simulating other correlation functions using a protocol with bounded communication, or preserving local averages, has been posed as an open one. Within this paper we resolve it in the negative: we show that any such protocol must have unbounded communication for some subset of executions. In particular, we show that for any protocol, there exist inputs for which the random variable describing the number of communicated bits has arbitrarily large variance.
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.
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.
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.
Suppose Alice and Bob share a maximally entangled state of any finite dimension and each perform two-outcome measurements on the respective part of the state. It is known, due to the recent result of Regev and Toner, that if a classical model is augmented with two bits of communication, then all the quantum correlations arising from these measurements can be reproduced. Here, we show that two bits of communication are in fact necessary for the perfect simulation. In particular, we prove that a pair of maximally entangled four-dimensional quantum systems cannot be simulated by a classical model augmented by only one bit of communication.
We consider general prepare-and-measure scenarios in which Alice can transmit qubit states to Bob, who can perform general measurements in the form of positive operator-valued measures (POVMs). We show that the statistics obtained in any such quantum protocol can be simulated by the purely classical means of shared randomness and two bits of communication. Furthermore, we prove that two bits of communication is the minimal cost of a perfect classical simulation. In addition, we apply our methods to Bell scenarios, which extends the well-known Toner and Bacon protocol. In particular, two bits of communication are enough to simulate all quantum correlations associated to arbitrary local POVMs applied to any entangled two-qubit state.
In [Toner and Bacon, Phys. Rev. Lett. 91, 187904 (2003)], 111 bit of communication was proven to be enough to simulate the statistics of local projective measurements over the maximally entangled state. Ever since then, the question of whether 111 bit is also enough for the case of generalized measurements has been open. In this thesis, we retort to inefficiency-resistant Bell functionals, a powerful technique to prove lower bounds communication complexity, to numerically study this question. The results obtained suggest that, indeed, as is the case with projective measurements, 111 bit of communication suffices to simulate POVMs over maximally entangled qubits.