# Approximate classical simulation cost for entanglement correlations

Question: What is the classical communication cost of approximately simulating quantum entanglement correlations, as a function of approximation error, and does approximation defeat the known exponential lower bounds?

Bottom line (Evidence class: Established, with one explicitly marked inference below): the Brassard-Cleve-Tapp exponential lower bound is an exact-simulation, worst-case-communication lower bound for global/projective measurements on n Bell states. I found no BCT or Massar-Bacon-Cerf-Cleve theorem that preserves an Omega(2^n) lower bound under constant approximation error. The exact BCT reduction is to an exact promise equality/Deutsch-Jozsa communication problem; with bounded error that promise problem is easy using public randomness and constant communication, so the BCT proof itself is not robust. Known bounded-error lower bounds relevant to simulating general quantum channels/correlations are weaker, e.g. Hidden Matching/Raz-type exponential separations giving sub-2^n lower bounds such as 2^{Omega(sqrt(n))} in the formulations Montina cites. Montina's 2011 linear-communication protocols are approximate and numerical/low-dimensional; they approximate full joint probabilities for projective measurements in tested families, but their worst-case error is not bounded independently of n.

## 1. Brassard, Cleve & Tapp PRL 83, 1874 (1999)

Evidence class: Established.

Citation: Gilles Brassard, Richard Cleve, and Alain Tapp, "Cost of Exactly Simulating Quantum Entanglement with Classical Communication," Physical Review Letters 83, 1874-1877 (1999), arXiv:quant-ph/9901035, DOI: 10.1103/PhysRevLett.83.1874.

Title and abstract already fix the exactness condition. The arXiv abstract says: "We consider the scenario where a bipartite measurement is given from a set of possibilities and the goal is to obtain exactly the same correlations ..." It also says: "in the case of a system of n Bell states, a constant times 2^n bits of communication are necessary."

Their definition of simulation is exact distributional equality: "A local hidden variable scheme simulates a measurement scenario ... if, for any x in M_A and y in M_B, the outputs ... have exactly the same bivariate distribution ..." A scheme augmented by k bits permits up to k communicated bits in the measurement stage before outputs.

Theorem 4, quoted from quant-ph/9901035/PRL text:

> "There exists a pair of sets of measurements, M_A and M_B (each of size 2^{2^n}) on n qubits, such that, for the quantum measurement scenario (|Phi+>^{\otimes n}_{AB}, M_A, M_B) with |Phi+>^{\otimes n}_{AB}=1/sqrt(2^n) sum_i |i>|i>, any local hidden variable scheme must be augmented with a constant times 2^n bits of communication in order to exactly simulate it."

Hypotheses of Theorem 4:

- Exact simulation, not approximate simulation.
- Worst-case/bounded communication model: the augmented LHV scheme has a maximum number of communicated bits.
- Shared randomness is allowed.
- The state is n Bell states, i.e. the maximally entangled state on two N-dimensional systems with N=2^n.
- The measurements are not restricted to product single-qubit measurements. They are coherent n-qubit von Neumann/projective measurements. The proof uses Deutsch-Jozsa measurements indexed by z in {0,1}^{2^n}: apply phases according to z, then an n-qubit Hadamard transform, then computational-basis measurement. Each party's measurement set has size 2^{2^n}.

Null result (Evidence class: Established): I found no bounded-error/constant-error version of Theorem 4 in BCT. The statement is exact, and the proof reduces exact simulation to exactly solving the Deutsch-Jozsa/promise equality problem.

Own inference, but mechanically follows from the proof structure: BCT's reduction does not survive constant error. Their exact promise problem is: x=y versus Hamming distance 2^{n-1}. With public coins and bounded error, Alice and Bob can sample O(log(1/delta)) public coordinates, Alice sends the sampled bits, and Bob checks for a disagreement. This uses O(log(1/delta)) bits, independent of 2^n, to distinguish the two cases with error delta. Therefore the exact-communication lower bound used by BCT is not a robust bounded-error lower bound.

Related exact upper bounds in BCT (Evidence class: Established): for one Bell state, Theorem 2 gives an exact four-bit protocol for real-plane von Neumann qubit measurements; Theorem 3 gives an exact eight-bit protocol for arbitrary complex qubit von Neumann measurements. They note independent arbitrary von Neumann measurements on n Bell states can be simulated by applying the one-pair protocol n times, but Theorem 4 shows coherent n-qubit measurements can force Omega(2^n) bits exactly.

## 2. Constant-error lower bounds for n Bell states

Evidence class: Established for the citations and for the null result within the searched papers; Serious speculation only where a communication-complexity lower bound is used as relevance rather than a direct entanglement-simulation theorem.

Massar-Bacon-Cerf-Cleve citation: Serge Massar, Dave Bacon, Nicolas J. Cerf, and Richard Cleve, "Classical simulation of quantum entanglement without local hidden variables," Physical Review A 63, 052305 (2001), arXiv:quant-ph/0009088, DOI: 10.1103/PhysRevA.63.052305.

MBCC is still an exact-simulation paper. The abstract describes exact simulation of quantum correlations and arbitrary POVMs using communication without requiring a local hidden-variable model. Their introduction says:

> "Regarding the classical entanglement simulation of more than one Bell state, it is shown in [1] that the exact simulation of arbitrary von Neumann measurements on n Bell states requires Omega(2^n) bits of communication in the bounded communication model. With minor modifications to the techniques in [1,5], this Omega(2^n) lower bound also carries over to the average communication model."

That lower bound is for exact simulation. Their constructive result is also exact. The main high-dimensional upper bound is an exact average-communication protocol: arbitrary POVMs on n Bell states can be simulated with average communication less than (3n+6)2^n bits from Alice to Bob and less than 2 bits from Bob to Alice.

Null result (Evidence class: Established): In BCT and MBCC I found no theorem of the form "constant total-variation/correlation error still requires Omega(2^n) bits" for all measurements on n Bell states. Search terms used included bounded error, approximate communication complexity, robust simulation of nonlocal correlations, BCT bounded-error, Massar Bacon Cerf Cleve bounded error, and approximate simulation entanglement communication lower bound.

Known weaker bounded-error lower-bound context (Evidence class: Established citations; relevance is Serious speculation unless the simulation-to-communication reduction is stated in the cited paper): Montina summarizes the state of play as follows in PRA 84, 042307 (2011):

> "There is an open question concerning the classical communication complexity of a quantum channel. On the one hand, the best known protocol for simulating a quantum channel uses an amount of resources that scales as n2^n [6,9], even with a bounded error. On the other hand, the HM problem gives the lower bound 2^{Omega(sqrt(n))} for the minimal amount of communication in the case of bounded error. At present, no other constraint is known; thus one could hope to find a better bounded-error simulation of a quantum channel with communication complexity scaling as 2^{sqrt(n)}."

Montina's reference for the Hidden Matching lower bound is Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis, "Exponential separation of quantum and classical one-way communication complexity," Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 128-137; journal version SIAM Journal on Computing 38(1), 366-384 (2008), DOI: 10.1137/060651835. The result gives an exponential separation between one-way quantum communication and bounded-error randomized one-way communication for the Hidden Matching problem.

Raz context: Ran Raz, "Exponential separation of quantum and classical communication complexity," Proceedings of the 31st Annual ACM Symposium on Theory of Computing (STOC 1999), pp. 358-367. This is an approximate/bounded-error communication-complexity separation and is relevant to classical simulation of quantum communication protocols, but it is not itself a direct BCT-style lower bound for approximate simulation of all n-Bell-state measurement correlations.

Conclusion for item 2 (Evidence class: Established): approximation defeats the known BCT exponential lower-bound proof. I found bounded-error lower bounds relevant to simulating quantum communication/channels, but not a constant-error Omega(2^n) lower bound for simulating n Bell states' full measurement statistics.

## 3. Montina approximate simulation with linear communication

Evidence class: Established.

Citation: Alberto Montina, "Approximate simulation of entanglement with a linear cost of communication," Physical Review A 84, 042307 (2011), arXiv:1107.4647 [quant-ph], DOI: 10.1103/PhysRevA.84.042307.

Abstract quote:

> "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."

Introduction quote:

> "we present three approximate classical protocols for simulating bipartite entanglement that need a one-way communication equal to the number of entangled bits (ebits)."

What is simulated: the target is the maximally entangled state

|psi_AB> = (1/sqrt(N)) sum_{k=1}^N |k>_A |k>_B,

with N=2^n, and local projective measurements with N outcomes. The protocols generate Alice and Bob outcomes and are aimed at approximating the full joint probability distribution p(a,b|measurements), not merely a two-point correlator. The marginals are exactly uniform/correct by construction; the tested error concerns the joint/correlation probabilities.

Communication scaling: one-way communication equal to log_2 N = n bits for the entanglement-simulation protocol. Montina notes conversion to approximate quantum-channel simulation adds n bits on average, doubling the communication on average.

Error measure and numerical status: Montina does not prove a uniform constant-error bound over all n and all projective measurements. The error is studied numerically for a family of measurements. In the N=3 plots, protocol 2b has maximum discrepancy below 0.01; protocol 1 is about 0.014; protocol 2a is about 0.025. Figure 3 reports the maximum discrepancy versus dimension N in the tested range up to N=32, with growth sublinear in n=log_2 N. The paper explicitly warns that the error cannot remain bounded in the strongest setting; Montina writes:

> "The maximum error ... increases sublinearly ... (Note that the error cannot be bounded, since, as previously said, a protocol with bounded error needs at least 2^{Omega(sqrt(n))} bits of communication)."

Conclusion (Evidence class: Established): Montina gives approximate, linear-communication protocols with numerical evidence of small error in low dimensions and selected measurement families. These do not constitute a proof that all n-Bell-state correlations can be simulated to fixed epsilon with O(n) bits.

## 4. EPR2/local-content decomposition

Evidence class: Established.

EPR2 citation: A. C. Elitzur, S. Popescu, and D. Rohrlich, "Quantum nonlocality for each pair in an ensemble," Physics Letters A 162, 25-28 (1992), DOI: 10.1016/0375-9601(92)90952-I.

Barrett-Kent-Pironio citation: Jonathan Barrett, Adrian Kent, and Stefano Pironio, "Maximally Nonlocal and Monogamous Quantum Correlations," Physical Review Letters 97, 170409 (2006), arXiv:quant-ph/0605182, DOI: 10.1103/PhysRevLett.97.170409.

BKP abstract quote:

> "the maximally entangled state of two d dimensional quantum systems has no local component. That is, if we write its quantum correlations as a mixture of local correlations and general (not necessarily quantum) correlations, the coefficient of the local correlations must be zero."

Decomposition: write P_QM = p P_L + (1-p)P_NL, where P_L is local and P_NL is general nonsignalling/not necessarily quantum. BKP use a chained Bell inequality I_N and derive p <= I_N(QM)/(d-1). For maximally entangled states, I_N(QM) -> 0 as the number of settings N -> infinity, so p_max=0. For the two-qubit singlet, this says the maximum local content over the full measurement family is zero.

Experimental measured bound (Null result; Evidence class: Established for search result, not a claim of nonexistence): I did not find a primary experimental paper reporting a numerical measured upper bound on the EPR2/BKP "local content" of singlet correlations. Searches included "local content experimentally singlet Bell", "local part singlet experiment EPR2", "nonlocal content experiment BKP local content", and variants. What BKP provide is a route for experiments: for a measured chained-inequality value I_N(EXP), the data would imply p <= I_N(EXP)/(d-1). I found no reliable actual I_N(EXP)-based number to report.

## 5. Measurement dependence bounds

Evidence class: Established for Hall/Putz/Aktas citations and quoted numerical bounds. Note: Hall's 0.0663-bit number is a sufficient amount of measurement dependence for a model of singlet correlations, not an experimental upper bound.

Hall citation: M. J. W. Hall, "Local deterministic model of singlet state correlations based on relaxing measurement independence," Physical Review Letters 105, 250404 (2010), arXiv:1007.5518, DOI: 10.1103/PhysRevLett.105.250404.

Hall abstract quote:

> "all spin correlations of a singlet state can be modeled via giving up a fraction of just 14% of measurement independence. The underlying model is deterministic and no-signalling ... maximum possible violation ... at a cost of only 1/3 of measurement independence."

Hall's variational measurement-dependence measure is M = sup_{X,X',Y,Y'} integral d lambda |rho_{XY}(lambda)-rho_{X'Y'}(lambda)|, with measurement-independence fraction F=1-M/2. For the singlet model, Hall gives M = 2(sqrt(2)-1)/3 = 0.276... and F=(4-sqrt(2))/3 = 0.862..., commonly summarized as about 14% measurement independence relaxed / 86% retained.

Hall mutual-information measure: later Hall/Barrett-Gisin discussions use mutual information I(settings:lambda). A commonly cited number is about 0.0663 bits sufficient to simulate all projective spin measurements on a singlet for arbitrary setting distributions. I did not locate this exact number in the PRL 105, 250404 text itself; it appears in later measurement-dependence discussions and reviews. Treat it as a theoretical sufficiency result, not an experimental bound.

Putz et al. citation: Gilles Putz, Denis Rosset, Tomer Jack Barnea, Yeong-Cherng Liang, and Nicolas Gisin, "Arbitrarily small amount of measurement independence is sufficient to manifest quantum nonlocality," Physical Review Letters 113, 190402 (2014), arXiv:1407.5634, DOI: 10.1103/PhysRevLett.113.190402.

Putz et al. result: in the MDL model, measurement dependence is parameterized by bounds l <= P(x,y|lambda) <= h on setting probabilities conditioned on hidden variables. They prove that for any l>0, quantum correlations can violate an MDL inequality. Their central inequality is of the form l P(0000) - h[P(0101)+P(1010)+P(0011)] <= 0 for the relevant binary-input/output notation. This is theoretical, not the Aktas experiment.

Aktas citation correction: the requested "Aktas, Tanzilli, Martin, Putz, Thew & Gisin PRL 112, 190401 (2014)" does not match the measurement-dependence experiment I found. The relevant paper is Djeylan Aktas, Sebastien Tanzilli, Anthony Martin, Gilles Putz, Rob Thew, and Nicolas Gisin, "Demonstration of Quantum Nonlocality in the Presence of Measurement Dependence," Physical Review Letters 114, 220404 (2015), arXiv:1504.08332, DOI: 10.1103/PhysRevLett.114.220404. PRL 112, 190401 (2014) is not this paper.

Aktas et al. numerical bound quote:

> "Our experiment ... lowers this bound on Measurement Dependence down to 0.090."

More detailed result:

> "we can exclude all values of l for which our data violates the MDL inequality, with l_net > 0.074(6) or l_raw > 0.090(4) ... Recall that a maximal violation of a CHSH MDL-adjusted inequality only excludes l>0.1465."

Units and meaning: l is dimensionless. It is not bits. It is the minimum conditional probability assigned to each setting pair x,y given hidden variable lambda. The experimental result forbids MDL local models satisfying l above the quoted threshold from explaining the observed correlations; it does not rule out arbitrarily strong measurement dependence l near 0. The Aktas experiment was photonic and did not close all standard Bell loopholes; its target was the measurement-dependence parameter in the MDL framework.

## 6. Loophole-free Bell tests: trials and statistics

Evidence class: Established where exact values are from abstracts/papers/arXiv sources; Null result explicitly marked for missing Giustina trial count.

### Hensen et al. 2015

Citation: B. Hensen, H. Bernien, A. E. Dreau, A. Reiserer, N. Kalb, M. S. Blok, J. Ruitenberg, R. F. L. Vermeulen, R. N. Schouten, C. Abellan, W. Amaya, V. Pruneri, M. W. Mitchell, M. Markham, D. J. Twitchen, D. Elkouss, S. Wehner, T. H. Taminiau, and R. Hanson, "Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres," Nature 526, 682-686 (2015), arXiv:1508.05949, DOI: 10.1038/nature15759.

Reported statistic: 245 trials testing CHSH-Bell inequality S <= 2. Result S = 2.42 +/- 0.20. Null-hypothesis p-value p = 0.039 allowing for memory. ArXiv abstract quote: "We perform 245 trials testing the CHSH-Bell inequality S <= 2 and find S = 2.42 +/- 0.20. A null hypothesis test yields a probability of p = 0.039 ..."

### Giustina et al. 2015

Citation: Marissa Giustina, Marijn A. M. Versteegh, Soren Wengerowsky, Johannes Handsteiner, Armin Hochrainer, Kevin Phelan, Fabian Steinlechner, Johannes Kofler, Jan-Ake Larsson, Carlos Abellan, Waldimar Amaya, Valerio Pruneri, Morgan W. Mitchell, Jorn Beyer, Thomas Gerrits, Adriana E. Lita, Lynden K. Shalm, Sae Woo Nam, Thomas Scheidl, Rupert Ursin, Bernhard Wittmann, and Anton Zeilinger, "Significant-Loophole-Free Test of Bell's Theorem with Entangled Photons," Physical Review Letters 115, 250401 (2015), arXiv:1511.03190, DOI: 10.1103/PhysRevLett.115.250401.

Reported statistic: CH-Eberhard/CH-E inequality, not CHSH S. Main text quote: "We set a state with r approximately -2.9 and measured at angles ... for approximately 3,510 seconds, and obtained the probabilities shown in Fig. 3, corresponding to a J-value of 7.27 x 10^{-6}." Statistical quote: "the probability of observing our measured J-value does not exceed a p-value of 3.74 x 10^{-31}" and this corresponds to "an 11.5 standard deviation effect."

Null result on N: I did not recover an exact total trial count from the PRL/arXiv text accessible here. I searched the arXiv abstract, main TeX source, and web results for total trials/N. The main article reports the run duration (about 3,510 s), probabilities, J=7.27 x 10^{-6}, p=3.74 x 10^{-31}, and 11.5 sigma, but not an explicit total N in the main text I extracted. I therefore do not report an inferred N.

### Shalm et al. 2015

Citation: L. K. Shalm et al., "Strong Loophole-Free Test of Local Realism," Physical Review Letters 115, 250402 (2015), arXiv:1511.03189, DOI: 10.1103/PhysRevLett.115.250402.

Reported statistic: CH/Eberhard-style hypothesis test, not CHSH S. Abstract reports p-values as small as 5.9 x 10^{-9}; after accounting for trials/look-elsewhere, adjusted p-value 2.3 x 10^{-7}.

Extracted aggregate table values from arXiv source:

- 1-pulse window: N(++|ab)=1257, N_stop=2376, total trials=175,654,992, p=2.5 x 10^{-3}, adjusted p=5.9 x 10^{-3}.
- 3-pulse window: N(++|ab)=3800, N_stop=7211, total trials=175,744,824, p=2.4 x 10^{-6}, adjusted p=2.4 x 10^{-5}.
- 5-pulse window: N(++|ab)=6378, N_stop=12127, total trials=177,358,351, p=5.9 x 10^{-9}, adjusted p=2.3 x 10^{-7}.
- 7-pulse window: N(++|ab)=8820, N_stop=16979, total trials=177,797,650, p=2.0 x 10^{-7}, adjusted p=9.2 x 10^{-6}.

The headline/best result is the 5-pulse window: 177,358,351 trials and adjusted p=2.3 x 10^{-7}.

### Rosenfeld et al. 2017

Citation: Wenjamin Rosenfeld, Daniel Burchardt, Robert Garthoff, Kai Redeker, Norbert Ortegel, Markus Rau, and Harald Weinfurter, "Event-Ready Bell Test Using Entangled Atoms Simultaneously Closing Detection and Locality Loopholes," Physical Review Letters 119, 010402 (2017), arXiv:1611.04604, DOI: 10.1103/PhysRevLett.119.010402.

Reported statistic: CHSH S. Abstract result: S = 2.221 +/- 0.033, P < 2.57 x 10^{-9}. Main run: 10,000 event-ready observations, collected as 5,000 events for each of two atom-atom Bell states over 44 days. Individual S values were S=2.240 +/- 0.047 for |Psi-> and S=2.204 +/- 0.047 for |Psi+>; combined S=2.221 +/- 0.033, a 6.7-standard-deviation violation. Reported p-values include P_m=2.57 x 10^{-9} and P_g=1.74 x 10^{-10} depending on the statistical treatment.

### BIG Bell Test 2018

Citation: The BIG Bell Test Collaboration, "Challenging local realism with human choices," Nature 557, 212-216 (2018), arXiv:1805.04431, DOI: 10.1038/s41586-018-0085-3.

Overall scale: about 100,000 human participants produced 97,347,490 binary choices for 13 experiments in 12 laboratories.

Loophole-free photonic station details reported in the Nature/arXiv material: the human-input run used 40,559,990 trials in just under 7 minutes, consuming 81,119,980 human bits. The corresponding Bell parameter was K=(1.70 +/- 0.20) x 10^{-4}, quoted as an 8.7 sigma violation under normal/iid assumptions. Table counts for the human run list event counts 20265, 712, 7475, 143, 8181, 123 and trial counts 11,126,350; 9,202,147; 10,125,716; 10,125,716; 10,105,777; 10,105,777 for the six relevant terms.

Important caveat: the authors report that the initial human-input hypothesis-test protocol was flawed because the Bellster bit stream had an approximately 5% excess of zeros. The originally planned human-input test gave an uncorrected p=3.3 x 10^{-70} with n_cut=30,916 but was invalid under the corrected analysis; the corrected human-input p-value was approximately 1, so that strict protocol did not reject local realism using the biased human bits alone. A follow-up computer-random run used 74,400,000 trials and gave p=2.6 x 10^{-27} with n_cut=54,720.

## Final answer to the cost question

Evidence class: Established.

Exact all-measurement simulation of n Bell states has worst-case/average lower bounds Omega(2^n) in BCT/MBCC settings, with exact exponential-cost upper bounds of order n2^n for very general measurements. Once constant approximation error is allowed, I found no known Omega(2^n) lower bound in those sources. The BCT exact proof is defeated because its communication-complexity core is exact Deutsch-Jozsa/promise equality, which becomes cheap under bounded error. Known bounded-error lower bounds relevant to channel/correlation simulation are weaker, such as Hidden-Matching/Raz-type bounds discussed by Montina. Linear communication is known for Montina's approximate numerical protocols in low dimensions/tested measurement families, but not as a proven constant-epsilon simulation of all n-Bell-state correlations.