Sums of squares certificates for polynomial moment inequalities

• URL: http://arxiv.org/abs/2306.05761v2
• Date: Fri, 10 May 2024 20:00:42 GMT
• Title: Sums of squares certificates for polynomial moment inequalities
• Authors: Igor Klep, Victor Magron, Jurij Volčič,
• Abstract summary: This paper introduces and develops the framework of moment expressions, which are expressions in commuting variables and their formal mixed moments. As an application, two open nonlinear Bell inequalities from quantum physics are settled.
• Score: 1.6385815610837167
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces and develops the algebraic framework of moment polynomials, which are polynomial expressions in commuting variables and their formal mixed moments. Their positivity and optimization over probability measures supported on semialgebraic sets and subject to moment polynomial constraints is investigated. A positive solution to Hilbert's 17th problem for pseudo-moments is given. On the other hand, moment polynomials positive on actual measures are shown to be sums of squares and formal moments of squares up to arbitrarily small perturbation of their coefficients. When only measures supported on a bounded semialgebraic set are considered, a stronger algebraic certificate for moment polynomial positivity is derived. This result gives rise to a converging hierarchy of semidefinite programs for moment polynomial optimization. Finally, as an application, two open nonlinear Bell inequalities from quantum physics are settled.

Related papers

• Spectral quantization of discrete random walks on half-line, and orthogonal polynomials on the unit circle [0.0]
  We represent unitary evolution operator of the quantum walk in terms of Verbs on the unit circle. We show that the both Markovs systems and their measures are connected by the classical SzegHo map.
  arXiv  Detail & Related papers  (2023-06-21T13:41:51Z)
• State polynomials: positivity, optimization and nonlinear Bell inequalities [3.9692590090301683]
  This paper introduces states in noncommuting variables and formal states of their products. It shows that states, positive over all and matricial states, are sums of squares with denominators. It is also established that avinetengle Kritivsatz fails to hold in the state setting.
  arXiv  Detail & Related papers  (2023-01-29T18:52:21Z)
• A Direct Reduction from the Polynomial to the Adversary Method [92.54311953850168]
  We give a simple and direct reduction from the method (in the form of a dual) to the adversary method. This shows that any lower bound in the form of a dual is an adversary lower bound of a specific form.
  arXiv  Detail & Related papers  (2023-01-24T21:37:20Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  We show that pointwise inequalities are turned into equalities within a class of nonnegative kSoS functions. We also show that focusing on pointwise equality constraints enables the use of scattering inequalities to mitigate the curse of dimensionality in sampling the constraints.
  arXiv  Detail & Related papers  (2023-01-16T10:30:04Z)
• Grothendieck inequalities characterize converses to the polynomial method [1.024113475677323]
  A surprising 'converse to the method' of Aaronson et al. (CCC16) shows that any bounded quadratic can be computed exactly by a 1-query up to a universal multiplicative factor related to the Grothendieck constant.
  arXiv  Detail & Related papers  (2022-12-16T16:26:04Z)
• Growth of entanglement of generic states under dual-unitary dynamics [77.34726150561087]
  Dual-unitary circuits are a class of locally-interacting quantum many-body systems. In particular, they admit a class of solvable" initial states for which, in the thermodynamic limit, one can access the full non-equilibrium dynamics. We show that in this case the entanglement increment during a time step is sub-maximal for finite times, however, it approaches the maximal value in the infinite-time limit.
  arXiv  Detail & Related papers  (2022-07-29T18:20:09Z)
• Progressive approximation of bound states by finite series of square-integrable functions [0.0]
  We use the "tridiagonal representation approach" to solve the time-independent Schr"odinger equation for bound states in a basis set of finite size.
  arXiv  Detail & Related papers  (2022-02-20T00:25:35Z)
• Dimension-free entanglement detection in multipartite Werner states [1.5771347525430772]
  Werner states are multipartite quantum states that are invariant under the diagonal conjugate action of the unitary group. This paper gives a complete characterization of their entanglement that is independent of the underlying local space. For every entangled Werner state there exists a dimension-free entanglement witness.
  arXiv  Detail & Related papers  (2021-08-19T14:41:09Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  We show that a piecewise discretization preserves better contrast from existing discretization problems. We apply this theory to the problem of matching two images.
  arXiv  Detail & Related papers  (2021-07-13T12:31:06Z)
• A refinement of Reznick's Positivstellensatz with applications to quantum information theory [72.8349503901712]
  In Hilbert's 17th problem Artin showed that any positive definite in several variables can be written as the quotient of two sums of squares. Reznick showed that the denominator in Artin's result can always be chosen as an $N$-th power of the squared norm of the variables.
  arXiv  Detail & Related papers  (2019-09-04T11:46:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.