Better bounds on finite-order Grothendieck constants

Abstract

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⩽9$. 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\mapsto 2)$ 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\mapsto 2)$.

12 pages, 1 figure

References in corpus (10)

• Grothendieck's constant and local models for noisy entangled quantum states
• More efficient Bell inequalities for Werner states
• Efficiency of higher dimensional Hilbert spaces for the violation of Bell inequalities
• Generalized Clauser-Horne-Shimony-Holt inequalities maximally violated by higher dimensional systems
• Qutrit witness from the Grothendieck constant of order four
• Towards Grothendieck Constants and LHV Models in Quantum Mechanics
• Improved local models and new Bell inequalities via Frank-Wolfe algorithms
• Symmetric multipartite Bell inequalities via Frank-Wolfe algorithms
• Discovering Local Hidden-Variable Models for Arbitrary Multipartite Entangled States and Arbitrary Measurements
• Improved algorithms and novel applications of the FrankWolfe.jl library