PaperlayerView exact revision on arXiv

Source-linked AI summary

Convergent relaxations of polynomial optimization problems with non-commuting variables

Stefano Pironio, Miguel Navascues, Antonio Acin

arXiv:0903.4368v2math.OCquant-ph

TL;DR

The paper studies polynomial optimization with non-commuting variables motivated by quantum theory. It introduces convergent semidefinite-programming relaxations, a stopping criterion, and a constructive procedure for extracting a global minimizer.

  • Problem

    Polynomial optimization is formulated for non-commuting variables, motivated by quantum theory’s matrices and operators.

  • Method

    The paper develops a non-commutative version of Lasserre’s method using a hierarchy of semidefinite-programming relaxations.

  • Results

    The relaxation bounds form a monotonically increasing sequence converging to the global minimum p⋆.

  • Takeaways & Limitations

    A criterion detects when the global optimum is reached, and optimal SDP solutions yield an explicit global minimizer (H⋆, X⋆, φ⋆).

  • Takeaways & Limitations

    For commuting-variable instances, it is highly unlikely that relaxations up to a bounded order suffice to solve the problem.

Abstract

from arXiv · show

We consider optimization problems with polynomial inequality constraints in non-commuting variables. These non-commuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.

1 Introduction

The paper generalizes polynomial optimization to non-commuting operator variables on Hilbert spaces of unfixed dimension. It develops convergent SDP relaxations, finite-step optimality detection, and optimizer extraction, with applications in quantum information and chemistry.

  • Method: The approach generalizes Lasserre’s commutative hierarchy to constrained non-commutative polynomial optimization using SDP relaxations.When commutation constraints are imposed, the method reduces to Lasserre’s method.
  • Problem: The problem minimizes ⟨φ, p(X)φ⟩ over bounded operators, a normalized state, and a Hilbert space whose dimension is also optimized, subject to qi(X) ⪰0.Non-commuting variables satisfy xi xj ≠ xj xi in general.
  • Convergence: The SDP optima form a monotonically increasing sequence of lower bounds that converges to the global minimum p⋆ when feasible operators are bounded.The boundedness condition is expressed through C^2 − (X1 + · · · + Xn) ⪰0 for some C > 0.
  • Optimality and extraction: A criterion can detect when a finite relaxation already reaches p⋆ and then extract a global optimizer from that SDP solution.The extracted Hilbert space is finite-dimensional, with dimension determined by the rank of matrices in the relaxation.
  • Applications: The method has applications to Bell-inequality violations and atomic or molecular ground-state energies, with convergence usually fast and finite up to machine precision.The hierarchy extends earlier unconstrained non-commutative results to arbitrary constrained problems.

2 Notation and definitions

The paper works with free *-algebra polynomials in noncommuting variables and evaluates them on bounded operators, using operator positivity to formulate constraints.

  • Algebraic notation: Polynomials are finite linear combinations of words in 2n noncommuting variables x and x∗ over K ∈ {R, C}.The involution acts by conjugation on coefficients, adjoints on letters, and reversal with adjoints on words.
  • Algebraic notation: Words serve as monomials, with length defining degree and Wd containing all words of length at most d.The set K[x, x∗]d consists of polynomials of degree at most d.
  • Operator evaluation: Substituting bounded operators Xi for xi and their adjoints for x∗i produces an operator p(X).Hermitian polynomials evaluate to Hermitian operators.
  • Operator positivity: A Hermitian operator is positive semidefinite when ⟨φ, Oφ⟩ ≥ 0 for every vector φ in the Hilbert space.For Hermitian p(X), the quadratic form ⟨φ, p(X)φ⟩ is real.
  • Optimization problem: The optimization problem ranges over arbitrary Hilbert-space dimensions, bounded operator tuples, and normalized vectors subject to qi(X) ⪰ 0.The constraints are assumed feasible and are represented through the positivity domain SQ.
  • Optimization problem: The positivity domain SQ consists of operator tuples for which every constraint polynomial qi(X) is positive semidefinite.Its associated quadratic module MQ contains sums of Hermitian squares and constraint-weighted Hermitian squares; Archimedeanness ensures boundedness.

3 Main results

The main-results setup encodes operator optimization through moment sequences, moment matrices, and localizing matrices whose positivity reflects feasible operator representations.

  • Moment representations: A truncated sequence y assigns a scalar yw to every word w up to a specified degree and defines a linear functional Ly.Moment representations arise from normalized operator tuples and vectors.
  • Moment matrices: The moment matrix Mk(y) has rows and columns indexed by words in Wk, with entries determined by the sequence y.It captures quadratic expressions in words of length at most k.
  • Localizing matrices: For a polynomial q of degree d, the localizing matrix Mk(qy) is indexed by Wk and incorporates coefficients of q into its entries.The sequence must extend through degree 2k+d to define this matrix.
  • Positivity conditions: Any sequence admitting a moment representation satisfies y1 = 1 and Mk(y) ⪰ 0.If q(X) ⪰ 0 in the representation, then Mk−d(qy) ⪰ 0 for d = ⌈deg(q)/2⌉.

3.2 Convergent SDP relaxations

The paper constructs SDP relaxations from moment and localizing matrix positivity; under an Archimedean assumption, their optimal values increase to the original global optimum.

  • Relaxation construction: For sufficiently large k, the SDP relaxation Rk optimizes the objective over truncated sequences y subject to moment and localizing matrix positivity.The order must satisfy 2k ≥ max{deg(p), maxi deg(qi)}.
  • Lower bounds: Any feasible solution of the original operator problem yields a feasible point of every sufficiently large relaxation, so pk is a lower bound on p⋆.The relaxation objective values therefore satisfy pk ≤ p⋆.
  • Boundedness: Archimedeanness bounds feasible moment sequences and supports boundedness of the relaxation optima.The resulting coefficient bounds have the form |yw| ≤ C^|w| for words through the relevant degree.
  • Convergence: The relaxation values form a monotonically increasing bounded sequence, so the limit p̂ = limk→∞ pk exists.Monotonicity follows from the nesting of feasible moment and localizing constraints across relaxation orders.
  • Convergence: Theorem 1 establishes limk→∞ pk = p⋆ when MQ is Archimedean.A limiting sequence is used to construct, through a Gelfand–Naimark–Segal-like procedure, operators and a vector attaining the limiting value.

3.3 Optimality detection and extraction of optimizers

The paper gives a rank-based certificate for finite-step optimality: a flat moment-matrix condition implies the relaxation is globally optimal and enables optimizer extraction.

  • Optimality detection: When the rank condition holds, pk = p⋆, so the order-k relaxation already reaches the global optimum.The proof constructs a feasible operator solution with objective value pk, while relaxation feasibility gives pk ≤ p⋆.
  • Optimizer extraction: The same condition permits extraction of a global optimizer from the optimal moment sequence.The construction uses a Gram decomposition of the moment matrix and defines operators through their action on the resulting span.
  • Optimality detection: The criterion tests whether an optimal moment matrix satisfies rank Mk(yk) = rank Mk−d(yk).Here d = maxi di ≥ 1, with di = ⌈deg(qi)/2⌉ in the relaxation construction.
  • Optimizer extraction: The extracted optimizer can be chosen on a Hilbert space of dimension rank Mk−d(yk).The theorem identifies this rank as the dimension of H⋆.
  • Optimizer extraction: The extracted operators satisfy the original positivity constraints because the relevant constraint matrix is a positive-semidefinite submatrix of Mk−di(qiyk).This verifies qi(X) ⪰ 0 for each constraint.

3.4 Relation to the Positivstellensatz for non-commutative polynomials

The hierarchy’s convergence can alternatively be established through the non-commutative Positivstellensatz. This proof connects SDP lower bounds with positive-polynomial representations, while the earlier proof is more constructive and supports optimizer extraction.

  • Positivstellensatz connection: The SOS formulation is an SDP that is dual to Rk, so its optimum provides a lower bound on p⋆.The SOS expression uses polynomial squares and constraint-weighted terms.
  • Convergence proof: For every k, the relaxation values satisfy λk ≤ pk ≤ p⋆.The first inequality comes from feasibility relations between the primal and dual formulations.
  • Convergence proof: For any ϵ > 0, strict positivity of p(X) − (p⋆−ϵ) yields a Positivstellensatz representation at sufficiently large degree.Choosing k at least as large as the relevant polynomial degrees makes the representation feasible for the SDP.
  • Convergence proof: The resulting bounds p⋆−ϵ ≤ λk ≤ pk ≤ p⋆ imply pk → p⋆ as ϵ is arbitrary.Thus the SDP relaxation sequence converges to the global optimum.
  • Interpretation: The Positivstellensatz proof is conceptually connected to positive-polynomial theory, whereas the earlier proof is more constructive and inspires optimizer extraction.The paper presents the two proofs as somewhat equivalent but emphasizes their different perspectives.
  • Open direction: An a priori bound on the maximal SOS degree would provide information about the convergence speed of the relaxations.The paper identifies this degree bound as a route to convergence-rate information.

3.5 Dealing with equality constraints

Equality constraints can be incorporated algebraically by reducing polynomials modulo their ideal, which yields smaller SDP relaxations. In commuting settings, the same framework recovers Lasserre’s construction and gives specialized extraction and convergence observations.

  • Equality constraints: Equality constraints ei(X)=0 can be enforced by imposing both ei(X)⪰0 and −ei(X)⪰0, or exploited directly to reduce relaxation complexity.The paper favors using the equalities to work in the quotient ring K[x,x∗]/I.
  • Scope: The Positivstellensatz proof cited in the paper directly covers real-coefficient polynomials, while the complex case requires a straightforward generalization.The paper points to prior work for the complex extension.
  • Quotient-ring reduction: Working modulo the ideal I permits each polynomial to be represented using a monomial basis B of K[x,x∗]/I.At order k, the reduced basis is Bk=B∩Wk.
  • Quotient-ring reduction: The reduced relaxation uses variables indexed by B2k and moment and localizing matrices of sizes |Bk|×|Bk| and |Bk−di|×|Bk−di|.This reduction decreases the complexity of the original problem.
  • Hermitian variables: For hermitian variables, words use n generators rather than 2n, reducing the word count and correspondingly shrinking SDP variables and matrices.The word count is |Wd|=(n^(k+1)−1)/(n−1), compared with ((2n)^(k+1)−1)/(2n−1) in the general case.
  • Commuting variables: In the commutative specialization, imposing XiXj−XjXi=0 reduces the canonical basis to commutative monomials and reproduces Lasserre’s construction.The optimality-detection criterion also coincides with the commutative criterion.
  • Solution extraction: For commuting variables, extracted commuting matrices can be simultaneously diagonalized, with common eigenvalues corresponding to global solutions.The matrix dimension is r=rank Mk(yk), which relates to the number of extracted solutions.
  • Commuting variables: The non-commutative hierarchy may converge faster computationally than the commutative one, as illustrated by projection-operator problems.For quadratic problems with hermitian projection operators, the first-order relaxation already gives p1=p⋆; the same holds for arbitrary-degree polynomials evaluated over projection operators.

3.6 Generalization

The paper generalizes its non-commutative optimization framework by adding polynomial equalities and state-dependent positivity constraints, then defines corresponding SDP relaxations. Under an Archimedean assumption, these bounds converge, and a rank condition certifies exactness while enabling optimizer extraction.

  • Generalized problem: The generalized problem imposes qi(X) ⪰ 0, ri(X)φ = 0, and nonnegative expectation values for hermitian si(X).These constraints extend operator positivity with annihilation conditions and state-dependent inequalities.
  • SDP relaxation: The order-k relaxation is an SDP over moments indexed through degree 2k, with localizing constraints encoding polynomial equalities and inequalities.The construction uses moment vectors mk(ry) and requires 2k to cover the relevant polynomial degrees.
  • Convergence: The relaxed optima form monotone lower bounds: ˜pk ≤ ˜pk′ for k ≤ k′ and ˜pk ≤ ˜p⋆.Thus each relaxation remains a certified lower bound while tightening with order.
  • Convergence: Under the Archimedean condition on MQ, limk→∞˜pk = ˜p⋆.This establishes convergence of the generalized hierarchy to the global optimum.
  • Exactness and extraction: When the optimal moment solution satisfies the stated rank condition, ˜pk = ˜p⋆ and a global optimizer exists with dim H⋆ = rank Mk−d(yk).The proof reconstructs operators and a state satisfying the added equality and positivity constraints.
  • Dual certificates: The dual relaxation supplies a polynomial positivity certificate showing that the original optimum cannot be below the dual value.The certificate follows from the dual decomposition of p − ˜λk.

4 Illustration of the method

Examples illustrate the hierarchy, exactness criterion, optimizer extraction, dual certificates, and differences between non-commutative and commutative formulations. In the presented cases, low-order relaxations attain the global optima.

  • Basic example: The first example obtains p1 = −3/4 after rounding and p2 = −3/4 at second order.The associated moment matrices are used to test exactness.
  • Basic example: The rank condition holds because M1(y2) and M2(y2) both have rank 2, proving p⋆ = p2 = −3/4 and enabling a two-dimensional optimizer.The extracted optimizer is realized in a space of dimension 2.
  • Dual certificate: The dual SOS decomposition certifies ⟨φ, X1X2 + X2X1φ⟩ ≥ −3/4 for every feasible realization.The decomposition provides a lower-bound certificate for the original problem.
  • Commutative comparison: First-order commutative and non-commutative relaxations coincide because moment-matrix hermiticity implies y12 = y21.At higher order, the commutative formulation identifies monomials such as x1x2 and x2x1.
  • Commutative comparison: The commutative global minimum is higher than the non-commutative one because commutativity imposes an additional constraint.The comparison is illustrated through the second-order relaxation.
  • Additional constraints: With additional constraints, the first-order relaxation gives p1 = −2/3, while the rank condition proves p⋆ = p2 = −2/3 at second order.The first-order moment matrix has eigenvalues 0, 2/3, and 7/6; the second-order solution has two nonzero eigenvalues.

5 Applications

The hierarchy applies to quantum-information and many-body problems with operator constraints, including Bell inequalities and electronic-structure optimization. The passages report convergence, tight bounds, finite-order termination, and broader scope than fixed-dimensional parametrizations.

  • Bell inequalities: Bell-inequality optimization maximizes a linear expression in quantum joint probabilities represented as ⟨φ, EiEjφ⟩.Measurement operators for different subsystems commute, while each measurement forms an orthogonal resolution of identity.
  • Bell inequalities: The Bell-inequality SDP hierarchy converges because the associated quadratic module is Archimedean.The same relaxation sequence was introduced previously and is used to compute maximal violations.
  • Bell inequalities: Third-order relaxations produced upper bounds for 241 Bell inequalities, tight for all but 20, with small gaps for the remainder.These bounds address maximal quantum violations.
  • Bell inequalities: The hierarchy can decide whether a probability set admits a quantum representation and may support other quantum-information applications.The paper identifies this as a further use of the relaxation sequence.
  • Many-body systems: For fermionic systems, the hierarchy applies to degree-4 polynomial constraints and terminates at order N, yielding pN = p⋆.The operator algebra has a unique irreducible representation of dimension 2^M.
  • Many-body systems: The approach can compute ground-state electronic energies and extends beyond existing N-representability methods to other many-body systems.The paper mentions spin systems and systems with canonical relations, with adaptations required for unbounded operators.
  • Fixed-dimensional problems: For fixed Hilbert-space dimension, the method treats each matrix as one variable and offers lower bounds when explicit parametrization is impractical.It remains a relaxation because convergence to a solution with the prescribed dimension is not guaranteed.

Appendix A: Basics of semidefinite programming

The appendix introduces semidefinite programming through primal and dual formulations, feasibility, weak duality, and conditions for equality of optimal values. It also notes numerical software for solving both programs.

  • Primal problem: A semidefinite program optimizes a vector subject to a matrix-affine positive-semidefinite constraint.The problem parameters include matrices, scalars, and the vector of decision variables.
  • Dual problem: Each primal program has an associated dual semidefinite program whose variable is a matrix Z.Dual feasibility is defined by satisfying the dual matrix constraints.
  • Duality: The dual program provides bounds on the optimal primal value.This property underlies the use of dual solutions as certificates in the paper’s relaxations.
  • Duality: Weak duality guarantees d∗ ≤ p∗, while strict feasibility of the dual or primal is sufficient for d∗ = p∗.Strict feasibility means the relevant matrix inequality is positive definite.
  • Numerical solution: SeDuMi and YALMIP are example Matlab toolboxes that solve primal and dual SDPs simultaneously and provide accuracy bounds.The appendix cites these packages as available numerical solvers.

Appendix B: Duals of the SDP relaxations

The appendix derives dual formulations for the SDP relaxations and explains how their polynomial coefficients are represented through monomial bases and moment-matrix structure. It also extends the discussion from real to complex polynomial and SDP relaxations.

  • Dual formulation: The duals of the relaxations Rk are identified with corresponding polynomial optimization problems.The SDP relaxation is written in primal form, followed by its dual, with matrix dimensions specified for the variables.
  • Polynomial representation: Equality-constraint coefficients correspond to polynomial coefficients in the canonical monomial basis W2k = {w : |w| ≤2k}.The right-hand-side quantities tr(BwV) provide coefficients of a polynomial representation, while the matrices Bw are determined by monomial products.
  • Positive-semidefinite decomposition: Positive semidefinite dual matrices are decomposed spectrally to obtain sums involving degree-k polynomials.The decomposition uses nonnegative eigenvalues and corresponding eigenvectors, together with the symmetry of V.
  • Real and complex cases: The same dual structure extends to complex polynomials, while real free *-algebra relaxations use only real quantities.Complex cases may be handled by decomposing the SDP variables into real and imaginary parts.
Loading 0903.4368v2…