betaFeedback

WorksPhysics and Astronomy

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

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×130130 \times 130 and rectangular matrices of sizes up to 81×32181 \times 321. Applications provide improved lower bounds on finite-order Grothendieck constants for d=3,4,5,7d=3,4,5,7 and uniform-input XOR games with quantum-to-classical ratios exceeding 2\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.

Paper details

vlnc:W_f3hbgwmm
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 6

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

LLM tools

View statement
Looking for related papers…