Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm

• URL: http://arxiv.org/abs/2307.08980v1
• Date: Tue, 18 Jul 2023 05:28:45 GMT
• Title: Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm
• Authors: Hui-Min Li, Jin-Min Liang, Zhi-Xi Wang, Shao-Ming Fei
• Abstract summary: Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for optimization problems. The Metropolis-Hassting warm-starting algorithm for QAOA is presented which can provably converge to the global optimal solutions.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum approximate optimization algorithm (QAOA) is a promising variational quantum algorithm for combinatorial optimization problems. However, the implementation of QAOA is limited due to the requirement that the problems be mapped to Ising Hamiltonians and the nonconvex optimization landscapes. Although the Ising Hamiltonians for many NP hard problems have been obtained, a general method to obtain the Ising Hamiltonians for constrained combinatorial optimization problems (CCOPs) has not yet been investigated. In this paper, a general method is introduced to obtain the Ising Hamiltonians for CCOPs and the Metropolis-Hastings warm-starting algorithm for QAOA is presented which can provably converge to the global optimal solutions. The effectiveness of this method is demonstrated by tackling the minimum weight vertex cover (MWVC) problem, the minimum vertex cover (MVC) problem, and the maximal independent set problem as examples. The Ising Hamiltonian for the MWVC problem is obtained first time by using this method. The advantages of the Metropolis-Hastings warm-starting algorithm presented here is numerically analyzed through solving 30 randomly generated MVC cases with 1-depth QAOA.

Related papers

• 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)
• Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm [1.3469999282609788]
  We focus on the generalized formulation of optimization problems defined on the sets of $n-element $d$-ary strings. Our main contribution encompasses dimension for the originally proposed QAOA. Restricting the algorithm to spaces of smaller dimension may lead to significant acceleration of both quantum and classical simulation of circuits.
  arXiv  Detail & Related papers  (2023-09-25T00:35:40Z)
• Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions [0.0]
  We study how the accuracy of approximate solutions affect the performance of the warm-start QAOA (WS-QAOA) We find that WS-QAOA tends to outperform QAOA as approximate solutions become closer to the exact solutions in terms of the Hamming distance. We also solve MAX-CUT problems by WS-QAOA with approximate solutions obtained via QAOA, having a better result than QAOA especially when the circuit is relatively shallow.
  arXiv  Detail & Related papers  (2022-09-07T05:26:48Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Iterative Quantum Optimization with Adaptive Problem Hamiltonian [19.4417702222583]
  We describe an iterative algorithm in which a solution obtained with such a restricted problem Hamiltonian is used to define a new problem Hamiltonian that is better suited than the previous one. In numerical examples of the shortest vector problem, we show that the algorithm with a sequence of improved problem Hamiltonians converges to the desired solution.
  arXiv  Detail & Related papers  (2022-04-28T12:04:03Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• 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)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• Quantum Approximation for Wireless Scheduling [11.79760591464748]
  This paper proposes a quantum approximate optimization algorithm (QAOA) for wireless scheduling problems. QAOA is one of the promising hybrid quantum-classical algorithms for many applications. Inspired by QAOA, a quantum approximate optimization for scheduling (QAOS) algorithm is proposed.
  arXiv  Detail & Related papers  (2020-04-14T13:29:22Z)
• 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)

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.