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:2402.11610 · Physical Review A

Communication cost in simulating unknown entangled states

Kelvin Onggadinata, Paweł Kurzyński, Dagomir Kaszlikowski

Published Sep 24, 2024• 1 citation
arXivHTMLPDF

Abstract

We demonstrate how to universally simulate ensemble statistics of projective local measurements on any $n$-qubit state shared among $n$ observers with classical communication and shared randomness. Our technique originates from protocols designed to simulate quantum nonlocality [in Horizons of the Mind (Springer, Cham, 2014)] and classical simulation of quantum circuits [Phys. Rev. Lett. 115, 070501 (2015)]. The protocol preserves three crucial aspects of the simulated quantum scenario in contrast to other approaches: no involvement of additional parties, none of the observers knows the global state of the system, and local measurement settings remain undisclosed. The simulation cost grows exponentially with the number of observers.

DOI
10.1103/physreva.110.032623

Related papers

Communication cost of simulating entanglement swapping

Nicolas Brunner, Cyril Branciard, Nicolas Gisin +1 more

Entanglement appears in two different ways in quantum mechanics, namely as a property of states and as a property of measurement outcomes in joint measurements. By combining these two aspects of entanglement, it is possible to generate nonlocality between particles that never interacted, using the protocol of entanglement swapping. We investigate the communication cost of classically simulating this process. While the communication cost of simulating nonlocal correlations of entangled states appears to be generally quite low, we show here that infinite communication is required to simulate entanglement swapping. This result is derived in the scenario of bilocality, where distant sources of particles are assumed to be independent, and takes advantage of a previous result of Massar et al. [Phys. Rev. A {\bf 63}, 052305 (2001)]. Our result implies that any classical model simulating entanglement swapping must either assume that (i) infinite shared randomness is available between any two locations in the universe, or that (ii) infinite communication takes place.

arXiv:1103.5058•Mar 25, 2011•0 citations

Bounding the classical cost of simulating quantum behaviors in the prepare-and-measure scenario

Sebastian Schlösser, Matthias Kleinmann

We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of $1.89$ bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only $6$ state preparations and $5$ measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least $5$ classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.

quant-pharXiv:2603.01255•Mar 3, 2026•0 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

Approximate simulation of entanglement with a linear cost of communication

A. Montina

Bell's theorem implies that the outcomes of local measurements on two maximally entangled systems cannot be simulated without classical communication between the parties. The communication cost is finite for $n$ Bell states, but it grows exponentially in $n$. Three simple protocols are presented that provide approximate simulations for low-dimensional entangled systems and require a linearly growing amount of communication. We have tested them by performing some simulations for a family of measurements. The maximal error is less than $1%$ in three dimensions and grows sublinearly with the number of entangled bits in the range numerically tested. One protocol is the multidimensional generalization of the exact Toner-Bacon [Phys. Rev. Lett. 91, 187904 (2003)] model for a single Bell state. The other two protocols are generalizations of an alternative exact model, which we derive from the Kochen-Specker [J. Math. Mech. 17, 59 (1967)] scheme for simulating single-qubit measurements. These protocols can give some indication for finding optimal one-way communication protocols that classically simulate entanglement and quantum channels. Furthermore they can be useful for deciding if a quantum communication protocol provides an advantage on classical protocols.

arXiv:1107.4647•Physical Review A•Oct 5, 2011•8 citations

Unbounded Sharing of Nonlocality Using Qubit Projective Measurements

Satyaki Sasmal, Som Kanjilal, A. K. Pan

The prevailing consensus is that the sequential sharing of nonlocality in a Bell experiment requires generalized unsharp measurements, given that a sharp measurement inevitably destroys the entanglement of the shared state. In contrast, a recent work [A. Steffinlongo and A. Tavakoli, Projective measurements are sufficient for recycling nonlocality, Phys. Rev. Lett. 129, 230402 (2022)PRLTAO0031-900710.1103/PhysRevLett.129.230402] demonstrated the sharing of nonlocality up to two sequential observers by employing projective measurement aided with local randomness. Here, we introduce a form of local randomness-assisted qubit projective measurement protocol that enables the sharing of nonlocality by an arbitrary number of sequential observers (Bobs) with a single spatially separated observer (Alice). We achieve this by inspecting the diversity involved in implementing generalized measurements that harness nonlocality by preserving a sufficient amount of entanglement of the shared two-qubit entangled state. Furthermore, we highlight the crucial interplay between the degrees of measurement incompatibility of Alice and Bob in demonstrating the unbounded sharing of nonlocality.

arXiv:2311.07977•Physical Review Letters•Oct 22, 2024•13 citations

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•5 citations
We demonstrate how to universally simulate ensemble statistics of projective local measurements on any nnn-qubit state shared among nnn observers with classical communication and shared randomness. Our technique originates from protocols designed to simulate quantum nonlocality [in Horizons of the Mind (Springer, Cham, 2014)] and classical simulation of quantum circuits [Phys. Rev. Lett. 115, 070501 (2015)]. The protocol preserves three crucial aspects of the simulated quantum scenario in contrast to other approaches: no involvement of additional parties, none of the observers knows the global state of the system, and local measurement settings remain undisclosed. The simulation cost grows exponentially with the number of observers.
Entanglement appears in two different ways in quantum mechanics, namely as a property of states and as a property of measurement outcomes in joint measurements. By combining these two aspects of entanglement, it is possible to generate nonlocality between particles that never interacted, using the protocol of entanglement swapping. We investigate the communication cost of classically simulating this process. While the communication cost of simulating nonlocal correlations of entangled states appears to be generally quite low, we show here that infinite communication is required to simulate entanglement swapping. This result is derived in the scenario of bilocality, where distant sources of particles are assumed to be independent, and takes advantage of a previous result of Massar et al. [Phys. Rev. A {\bf 63}, 052305 (2001)]. Our result implies that any classical model simulating entanglement swapping must either assume that (i) infinite shared randomness is available between any two locations in the universe, or that (ii) infinite communication takes place.
We study the prepare-and-measure scenario in which Alice transmits a quantum system to Bob, who then performs a quantum measurement. The quantum state of the system is unknown to Bob, and the measurement is unknown to Alice. It has recently been shown that shared randomness and two bits of classical communication are necessary and sufficient to simulate the transmission of a qubit. We show that the communication cost can be reduced to an average of 1.891.891.89 bits. We then study restricted sets of state preparations: First, for a restriction to real-valued qubit states, if the communication of a classical trit is sufficient, we show that the corresponding protocol must have a convoluted form. We then reduce the smallest qubit scenario requiring two bits of classical communication to only 666 state preparations and 555 measurements. For a qutrit, it is not known whether the communication cost is finite; we identify a scenario that requires at least 555 classical messages, already for the simulation of the real qutrit. Finally, we develop a method for restricted sets of states, that allows us to lower bound the classical communication cost based solely on the set of quantum states.
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.
Bell's theorem implies that the outcomes of local measurements on two maximally entangled systems cannot be simulated without classical communication between the parties. The communication cost is finite for nnn Bell states, but it grows exponentially in nnn. Three simple protocols are presented that provide approximate simulations for low-dimensional entangled systems and require a linearly growing amount of communication. We have tested them by performing some simulations for a family of measurements. The maximal error is less than 11%1 in three dimensions and grows sublinearly with the number of entangled bits in the range numerically tested. One protocol is the multidimensional generalization of the exact Toner-Bacon [Phys. Rev. Lett. 91, 187904 (2003)] model for a single Bell state. The other two protocols are generalizations of an alternative exact model, which we derive from the Kochen-Specker [J. Math. Mech. 17, 59 (1967)] scheme for simulating single-qubit measurements. These protocols can give some indication for finding optimal one-way communication protocols that classically simulate entanglement and quantum channels. Furthermore they can be useful for deciding if a quantum communication protocol provides an advantage on classical protocols.
The prevailing consensus is that the sequential sharing of nonlocality in a Bell experiment requires generalized unsharp measurements, given that a sharp measurement inevitably destroys the entanglement of the shared state. In contrast, a recent work [A. Steffinlongo and A. Tavakoli, Projective measurements are sufficient for recycling nonlocality, Phys. Rev. Lett. 129, 230402 (2022)PRLTAO0031-900710.1103/PhysRevLett.129.230402] demonstrated the sharing of nonlocality up to two sequential observers by employing projective measurement aided with local randomness. Here, we introduce a form of local randomness-assisted qubit projective measurement protocol that enables the sharing of nonlocality by an arbitrary number of sequential observers (Bobs) with a single spatially separated observer (Alice). We achieve this by inspecting the diversity involved in implementing generalized measurements that harness nonlocality by preserving a sufficient amount of entanglement of the shared two-qubit entangled state. Furthermore, we highlight the crucial interplay between the degrees of measurement incompatibility of Alice and Bob in demonstrating the unbounded sharing of nonlocality.
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.