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:1606.09514 · Quantum

Robust Bell inequalities from communication complexity

Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, Gabriel Senno

Published Jun 7, 2018• 12 citations
arXivHTMLPDF

Abstract

The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given for the quantum violation of these Bell inequalities in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. This makes the Bell inequality resistant to the detection loophole, while a normalized Bell inequality is resistant to general local noise. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bound techniques. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.

DOI
10.22331/q-2018-06-07-72

Related papers

Does violation of a Bell inequality always imply quantum advantage in a communication complexity problem?

Armin Tavakoli, Marek Żukowski, Časlav Brukner

Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, \cite{BZ02}; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the I3322 Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs

arXiv:1907.01322•Quantum•Sep 7, 2020•20 citations

Device-Independent Bounds on Detection Efficiency

Jochen Szangolies, Hermann Kampermann, Dagmar Bruß

In many quantum information applications, a minimum detection efficiency must be exceeded to ensure success. Protocols depending on the violation of a Bell inequality, for instance, may be subject to the so-called detection loophole: Imperfect detectors may yield spurious violations, which consequently cannot be used to ensure, say, quantum cryptographic security. Hence, we investigate the possibility of giving lower bounds on detector efficiency even if an adversary has full control over both the source and the detectors. To this end, we present a technique to systematically derive Bell inequalities free from the detection loophole using only the observed measurements statistics. The violation of these inequalities certifies that the detectors used exceed a certain minimal efficiency.

arXiv:1609.06126•Physical Review Letters•Jun 27, 2017•11 citations

Tight Bell inequalities from polytope slices

José Jesus, Emmanuel Zambrini Cruzeiro

We derive tight bipartite Bell inequalities for various scenarios. A bipartite Bell scenario $(X,Y,A,B)$ is defined by the numbers of settings and outcomes per party, $X,A$, and $Y,B$ for Alice and Bob, respectively. We derive the complete set of facets of the local polytopes of (6,3,2,2), (3,3,3,2), (3,2,3,3), and (2,2,3,5). We provide extensive lists of facets for (2,2,4,4), (3,3,4,2), and (4,3,3,2). For each inequality we compute the maximum quantum violation, the resistance to noise, and the minimal symmetric detection efficiency required to close the detection loophole, for qubits, qutrits, and ququarts. Based on these results, we identify scenarios which perform better in terms of visibility, resistance to noise, or both, when compared to the Clauser-Horne-Shimony-Holt inequality. Such scenarios could find important applications in quantum communication.

arXiv:2212.03212•Physical Review A•Nov 27, 2023•4 citations

Violating a Bell Inequality: What to Do When You Lose Your Quantum System

Xinyu Xu, Yuqing Li, Mingze Xu +1 more

The detection loophole is a well-known loophole in Bell nonlocality motivated by the inefficiency of detectors used in Bell experiments. However, this inefficiency is actually a ubiquitous feature of any photonic platform for quantum networks since photons are readily absorbed by the surrounding environment. When the quantum system, usually a photon, is lost, what should the parties output? The most natural choice is to fall back to a deterministic strategy where each party produces an output via a function of her local input. In this paper, we study how to choose such a fallback strategy for general Bell inequalities with respect to different efficiencies $η$ to maximize the possible violation. We mathematically prove that for the CHSH inequality, there exists a fallback strategy that is optimal for all $η$. However, in general, we find that the optimal fallback strategy can vary with $η$, sometimes in surprising ways. For example, we find an example of a Bell inequality where the optimal fallback strategy near the threshold efficiency is not an optimal deterministic strategy in the lossless setting. Our results can reduce the efficiency requirements for closing the detection loophole and thus are useful for applications of Bell inequality violation, such as quantum telepathy or device-independent quantum key distribution.

quant-pharXiv:2609.12604•Sep 14, 2026•0 citations

Bell inequalities from no-signaling distributions

Thomas Cope, Roger Colbeck

A Bell inequality is a constraint on a set of correlations whose violation can be used to certify nonlocality. They are instrumental for device-independent tasks such as key distribution or randomness expansion. In this work, we consider bipartite Bell inequalities where two parties have ${m}_{A}$ and ${m}_{B}$ possible inputs and give ${n}_{A}$ and ${n}_{B}$ possible outputs, referring to this as the $({m}_{A},{m}_{B},{n}_{A},{n}_{B})$ scenario. By exploiting knowledge of the set of extremal no-signaling distributions, we find all 175 Bell inequality classes in the (4,4,2,2) scenario as well as provide a partial list of 18 277 classes in the (4,5,2,2) scenario. We also use a probabilistic algorithm to obtain 5 classes of inequality in the (2,3,3,2) scenario, which we confirmed to be complete, 25 classes in the (3,3,2,3) scenario, and a partial list of 21 170 classes in the (3,3,3,3) scenario. Our inequalities are given as Supplemental Material. Finally, we discuss the application of these inequalities to the detection loophole problem and provide lower bounds on the detection efficiency threshold for small numbers of inputs and outputs.

arXiv:1812.10017•Physical Review A•Aug 12, 2019•25 citations

Classical vs. quantum communication in XOR games

Marius Junge, Carlos Palazuelos, Ignacio Villanueva

In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games $G$ when Alice and Bob are allowed to use a limited amount of one-way classical communication $ω_{o.w.-c}(G)$ (resp. one-way quantum communication $ω_{o.w.-c}^*(G)$), where $c$ denotes the number of bits (resp. qubits). The key quantity here is the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)$. We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient $ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)$ is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information $c$. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.

arXiv:1706.02653•Jun 8, 2017•0 citations
The question of how large Bell inequality violations can be, for quantum distributions, has been the object of much work in the past several years. We say that a Bell inequality is normalized if its absolute value does not exceed 1 for any classical (i.e. local) distribution. Upper and (almost) tight lower bounds have been given for the quantum violation of these Bell inequalities in terms of number of outputs of the distribution, number of inputs, and the dimension of the shared quantum states. In this work, we revisit normalized Bell inequalities together with another family: inefficiency-resistant Bell inequalities. To be inefficiency-resistant, the Bell value must not exceed 1 for any local distribution, including those that can abort. This makes the Bell inequality resistant to the detection loophole, while a normalized Bell inequality is resistant to general local noise. Both these families of Bell inequalities are closely related to communication complexity lower bounds. We show how to derive large violations from any gap between classical and quantum communication complexity, provided the lower bound on classical communication is proven using these lower bound techniques. This leads to inefficiency-resistant violations that can be exponential in the size of the inputs. Finally, we study resistance to noise and inefficiency for these Bell inequalities.
Quantum correlations which violate a Bell inequality are presumed to power better-than-classical protocols for solving communication complexity problems (CCPs). How general is this statement? We show that violations of correlation-type Bell inequalities allow advantages in CCPs, when communication protocols are tailored to emulate the Bell no-signaling constraint (by not communicating measurement settings). Abandonment of this restriction on classical models allows us to disprove the main result of, inter alia, \cite{BZ02}; we show that quantum correlations obtained from these communication strategies assisted by a small quantum violation of the CGLMP Bell inequalities do not imply advantages in any CCP in the input/output scenario considered in the reference. More generally, we show that there exists quantum correlations, with nontrivial local marginal probabilities, which violate the I3322 Bell inequality, but do not enable a quantum advantange in any CCP, regardless of the communication strategy employed in the quantum protocol, for a scenario with a fixed number of inputs and outputs
In many quantum information applications, a minimum detection efficiency must be exceeded to ensure success. Protocols depending on the violation of a Bell inequality, for instance, may be subject to the so-called detection loophole: Imperfect detectors may yield spurious violations, which consequently cannot be used to ensure, say, quantum cryptographic security. Hence, we investigate the possibility of giving lower bounds on detector efficiency even if an adversary has full control over both the source and the detectors. To this end, we present a technique to systematically derive Bell inequalities free from the detection loophole using only the observed measurements statistics. The violation of these inequalities certifies that the detectors used exceed a certain minimal efficiency.
We derive tight bipartite Bell inequalities for various scenarios. A bipartite Bell scenario (X,Y,A,B)(X,Y,A,B)(X,Y,A,B) is defined by the numbers of settings and outcomes per party, X,AX,AX,A, and Y,BY,BY,B for Alice and Bob, respectively. We derive the complete set of facets of the local polytopes of (6,3,2,2), (3,3,3,2), (3,2,3,3), and (2,2,3,5). We provide extensive lists of facets for (2,2,4,4), (3,3,4,2), and (4,3,3,2). For each inequality we compute the maximum quantum violation, the resistance to noise, and the minimal symmetric detection efficiency required to close the detection loophole, for qubits, qutrits, and ququarts. Based on these results, we identify scenarios which perform better in terms of visibility, resistance to noise, or both, when compared to the Clauser-Horne-Shimony-Holt inequality. Such scenarios could find important applications in quantum communication.
The detection loophole is a well-known loophole in Bell nonlocality motivated by the inefficiency of detectors used in Bell experiments. However, this inefficiency is actually a ubiquitous feature of any photonic platform for quantum networks since photons are readily absorbed by the surrounding environment. When the quantum system, usually a photon, is lost, what should the parties output? The most natural choice is to fall back to a deterministic strategy where each party produces an output via a function of her local input. In this paper, we study how to choose such a fallback strategy for general Bell inequalities with respect to different efficiencies ηηη to maximize the possible violation. We mathematically prove that for the CHSH inequality, there exists a fallback strategy that is optimal for all ηηη. However, in general, we find that the optimal fallback strategy can vary with ηηη, sometimes in surprising ways. For example, we find an example of a Bell inequality where the optimal fallback strategy near the threshold efficiency is not an optimal deterministic strategy in the lossless setting. Our results can reduce the efficiency requirements for closing the detection loophole and thus are useful for applications of Bell inequality violation, such as quantum telepathy or device-independent quantum key distribution.
A Bell inequality is a constraint on a set of correlations whose violation can be used to certify nonlocality. They are instrumental for device-independent tasks such as key distribution or randomness expansion. In this work, we consider bipartite Bell inequalities where two parties have mA{m}_{A}mA​ and mB{m}_{B}mB​ possible inputs and give nA{n}_{A}nA​ and nB{n}_{B}nB​ possible outputs, referring to this as the (mA,mB,nA,nB)({m}_{A},{m}_{B},{n}_{A},{n}_{B})(mA​,mB​,nA​,nB​) scenario. By exploiting knowledge of the set of extremal no-signaling distributions, we find all 175 Bell inequality classes in the (4,4,2,2) scenario as well as provide a partial list of 18 277 classes in the (4,5,2,2) scenario. We also use a probabilistic algorithm to obtain 5 classes of inequality in the (2,3,3,2) scenario, which we confirmed to be complete, 25 classes in the (3,3,2,3) scenario, and a partial list of 21 170 classes in the (3,3,3,3) scenario. Our inequalities are given as Supplemental Material. Finally, we discuss the application of these inequalities to the detection loophole problem and provide lower bounds on the detection efficiency threshold for small numbers of inputs and outputs.
In this work we introduce an intermediate setting between quantum nonlocality and communication complexity problems. More precisely, we study the value of XOR games GGG when Alice and Bob are allowed to use a limited amount of one-way classical communication ωo.w.−c(G)ω_{o.w.-c}(G)ωo.w.−c​(G) (resp. one-way quantum communication ωo.w.−c∗(G)ω_{o.w.-c}^*(G)ωo.w.−c∗​(G)), where ccc denotes the number of bits (resp. qubits). The key quantity here is the quotient ωo.w.−c∗(G)/ωo.w.−c(G)ω_{o.w.-c}^*(G)/ω_{o.w.-c}(G)ωo.w.−c∗​(G)/ωo.w.−c​(G). We provide a universal way to obtain Bell inequality violations of general Bell functionals from XOR games for which the quotient ωo.w.−c∗(G)/ωo.w.−2c(G)ω_{o.w.-c}^*(G)/ω_{o.w.-2c}(G)ωo.w.−c∗​(G)/ωo.w.−2c​(G) is larger than 1. This allows, in particular, to find (unbounded) Bell inequality violations from communication complexity problems in the same spirit as the recent work by Buhrman et al. (2016). We also provide an example of a XOR game for which the previous quotient is optimal (up to a logarithmic factor) in terms of the amount of information ccc. Interestingly, this game has only polynomially many inputs per player. For the related problem of separating the classical vs quantum communication complexity of a function, the known examples attaining exponential separation require exponentially many inputs per party.