Exact classical bounds of bipartite correlation Bell inequalities using improved branch-and-bound

We present an improved branch-and-bound (IBB) algorithm for the exact computation of classical (local) bounds of bipartite correlation Bell inequalities. We strengthen pruning in the standard BB algorithm in two ways: a heuristic search based on see-saw iteration supplies a strong initial lower bound, and greedy row reordering of the Bell matrix reduces the tail bounds used during the exact search. An OpenMP implementation combines these improvements with shared-memory parallelism and dynamic work redistribution. Random-matrix benchmarks show substantial runtime reductions in matrix sizes, while explicit constructions demonstrate exact local-bound computations for square matrices up to $130 \times 130$ and rectangular matrices of sizes up to $81 \times 321$. Applications provide improved lower bounds on finite-order Grothendieck constants for $d=3,4,5,7$ and uniform-input XOR games with quantum-to-classical ratios exceeding $\sqrt2$. The method retains an exponential worst-case search for this NP-hard optimization problem, and its practical performance depends on matrix structure and tail-bound preprocessing depth.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22893
Primary Topic
Quantum Mechanics and Applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Exact classical bounds of bipartite correlation Bell inequalities using improved branch-and-bound

István Márton, Tamás Vértesi, Péter Diviánszky, Erika Bene
arXiv (Cornell University)
Quantum Mechanics and Applications
preprint

Exact classical bounds of bipartite correlation Bell inequalities using improved branch-and-bound

István Márton, Tamás Vértesi, Péter Diviánszky, Erika Bene
preprint en

Abstract

We present an improved branch-and-bound (IBB) algorithm for the exact computation of classical (local) bounds of bipartite correlation Bell inequalities. We strengthen pruning in the standard BB algorithm in two ways: a heuristic search based on see-saw iteration supplies a strong initial lower bound, and greedy row reordering of the Bell matrix reduces the tail bounds used during the exact search. An OpenMP implementation combines these improvements with shared-memory parallelism and dynamic work redistribution. Random-matrix benchmarks show substantial runtime reductions in matrix sizes, while explicit constructions demonstrate exact local-bound computations for square matrices up to $130 \times 130$ and rectangular matrices of sizes up to $81 \times 321$. Applications provide improved lower bounds on finite-order Grothendieck constants for $d=3,4,5,7$ and uniform-input XOR games with quantum-to-classical ratios exceeding $\sqrt2$. The method retains an exponential worst-case search for this NP-hard optimization problem, and its practical performance depends on matrix structure and tail-bound preprocessing depth.

arXiv (Cornell University)
Quantum Mechanics and Applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon