Optimal Sufficient Requirements on the Embedded Ising Problem in Polynomial Time

• URL: http://arxiv.org/abs/2302.04162v1
• Date: Wed, 8 Feb 2023 16:13:55 GMT
• Title: Optimal Sufficient Requirements on the Embedded Ising Problem in Polynomial Time
• Abstract summary: We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. This allows to formulate provably equivalent embedded Ising problems in a practical setup.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: One of the central applications for quantum annealers is to find the solutions of Ising problems. Suitable Ising problems, however, need to be formulated such that they, on the one hand, respect the specific restrictions of the hardware and, on the other hand, represent the original problems which shall actually be solved. We evaluate sufficient requirements on such an embedded Ising problem analytically and transform them into a linear optimization problem. With an objective function aiming to minimize the maximal absolute problem parameter, the precision issues of the annealers are addressed. Due to the redundancy of several constraints, we can show that the formally exponentially large optimization problem can be reduced and finally solved in polynomial time for the standard embedding setting where the embedded vertices induce trees. This allows to formulate provably equivalent embedded Ising problems in a practical setup.

Related papers

• Quantum Annealing for the Set Splitting Problem [0.0]
  I present a novel use of quantum annealing to solve the Set Splitting Problem using (QUBO) problem formulation.<n>The contribution of the work is in formulating penalty functions that ensure the ground state of the QUBO Hamiltonian corresponds to valid solutions that split the input subsets.<n> Empirical tests of the proposed solution show convergence to globally optimal solutions, with high accuracy rates over repeated trials.
  arXiv  Detail & Related papers  (2025-08-08T15:55:30Z)
• Adaptive Graph Shrinking for Quantum Optimization of Constrained Combinatorial Problems [4.266376725904727]
  We propose a hybrid classical--quantum framework based on graph shrinking to reduce the number of variables and constraints in QUBO formulations of optimization problems.<n>Our approach improves solution feasibility, reduces repair complexity, and enhances quantum optimization quality on hardware-limited instances.
  arXiv  Detail & Related papers  (2025-06-17T07:11:48Z)
• Towards graph neural networks for provably solving convex optimization problems [5.966097889241178]
  We propose an iterative MPNN framework to solve convex optimization problems with provable feasibility guarantees. Experimental results show that our approach outperforms existing neural baselines in solution quality and feasibility.
  arXiv  Detail & Related papers  (2025-02-04T16:11:41Z)
• Solving the Product Breakdown Structure Problem with constrained QAOA [0.0]
  We present a method for solving the industry relevant Product Breakdown Structure problem. Our solution is based on constrained QAOA, which by construction never explores the part of the Hilbert space that represents solutions forbidden by the problem constraints. We experimentally show that this approach has not only a very favorable scaling behavior, but also appears to suppress the negative effects of Barren Plateaus.
  arXiv  Detail & Related papers  (2024-06-21T15:15:02Z)
• Multiobjective variational quantum optimization for constrained problems: an application to Cash Management [45.82374977939355]
  We introduce a new method for solving optimization problems with challenging constraints using variational quantum algorithms. We test our proposal on a real-world problem with great relevance in finance: the Cash Management problem. Our empirical results show a significant improvement in terms of the cost of the achieved solutions, but especially in the avoidance of local minima.
  arXiv  Detail & Related papers  (2023-02-08T17:09:20Z)
• Sparse Polynomial Optimization: Theory and Practice [5.27013884159732]
  Book presents several efforts to tackle this challenge with important scientific implications. It provides alternative optimization schemes that scale well in terms of computational complexity. We present sparsity-exploiting hierarchies of relaxations, for either unconstrained or constrained problems.
  arXiv  Detail & Related papers  (2022-08-23T18:56:05Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Good and Bad Optimization Models: Insights from Rockafellians [0.0]
  In this tutorial, we'll discuss the opportunities and insights afforded by this broad perspective. In this tutorial, we'll discuss the opportunities and insights afforded by this broad perspective.
  arXiv  Detail & Related papers  (2021-05-13T04:31:42Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)
• Modeling Linear Inequality Constraints in Quadratic Binary Optimization for Variational Quantum Eigensolver [0.0]
  This paper introduces the use of tailored variational forms for variational quantum eigensolver. Four constraints that usually appear in several optimization problems are modeled. The main advantage of the proposed methodology is that the number of parameters on the variational form remain constant.
  arXiv  Detail & Related papers  (2020-07-26T23:36:22Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  We propose two novel conditional gradient-based methods for solving structured convex optimization problems. The most important feature of our framework is that only a subset of the constraints is processed at each iteration. Our algorithms rely on variance reduction and smoothing used in conjunction with conditional gradient steps, and are accompanied by rigorous convergence guarantees.
  arXiv  Detail & Related papers  (2020-07-07T21:26:35Z)

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.