SIAM Journal on Discrete Mathematics

Bell Inequalities, Grothendieck’s Constant, and Root Two

P. C. Fishburn, James A. Reeds

Published Feb 1, 1994• 50 citations

Abstract

B. S. Tsirelson showed that comparisons between probabilities in “classical” physics and probabilities in quantum mechanics yield discrepancy measures $K_n $ for finite $n \times n$ real matrices that approach Grothendieck’s constant $K_G $ as n gets large. It is known that $K_2 = K_3 = \sqrt{2} $ and that $K_G \geq \pi /2 = 1.57 \cdots $, but examples of $n \times n$ matrices for specified n that demonstrate $K_n > \sqrt{2} $ have eluded researchers. A series of elementary examples are provided, which yield lower bounds on $K_{k ( k - 1 )} $ that approach 3/2 as k gets large. A uniform change along the main diagonal of our basic example shows that $K_{20} \geqq = 10/7 = 1.42 \cdots $.

DOI: 10.1137/s0895480191219350

Related papers

Better bounds on finite-order Grothendieck constants

Sébastien Designolle, Tamás Vértesi, Sebastian Pokutta

arXiv:2409.03739Sep 5, 20240 citations

Bell inequalities and the Grothendieck-Tsirelson inequality

Guillaume Aubrun, Stanisław Szarek

Mathematical surveys and monographsAug 30, 20170 citations

Grothendieck bound in a single quantum system

Apostol Vourdas

arXiv:2212.11663Journal of Physics A Mathematical and TheoreticalOct 27, 20226 citations

Tracing the bounds on Bell-type inequalities

Stefan Filipp, Karl Svozil

Jan 1, 20049 citations

Bell's inequality, random sequence, and quantum key distribution (3 pages)

Won-Young Hwang

Physical Review AJan 1, 20050 citations

The communication complexity of non-signaling distributions

Julien Degorre, Marc Kaplan, Sophie Laplante +1 more

Quantum Information and ComputationJul 1, 201111 citations

SIAM Journal on Discrete Mathematics

Bell Inequalities, Grothendieck’s Constant, and Root Two

P. C. Fishburn, James A. Reeds

Published Feb 1, 1994• 50 citations

Publisher

Abstract

B. S. Tsirelson showed that comparisons between probabilities in “classical” physics and probabilities in quantum mechanics yield discrepancy measures

K_n

for finite

n \times n

real matrices that approach Grothendieck’s constant

K_G

as n gets large. It is known that

K_2 = K_3 = \sqrt{2}

and that

K_G \geq \pi /2 = 1.57 \cdots

, but examples of

n \times n

matrices for specified n that demonstrate

K_n > \sqrt{2}

have eluded researchers. A series of elementary examples are provided, which yield lower bounds on

K_{k ( k - 1 )}

that approach 3/2 as k gets large. A uniform change along the main diagonal of our basic example shows that

K_{20} \geqq = 10/7 = 1.42 \cdots

DOI: 10.1137/s0895480191219350

Related papers

Better bounds on finite-order Grothendieck constants

Sébastien Designolle, Tamás Vértesi, Sebastian Pokutta

Grothendieck constants $K_G(d)$ bound the advantage of $d$ -dimensional strategies over $1$ -dimensional ones in a specific optimisation task. They have applications ranging from approximation algorithms to quantum nonlocality. However, apart from $d=2$ , their values are unknown. Here, we exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some of these constants. The complete proof relies on solving difficult binary quadratic optimisation problems. For $d\in\{3,4,5\}$ , we construct specific rectangular instances that we can solve to certify better bounds than those previously known; by monotonicity, our lower bounds improve on the state of the art for $d\leqslant9$ . For $d\in\{4,7,8\}$ , we exploit elegant structures to build highly symmetric instances achieving even greater bounds; however, we can only solve them heuristically. We also recall the standard relation with violations of Bell inequalities and elaborate on it to interpret generalised Grothendieck constants $K_G(d\mapsto2)$ as the advantage of complex $d$ -dimensional quantum mechanics over real qubit quantum mechanics. Motivated by this connection, we also improve the bounds on $K_G(d\mapsto2)$ .Grothendieck constants $K_G(d)$ bound the advantage of $d$-dimensional strategies over $1$-dimensional ones in a specific optimisation task. They have applications ranging from approximation algorithms to quantum nonlocality. However, apart from $d=2$, their values are unknown. Here, we exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some of these constants. The complete proof relies on solving difficult binary quadratic optimisation problems. For $d\in\{3,4,5\}$, we construct specific rectangular instances that we can solve to certify better bounds than those previously known; by monotonicity, our lower bounds improve on the state of the art for $d\leqslant9$. For $d\in\{4,7,8\}$, we exploit elegant structures to build highly symmetric instances achieving even greater bounds; however, we can only solve them heuristically. We also recall the standard relation with violations of Bell inequalities and elaborate on it to interpret generalised Grothendieck constants $K_G(d\mapsto2)$ as the advantage of complex $d$-dimensional quantum mechanics over real qubit quantum mechanics. Motivated by this connection, we also improve the bounds on $K_G(d\mapsto2)$.

arXiv:2409.03739Sep 5, 20240 citations

Bell inequalities and the Grothendieck-Tsirelson inequality

Guillaume Aubrun, Stanisław Szarek

Mathematical surveys and monographsAug 30, 20170 citations

Grothendieck bound in a single quantum system

Apostol Vourdas

Abstract Grothendieck’s bound is used in the context of a single quantum system, in contrast to previous work which used it for multipartite entangled systems and the violation of Bell-like inequalities. Roughly speaking the Grothendieck theorem considers a ‘classical’ quadratic form C that uses complex numbers in the unit disc, and takes values less than 1. It then proves that if the complex numbers are replaced with vectors in the unit ball of the Hilbert space, then the ‘quantum’ quadratic form Q might take values greater than 1, up to the complex Grothendieck constant k G . The Grothendieck theorem is reformulated here in terms of arbitrary matrices (which are multiplied with appropriate normalisation prefactors), so that it is directly applicable to quantum quantities. The emphasis in the paper is in the ‘Grothendieck region’ ( 1 , k G ) , which is a classically forbidden region in the sense that C cannot take values in it. Necessary (but not sufficient) conditions for Q taking values in the Grothendieck region are given. Two examples that involve physical quantities in systems with six and 12-dimensional Hilbert space, are shown to lead to Q in the Grothendieck region ( 1 , k G ) . They involve projectors of the overlaps of novel generalised coherent states that resolve the identity and have a discrete isotropy.Abstract Grothendieck’s bound is used in the context of a single quantum system, in contrast to previous work which used it for multipartite entangled systems and the violation of Bell-like inequalities. Roughly speaking the Grothendieck theorem considers a ‘classical’ quadratic form C that uses complex numbers in the unit disc, and takes values less than 1. It then proves that if the complex numbers are replaced with vectors in the unit ball of the Hilbert space, then the ‘quantum’ quadratic form Q might take values greater than 1, up to the complex Grothendieck constant k G . The Grothendieck theorem is reformulated here in terms of arbitrary matrices (which are multiplied with appropriate normalisation prefactors), so that it is directly applicable to quantum quantities. The emphasis in the paper is in the ‘Grothendieck region’ ( 1 , k G ) , which is a classically forbidden region in the sense that C cannot take values in it. Necessary (but not sufficient) conditions for Q taking values in the Grothendieck region are given. Two examples that involve physical quantities in systems with six and 12-dimensional Hilbert space, are shown to lead to Q in the Grothendieck region ( 1 , k G ) . They involve projectors of the overlaps of novel generalised coherent states that resolve the identity and have a discrete isotropy.

arXiv:2212.11663Journal of Physics A Mathematical and TheoreticalOct 27, 20226 citations

Tracing the bounds on Bell-type inequalities

Stefan Filipp, Karl Svozil

Bell-type inequalities and violations thereof reveal the fundamental differences between standard probability theory and its quantum counterpart. In the course of previous investigations ultimate bounds on quantum mechanical violations have been found. For example, Tsirelson's bound constitutes a global upper limit for quantum violations of the Clauser-Horne-Shimony-Holt (CHSH) and the Clauser-Horne (CH) inequalities. Here we investigate a method for calculating the precise quantum bounds on arbitrary Bell-type inequalities by solving the eigenvalue problem for the operator associated with each Bell-type inequality. Thereby, we use the min-max principle to calculate the norm of these self-adjoint operators from the maximal eigenvalue yielding the upper bound for a particular set of measurement parameters. The eigenvectors corresponding to the maximal eigenvalues provide the quantum state for which a Bell-type inequality is maximally violated.Bell-type inequalities and violations thereof reveal the fundamental differences between standard probability theory and its quantum counterpart. In the course of previous investigations ultimate bounds on quantum mechanical violations have been found. For example, Tsirelson's bound constitutes a global upper limit for quantum violations of the Clauser-Horne-Shimony-Holt (CHSH) and the Clauser-Horne (CH) inequalities. Here we investigate a method for calculating the precise quantum bounds on arbitrary Bell-type inequalities by solving the eigenvalue problem for the operator associated with each Bell-type inequality. Thereby, we use the min-max principle to calculate the norm of these self-adjoint operators from the maximal eigenvalue yielding the upper bound for a particular set of measurement parameters. The eigenvectors corresponding to the maximal eigenvalues provide the quantum state for which a Bell-type inequality is maximally violated.

Jan 1, 20049 citations

Bell's inequality, random sequence, and quantum key distribution (3 pages)

Won-Young Hwang

Physical Review AJan 1, 20050 citations

The communication complexity of non-signaling distributions

Julien Degorre, Marc Kaplan, Sophie Laplante +1 more

We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input $x$ , Bob gets an input $y$ , and their goal is to each produce an output $a,b$ distributed according to some pre-specified joint distribution $p(a,b|x,y)$ . Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.We study a model of communication complexity that encompasses many well-studied problems, including classical and quantum communication complexity, the complexity of simulating distributions arising from bipartite measurements of shared quantum states, and XOR games. In this model, Alice gets an input $x$, Bob gets an input $y$, and their goal is to each produce an output $a,b$ distributed according to some pre-specified joint distribution $p(a,b|x,y)$. Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.

Quantum Information and ComputationJul 1, 201111 citations

B. S. Tsirelson showed that comparisons between probabilities in “classical” physics and probabilities in quantum mechanics yield discrepancy measures

K_n

for finite

n \times n

real matrices that approach Grothendieck’s constant

K_G

as n gets large. It is known that

K_2 = K_3 = \sqrt{2}

and that

K_G \geq \pi /2 = 1.57 \cdots

, but examples of

n \times n

matrices for specified n that demonstrate

K_n > \sqrt{2}

have eluded researchers. A series of elementary examples are provided, which yield lower bounds on

K_{k ( k - 1 )}

that approach 3/2 as k gets large. A uniform change along the main diagonal of our basic example shows that

K_{20} \geqq = 10/7 = 1.42 \cdots

Grothendieck constants

K_G(d)

bound the advantage of

d

-dimensional strategies over

1

-dimensional ones in a specific optimisation task. They have applications ranging from approximation algorithms to quantum nonlocality. However, apart from

d=2

, their values are unknown. Here, we exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some of these constants. The complete proof relies on solving difficult binary quadratic optimisation problems. For

d\in\{3,4,5\}

, we construct specific rectangular instances that we can solve to certify better bounds than those previously known; by monotonicity, our lower bounds improve on the state of the art for

d\leqslant9

. For

d\in\{4,7,8\}

, we exploit elegant structures to build highly symmetric instances achieving even greater bounds; however, we can only solve them heuristically. We also recall the standard relation with violations of Bell inequalities and elaborate on it to interpret generalised Grothendieck constants

K_G(d\mapsto2)

as the advantage of complex

d

-dimensional quantum mechanics over real qubit quantum mechanics. Motivated by this connection, we also improve the bounds on

K_G(d\mapsto2)

x

, Bob gets an input

y

, and their goal is to each produce an output

a,b

distributed according to some pre-specified joint distribution

p(a,b|x,y)

. Our results apply to any non-signaling distribution, that is, those where Alice's marginal distribution does not depend on Bob's input, and vice versa.~~~By taking a geometric view of the non-signaling distributions, we introduce a simple new technique based on affine combinations of lower-complexity distributions, and we give the first general technique to apply to all these settings, with elementary proofs and very intuitive interpretations. Specifically, we introduce two complexity measures, one which gives lower bounds on classical communication, and one for quantum communication. These measures can be expressed as convex optimization problems. We show that the dual formulations have a striking interpretation, since they coincide with maximum violations of Bell and Tsirelson inequalities. The dual expressions are closely related to the winning probability of XOR games. Despite their apparent simplicity, these lower bounds subsume many known communication complexity lower bound methods, most notably the recent lower bounds of Linial and Shraibman for the special case of Boolean functions. We show that as in the case of Boolean functions, the gap between the quantum and classical lower bounds is at most linear in the size of the support of the distribution, and does not depend on the size of the inputs. This translates into a bound on the gap between maximal Bell and Tsirelson inequality violations, which was previously known only for the case of distributions with Boolean outcomes and uniform marginals. It also allows us to show that for some distributions, information theoretic methods are necessary to prove strong lower bounds. ~~~ Finally, we give an exponential upper bound on quantum and classical communication complexity in the simultaneous messages model, for any non-signaling distribution. One consequence of this is a simple proof that any quantum distribution can be approximated with a constant number of bits of communication.