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)$.

arXiv comment12 pages, 1 figure

References in corpus (19)

• Bell nonlocality
• Grothendieck's constant and local models for noisy entangled quantum states
• More efficient Bell inequalities for Werner states
• Better local hidden variable models for two-qubit Werner states and an upper bound on the Grothendieck constant $K_G(3)$
• General method for constructing local-hidden-variable models for entangled quantum states
• Algorithmic construction of local hidden variable models for entangled quantum states
• Self-testing of Pauli observables for device-independent entanglement certification
• Bounding the dimension of bipartite quantum systems
• COSMO: A conic operator splitting method for convex conic problems
• Efficiency of higher dimensional Hilbert spaces for the violation of Bell inequalities
• A framework for the study of symmetric full-correlation Bell-like 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
• Grothendieck inequalities for semidefinite programs with rank constraint
• 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