Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.14755

Moment Optimization in the Navascués-Pironio-Acín Hierarchy

Francesco Flora, Losel Matos, Tim Heightman, Tamás Kriváchy, Adan Garriga, Antonio Acín

quant-phSubmitted Jul 16, 2026• Announced Jul 17, 2026• 2 citations• Revised Oct 8, 2026 (v2)
v1 · Jul 16, 2026v2 · Oct 8, 2026
arXivHTMLPDF

Abstract

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 $I_{3322}$ 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.

Related papers

Noncommutative polynomial optimization under symmetry

Marie Ioannou, Denis Rosset

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.

arXiv:2112.10803•Dec 20, 2021•26 citations

Two convergent NPA-like hierarchies for the quantum bilocal scenario

Marc-Olivier Renou, Xiangling Xu, Laurens T. Ligthart

Characterising the correlations that arise from locally measuring a single part of a joint quantum system is one of the main problems of quantum information theory. The seminal work [M. Navascués et al., New J. Phys. 10, 073013 (2008)], known as the Navascués–Pironio–Acín (NPA) hierarchy, reformulated this question as a polynomial optimisation problem over noncommutative variables and proposed a convergent hierarchy of necessary conditions, each testable using semidefinite programming. More recently, the problem of characterising the quantum network correlations, which arise when locally measuring several independent quantum systems distributed in a network, has received considerable interest. Several generalisations of the NPA hierarchy, such as the scalar extension [A. Pozas-Kerstjens et al., Phys. Rev. Lett. 123, 140503 (2019)], were introduced while their converging sets remain unknown. In this work, we introduce a new bilocal factorisation NPA hierarchy, prove its equivalence to a modified bilocal scalar extension NPA hierarchy, and characterise its convergence in the case of the simplest network, the bilocal scenario. We further explore its relations with the other known generalisations.

arXiv:2210.09065•Journal of Mathematical Physics•Jan 1, 2026•13 citations

State polynomial optimization for nonlinear Bell inequalities

Victor Magron

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.

•Jul 29, 2024•0 citations

Semidefinite block-matrix relaxations for computing quantum correlations

Nicola D'Alessandro, Carles Roch i Carceller, Armin Tavakoli

Bounding the correlations predicted by quantum theory is an important challenge in quantum information science. Today's leading approach is semidefinite programming relaxations, but existing methods still cannot account for many relevant types of constraints. Here, we propose a semidefinite relaxation methodology that can incorporate a breadth of constraints needed in various quantum correlation problems, thereby generalising the seminal Navascués-Pironio-Acín hierarchy. It yields useful results at reasonable computational cost. We showcase the methodology and its features by using it to address five different quantum information problems. These are (i) entanglement witnessing from imperfect measurement devices, (ii) certifying measurements from fidelity-constrained sources, (iii) computing dimensionality in genuine multi-particle entangled states, (iv) benchmarking dimensionality for state preparation devices, and (v) finding uncertainty relations for nearly anti-commuting observables. These applications reflect both the usefulness and versatility of the methodology, as well as its potential for broader relevance in the field.

quant-pharXiv:2603.19388•Physical Review X•Mar 23, 2026•5 citations

An SU(2)-symmetric Semidefinite Programming Hierarchy for Quantum Max Cut

Jun Takahashi, Sankara Sai Chaithanya Rayudu, Cunlu Zhou +3 more

Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.

arXiv:2307.15688•Jul 28, 2023•27 citations

Characterizing finite-dimensional quantum behavior

Miguel Navascués, Adrien Feix, Mateus Araújo +1 more

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.

arXiv:1507.07521•Physical Review A•Oct 21, 2015•55 citations
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 I3322I_{3322}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)(4,4,2,2)(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.
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.
Characterising the correlations that arise from locally measuring a single part of a joint quantum system is one of the main problems of quantum information theory. The seminal work [M. Navascués et al., New J. Phys. 10, 073013 (2008)], known as the Navascués–Pironio–Acín (NPA) hierarchy, reformulated this question as a polynomial optimisation problem over noncommutative variables and proposed a convergent hierarchy of necessary conditions, each testable using semidefinite programming. More recently, the problem of characterising the quantum network correlations, which arise when locally measuring several independent quantum systems distributed in a network, has received considerable interest. Several generalisations of the NPA hierarchy, such as the scalar extension [A. Pozas-Kerstjens et al., Phys. Rev. Lett. 123, 140503 (2019)], were introduced while their converging sets remain unknown. In this work, we introduce a new bilocal factorisation NPA hierarchy, prove its equivalence to a modified bilocal scalar extension NPA hierarchy, and characterise its convergence in the case of the simplest network, the bilocal scenario. We further explore its relations with the other known generalisations.
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.
Bounding the correlations predicted by quantum theory is an important challenge in quantum information science. Today's leading approach is semidefinite programming relaxations, but existing methods still cannot account for many relevant types of constraints. Here, we propose a semidefinite relaxation methodology that can incorporate a breadth of constraints needed in various quantum correlation problems, thereby generalising the seminal Navascués-Pironio-Acín hierarchy. It yields useful results at reasonable computational cost. We showcase the methodology and its features by using it to address five different quantum information problems. These are (i) entanglement witnessing from imperfect measurement devices, (ii) certifying measurements from fidelity-constrained sources, (iii) computing dimensionality in genuine multi-particle entangled states, (iv) benchmarking dimensionality for state preparation devices, and (v) finding uncertainty relations for nearly anti-commuting observables. These applications reflect both the usefulness and versatility of the methodology, as well as its potential for broader relevance in the field.
Understanding and approximating extremal energy states of local Hamiltonians is a central problem in quantum physics and complexity theory. Recent work has focused on developing approximation algorithms for local Hamiltonians, and in particular the ``Quantum Max Cut'' (QMax-Cut) problem, which is closely related to the antiferromagnetic Heisenberg model. In this work, we introduce a family of semidefinite programming (SDP) relaxations based on the Navascues-Pironio-Acin (NPA) hierarchy which is tailored for QMaxCut by taking into account its SU(2) symmetry. We show that the hierarchy converges to the optimal QMaxCut value at a finite level, which is based on a new characterization of the algebra of SWAP operators. We give several analytic proofs and computational results showing exactness/inexactness of our hierarchy at the lowest level on several important families of graphs. We also discuss relationships between SDP approaches for QMaxCut and frustration-freeness in condensed matter physics and numerically demonstrate that the SDP-solvability practically becomes an efficiently-computable generalization of frustration-freeness. Furthermore, by numerical demonstration we show the potential of SDP algorithms to perform as an approximate method to compute physical quantities and capture physical features of some Heisenberg-type statistical mechanics models even away from the frustration-free regions.
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.