Quantum approximate algorithm for NP optimization problems with constraints

• URL: http://arxiv.org/abs/2002.00943v1
• Date: Sat, 1 Feb 2020 04:45:41 GMT
• Title: Quantum approximate algorithm for NP optimization problems with constraints
• Authors: Yue Ruan, Samuel Marsh, Xilin Xue, Xi Li, Zhihao Liu, and Jingbo Wang
• Abstract summary: In this paper, we formalize different constraint types to equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme.
• Score: 12.294570891467604
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is an algorithmic framework for finding approximate solutions to combinatorial optimization problems, derived from an approximation to the Quantum Adiabatic Algorithm (QAA). In solving combinatorial optimization problems with constraints in the context of QAOA or QAA, one needs to find a way to encode problem constraints into the scheme. In this paper, we formalize different constraint types to linear equalities, linear inequalities, and arbitrary form. Based on this, we propose constraint-encoding schemes well-fitting into the QAOA framework for solving NP combinatorial optimization problems. The implemented algorithms demonstrate the effectiveness and efficiency of the proposed scheme by the testing results of varied instances of some well-known NP optimization problems. We argue that our work leads to a generalized framework for finding, in the context of QAOA, high-quality approximate solutions to combinatorial problems with various types of constraints.

Related papers

• 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)
• A two-phase-ACO algorithm for solving nonlinear optimization problems subjected to fuzzy relational equations [0.0]
  In this paper, we investigate nonlinear optimization problems whose constraints are defined as fuzzy relational equations (FRE) with feasible-min composition. The ability of an ant colony optimization algorithm (denoted by ACOR) to tackle algorithm problems and that of continuous ant colony optimization algorithm (denoted by ACO) to solve continuous optimization problems are discussed.
  arXiv  Detail & Related papers  (2024-05-17T09:24:07Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
  This paper studies first-order algorithms for solving fully composite optimization problems convex compact sets. We leverage the structure of the objective by handling differentiable and non-differentiable separately, linearizing only the smooth parts.
  arXiv  Detail & Related papers  (2023-02-24T18:41:48Z)
• A quantum-inspired tensor network method for constrained combinatorial optimization problems [5.904219009974901]
  We propose a quantum-inspired tensor-network-based algorithm for general locally constrained optimization problems. Our algorithm constructs a Hamiltonian for the problem of interest, effectively mapping it to a quantum problem. Our results show the effectiveness of this construction and potential applications.
  arXiv  Detail & Related papers  (2022-03-29T05:44:07Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• Quantum constraint learning for quantum approximate optimization algorithm [0.0]
  This paper introduces a quantum machine learning approach to learn the mixer Hamiltonian required to hard constrain the search subspace. One can directly plug the learnt unitary into the QAOA framework using an adaptable ansatz. We also develop an intuitive metric that uses Wasserstein distance to assess the performance of general approximate optimization algorithms with/without constraints.
  arXiv  Detail & Related papers  (2021-05-14T11:31:14Z)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.