In Bell scenarios with two outcomes per party, we algorithmically consider the two sides of the membership problem for the local polytope: constructing local models and deriving separating hyperplanes, that is, Bell inequalities. We take advantage of the recent developments in so-called Frank-Wolfe algorithms to significantly increase the convergence rate of existing techniques.
With this method, we study the threshold value for the nonlocality of two-qubit Werner states under projective measurements. As already noticed by Tsirelson, this quantity is the inverse of the Grothendieck constant of order three, for which we refine the existing bounds. We further apply the method to improve the bounds on Grothendieck constants of higher orders. These constants are approximation factors of the rank-constrained SDP relaxations of the Max-Cut problem, a connection that we discuss in more details throughout the presentation.
We also study multipartite Bell scenarios, especially a symmetric case involving the Green-Horne-Zeilinger state. For this instance, we exploit the symmetry to drastically accelerate the computation of (i) a Bell inequality via Frank-Wolfe algorithms, and (ii) the corresponding local bound. We compute the detection efficiency of our inequalities and show that some give rise to activation of nonlocality in star networks, a property that was only shown before with an infinite number of measurements.

Finding a high (or low) energy state of quantum local Hamiltonians is fundamental physical problem and a potential area to gain a provable and practical quantum advantage. A recent line of work has focused on developing approximation algorithms for Quantum Max Cut, a quantum local Hamiltonian analogue of Max Cut, using non-commutative sum of squares (ncSoS) hierarchies. I will describe a simple ncSoS-based classical approximation algorithm for Quantum Max Cut achieving an approximation ratio of 0.595, outperforming the previous best algorithms of Lee (0.562, generic input graph) and King (0.582, triangle-free input graph). The algorithm is based on finding a maximum weight matching of the input graph and outputs a product of at most 2-qubit states, which is simpler than the fully entangled output states produced by the previous best algorithms. The analysis leverages monogamy of entanglement inequalities satisfied by ncSoS solutions as well as connections to the matching polytope.

The noncommutative sum-of-squares (ncSoS) hierarchy was introduced by Navascues--Pironio--Acin as a sequence of semidefinite programming relaxations for approximating values of "noncommutative polynomial optimization problems," which were originally intended to generalize quantum values of nonlocal games. Recent work has started to analyze the hierarchy for approximating ground energies of local Hamiltonians, initially through rounding algorithms which output product states for degree-2 ncSoS. Some rounding methods are known which output entangled states, but they use degree-4 ncSoS. Based on this, Hwang--Neeman--Parekh--Thompson--Wright conjectured that degree-2 ncSoS cannot beat product state approximations for quantum max-cut and gave a partial proof relying on a conjectural generalization of Borrell's inequality. In this talk we will describe the ncSoS hierarchy and a family of Hamiltonians (called the quantum rotor model in condensed matter literature or lattice O(n) vector model in QFT) over an infinite-dimensional local Hilbert space, and sketch a proof that a degree-2 ncSoS relaxation approximates the ground energy better than any product state.

The Quantum Max Cut (QMC) problem has emerged as a test-problem for designing approximation algorithms for local Hamiltonian problems. In this talk I’ll describe an approaches to solving this problem (approximately and exactly) using the relationship between the quantum max cut Hamiltonian and the representation theory of the symmetric group. The first major result I’ll describe is an extension of non-commutative Sum of Squares (ncSoS) optimization techniques to give a new hierarchy of relaxations to Quantum Max Cut. This hierarchy is based on optimizations over polynomials in the qubit swap operators. This is in contrast to the “standard” quantum Lasserre Hierarchy, which is based on polynomials expressed in terms of the Pauli matrices. The second major result covered will be a polynomial-time algorithm that exactly computes the maximum eigenvalue of the QMC Hamiltonian for certain graphs, including graphs that can be “decomposed” as a signed combination of cliques. A special case of the latter are complete bipartite graphs with uniform edge-weights, for which exact solutions are known from the work of Lieb and Mattis [LM62]. Our methods, which use representation theory of the symmetric group, can be seen as a generalization of the Lieb-Mattis result.