An Introduction to the Quantum Approximate Optimization Algorithm

• URL: http://arxiv.org/abs/2511.18377v1
• Date: Sun, 23 Nov 2025 09:54:20 GMT
• Title: An Introduction to the Quantum Approximate Optimization Algorithm
• Authors: Alessandro Giovagnoli,
• Abstract summary: 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.
• Score: 51.56484100374058
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a promising variational quantum algorithm introduced to tackle classically intractable combinatorial optimization problems. This tutorial offers a comprehensive, first-principles introduction to QAOA and its properties, focusing on its application to Quadratic and Polynomial Unconstrained Binary Optimization (QUBO and PUBO) problems. The tutorial begins by outlining variational quantum circuits and QUBO problems, focusing on their key properties and the encoding of problem constraints through quadratic penalty terms. Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications, along with their implementation and performance results. This is followed by an analysis of the algorithm's energy landscape, where proofs are provided for its symmetry and periodicity, and where a resulting parameter space reduction is proposed. Finally, the tutorial extends these concepts to PUBO problems by generalizing the results to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.

Related papers

• Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study [0.0]
  Quadratic Unconstrained Binary Optimization provides a unifying modeling framework for a broad class of $mathbfNP$-hard problems.<n>We develop QUBO formulations for several fundamental problems in location science, network design, and logistics.<n>These QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware.
  arXiv  Detail & Related papers  (2026-02-11T15:39:26Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Quantum Approximate and Quantum Walk Optimization Approaches to Set Balancing [0.0]
  We explore the application of variational quantum algorithms to the NP-hard set balancing problem.<n>The problem is mapped to an Ising model, with tailored Quadratic Unconstrained Binary Optimization (QUBO) formulations and cost Hamiltonians expressed in Pauli-Z form.<n>For QAOA, we perform a comparative analysis of six mixer Hamiltonians (X, XY, Full-SWAP, Ring-SWAP, Grover, and Warm-Started), employing scaled-exponential Pauli-string realizations of the mixer unitaries.<n>We introduce a Shannon-entropy-based post
  arXiv  Detail & Related papers  (2025-09-08T20:31:30Z)
• Expressivity Limits in Quantum Walk-based Optimization [0.0]
  Quantum walk optimization algorithm (QWOA) is one such variational approach that has recently gained attention.<n>A key method to study this aspect involves analyzing the dimension of the dynamic Lie algebra (DLA)<n>We show that the DLA dimension dimension scales at most quadratically with a number of distinct eigenvalues of the problem Hamiltonian.
  arXiv  Detail & Related papers  (2025-08-07T18:04: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.<n>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)
• Lagrangian Duality in Quantum Optimization: Overcoming QUBO Limitations for Constrained Problems [0.0]
  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.
  arXiv  Detail & Related papers  (2023-10-06T19:09:55Z)
• 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)
• 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)
• Analyzing Prospects for Quantum Advantage in Topological Data Analysis [35.423446067065576]
  We analyze and optimize an improved quantum algorithm for topological data analysis. We show that super-quadratic quantum speedups are only possible when targeting a multiplicative error approximation. We argue that quantum circuits with tens of billions of Toffoli can solve seemingly classically intractable instances.
  arXiv  Detail & Related papers  (2022-09-27T17:56:15Z)
• 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)
• An Analysis of the Quantum Approximation Optimisation Algorithm [0.0]
  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.
  arXiv  Detail & Related papers  (2021-03-23T18:54:15Z)
• 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.