ADAPT-QAOA with a classically inspired initial state

• URL: http://arxiv.org/abs/2310.09694v1
• Date: Sun, 15 Oct 2023 01:12:12 GMT
• Title: ADAPT-QAOA with a classically inspired initial state
• Authors: Vishvesha K. Sridhar, Yanzhu Chen, Bryan Gard, Edwin Barnes and Sophia E. Economou
• Abstract summary: We propose to start ADAPT-QAOA with an initial state inspired by a classical approximation algorithm. We show that this new algorithm can reach the same accuracy with fewer layers than the standard QAOA and the original ADAPT-QAOA.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum computing may provide advantage in solving classical optimization problems. One promising algorithm is the quantum approximate optimization algorithm (QAOA). There have been many proposals for improving this algorithm, such as using an initial state informed by classical approximation solutions. A variation of QAOA called ADAPT-QAOA constructs the ansatz dynamically and can speed up convergence. However, it faces the challenge of frequently converging to excited states which correspond to local minima in the energy landscape, limiting its performance. In this work, we propose to start ADAPT-QAOA with an initial state inspired by a classical approximation algorithm. Through numerical simulations we show that this new algorithm can reach the same accuracy with fewer layers than the standard QAOA and the original ADAPT-QAOA. It also appears to be less prone to the problem of converging to excited states.

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)
• Multiscale Quantum Approximate Optimization Algorithm [0.0]
  The quantum approximate optimization algorithm (QAOA) is one of the canonical algorithms designed to find approximate solutions to optimization problems. We propose a new version of QAOA that incorporates the capabilities of QAOA and the real-space renormalization group transformation.
  arXiv  Detail & Related papers  (2023-12-11T07:47:16Z)
• 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)
• How Much Entanglement Do Quantum Optimization Algorithms Require? [0.0]
  We study the entanglement generated during the execution of ADAPT-QAOA. By incrementally restricting this flexibility, we find that a larger amount of entanglement entropy at earlier stages coincides with faster convergence at later stages.
  arXiv  Detail & Related papers  (2022-05-24T18:00:02Z)
• 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 Computational Phase Transition in Combinatorial Problems [0.966840768820136]
  Quantum Approximate Optimization algorithm (QAOA) aims to search for approximate solutions to discrete optimization problems with near-term quantum computers. We identify a computational phase transition of QAOA when solving hard problems such as SAT. We show that the high problem density region, which limits QAOA's performance in hard optimization problems, is actually a good place to utilize QAOA.
  arXiv  Detail & Related papers  (2021-09-27T20:46:52Z)
• 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)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Digitized-counterdiabatic quantum approximate optimization algorithm [3.0638256603183054]
  We propose a digitized version of QAOA enhanced via the use of shortcuts to adiabaticity. We apply our digitized-counterdiabatic QAOA to Ising models, classical optimization problems, and the P-spin model, demonstrating that it outperforms standard QAOA in all cases.
  arXiv  Detail & Related papers  (2021-07-06T17:57:32Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  We show how to apply the quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs.
  arXiv  Detail & Related papers  (2020-11-26T18:22:21Z)
• An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer [0.0]
  The quantum approximate optimization algorithm (QAOA) is a hybrid variational quantum-classical algorithm that solves optimization problems. We develop an iterative version of QAOA that is problem-tailored, and which can also be adapted to specific hardware constraints. We simulate the algorithm on a class of Max-Cut graph problems and show that it converges much faster than the standard QAOA.
  arXiv  Detail & Related papers  (2020-05-20T18:00:01Z)
• 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.