Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems

• URL: http://arxiv.org/abs/2310.04542v2
• Date: Mon, 29 Apr 2024 17:52:55 GMT
• Title: Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems
• Authors: Einar Gabbassov, Gili Rosenberg, Artur Scherer,
• Abstract summary: We propose an approach to solving constrained optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an approach to solving constrained combinatorial optimization problems based on embedding the concept of Lagrangian duality into the framework of adiabatic quantum computation. Within the setting of circuit-model fault-tolerant quantum computation, we demonstrate that this approach achieves a quadratic improvement in circuit depth and maintains a constraint-independent circuit width in contrast to the prevalent approach of solving constrained problems via reformulations based on the quadratic unconstrained binary optimization (QUBO) framework. Our study includes a detailed review of the limitations encountered when using QUBO for constrained optimization. We show that the proposed method overcomes these limitations by encoding the optimal solution at an energetically elevated level of a simpler problem Hamiltonian, which results in substantially more resource-efficient quantum circuits. We consolidate our strategy with a detailed analysis on how the concepts of Lagrangian duality such as duality gap and complementary slackness relate to the success probability of sampling the optimal solution. Our findings are illustrated by benchmarking the Lagrangian dual approach against the QUBO approach using the NP-complete binary knapsack problem.

Related papers

• Subgradient Method using Quantum Annealing for Inequality-Constrained Binary Optimization Problems [0.4915744683251151]
  We show that inequality constraints can be relaxed into a similar objective function through statistical mechanics. We evaluate the performance of this method in a typical inequality-constrained optimization problem, the quadratic knapsack problem.
  arXiv  Detail & Related papers  (2024-11-11T11:59:50Z)
• Two-Step QAOA: Enhancing Quantum Optimization by Decomposing One-Hot Constraints in QUBO Formulations [0.0]
  We propose a simple approach, the Two-Step QAOA, which aims to improve the effectiveness of QAOA. By identifying and separating the problem into two stages, we transform soft constraints into hard constraints.
  arXiv  Detail & Related papers  (2024-08-09T23:38:28Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  This paper presents a hybrid framework that combines the use of standard Ising Hamiltonians to solve a subset of the constraints. The resolution of these non-Ising constraints is achieved through either penalty dephasing or the quantum Zeno effect.
  arXiv  Detail & Related papers  (2023-05-14T03:49:10Z)
• Quantum annealing with inequality constraints: the set cover problem [0.0]
  This paper presents two novel approaches for solving the set cover problem with multiple inequality constraints on quantum annealers. The first method uses the augmented Lagrangian approach to represent the constraints, while the second method employs a higher-order binary optimization (HUBO) formulation. Both approaches outperform the standard approach with slack variables for solving problems with inequality constraints on D-Wave quantum annealers.
  arXiv  Detail & Related papers  (2023-02-22T07:39:51Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  In this paper, we develop a simple yet efficient approach for the problem of comparing uncertain quantities. We recast inner optimization in the Lagrangian as a learning problem for surrogate approximation, which bypasses apparent intractability. The proposed light-SD demonstrates superior performance on several representative problems ranging from finance to supply chain management.
  arXiv  Detail & Related papers  (2022-11-14T21:54:31Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• 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)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• 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)
• Multi-block ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers [3.04585143845864]
  We present a decomposition-based approach to extend the applicability of current approaches to "quadratic plus convex" mixed binary optimization problems. We show that the alternating direction method of multipliers (ADMM) can split the MBO into a binary unconstrained problem (that can be solved with quantum algorithms) The validity of the approach is then showcased by numerical results obtained on several optimization problems via simulations with VQE and QAOA on the quantum circuits implemented in Qiskit.
  arXiv  Detail & Related papers  (2020-01-07T14:43:13Z)

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.