⚛️ quantum physics

Better bounds on finite-order Grothendieck constants

This paper improves lower bounds on finite-order Grothendieck constants $K_G(d)$ for dimensions up to nine by constructing and solving specific optimization instances using a Frank-Wolfe approach, while also interpreting these constants as the advantage of complex $d$ -dimensional quantum mechanics over real qubit mechanics to refine bounds on $K_G(d\mapsto2)$ .

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

Published 2026-02-03

📖 4 min read🧠 Deep dive

CC BY 4.0

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

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, complex puzzle. You have two ways to approach it:

The Simple Way (1D): You can only look at the puzzle pieces one by one, in a straight line. It's easy to understand, but you might miss the big picture.
The Complex Way (d-Dimensional): You can look at the pieces from many angles at once, seeing how they twist and turn in a high-dimensional space. This is much harder to do, but it often reveals a solution that the simple way misses.

This paper is about measuring how much better the "Complex Way" is compared to the "Simple Way" for a specific type of mathematical puzzle. The authors call this measurement the Grothendieck Constant.

Here is a breakdown of what they did, using simple analogies:

The Core Problem: The "Gap"

Mathematicians have known for decades that the Complex Way is always better than the Simple Way, but they didn't know exactly by how much for most puzzle sizes.

For a 2-dimensional puzzle, we know the answer.
For puzzles with 3, 4, 5, or more dimensions, the answer was a mystery. We only had rough guesses (bounds), but no one knew the exact limit.

The Authors' Strategy: The "Frank-Wolfe" Hiker

To find better answers, the authors used a clever hiking strategy called the Frank-Wolfe algorithm.

The Analogy: Imagine you are standing on a hill (the complex solution) and you want to find the exact edge of a valley (the simple solution). You can't see the whole valley at once. So, you take a step, look around, and see which direction points most sharply away from the valley floor. You take another step in that direction.
The Innovation: The authors combined this hiking method with a powerful "map solver" (a computer program) to find the sharpest possible edge. This allowed them to construct specific, tricky puzzles where the Complex Way shines even brighter than previously thought.

The Results: New Records

The team managed to find new, higher "score limits" for puzzles of size 3, 4, and 5.

The "Rectangular" Trick: Usually, these puzzles are square (same number of rows and columns). The authors realized that by making the puzzles rectangular (tall and thin, or wide and short), they could trick the computer into solving the "Simple Way" part of the puzzle exactly, while still keeping the "Complex Way" part very strong.
The Outcome: They proved that for dimensions 3 through 9, the advantage of the Complex Way is actually larger than anyone had calculated before. They set new "world records" for the lower bounds of these constants.

The "Symmetry" Guess (Heuristics)

For some very specific, highly symmetrical puzzles (like those based on the shapes of 4D or 8D crystals), the authors found even better potential scores.

The Catch: These puzzles are so symmetrical and complex that their computer couldn't prove the answer was 100% correct. They had to use a "best guess" method (heuristics).
The Metaphor: It's like finding a treasure map that looks perfect and points to a spot where the gold must be, but you haven't dug deep enough to confirm it's there yet. They are confident these new scores are real, but they need someone else to do the final "digging" to prove it mathematically.

The Quantum Connection: Real vs. Complex

The paper also connects this math to Quantum Mechanics.

The Analogy: Imagine a quantum computer that can only use "Real Numbers" (like standard math) versus one that can use "Complex Numbers" (which include imaginary numbers, $i$ ).
The Finding: The authors showed that the "Complex Number" quantum computer has a distinct advantage over the "Real Number" one. They calculated exactly how much better the Complex version is for 3-dimensional quantum systems. They even found a strict "ceiling" (an upper bound) proving that the Complex version can't be too much better, narrowing the gap between the best and worst possible scenarios.

Summary

In short, this paper is a mathematical tour de force that:

Refined the map: It found better ways to measure the advantage of complex strategies over simple ones.
Broke records: It established new, higher minimum scores for how much better complex systems perform in dimensions 3 through 9.
Connected to physics: It clarified exactly how much more powerful complex quantum mechanics is compared to real quantum mechanics.

The authors didn't invent a new machine or cure a disease; they simply solved a very old, very difficult math riddle more precisely than anyone else has before, using a mix of clever geometry and powerful computer algorithms.

Technical Summary: Better bounds on finite-order Grothendieck constants

Problem Statement
The paper addresses the computation of finite-order Grothendieck constants, denoted $KG(d)$. These constants quantify the advantage of $d$ -dimensional strategies over 1-dimensional strategies in a specific optimization task involving tensor norms. While the infinite-order constant $KG$ and the case $d=2$ are well-studied, the values for $d \geq 3$ remain largely unknown. The primary challenge lies in finding matrices $M$ that maximize the ratio between the $d$ -dimensional semidefinite programming (SDP) value, $SDP_d(M)$ , and the 1-dimensional value, $SDP_1(M)$ (which is equivalent to the NP-hard MaxCut problem). Existing bounds for $d \in \{3, \dots, 9\}$ are loose, and finding suitable high-dimensional ansätze is hindered by the curse of dimensionality.

Methodology
The authors combine a recent projection technique based on Frank-Wolfe (FW) algorithms with powerful solvers for binary quadratic optimization. The methodology is divided into two main approaches:

Symmetric Instances (Heuristic & Analytical):
- The authors utilize highly symmetric line packings (e.g., root systems like $E_7, E_8$ , and polytopes like the 600-cell and 120-cell) to construct Gram matrices $P$ .
- They employ a Blended Pairwise Conditional Gradient (BPCG) algorithm to project $P$ onto the symmetrized correlation polytope $SDP_1$ . This process seeks to separate $P$ from $SDP_1$ via a hyperplane (a facet $A$ ).
- For symmetric structures, the dimension of the ambient space is reduced, allowing for the derivation of "putative" facets. However, computing the exact $SDP_1(A)$ for these large, symmetric instances is often intractable for exact solvers. Consequently, the authors use heuristic methods (alternating minimization/seesaw optimization) to estimate $SDP_1(A)$ , yielding lower bounds that are not rigorously certified but are highly suggestive.
Asymmetric Instances (Exact Certification):
- To obtain rigorously certified bounds, the authors construct rectangular matrices $M$ where the number of rows ( $m_1$ ) is small and columns ( $m_2$ ) is large. This reduces the complexity of the $SDP_1(M)$ computation (which is exponential in $m_1$ but linear in $m_2$ ).
- They use the Frank-Wolfe algorithm to find a separating hyperplane $M$ and then solve the resulting binary quadratic optimization problem (MaxCut) exactly using the branch-and-bound solver from [13] and the QuBowl solver from [39].
- For $d=3$ , they refine existing quantum strategies using the first level of the Lasserre hierarchy to slightly improve the lower bound.

Key Contributions and Results

Certified Lower Bounds for $d \in \{3, 4, 5\}$ :
The paper provides rigorously certified lower bounds that improve upon the state of the art (SoA) for $d=3, 4, 5$ . By the monotonicity of $KG(d)$, these improvements extend to all $d \leq 9$ .
- $KG(3) \geq 1.43670$ (improving on the previous $1.43665$).
- $KG(4) \geq 1.48579$ (improving on the previous $1.48217$).
- $KG(5) \geq 1.49339$ (improving on the previous $1.48217$).
- These results beat the best known bounds for $KG(d)$ up to $d=9$ .
Heuristic Bounds for Higher Dimensions:
Using highly symmetric structures (specifically the $E_7$ root system and the 120-cell), the authors derive heuristic lower bounds that are significantly higher than current SoA values.
- For $KG(7)$, the $E_7$ root system yields a heuristic bound of $\approx 1.4997$ , which is higher than the certified bound for $KG(5)$.
- For $KG(8)$, the 120-cell yields a heuristic bound of $\approx 1.5138$ .
- The authors note that while these bounds are currently heuristic due to the inability to solve the corresponding $SDP_1$ instances exactly, the underlying symmetric instances are provided for future work to potentially certify them.
Generalized Constants $KG(d \to 2)$ :
The authors extend their analysis to generalized Grothendieck constants $KG(d \to 2)$ , which relate to the advantage of complex $d$ -dimensional quantum mechanics over real qubit quantum mechanics.
- Lower Bounds: They provide numerical lower bounds for $KG(d \to 2)$ using the Lasserre hierarchy (level 2) to upper bound $SDP_2(M)$ . These bounds improve upon the state of the art for several dimensions (e.g., $d=3, 4, 5$ ).
- Upper Bound: They derive a rigorous analytical upper bound for $KG(3 \to 2) \leq 1.1233\dots$ using a decomposition method adapted from [14]. This is the first non-trivial upper bound for this specific constant.

Significance and Claims
The paper claims that by combining Frank-Wolfe projection techniques with advanced binary optimization solvers, it has successfully tightened the known lower bounds for finite-order Grothendieck constants in the range $3 \leq d \leq 9$ . The work highlights that while exact certification for highly symmetric, high-dimensional instances remains computationally difficult, the heuristic results suggest that the true values of these constants may be significantly higher than previously thought.

The authors emphasize the connection to quantum nonlocality, interpreting $KG(d \to 2)$ as the quantitative advantage of complex quantum mechanics over real quantum mechanics. Their rigorous upper bound on $KG(3 \to 2)$ provides a concrete limit on this advantage. The paper concludes that the provided instances and methods offer a pathway for future research to exploit symmetry to solve the remaining open quadratic optimization problems, potentially leading to bounds that could compete with the best known lower bound for the infinite-order Grothendieck constant ( $\approx 1.6769$ ).