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

The communication cost of simulating POVMs over maximally entangled qubits

Ricard Ravell Rodríguez

Published Sep 9, 2019• 0 citations
OpenAlex

Abstract

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.

Related papers

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•25 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•12 citations

The minimal communication cost for simulating entangled qubits

Martin J. Renner, Marco Túlio Quintino

We analyze the amount of classical communication required to reproduce the statistics of local projective measurements on a general pair of entangled qubits, |ΨAB⟩=p |00⟩+1−p |11⟩ (with 1/2≤p≤1 ). We construct a classical protocol that perfectly simulates local projective measurements on all entangled qubit pairs by communicating one classical trit. Additionally, when 2p(1−p)2p−1log⁡(p1−p)+2(1−p)≤1 , approximately 0.835≤p≤1 , we present a classical protocol that requires only a single bit of communication. The latter model even allows a perfect classical simulation with an average communication cost that approaches zero in the limit where the degree of entanglement approaches zero ( p→1 ). This proves that the communication cost for simulating weakly entangled qubit pairs is strictly smaller than for the maximally entangled one.

arXiv:2207.12457•Quantum•Oct 24, 2023•10 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•16 citations

Beating one bit of communication with and without quantum pseudo-telepathy

István Márton, Erika Bene, Péter Diviánszky +1 more

Abstract According to Bell’s theorem, certain entangled states cannot be simulated classically using local hidden variables (LHV). Suppose that we can augment LHV by some amount of classical communication. The question then arises as to how many bits are needed to simulate entangled states? There is very strong evidence that a single bit of communication is powerful enough to simulate projective measurements on any two-qubit entangled state. However, the problem of simulating measurements on higher-dimensional systems remains largely unexplored. In this study, we present Bell-like scenarios, even with three inputs per party, in which bipartite correlations resulting from measurements on higher-dimensional states cannot be simulated with a single bit of communication. We consider the case where the communication direction is fixed and the case where it is bidirectional. To this end, we introduce constructions based on parallel repetition of pseudo-telepathy games and an original algorithm based on branch-and-bound technique to compute the one-bit classical bound. Two copies of emblematic Bell expressions, such as the Magic square pseudo-telepathy game, prove to be particularly powerful, requiring a 16 × 16 state to beat the bidirectional one-bit classical bound, and look a promising candidate for implementation on an optical platform.

arXiv:2308.10771•npj Quantum Information•Aug 22, 2024•4 citations

Communication cost of classically simulating a quantum channel with subsequent rank-1 projective measurement

A. Montina

A process of preparation, transmission, and subsequent projective measurement of a qubit can be simulated by a classical model with only two bits of communication and some amount of shared randomness. However, to the best of our knowledge, no model for $n$ qubits with a finite amount of classical communication is known at present. A lower bound for the communication cost can provide useful hints for a generalization. It is known, for example, that the amount of communication must be greater than $c{2}^{n}$, where $c\ensuremath{\simeq}0.01$. The proof uses a quite elaborate theorem of communication complexity. Using a mathematical conjecture known as the ``double cap conjecture,'' we strengthen this result by presenting a geometrical and extremely simple derivation of the lower bound ${2}^{n}\ensuremath{-}1$. Only rank-1 projective measurements are involved in the derivation.

arXiv:1110.5944•Physical Review A•Dec 29, 2011•17 citations
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.
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.
We analyze the amount of classical communication required to reproduce the statistics of local projective measurements on a general pair of entangled qubits, |ΨAB⟩=p |00⟩+1−p |11⟩ (with 1/2≤p≤1 ). We construct a classical protocol that perfectly simulates local projective measurements on all entangled qubit pairs by communicating one classical trit. Additionally, when 2p(1−p)2p−1log⁡(p1−p)+2(1−p)≤1 , approximately 0.835≤p≤1 , we present a classical protocol that requires only a single bit of communication. The latter model even allows a perfect classical simulation with an average communication cost that approaches zero in the limit where the degree of entanglement approaches zero ( p→1 ). This proves that the communication cost for simulating weakly entangled qubit pairs is strictly smaller than for the maximally entangled one.
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.
Abstract According to Bell’s theorem, certain entangled states cannot be simulated classically using local hidden variables (LHV). Suppose that we can augment LHV by some amount of classical communication. The question then arises as to how many bits are needed to simulate entangled states? There is very strong evidence that a single bit of communication is powerful enough to simulate projective measurements on any two-qubit entangled state. However, the problem of simulating measurements on higher-dimensional systems remains largely unexplored. In this study, we present Bell-like scenarios, even with three inputs per party, in which bipartite correlations resulting from measurements on higher-dimensional states cannot be simulated with a single bit of communication. We consider the case where the communication direction is fixed and the case where it is bidirectional. To this end, we introduce constructions based on parallel repetition of pseudo-telepathy games and an original algorithm based on branch-and-bound technique to compute the one-bit classical bound. Two copies of emblematic Bell expressions, such as the Magic square pseudo-telepathy game, prove to be particularly powerful, requiring a 16 × 16 state to beat the bidirectional one-bit classical bound, and look a promising candidate for implementation on an optical platform.
A process of preparation, transmission, and subsequent projective measurement of a qubit can be simulated by a classical model with only two bits of communication and some amount of shared randomness. However, to the best of our knowledge, no model for nnn qubits with a finite amount of classical communication is known at present. A lower bound for the communication cost can provide useful hints for a generalization. It is known, for example, that the amount of communication must be greater than c2nc{2}^{n}c2n, where $c\ensuremath{\simeq}0.01$. The proof uses a quite elaborate theorem of communication complexity. Using a mathematical conjecture known as the ``double cap conjecture,'' we strengthen this result by presenting a geometrical and extremely simple derivation of the lower bound ${2}^{n}\ensuremath{-}1$. Only rank-1 projective measurements are involved in the derivation.