S. Designolle (Zuse Institute Berlin): Better bounds on Grothendieck constants of finite orders

Sébastien Designolle (Zuse Institute Berlin).
Better bounds on Grothendieck constants of finite orders.
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 ∈ {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 smaller than 10. For d ∈ {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 → 2) as the advantage of complex quantum mechanics over real quantum mechanics. Motivated by this connection, we also improved the bounds on K_G (d → 2).
Quantum Information and Quantum Computing Seminars CTP PAS
2024-10-30