An Analysis of the Quantum Approximation Optimisation Algorithm

• URL: http://arxiv.org/abs/2103.12791v1
• Date: Tue, 23 Mar 2021 18:54:15 GMT
• Title: An Analysis of the Quantum Approximation Optimisation Algorithm
• Authors: Behzad Mansouri
• Abstract summary: This article introduces the quantum approximation optimisation algorithm (QAOA) The mathematical structure of the QAOA, as well as its basic properties, are described. The implementation of the QAOA on MaxCut problems, quadratic unconstrained binary optimisation problems (QUBOs), and Ising-type Hamiltonians is considered in detail.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This article consists of a short introduction to the quantum approximation optimisation algorithm (QAOA). The mathematical structure of the QAOA, as well as its basic properties, are described. The implementation of the QAOA on MaxCut problems, quadratic unconstrained binary optimisation problems (QUBOs), and Ising-type Hamiltonians is considered in detail.

Related papers

• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  We present a new method for calculating expectation values of operators that can be expressed as a linear combination of unitary (LCU) operators. This method is general for any quantum algorithm and is of particular interest in the acceleration of variational quantum algorithms.
  arXiv  Detail & Related papers  (2025-03-03T17:15:23Z)
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation [1.4691887238367354]
  We introduce means of efficiently approximating the QAOA optimisation landscape from solution space structures.<n>We derive a new algorithmic of unit-depth QAOA for two-level Hamiltonians.<n>Our approach is based on proving a long-standing conjecture regarding quantum-independent structures in QAOA.
  arXiv  Detail & Related papers  (2024-08-12T21:02:58Z)
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models [0.0]
  parity mapping provides a geometrically local encoding of the Quantum Approximate Optimization Algorithm (QAOA) We benchmark the parity-encoded QAOA on spin-glass models. We show that for fixed number of parity-encoded QAOA layers, the performance drops as $N-1/2$.
  arXiv  Detail & Related papers  (2023-11-03T18:00:00Z)
• Ising Hamiltonians for Constrained Combinatorial Optimization Problems and the Metropolis-Hastings Warm-Starting Algorithm [0.0]
  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.
  arXiv  Detail & Related papers  (2023-07-18T05:28:45Z)
• 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)
• Elementary Proof of QAOA Convergence [0.0]
  We provide a rigorous proof of convergence for the Quantum Alternating Operator Ansatz (QAOA) The proof involves retracing the connection between the Quantum Adiabatic Algorithm and the QAOA, and naturally suggests a refined definition of the phase separator' and mixer' keywords.
  arXiv  Detail & Related papers  (2023-02-09T22:57:59Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Evaluating the Convergence of Tabu Enhanced Hybrid Quantum Optimization [58.720142291102135]
  We introduce the Tabu Enhanced Hybrid Quantum Optimization metaheuristic approach useful for optimization problem solving on a quantum hardware. We address the theoretical convergence of the proposed scheme from the viewpoint of the collisions in the object which stores the tabu states, based on the Ising model.
  arXiv  Detail & Related papers  (2022-09-05T07:23:03Z)
• How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization [11.095381943951539]
  We present a toolkit of methods to transform almost arbitrary problems to Quadratic unconstrained binary optimization (QUBO) We showcase the usage of our approaches on two example problems (ratio cut and logistic regression)
  arXiv  Detail & Related papers  (2022-04-23T09:43:06Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• 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)
• 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)
• 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.