Quantum estimates for classical polynomial optimization

• URL: http://arxiv.org/abs/2607.25445v2
• Date: Tue, 04 Aug 2026 04:01:54 GMT
• Title: Quantum estimates for classical polynomial optimization
• Abstract summary: The problem of finding bounds on tensors is both difficult and important given its applications to questions ranging from dynamical stability in complex landscapes to data analysis.<n>From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and largest eigenvalues of the coefficient corresponding to the given amount.<n>In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on Stricharts.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The problem of finding lower and upper bounds on multivariate homogeneous polynomials is both difficult and important given its applications to questions ranging from dynamical stability in complex potential landscapes to data analysis. From the standpoint of tensor eigenvalue theory, the question is equivalent to finding the smallest and the largest eigenvalues of the coefficient tensor corresponding to the given polynomial. Standard approaches outlined in the literature amount to running nonlinear iterations in search for the optimal rays along which the growth of the polynomial is fastest or slowest. Unlike the case of matrices (or their corresponding multivariate quadratic forms) convergence of such algorithms for higher-rank tensors is capricious due to the complex topography of polynomial objective functions. In this essay, a very different strategy, inspired by quantum-mechanical variational methods, is introduced for finding bounds on polynomials. The original polynomial is replaced by an operator acting in a suitably chosen (large) space of states, such that in an appropriate "classical" limit this operator approaches the original polynomial expression made of commutative variables. As a result, approximating the smallest and largest eigenvalues of the coefficient tensor, and thus finding bounds on polynomials, amounts to diagonalizing the resulting quantum operator, represented as a large matrix, and then inspecting the smallest and largest eigenvalues of this matrix. This approach is then successfully applied to standard test examples from tensor eigenvalue literature and other problems of interest in mathematical physics including Strichartz-type inequalities.

Related papers

• (MPO)$^2$: Multivariate Polynomial Optimization based on Matrix Product Operators [6.420068890493834]
  We introduce Multi Polynomial based on Matrix Product Operators (MPO)$2$, a framework that combines learned MPO feature embeddings with compact weight tensors.<n>Across regression and classification benchmarks, (MPO)$2$ improves over existing tensor decomposition based models and provides a flexible alternative for efficient function approximation.
  arXiv  Detail & Related papers  (2026-07-17T12:44:48Z)
• Nearly optimal polynomial approximations for the quantum singular value transform [0.0]
  We introduce approximations of the even and odd step functions on the interval $[-1,$] with simple Chebyshev coefficients.<n>We derive rigorous error bounds that are nearly optimal in the sense that their error deviates from the theoretically optimal error by a multiplicative factor.
  arXiv  Detail & Related papers  (2026-07-13T22:18:53Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• The moment polytope of matrix multiplication is not maximal [3.1593341358400737]
  We prove separations between the moment polytopes of matrix multiplication tensors and unit tensors.<n>As a consequence, we find that matrix multiplication moment polytopes are not maximal.<n>We extend these techniques to obtain a new proof of the optimal border subrank bound for matrix multiplication.
  arXiv  Detail & Related papers  (2025-03-28T17:25:06Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Entrywise error bounds for low-rank approximations of kernel matrices [55.524284152242096]
  We derive entrywise error bounds for low-rank approximations of kernel matrices obtained using the truncated eigen-decomposition. A key technical innovation is a delocalisation result for the eigenvectors of the kernel matrix corresponding to small eigenvalues. We validate our theory with an empirical study of a collection of synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2024-05-23T12:26:25Z)
• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction [55.57072563835959]
  We propose an eigenvalue correction strategy that can free filters from the constraints of repeated eigenvalue inputs.<n>Concretely, the proposed eigenvalue correction strategy enhances the uniform distribution of eigenvalues, and improves the fitting capacity and expressive power of filters.
  arXiv  Detail & Related papers  (2024-01-28T08:12:00Z)
• Quantum eigenvalue processing [0.0]
  Problems in linear algebra can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary transformations on eigenvalues of block-encoded non-normal operators. We also present a Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra.
  arXiv  Detail & Related papers  (2024-01-11T19:49:31Z)
• Covering Number of Real Algebraic Varieties and Beyond: Improved Bounds and Applications [8.438718130535296]
  We prove upper bounds on the covering number of numerous sets in Euclidean space.<n>We illustrate the power of the result on three computational applications.
  arXiv  Detail & Related papers  (2023-11-09T03:06:59Z)
• Dimension-free discretizations of the uniform norm by small product sets [45.85600902330814]
  A classical inequality of Bernstein compares the supremum norm of $f$ over the unit circle to its supremum norm over the sampling set of the $K$-th roots of unity.<n>We show that dimension-free discretizations are possible with sampling sets whose cardinality is independent of $deg(f)$ and is instead governed by the maximum individual degree of $f$.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• 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)

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.