First-order optimality conditions for non-commutative optimization problems

• URL: http://arxiv.org/abs/2311.18707v4
• Date: Fri, 22 Nov 2024 15:41:09 GMT
• Title: First-order optimality conditions for non-commutative optimization problems
• Authors: Mateus Araújo, Igor Klep, Andrew J. P. Garner, Tamás Vértesi, Miguel Navascués,
• Abstract summary: We consider the problem of optimizing the state average of a derivation of non-commuting variables. State optimality conditions are shown to be satisfied by all NPO problems. Operator optimality conditions are the non-commutative analogs of the Karush-Kuhn-Tucker conditions.
• Score: 0.0
• License:
• Abstract: We consider the problem of optimizing the state average of a polynomial of non-commuting variables, over all states and operators satisfying a number of polynomial constraints, and over all Hilbert spaces where such states and operators are defined. Such non-commutative polynomial optimization (NPO) problems are routinely solved through hierarchies of semidefinite programming (SDP) relaxations. By formulating the general NPO problem in Lagrangian terms, we heuristically derive first-order optimality conditions via small variations in the problem variables. Although the derivation is not rigorous, it gives rise to two types of optimality conditions - state and operator - which are rigorously analyzed in the paper. Both types of conditions can be enforced through additional positive semidefinite constraints in the SDP hierarchies. State optimality conditions are shown to be satisfied by all NPO problems. For NPO problems with optimal solutions (such as, e.g., Archimedean ones) they allow enforcing a new type of constraints: namely, restricting the optimization over states to the set of common ground states of an arbitrary number of operators. Operator optimality conditions are the non-commutative analogs of the Karush-Kuhn-Tucker (KKT) conditions, which are known to hold in many classical optimization problems. In this regard, we prove that a weak form of operator optimality holds for all NPO problems; stronger versions require the problem constraints to satisfy some qualification criterion, just like in the classical case (e.g. Mangasarian-Fromovitz constraint qualification). We test the power of the new optimality conditions by computing local properties of ground states of many-body spin systems and the maximum quantum violation of Bell inequalities.

Related papers

• One for All: Universal Quantum Conic Programming Framework for Hard-Constrained Combinatorial Optimization Problems [0.0]
  We present a unified quantum-classical framework for solving NP-complete constrained optimization problems. We show that QCP's parameterized ansatz class always captures the optimum within its generated subcone.
  arXiv  Detail & Related papers  (2024-11-01T08:00:30Z)
• 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)
• Non-commutative optimization problems with differential constraints [0.0]
  We study a variant of NPO problems where a subset of the operator variables satisfies a system of ordinary differential equations. This allows us to define a complete hierarchy of SDPs to tackle the original differential problem. We apply this method to extrapolate quantum time series in a semi-device-independent way.
  arXiv  Detail & Related papers  (2024-08-05T15:46:57Z)
• QSlack: A slack-variable approach for variational quantum semi-definite programming [5.0579795245991495]
  Quantum computers could provide a speedup over the best known classical algorithms. We show how to solve optimization problems involving semi-definite and linear programs. We show that our implementations of both the primal and dual for these problems approach the ground truth.
  arXiv  Detail & Related papers  (2023-12-06T19:00:01Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Constrained Optimization Involving Nonconvex $\ell_p$ Norms: Optimality Conditions, Algorithm and Convergence [4.886985244621422]
  We provide the calculation of the subgradients of the $ell_p$ norm and the normal cones of the $ell_p$ ball. We show that the sequential optimality conditions can be easily satisfied for iteratively reweighted algorithms.
  arXiv  Detail & Related papers  (2021-10-27T02:17:42Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Parity Quantum Optimization: Compiler [0.4194295877935867]
  We introduce parity quantum optimization with the aim of solving optimization problems consisting of arbitrary $k$-body interactions and side conditions. The method introduces a decomposition of the problem graph with arbitrary $k$-body terms using generalized closed cycles of a hypergraph.
  arXiv  Detail & Related papers  (2021-05-13T12:35:57Z)
• Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
  Motivated by recent increased interest in analysis of optimization algorithms for non- optimization in deep networks and other problems in data, we give an overview of recent results of theoretical optimization algorithms for non- optimization.
  arXiv  Detail & Related papers  (2020-12-11T08:28:51Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
  We show that families of algorithms fail to produce nearly optimal solutions with high probability. For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
  arXiv  Detail & Related papers  (2020-04-25T05:45:59Z)

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.