We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of symmetries present in the problem. Using our formalism, we compute analytical sum-of-square certificates for various Bell inequalities, and prove a long-standing conjecture about the exact maximal quantum violation of the CGLMP inequalities for dimension 3 and 4. We also apply our technique to the Sliwa inequalities in the Bell scenario with three parties with binary measurements settings/outcomes. Symmetry reduction is key to scale the applications of the NPA relaxation, and our formalism encompasses and generalizes the approaches found in the literature.
We present a general framework to exploit the symmetries present in the Navascu{é}s-Pironio-Ac{í}n semidefinite relaxations that approximate invariant noncommutative polynomial optimization problems. We put equal emphasis on the moment and sum-of-squares dual approaches, and provide a pedagogical and formal introduction to the Navascu{é}s-Pironio-Ac{í}n technique before working out the impact of symmetries present in the problem. Using our formalism, we compute analytical sum-of-square certificates for various Bell inequalities, and prove a long-standing conjecture about the exact maximal quantum violation of the CGLMP inequalities for dimension 3 and 4. We also apply our technique to the Sliwa inequalities in the Bell scenario with three parties with binary measurements settings/outcomes. Symmetry reduction is key to scale the applications of the NPA relaxation, and our formalism encompasses and generalizes the approaches found in the literature.
The Navascués-Pironio-Acín (NPA) hierarchy provides a convergent sequence of semidefinite programming (SDP) relaxations for noncommutative polynomial optimisation, ubiquitous in quantum physics. However, its practical applicability is limited by the combinatorial growth in operator moments required at each level. Since not all moments contribute equally to bound tightness, selecting moments within a fixed computational budget is a relevant problem.
We reframe moment selection as combinatorial subset selection and show it is governed by strong higher-order synergistic interactions among moments, quantified through a marginal synergy diagnostic adapted from complex systems theory. We develop and compare three optimisation methods: Parallel Tempering (PT), an RBM-based reinforcement learning policy, and Bayesian Optimisation (BO). On the I3322 Bell inequality benchmark, all three substantially outperform greedy approaches at costs around two orders of magnitude below brute force, with the RBM achieving the closest approach to optimal throughout the hard transition regime.
We apply the framework to the 174 Bell inequalities in the (4,4,2,2) scenario, finding heterogeneous convergence behaviour across inequalities, and to the one-dimensional Heisenberg spin chain, demonstrating that physically motivated monomial bases are internally compressible and are not globally optimal in general. A budget-aware search over a broader pool improves certified bounds on long-range correlations by nearly two orders of magnitude. These results establish a scalable framework for moment selection in noncommutative polynomial optimisation, with broad applications across quantum physics and quantum information.
This talk focuses on optimization over state polynomials, i.e., polynomials in noncommuting variables and formal states of their products.An archimedean Positivstellensatz in the spirit of Putinar and Helton-McCullough is presented leading to a hierarchy of semidefinite relaxations converging monotonically to the optimum of a state polynomial subject to state constraints. This hierarchy can be seen as a state analog of the Lasserre hierarchy for optimization of polynomials, and the Navascués-Pironio-Acín scheme for optimization of noncommutative polynomials.The motivation behind this theory arises from the study of correlations in quantum networks. Determining the maximal quantum violation of a polynomial Bell inequality for an arbitrary network is reformulated as a state polynomial optimization problem. Several examples of quadratic Bell inequalities in the bipartite scenario are analyzed.To reduce the size of the semidefinite programs, sparsity, sign symmetry and conditional expectation of the observables' group structure are exploited.This is based on the joint work with Igor Klep, Jurij Volčič, and Jie Wang.
Abstract. Bell inequalities are pillars of quantum physics in that their violations imply that certain properties of quantum physics (e.g., entanglement) cannot be represented by any classical picture of physics. In this article Bell inequalities and their violations are considered through the lens of noncommutative polynomial optimization. Optimality of these violations is certified for a large majority of a set of standard Bell inequalities, denoted A2–A89 in the literature. The main techniques used in the paper include the NPA hierarchy, i.e., the noncommutative version of the Lasserre semidefinite programming (SDP) hierarchies based on the Helton–McCullough Positivstellensatz, the Gelfand–Naimark–Segal (GNS) construction with a novel use of the Artin–Wedderburn theory for rounding and projecting, and nonlinear programming (NLP). A new “Newton chip”-like technique for reducing sizes of SDPs arising in the constructed polynomial optimization problems is presented. This technique is based on conditional expectations. Finally, noncommutative Gröbner bases are exploited to certify when an optimizer (a solution yielding optimum violation) cannot be extracted from a dual SDP solution.
Semidefinite relaxations are widely used to compute upper bounds on the objective of optimization problems involving noncommutative polynomials. Such optimization problems are prevalent in quantum information. We present an algorithm able to discover automatically and exploit the symmetries present in the problem formulation. We also provide an open source software library written in Scala ( https://denisrosset.github.io/symdpoly ) that computes symmetry-adapted semidefinite relaxations with interfaces to a variety of open-source and commercial semidefinite solvers. We discuss the advantages of symmetrization, namely reductions in memory use, computation time, and increase in the solution precision.
We study and extend the semidefinite programming (SDP) hierarchies introduced in Navascu\'es and V\'ertesi [Phys. Rev. Lett. 115, 020501 (2015)] for the characterization of the statistical correlations arising from finite-dimensional quantum systems. First, we introduce the dimension-constrained noncommutative polynomial optimization (NPO) paradigm, where a number of polynomial inequalities are defined and optimization is conducted over all feasible operator representations of bounded dimensionality. Important problems in device-independent and semi-device-independent quantum information science can be formulated (or almost formulated) in this framework. We present effective SDP hierarchies to attack the general dimension-constrained NPO problem (and related ones) and prove their asymptotic convergence. To illustrate the power of these relaxations, we use them to derive a number of dimension witnesses for temporal and Bell-type correlation scenarios, and also to bound the probability of success of quantum random access codes.
A set of k orthonormal bases of Cd is called mutually unbiased if |⟨e,f⟩|2=1/d whenever e and f are basis vectors in distinct bases. A natural question is for which pairs (d,k) there exist k mutually unbiased bases in dimension d . The (well-known) upper bound k≤d+1 is attained when d is a power of a prime. For all other dimensions it is an open problem whether the bound can be attained. Navascués, Pironio, and Acín showed how to reformulate the existence question in terms of the existence of a certain C∗ -algebra. This naturally leads to a noncommutative polynomial optimization problem and an associated hierarchy of semidefinite programs. The problem has a symmetry coming from the wreath product of Sd and Sk .We exploit this symmetry (analytically) to reduce the size of the semidefinite programs making them (numerically) tractable. A key step is a novel explicit decomposition of the Sd≀Sk -module C([d]×[k])t into irreducible modules. We present numerical results for small d,k and low levels of the hierarchy. In particular, we obtain sum-of-squares proofs for the (well-known) fact that there do not exist d+2 mutually unbiased bases in dimensions d=2,3,4,5,6,7,8 . Moreover, our numerical results indicate that a sum-of-squares refutation, in the above-mentioned framework, of the existence of more than 3 MUBs in dimension 6 requires polynomials of total degree at least 12 .