In this paper, we prove that ${K}_{G}(3)<{K}_{G}(4)$, where ${K}_{G}(d)$ denotes the Grothendieck constant of order $d$. To this end, we use a branch-and-bound algorithm commonly used in the solution of NP-hard problems. It has recently been proven that ${K}_{G}(3)\ensuremath{\le}1.4644$. Here we prove that ${K}_{G}(4)\ensuremath{\ge}1.4841$, which has implications for device-independent witnessing dimensions greater than two. Furthermore, the algorithm with some modifications may find applications in various black-box quantum information tasks with large number of inputs and outputs.
In this paper, we prove that KG(3)<KG(4), where KG(d) denotes the Grothendieck constant of order d. To this end, we use a branch-and-bound algorithm commonly used in the solution of NP-hard problems. It has recently been proven that KG(3)\ensuremath≤1.4644. Here we prove that KG(4)\ensuremath≥1.4841, which has implications for device-independent witnessing dimensions greater than two. Furthermore, the algorithm with some modifications may find applications in various black-box quantum information tasks with large number of inputs and outputs.
Grothendieck constants KG(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⩽9. 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 KG(d↦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 KG(d↦2).
We relate the nonlocal properties of noisy entangled states to Grothendieck's constant, a mathematical constant appearing in Banach space theory. For two-qubit Werner states ${\ensuremath{\rho}}_{p}^{W}=p\ensuremath{\mid}{\ensuremath{\psi}}^{\ensuremath{-}}⟩⟨{\ensuremath{\psi}}^{\ensuremath{-}}\ensuremath{\mid}+(1\ensuremath{-}p)\mathbb{1}∕4$, we show that there is a local model for projective measurements if and only if $p\ensuremath{\leqslant}1∕{K}_{G}(3)$, where KG(3) is Grothendieck's constant of order 3. Known bounds on KG(3) prove the existence of this model at least for $p\ensuremath{\lesssim}0.66$, quite close to the current region of Bell violation, $p\ensuremath{\sim}0.71$. We generalize this result to arbitrary quantum states.
The Grothendieck constant KG is the smallest constant such that for every d ∈ N and every matrix A = (aij), sup u i,v j ∈B (d) X aij〈ui, vj 〉 � KG · ij sup x i,y j ∈[−1,1] X ij aijxiyj, where B (d) is the unit ball in R d. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (aij) and the objective is to maximize the quadratic form P ij aijxiyj over xi, yj ∈ [−1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping ” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: ◦ An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). ◦ We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
The Grothendieck constant KG is a fundamental quantity in functional analysis, with important connections to quantum information, combinatorial optimization, and the geometry of Banach spaces. Despite decades of study, the value of KG is unknown. The best known lower bound on KG was obtained independently by Davie and Reeds in the 1980s. In this paper we show that their bound is not optimal. We prove that KG≥KDR+10−12, where KDR denotes the Davie-Reeds lower bound.
Our argument is based on a perturbative analysis of the Davie-Reeds operator. We show that every near-extremizer for the Davie-Reeds problem has Ω(1) weight on its degree-3 Hermite coefficients, and therefore introducing a small cubic perturbation increases the integrality gap of the operator.
The Grothendieck constant KG is the smallest constant such that for every d ∊ ℕ and every matrix A = (aij), where B(d) is the unit ball in ℝd. Despite several efforts [15, 23], the value of the constant KG remains unknown. The Grothendieck constant KG is precisely the integrality gap of a natural SDP relaxation for the KM,N-Quadratic Programming problem. The input to this problem is a matrix A = (αij) and the objective is to maximize the quadratic form Σij aijxiyj over xi, yj ∊ [–1, 1]. In this work, we apply techniques from [22] to the KM,N-Quadratic Programming problem. Using some standard but non-trivial modifications, the reduction in [22] yields the following hardness result: Assuming the Unique Games Conjecture [9], it is NP-hard to approximate the KM,N-Quadratic Programming problem to any factor better than the Grothendieck constant KG. By adapting a “bootstrapping” argument used in a proof of Grothendieck inequality [5], we are able to perform a tighter analysis than [22]. Through this careful analysis, we obtain the following new results: An approximation algorithm for KM,N-Quadratic Programming that is guaranteed to achieve an approximation ratio arbitrarily close to the Grothendieck constant KG (optimal approximation ratio assuming the Unique Games Conjecture). We show that the Grothendieck constant KG can be computed within an error η, in time depending only on η. Specifically, for each η, we formulate an explicit finite linear program, whose optimum is η-close to the Grothendieck constant. We also exhibit a simple family of operators on the Gaussian Hilbert space that is guaranteed to contain tight examples for the Grothendieck inequality.
We propose candidate lower bounds on the real Grothendieck constants KG(d) and their infinite-dimensional limit KG using rotationally invariant cubic kernels. For the continuous construction, we identify an explicit threshold above which hemispherical binary strategies are unstable under cubic boundary deformations. Supported by numerical evidence, we conjecture that hemispherical strategies are globally optimal at this threshold. This conjecture would imply KG≥9π/16≃1.767146, improving the rigorous lower bound 6π/11≃1.713596. We also construct finite symmetric coefficient matrices from unit vectors in dimensions up to 24. Large-scale see-saw optimization supports the continuous predictions and suggests improved lower bounds on KG(d) in the studied dimensions from 4 to 24, conditional on the conjectured binary optima being exact. Selected matrices also yield finite-setting candidate dimension witnesses when interpreted as bipartite correlation Bell functionals. If the corresponding binary upper bounds hold, these witnesses would certify a local Hilbert-space dimension of at least five for each party.