# A Review on Quantum Approximate Optimization Algorithm and its Variants

Kostas Blekos<EMAIL_ADDRESS>Department of Physics, School of Natural
Sciences, University of Patras, Patras 26504, Greece; email:
<EMAIL_ADDRESS>Dean Brand  Department of Physics, Stellenbosch
University, Stellenbosch 7600, South Africa; email<EMAIL_ADDRESS>Andrea Ceschini  Department of Information Engineering, Electronics and
Telecommunications, Sapienza University of Rome, Rome 00184, Italy; email:
<EMAIL_ADDRESS>Chiao-Hui Chou  Department of Engineering Science
and Ocean Engineering, National Taiwan University, Taipei 10617, Taiwan;
email<EMAIL_ADDRESS>Rui-Hao Li  Department of Physics, Case Western
Reserve University, Cleveland, Ohio 44106, USA; email<EMAIL_ADDRESS>Komal
Pandya  Department of Computer Science and Engineering, Indian Institute of
Technology Patna, Patna 801106, India; email<EMAIL_ADDRESS>Alessandro
Summer  School of Physics, Trinity College Dublin, Dublin 2, Ireland; email:
<EMAIL_ADDRESS>
###### Abstract

The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising
variational quantum algorithm that aims to solve combinatorial optimization
problems that are classically intractable. This comprehensive review offers an
overview of the current state of QAOA, encompassing its performance analysis
in diverse scenarios, its applicability across various problem instances, and
considerations of hardware-specific challenges such as error susceptibility
and noise resilience. Additionally, we conduct a comparative study of selected
QAOA extensions and variants, while exploring future prospects and directions
for the algorithm. We aim to provide insights into key questions about the
algorithm, such as whether it can outperform classical algorithms and under
what circumstances it should be used. Towards this goal, we offer specific
practical points in a form of a short guide. Keywords: Quantum Approximate
Optimization Algorithm (QAOA), Variational Quantum Algorithms (VQAs), Quantum
Optimization, Combinatorial Optimization Problems, NISQ Algorithms

All authors contributed equally to this work.

###### Contents

  1. 1 Introduction
  2. 2 Background
    1. 2.1 MaxCut Problem Overview
    2. 2.2 QUBO Problems and Applications
    3. 2.3 Classical Algorithms for MaxCut Problem
    4. 2.4 Variational Quantum Algorithms
      1. 2.4.1 Variational Quantum Eigensolver (VQE)
      2. 2.4.2 Quantum Adiabatic Algorithm (QAA)
      3. 2.4.3 Barren plateaus
    5. 2.5 The Quantum Approximate Optimization Algorithm (QAOA)
  3. 3 QAOA Analysis
    1. 3.1 Ansatz Variants
      1. 3.1.1 Multi-Angle QAOA
      2. 3.1.2 QAOA+
      3. 3.1.3 Digitized counterdiabatic QAOA
      4. 3.1.4 Adaptive bias QAOA
      5. 3.1.5 ADAPT-QAOA
      6. 3.1.6 Recursive QAOA
      7. 3.1.7 Quantum alternating operator ansatzes
      8. 3.1.8 Warm-starting QAOA
      9. 3.1.9 FALQON
      10. 3.1.10 Fermionic QAOA
      11. 3.1.11 Other approaches
    2. 3.2 Parameter Optimization
      1. 3.2.1 Finding good initial parameters
      2. 3.2.2 Selecting an appropriate optimizer
      3. 3.2.3 Overcoming barren plateaus
      4. 3.2.4 Parameter transferability and reusability
      5. 3.2.5 Leveraging parameter symmetries
    3. 3.3 Computational Resource Efficiency
      1. 3.3.1 Speedup potential
      2. 3.3.2 Obstacles to quantum speedup
      3. 3.3.3 Runtime performance improvements
    4. 3.4 Quality of Solution
      1. 3.4.1 Solution guarantees
      2. 3.4.2 Performance limitations
      3. 3.4.3 Empirical evidence
    5. 3.5 Noise and Errors Considerations
      1. 3.5.1 Characterizing the sources of noise
      2. 3.5.2 Quantum advantage in the presence of noise
      3. 3.5.3 Noise mitigation techniques
    6. 3.6 Hardware-Specific Approaches
  4. 4 Experimental Results
    1. 4.1 Related Tools
    2. 4.2 Implementation and Systematic Evaluation of QAOA Variants
    3. 4.3 Experimental Results and Discussion
    4. 4.4 Limitations and Future Work
  5. 5 Discussion
    1. 5.1 Summary of Analysis
    2. 5.2 Potential Applications and Use Cases
    3. 5.3 The Quantum Advantage of QAOA
    4. 5.4 Open Questions and Future Directions
  6. 6 A Practical Guide to QAOA
    1. 6.1 Which QAOA Ansatz Variant Should I Use for My Problem?
    2. 6.2 How to Optimize the QAOA Parameters?
    3. 6.3 Practical Considerations for Implementing QAOA

###### List of Figures

  1. 1 Illustration of a 6-nodes graph and its maximum cut
  2. 2 Implementation of the elements of cost and mixing Hamiltonians
  3. 3 Scheme of the hybrid workflow of QAOA
  4. 4 General scheme of QAOA and its features
  5. 5 Representation of the QAOAnsatz
  6. 6 Three different graph types in generated dataset.
  7. 7 Performance of QAOA variants
  8. 8 Performance of QAOA variants on a simulator
  9. 9 Amount of resources employed by different QAOA variants

###### List of Tables

  1. 1 Summary of ansatz strategies for improving QAOA.
  2. 2 Summary of approaches in QAOA parameter optimization.
  3. 3 Summary of established theoretical bounds on the performance of QAOA and selected classical algorithms on optimization problems.
  4. 4 Summary of selected state-of-the-art experiments on various quantum devices.
  5. 5 Overview of the graph structures and instances used in experiment.
  6. 6 Summary statistics of the selected QAOA variants across all implementation combinations (simulation results).
  7. 7 Mean approximation ratio achieved in relation to circuit layer depth ($p$).
  8. 8 Mean approximation achieved for each variant for all problem types and sizes.
  9. 9 Summary of cosine similarity metrics across QAOA variants.

##  1 Introduction

Although fault-tolerant quantum computers are still years away, significant
progress has been made in the development of the Noisy Intermediate-Scale
Quantum (NISQ) machines, and there is a growing interest in finding useful
algorithms meant to be run on these near-term quantum devices. As such,
Variational Quantum Algorithms (VQAs) [1, 2, 3, 4, 5, 6] have been proposed to
take advantage of current quantum systems through a hybrid quantum-classical
optimization routine. The hybrid loop of a VQA involves a parameterized
quantum circuit to be run on a quantum computer and an optimizer that can
update the parameters on a classical machine by minimizing the cost function
constructed based on the outputs of the quantum circuit. In this way, VQAs
often have the advantage of having shallow quantum circuits, making them less
susceptible to noise in NISQ devices. To date, VQAs have found use cases in
various areas, including quantum chemistry simulations, machine learning, and
optimization [7, 8, 9, 10, 11].

In particular, the Quantum Approximate Optimization Algorithm (QAOA) [12, 13]
is one of the most promising VQAs that has attracted great interest in recent
years. QAOA is designed to find approximate solutions to hard combinatorial
optimization problems on quantum computers: it encodes the Hamiltonian related
to the problem into a quantum circuit and leverages adiabatic time evolution
and layering to optimize the variational parameters of the circuit, such that
the approximate solution to the problem can be constructed by measuring the
QAOA circuit with the optimal set of parameters. The fundamental building
block, a single layer of the QAOA circuit, consists of a cost layer associated
with the problem Hamiltonian and a mixer layer whose corresponding Hamiltonian
does not commute with the problem Hamiltonian. The performance of QAOA is
typically measured by the approximation ratio $C_{\text{QAOA}}/C_{\max}$,
i.e., the ratio of the cost associated with the solution output by QAOA to
that of the true optimal solution. Theoretically, such an approximation ratio
increases with increasing layers $p$, as QAOA recovers the adiabatic evolution
in the $p\to\infty$ limit.

QAOA is suitable for finding good approximated solutions to several
optimization problems, such as Maximum Cut (MaxCut) [12], Maximum Independent
Set (MIS) [14, 15], Binary Paint Shop Problem (BPSP) [16], Binary Linear Least
Squares (BLLS) [17], Max E3LIN2 [13], Multi-Knapsack [18], and, more
generally, Quadratic Unconstrained Binary Optimization (QUBO) problems [19].
Consequently, applications of QAOA in the real world are many and far-
reaching. Some recent examples include portfolio optimization [20, 21], tail
assignment [22], object detection [23], maximum likelihood detection of binary
symbols over a multiple-input and multiple-output channel [24], text
summarization [25], maximum independent set [26], factorization (Variational
Quantum Factoring algorithm) [27, 28], protein folding [29], and wireless
scheduling [30].

However, at the moment, literature still contains many conflicting opinions on
various aspects of the algorithm, such as for which problems, if any, QAOA can
outperform classical algorithms and whether it can provide any practical
quantum advantage under the noise and errors of current quantum devices. Here
we extensively study the available literature in order to provide a
comprehensive review of the current status of QAOA and summarize existing
results in different aspects of the algorithm. This review aims to be a guide
for using QAOA, providing insights into key questions about the algorithm,
that is, whether QAOA can outperform classical algorithms and under what
circumstances it should be used. Additionally, we provide meaningful insights
on QAOA’s potential for achieving quantum advantage, and discuss promising
research directions for the future. In particular, we focus on the following
aspects: a survey of various extensions and variants of the QAOA ansatz,
strategies to improve parameter optimization, efficiency, and performance
analysis of the algorithm in various problem instances, and hardware-specific
issues including the effects of noise and hardware-tailored implementations.
Moreover, we also implement and assess the efficiency and performance of some
promising QAOA variants on the MaxCut problem, which is a paradigmatic
combinatorial optimization problem commonly used to benchmark the potential of
the algorithm [31].

The remainder of this paper is organized as follows. The Background section
(Section 2) provides an overview of relevant hard combinatorial problems such
as the MaxCut problem, General QUBO Problems, and related algorithms,
including the Variational Quantum Eigensolver (VQE) and Quantum Adiabatic
Algorithm (QAA). The Analysis section (Section 3) provides a detailed
examination of various aspects of QAOA, including the ansatz, computational
efficiency, quality of solution, effects of noise and errors, and hardware-
specific implementations (see Figure 4). Our Experimental Results (Section 4)
provide quantitative evaluations and performance comparisons between different
QAOA variants. In Section 5 we summarize our findings, highlight possible
applications for QAOA, discuss its potential quantum advantage and examine
future directions for the research. Finally, in Section 6, we provide insights
for a practical guide to QAOA by answering key questions about the algorithm,
such as which QAOA variant or ansatz to use for a specific problem and how to
effectively optimize it.

##  2 Background

Generally speaking, combinatorial optimization problems concern finding the
optimal solution among a set of feasible solutions, given some constraints on
a discrete set of variables. The objective function can either be minimized or
maximized, and it can be seen as a (possibly weighted) sum of the clauses
satisfied by a feasible solution.

Some typical combinatorial optimization problems include the Knapsack,
Traveling Salesman, and MaxCut problem [32]. However, due to the combinatorial
nature of such problems, the solution space explodes with respect to the
number of inputs, and the optimization process quickly becomes intractable.
Generally, finding the exact solution to many combinatorial optimization
problems belongs to the NP complexity class [33]. This means that classical
algorithms cannot efficiently retrieve the optimal solution since the time
required scales exponentially with the number of inputs.

In this context, approximate optimization algorithms are employed to find a
good approximate solution in polynomial time [34], which can be formulated as
follows. Given a combinatorial optimization problem defined on $n$-bit binary
strings of the form $\textbf{x}=x_{1}\cdots x_{n}$, where the goal is to
maximize a given classical objective function
$C(\textbf{x}):{\\{0,1\\}}^{n}\rightarrow\mathbb{R}_{\geq 0}$, an approximate
optimization algorithm aims to find a solution $\mathbf{x^{*}}$ such that the
approximation ratio $\alpha$, defined as

$\alpha=\frac{C(\mathbf{x^{*}})}{C_{\text{max}}},$ (1)

with $C_{\text{max}}=\max_{\mathbf{x}}C(\mathbf{x})$, reaches some desired
value. Ideally, the value should be as close to 1. Despite the fact that the
solution found by approximate algorithms may not be optimal, it generally
comes with some optimality guarantees, which are typically lower bounds on the
quality of the solution. For example, an algorithm is said to be
$\alpha$-approximated for a problem if and only if it can find a solution
within a factor $\alpha$ ($\leq 1$) of the optimal solution for every instance
of the problem [35]. Thus, should such an algorithm exist, the above criterion
certifies that the approximate solution is at least $\alpha$ times the
optimum. However, for some optimization problems, the gap between the
approximate solution and the optimal one cannot be reduced in polynomial time,
suggesting the difficulty of finding tight lower bounds with respect to the
optimal solution. This is known as the “hardness of approximation”, and it
implies that finding a polynomial time approximation for the underlying
problem is impossible unless P = NP [36]. A comprehensive list of state-of-
the-art approximation algorithms for some key combinatorial optimization
problems can be found in [35].

More formally, as outlined in Section 2.2, many optimization problems can be
transformed into a quadratic unconstrained binary optimization (QUBO) form.
However, QUBO problems are usually NP-complete [37], meaning that finding the
solution classically requires traversing a solution space that grows
exponentially with the problem size. On the other hand, quantum computing
promises to enable exponentially faster computation due to the superposition
nature of qubits. A quantum system’s exponentially growing Hilbert space can
naturally accommodate the solution space of a combinatorial optimization
problem and, therefore, may provide advantages in solving such problems over
classical machines. The Quantum Approximate Optimization Algorithm (QAOA) is
designed to tackle QUBO problems by utilizing a quantum circuit to find
approximate solutions. The objective is to address the inherent hardness of
approximation present in classical computation by leveraging the capabilities
of QAOA. It should be noted, however, that while QAOA has the potential to be
applied to a wide range of optimization problems, its effectiveness is
dependent on the specific problem characteristics (more details in Sections
3.3 and 3.4).

###  2.1 MaxCut Problem Overview

Figure 1: Left: A problem graph with 6 vertices and 11 equal-weight edges.
Right: The solution to the MaxCut problem, where the vertices are partitioned
into two groups (red and blue) such that the number of edges crossed by the
cut (black curve) is maximized, which is 8.

The MaxCut problem is one of the most well-known optimization problems, and it
is hereby discussed in detail. It involves finding a cut in a graph such that
the vertices of the graph are divided into two complementary subsets, and the
sum of the weights of the edges crossed by the cut is maximized. The MaxCut
problem can be formulated as follows: Given an undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of
vertices, $\mathcal{E}$ is the set of edges, and $w_{ij}$ is the weight
corresponding to the edge $(i,j)\in\mathcal{E}$, which connects the vertices
$i$ and $j$. The objective of the MaxCut is to partition the graph vertices
$x_{i}$, for $i=1,\ldots,\lvert\mathcal{V}\rvert$, into two complementary
subsets labeled by 0 and 1, such that the weighted sum of the edges connecting
vertices in different partitions, defined as

$\
C(\mathbf{x})=\sum_{i,j=1}^{\absolutevalue{\mathcal{V}}}w_{ij}x_{i}(1-x_{j}),$
(2)

is maximized, where $w_{ij}>0$, $w_{ij}=w_{ji}$, $\forall(i,j)\in\mathcal{E}$,
and $x_{i}\in\\{0,1\\}$. An example of the MaxCut problem is illustrated in
Figure 1. With general weights $w_{ij}$, the problem is commonly known as the
weighted-MaxCut; the plain MaxCut problem is a special case of the weighted-
MaxCut where $w_{ij}=1$ for all $(i,j)\in\mathcal{E}$.

Since finding a cut that yields the maximum value of the objective function,
$C$ is an NP-hard problem [38], our best hope for a polynomial-time algorithm
lies in an approximate optimization approach. This means finding a partition
$\mathbf{x}^{*}$ which yields a value $C(\mathbf{x}^{*})$ that is as close as
possible to the maximum value $C_{\text{max}}=\max_{\mathbf{x}}C(\mathbf{x})$.
Håstad [39] conjectured that achieving an approximation ratio higher than
$16/17\simeq 0.9412$ is NP-hard, highlighting the hardness of approximation
for the MaxCut problem. Currently, the best-performing classical algorithm for
the MaxCut problem is the Goemans-Williamson algorithm, which delivers a
solution with $\alpha\simeq 0.878$ [40, 41] (Section 2.3). For these reasons,
the MaxCut is considered the paradigmatic example of hard combinatorial
optimization problems. As a result, the aspiration is to find good and
efficient approximate solutions to MaxCut by leveraging the power of quantum
algorithms. In this regard, QAOA is a quantum algorithm that has shown promise
in finding solutions to hard combinatorial optimization problems such as
MaxCut. More details of the performance analysis of QAOA and the comparison to
its classical counterparts will be provided in Section 3.4.

###  2.2 QUBO Problems and Applications

A more general formulation of the MaxCut problem is represented by Quadratic
Unconstrained Binary Optimization (QUBO) problems. QUBO problems belong to the
NP-complete class. This mathematically assures that any NP-complete problem
can be mapped to a QUBO one in polynomial time. Lucas [42] discussed how all
the Karp’s 21 NP-complete problems can be mapped to a QUBO one. Among them
some relevant optimization problems other than MaxCut are Graph Coloring [43],
Number Partitioning, and Quadratic Knapsack [44]. An extensive list of QUBO
applications is presented in [37]. In a QUBO problem, the vector of unknowns
$\mathbf{x}=(x_{1},\ldots,x_{n})$ is represented by decision variables taking
discrete binary values, so that $\mathbf{x}\in\\{0,1\\}^{n}$. Moreover, a QUBO
problem is defined by a square symmetric matrix
$\mathbf{Q}\in\mathbb{R}^{n\times n}$. Given the cost function

$C(\mathbf{x})=\mathbf{x}^{T}\mathbf{Q}\mathbf{x}=\sum_{i,j=1}^{n}Q_{ij}x_{i}x_{j},$
(3)

the aim of a QUBO problem is to find the optimal vector $\mathbf{x}^{*}$ such
that

$\mathbf{x}^{*}=\arg\min_{\mathbf{x}\in\\{0,1\\}^{n}}C(\mathbf{x}).$ (4)

QUBO can also be defined as maximization problems instead of minimization ones
by simply inverting the sign of the cost function $C(\mathbf{x})$, i.e., by
flipping the sign of the coefficients in $w$:

$\min_{\mathbf{x}\in\\{0,1\\}^{n}}C(\mathbf{x})=\max_{\mathbf{x}\in\\{0,1\\}^{n}}-C(\mathbf{x})=\max_{\mathbf{x}\in\\{0,1\\}^{n}}\sum_{i,j=1}^{n}(-Q_{ij})x_{i}x_{j}.$
(5)

It is important to note that QUBO problems are unconstrained, namely there are
no constraints on the variables $\mathbf{x}$.

QUBO instances can also be seen as a one-to-one correspondence with Ising
models [42]. Moreover, Lodewijks [45] discusses several mappings from NP-hard
problems to QUBO problems and corrects the errors in the approach taken in
[42]. It also expands the range of NP-complete and NP-hard optimization
problems that can be formulated as QUBO problems. Ising problems replace the
original QUBO variables $\mathbf{x}\in\\{0,1\\}^{n}$ with Ising variables
$\mathbf{z}\in\\{-1,1\\}^{n}$, such that $z_{i}=2x_{i}-1$ for $i=1,\ldots,n$.
The final Ising Hamiltonian, which depends on $\mathbf{z}$, is equivalent to
Eq. (3) except for a constant irrelevant to the optimization. A more detailed
explanation of the relationship between QUBO and Ising models can be found in
[44]. Inspired by the adiabatic theorem, annealing methods are used to find
the ground state of a physical system. Similarly, solutions to Ising problems
are often carried out with annealing techniques [46]. Due to its equivalence
with Ising models, QUBO represents a family of problems suitable to be solved
by adiabatic quantum computing through quantum annealing [47].

As previously mentioned, many optimization problems can be reformulated as
QUBO problems. Although QUBO problems are limited to quadratic interactions
between variables, they can be extended to higher-order terms. For example,
let us consider a problem with a third-order term $x_{i}x_{j}x_{k}$. To
convert this problem into a quadratic one, we can introduce an ancillary
variable (also called “gadget”) $x^{\prime}\coloneqq x_{i}x_{j}$, and express
the original term as $x_{i}x_{j}x_{k}=x^{\prime}x_{k}$. This allows us to
rewrite the entire problem in terms of quadratic interactions between
variables. Optimization problems with higher order interaction are in general
refereed to as Polynomial Unconstrained Binary Optimization (PUBO) problems.
Babbush et al. [48] analysed how to efficiently map PUBO problems to QUBO
ones. The fundamental reason why QAOA is focused on QUBO instances is linked
to the hardware constraints. However, in case the device can implement gates
on more than two qubits it could be more advantageous to reduce the number of
interaction by increasing their order. It was shown that arbitrary
combinatorial optimization problems can be mapped to PUBO problems through
dualizing constraints [49]. Alternatively, they can also be formulated in the
Lechner-Hauke-Zoller (LHZ), or parity model, which is a lattice gauge model
with nearest neighbor four-body interactions [50, 51, 52].

###  2.3 Classical Algorithms for MaxCut Problem

Despite the MaxCut problem being a well-known optimization problem in computer
science with a practical significance, finding the optimal solution is
computationally challenging, as it is an NP-hard problem [32]. This means that
no known algorithms can solve it in polynomial time concerning the size of the
input. However, several approximation algorithms and heuristics can provide
good solutions in a reasonable time for practical problem sizes [34].

For example, greedy algorithms are widely used because of their simplicity and
efficiency: they make locally optimal choices at each iteration step in the
hope of finding a globally optimal solution, but such a myopic strategy of
focusing only on the current step often leads to suboptimal solutions,
especially when the problem exhibits complex interactions between different
variables or features. Local search algorithms are heuristics techniques that
can overcome this limitation by systematically exploring the search space.
They start with an initial solution and iteratively improve it by considering
a neighborhood of the current solution and moving to the best neighboring
solution; the quality of the solution found profoundly depends on the initial
solution and the quality of the neighborhood explored. However, local search
algorithms may still get trapped in suboptimal solutions, especially if the
search space is large or complex. Simulated annealing, a specific type of
local search algorithm, can help avoid getting stuck in local optima. It uses
a temperature parameter to control the probability of accepting a worse
solution. In the context of the MaxCut problem, simulated annealing can
provide good solutions, but it can be slow for large problem instances.
Genetic algorithms are also popular metaheuristic algorithms that generate an
initial population of possible solutions and apply genetic operators like
selection, crossover, and mutation to generate new solutions, which are then
evaluated using an objective function. They can provide reasonable solutions
for complex optimization problems. However, they can be slow for large problem
instances due to the need to maintain a population of solutions and evaluate
each solution using the objective function. Another popular heuristic
algorithm for MaxCut is spectral clustering, that involves using the
eigenvectors of the graph Laplacian matrix to partition the graph into two
parts; the eigenvectors of the Laplacian matrix capture the global structure
of the graph and are able to identify the most significant cuts in the graph.
Spectral clustering can provide good solutions for many MaxCut instances,
despite being sensitive to the choice of the number of eigenvectors used for
partitioning and the spectral gap between the eigenvalues. In addition,
spectral clustering can be computationally expensive for large graphs.
Optimization techniques like linear programming and semidefinite programming
(SDP) are based on formulating the problem as a mathematical program and
solving it using optimization algorithms. These techniques can provide strong
theoretical guarantees on the quality of the solution, but they may require
significant computational resources to solve large instances of the problem.

In this regard, a prominent classical approximation algorithm for the MaxCut
problem is the Goemans-Williamson algorithm, based on Semidefinite Programming
(SDP) relaxations. The algorithm transforms the MaxCut problem into an SDP
problem by relaxing the binary constraints on the membership of each node in
one of the two sets into a real-valued vector in a high-dimensional space. The
solution of the SDP relaxation provides a set of real-valued vectors that can
be rounded randomly to obtain a feasible solution for the original problem.
The randomized rounding procedure maps each vector to one of the two sets with
probability proportional to its squared length. Notably, the algorithm
guarantees an approximation ratio of at least 0.87856, ensuring that the
obtained cut weights at least 87.856% of the optimal cut’s weight [40, 53].
Under the Unique Games Conjecture, this approximation ratio is the best
possible for any polynomial-time algorithm [54].

The Goemans-Williamson algorithm can be summarized in the following steps
[53]:

  1. 1.

Given a graph $G=(V,E)$ with $n$ vertices and edge weights $w_{ij}$, formulate
the MaxCut problem as a QUBO that maximizes the objective function:
$\sum_{i,j<i}w_{ij}x_{i}(1-x_{j})$, where $x_{i}\in\\{0,1\\}$ indicating which
side of the cut vertex $i$ belongs.

  2. 2.

Relax the QP by replacing binary variables $x_{i}$ with unit vectors
$y_{i}\in\mathbb{R}^{n}$ whose elements could be continuous variables, and
$x_{i}x_{j}$ with $y_{i}^{T}y_{j}$, where the superscript $T$ denotes the
transpose operation. This gives a semidefinite program (SDP) that maximizes
the objective function: $\sum_{i,j<i}w_{ij}(1-y_{i}^{T}y_{j})$, subject to
$\forall i\in\\{0,\dots,n\\}$, $y_{i}^{T}y_{i}=1$, and $Y=(y_{i}^{T}y_{j})$ is
positive semidefinite.

  3. 3.

Solve the SD using a polynomial-time algorithm such as interior point methods
to obtain an optimal solution $Y^{*}$.

  4. 4.

Choose a random vector $r\in\mathbb{R}^{n}$ from a Gaussian distribution and
$\forall i$, let $h_{i}=\operatorname{sgn}(r^{T}y_{i})$, where
$\operatorname{sgn}(x)=1$ if $x\geq 0$ and $-1$ otherwise. This gives a
partition of $V$ into two sets: $S_{+}={i|h_{i}=1}$ and $S_{-}={i|h_{i}=-1}$.

  5. 5.

Return the cut $(S_{+},S_{-})$ as the output of the algorithm.

Gaining a deep understanding of the classical approaches proposed to
approximate the MaxCut problem can offer valuable insights into the problem’s
complexity and the limitations of classical computing resources. Furthermore,
with the advent of quantum computing, this knowledge can inspire the
development of novel quantum algorithms that can leverage the power of quantum
mechanics to solve this problem more efficiently.

###  2.4 Variational Quantum Algorithms

QAOA is part of a broader category of quantum algorithms known as Variational
Quantum Algorithms (VQAs) [3, 55]. These algorithms share the properties of
being targeted primarily at optimization problems on NISQ devices, using the
variational principle in quantum theory. The variational principle is used to
find the lowest expectation value which can be obtained for a particular
observable, typically the ground state energy, with respect to a trial wave
function. This trial wave-function makes the principle variational, as it is
parameterized by a set of values which allows for a general wave-function form
to be fitted to the system and the minimum expectation value to be found. This
is expressed in terms of a Hamiltonian $\hat{H}$, and trial wave-function
$\ket{\psi}$, to find the ground state energy of the system $E_{0}$, which is
bounded as follows,

$E_{0}\leq\frac{\expectationvalue{\hat{H}}{\psi}}{\innerproduct{\psi}{\psi}}.$
(6)

Given this form, the objective of variational algorithms is to find a
parametrization of $\ket{\psi}$, which minimizes the expectation value of the
Hamiltonian. This is achieved by approximating the eigenvector, $\ket{\psi}$,
of the Hermitian operator, $\hat{H}$, with the lowest eigenvalue, $E_{0}$, by
iteratively improving upon an ansatz. The initial trial wave function and its
first set of parameters form the ansatz, with the parameters typically chosen
at random within a range expected to be reasonable in the context of the
quantum system.

The selection of the ansatz form is a problem of its own which has many
possible approaches depending on the Hamiltonian of the system, as explored in
[56, 57, 58] but is inspired by the context of the problem to be solved. For
example, in quantum chemistry, finding the ground state of a helium atom
involves having an ansatz wave-function of the product of two hydrogen atom
wave-functions, which is then improved upon from there [59]. Apart from the
“problem-inspired ansatze”, another architecture is the so-called hardware-
efficient ansatze [60], which build arbitrary unitaries using single- and two-
qubit gates that are native to the hardware in use. It has the advantage of
reducing circuit depth and being versatile enough to solve a wide range of
problems as it is “problem-agnostic”. Overall, this ambiguity and freedom of
choice in forming an ansatz for a variational problem allows for a smooth
transition to quantum computers being used, as they can encode Hamiltonians as
the sum of unitary operations. This linear combination of unitary operators
also allows for creating an ansatz wave function that can be easily
parameterized through Bloch sphere rotation angles.

This principle translates very smoothly to quantum computers, as qubits are
elementary and versatile manifestations of wave functions, which are measured
to obtain the expectation value and energy of the system at the end of the
quantum circuit after going through a set of parameterized quantum gates to
alter the system and its wave-functions. This idea’s simplest and most direct
implementation is the Variational Quantum Eigensolver (VQE).

####  2.4.1 Variational Quantum Eigensolver (VQE)

Variational Quantum Eigensolver (VQE) is a quantum algorithm that employs a
hybrid system, integrating both quantum and classical computing resources, to
solve the eigenvalue problem for a given Hamiltonian operator. This technique
was initially presented by Peruzzo et al. [61] as an alternative to the
quantum phase estimation algorithm by implementing a quantum chemistry problem
on a hybrid system consisting of a photonic quantum processor and a
conventional computer. This work was improved, and its theoretical framework
was reinforced and extended in a subsequent work by McClean et al. [1].

The VQE algorithm, as all VQAs, operates via a parameterized quantum circuit,
or ansatz, characterized by a set of parameters, $\bm{\theta}$. A systematic
method is required to vary the ansatz parameters until an optimal solution is
found to implement the variational principle on a quantum computer. The entire
action of this variational operation can be represented by a unitary gate
$U(\bm{\theta})$. The ansatz acts on the initial state of the quantum circuit
of $N$ qubits, $\ket{\psi_{0}}$, typically taken to be the ground state
$\ket*{\mathbf{0}}$ (also expressed as $\ket{0}^{\otimes N}$), and generates
an output $U(\bm{\theta})\ket{\psi_{0}}=\ket*{\psi(\bm{\theta})}$.

From this construction, it is clear that $U(\bm{\theta})\ket{\psi_{0}}$ is a
normalized wave-function, which allows for the expression of the optimization
problem as

$\lambda=\min_{\bm{\theta}}\expectationvalue{U^{\dagger}(\bm{\theta})\hat{H}U(\bm{\theta})}{\psi_{0}}.$
(7)

This is the state that is iteratively optimized by varying the parameters
$\bm{\theta}$ towards an optimal set of parameters, $\bm{\theta}^{*}$, to
obtain the optimized expectation value,

$\lambda_{\text{min}}=E_{0}\approx\expectationvalue{\hat{H}}{\psi(\bm{\theta}^{*})}.$
(8)

This algorithm can be easily scaled up to include more complexity, parameters,
variational gates, and entanglement schemes [62]. These more expressive
variational forms allow for better fine-tuning of the ansatz, resulting in a
more accurate output state estimation of the eigenvalues.

The VQE algorithm, as a VQA, relies on both a quantum and classical part. The
quantum part consists of estimating a quantum circuit, and it evaluates the
desired quantum states for the given set of parameters. Since it is not
optimized to calculate the variations in the parameters towards an optimized
set, this part is dealt with in the classical part of the algorithm. Indeed,
the mathematics involved in optimization calculations is very efficient on
modern classical computers.

Combining quantum and conventional computers to handle different components of
a larger problem is known as hybrid quantum-classical computing and is the
backbone of any VQA [1].

Moreover, it is a powerful framework for many use cases, especially with NISQ
devices, as quantum computers are less efficient and fault-tolerant than their
conventional counterparts with tasks such as optimizing parameters. So the
burden can be shared between the two to maximize overall performance. This
hybrid regime allows for the outsourcing of tweaking the parameters to a
classical computer which then passes the values back to the quantum computer
to calculate the eigenvalues. The classical computer calculates the new
parameters through optimization methods typically based on gradient descent
[63, 64], which calculates a hyperplane of error or deviation from the ideal
solution to find a minimum point that indicates the highest accuracy of the
model. An attempt to experimentally prove the efficiency of this hybrid method
was carried out by Otterbach et al. [65] by training a weighted MaxCut problem
on 19 qubits.

However, it should be noted that hybrid computing does not always provide the
most efficient solution, as some algorithms are more powerful when using only
quantum hardware, as demonstrated by Magann et al. [66]. Kandala et al. [60]
have used a medium-sized quantum computer to optimize Hamiltonian problems
with up to six qubits and over one hundred Pauli terms, determining ground-
state energy for molecules up to BeH2. The approach used a variational quantum
eigensolver, efficiently prepared trial states tailored to available quantum
processor interactions, and a robust stochastic optimization routine. Their
results help elucidate requirements for scaling the method to larger systems
and bridging gaps between high-performance computing problems and their
implementation on quantum hardware. Recent VQE variations have also been
proposed to efficiently tackle combinatorial optimization problems, similar to
those targeted by the QAOA [11, 65].

####  2.4.2 Quantum Adiabatic Algorithm (QAA)

As mentioned in Section 2.2, the adiabatic theorem is vital in solving
optimization problems. The adiabatic theorem states that starting in the
ground state of a time-dependent Hamiltonian, if the Hamiltonian evolves
slowly enough, the final state will be the ground state of the final
Hamiltonian. Moreover, the adiabatic theorem can be generalized to any other
eigenstate as long as there is no overlap (degeneracy) between different
eigenstates across the evolution. The $n$-th eigenstate of the initial
Hamiltonian will evolve into the $n$-th eigenstate of the final one. The
Quantum Adiabatic Algorithm (QAA) [67, 68] was developed based on this
principle to solve optimization problems on a quantum computer. It also falls
under a more general computational paradigm called Adiabatic Quantum Computing
(AQC) [69]. Specifically, we have an initial Hamiltonian $\hat{H}_{M}$, whose
ground state is typically easy to prepare, and a final Hamiltonian
$\hat{H}_{C}$, whose ground state encodes the solution to the optimization
problem of interest. The adiabatic evolution path is then encapsulated in the
transitional Hamiltonian, which is expressed as
$\hat{H}(t)=f(t)\hat{H}_{C}+g(t)\hat{H}_{M}$ with some slowly varying control
functions such as $f(t)=t/T$ and $g(t)=1-t/T$, where $t\in[0,T]$ and $T$ is
the total evolution time. The evolution operator will then be
$\hat{U}(t)\eqqcolon e^{-i\int^{t}_{0}\mathrm{d}\tau\hat{H}(\tau)}$. It is
worth noting that although the QAA requires a continuous evolution of the
state, it can be emulated on a gate-based quantum computer by Trotterizing
$\hat{U}(t)$ in sufficiently small steps, namely, decomposing $\hat{U}(t)$
into a sequence of small steps through the Trotter-Suzuki formula:

$\hat{U}(t)\approx\prod_{k=0}^{r-1}\exp\left[-i\hat{H}(k\Delta\tau)\Delta\tau\right]=\prod_{k=0}^{r-1}\exp\left[-if(k\Delta\tau)\hat{H}_{C}\Delta\tau\right]\exp\left[-ig(k\Delta\tau)\hat{H}_{M}\Delta\tau\right]$
(9)

where $\Delta\tau\eqqcolon t/r$. Here, we notice that as $k$ increases,
$f(k\Delta\tau)$ increases while $g(k\Delta\tau)$ decreases. Therefore, the
time steps of $\hat{H}_{C}$ ($\hat{H}_{M}$) will decrease (increase) linearly.

Crosson et al. [70] conducted numerical simulations of the QAA for over
200,000 instances of MAX 2-SAT on 20 qubits with a unique optimal solution.
They selected a subset of instances for which the success probability was less
than $10^{-4}$ at $T=100$ and proposed three strategies to increase the
success probability for all of these instances. The first strategy was to run
the adiabatic algorithm more rapidly, which increased the success probability
at shorter times for all instances. The second strategy was initializing the
system in a random first excited state of the problem Hamiltonian, producing
an average success probability close to the upper bound for most hard
instances. The third strategy involved adding a random local Hamiltonian to
the middle of the adiabatic path, which often increased the success
probability. These strategies were also tested on the QAA version of the
Grover search algorithm, but they did not improve the success probability. The
authors concluded that their strategies might be helpful only for particularly
challenging instances and could be tested on a quantum computer with higher
qubit numbers.

####  2.4.3 Barren plateaus

In training parameterized quantum circuits, such as VQE and QAOA, there is a
major challenge related to the cost function landscape. In fact, for certain
families of parameterized quantum circuits, the landscape of the cost function
can be flat, meaning that the gradients concerning the trainable parameters
are exponentially small in the number of qubits, causing the optimization
process to stall. This is known as the problem of barren plateaus [71], i.e.,
the gradient of the cost function with respect to any parameter vanishes
exponentially in the number of qubits. Formally, a cost function
$C(\bm{\theta})$ exhibits a barren plateau if, for all trainable parameters
$\theta_{i}\in\bm{\theta}$, the variance of the partial derivative of the cost
function vanishes exponentially in the number $n$ of qubits:

$\text{Var}_{\bm{\theta}}[\partial_{i}C(\bm{\theta})]\leq F(n),$ (10)

with $F(n)\in O(b^{-n})$ for some constant $b>1$. Eq. (10) implies that the
gradient of the cost function will be, on average, exponentially small: due to
Chebyshev’s inequality, the probability that the partial derivative
$\partial_{i}C(\bm{\theta})$ deviates from its average (of zero) by a value
larger than a given constant $c$, with $c>0$, is bounded by
$\text{Var}_{\bm{\theta}}[\partial_{i}C(\bm{\theta})]$, as illustrated in Eq.
(11).

$\text{Pr}[\absolutevalue{\partial_{i}C(\bm{\theta})}\geq
c]\leq\frac{1}{c^{2}}\text{Var}_{\bm{\theta}}[\partial_{i}C(\bm{\theta})]$
(11)

Quantum circuit training strategies are becoming increasingly crucial for all
variational algorithms.

###  2.5 The Quantum Approximate Optimization Algorithm (QAOA)

The QAOA was first introduced by Farhi et al. [12] as a VQA able to find
approximate solutions to the MaxCut problem, suitable to be run on NISQ
devices. Inspired by the Trotterized version of QAA (Section 2.4.2), QAOA was
designed to be a variational algorithm with repeated cost and mixer layers,
namely these steps, instead of following some $f,g$ functions, are trained
variationally. Hence, it comes with a repeated cost and mixer layers, denoted
$\hat{U}_{C}(\gamma_{k})$ and $\hat{U}_{M}(\beta_{k})$, respectively, where
$k$ denotes the $k$-th layer. These layers are analogous to the exponentiated
operators on the right-hand side of Eq. (9). However, instead of following
predefined $f$ and $g$ functions, the parameters $\gamma_{k}$ and $\beta_{p}$
are trained variationally. In this sense, QAOA can be regarded as a
discretized version of QAA and a special case of VQE (Section 2.4.1). The key
idea behind QAOA is to encode the objective function of the optimization
problem into the cost Hamiltonian $\hat{H}_{C}$ to search for an optimal
bitstring $\mathbf{x^{*}}$ that will give a good approximation ratio $\alpha$
with a high probability. In fact, the cost function $C(\mathbf{x})$ can be
mapped to a cost Hamiltonian $\hat{H}_{C}$ such that

$\hat{H}_{C}\ket{\mathbf{x}}=C(\mathbf{x})\ket{\mathbf{x}},$ (12)

where $\mathbf{x}$ is the quantum state encoding the bitstring $\bf x$.

Figure 2: Implementation of the elements of mixer (left) and cost (right)
layers based on the cost and mixer Hamiltonians, $\hat{H}_{C}$ and
$\hat{H}_{M}$. By
$\big{(}e^{-i\beta_{k}\hat{H}_{M}}\big{)}_{v_{i}}\eqqcolon\big{(}\hat{U}_{M}(\beta_{k})\big{)}_{v_{i}}$
we mean the element of $\hat{U}_{M}(\beta_{k})$ generated by the vertex
$v_{i}$, i.e.,
$e^{-i\beta_{p}(\hat{H}_{M})_{v_{i}}}=e^{-i\beta_{k}X_{i}}=R_{X_{i}}(2\beta_{k})$,
where $\beta_{k}$ is the variational parameter for the layer $k$. Similarly
for $\big{(}e^{-i\gamma_{k}\hat{H}_{C}}\big{)}_{v_{i},v_{j}}$, the cost
unitary is given by
$e^{-i\gamma_{k}(\hat{H}_{C})_{ij}}=R_{Z_{i}Z_{j}}(-2w_{ij}\gamma_{k})$, which
can be decomposed as shown on the right.

The original QAOA consists of the following steps:

  1. 1.

Define a cost Hamiltonian $\hat{H}_{C}$ such that its highest energy state
encodes the solution to the optimization problem. Define also a mixer
Hamiltonian $\hat{H}_{M}$ that does not commute with $\hat{H}_{C}$. Typically,
for the MaxCut problem of a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$,
$\hat{H}_{C}$ and $\hat{H}_{M}$ are given as:

$\displaystyle\hat{H}_{C}$
$\displaystyle=\frac{1}{2}\sum_{(i,j)\in\mathcal{E}}w_{ij}(I-Z_{i}Z_{j}),$
(13a) $\displaystyle\hat{H}_{M}$ $\displaystyle=\sum_{j\in\mathcal{V}}X_{j},$
(13b)

where $I$ is the identity operator, $Z_{j}$ ($X_{j}$) is the Pauli-Z (-X)
operator acting on the $j$-th qubit. In the problem Hamiltonian $\hat{H}_{C}$,
diagonal in the computational basis, each binary variable $x_{i}\in\\{0,1\\}$
in the MaxCut problem is mapped to a Pauli-Z operator $Z_{i}$ in the following
way:

$x_{i}\rightarrow\frac{1}{2}(1-Z_{i}).$ (14)

The Hamiltonian $\hat{H}_{C}$ in Eq. (13a) corresponds precisely to the
objective function in Eq. (2).

  2. 2.

Initialize the circuit in the state $\ket{s}$:

$\ket{s}=\ket{+}^{\otimes
n}=\frac{1}{\sqrt{2^{n}}}\sum_{\mathbf{x}\in\\{0,1\\}^{n}}\ket{\mathbf{x}},$
(15)

where $n$ is the number of qubits and $n=\lvert\mathcal{V}\rvert$. The state
$\ket{s}$ corresponds to the highest energy state of the Pauli-X basis, i.e.,
to the highest energy state of the mixer Hamiltonian $\hat{H}_{M}$.

  3. 3.

Construct the circuit ansatz by defining and applying the unitaries:

$\displaystyle\hat{U}_{C}(\gamma)$
$\displaystyle=e^{-i\gamma\hat{H}_{C}}=\prod_{i=1,j<i}^{n}R_{Z_{i}Z_{j}}(-2w_{ij}\gamma),$
(16a) $\displaystyle\hat{U}_{M}(\beta)$
$\displaystyle=e^{-i\beta\hat{H}_{M}}=\prod_{i=1}^{n}R_{X_{i}}(2\beta),$ (16b)

where $\gamma$ and $\beta$ are variational parameters of the circuit. We call
$\hat{U}_{C}(\gamma)$ and $\hat{U}_{M}(\beta)$ the cost and mixer layers,
respectively. A single QAOA layer comprises one cost and one mixer layer,
which can be further stacked to build a deeper circuit with more layers. As
shown in Figure 2, each element in the mixer layer can be implemented with a
single rotation gate $R_{X}$. In contrast, each of the two-qubit Pauli-Z
interactions in the cost layer is implemented through two CNOT gates
sandwiching a local rotation gate $R_{Z}$.

  4. 4.

Define the total number of QAOA layers, $p\geq 1$. Initialize the $2p$
variational parameters $\bm{\gamma}=(\gamma_{1},\gamma_{2},\ldots,\gamma_{p})$
and $\bm{\beta}=(\beta_{1},\beta_{2},\ldots,\beta_{p})$ such that
$\gamma_{k}\in[0,2\pi)$ and $\beta_{k}\in[0,\pi)$ for $k=1,\dots,p$. The final
state output by the circuit is therefore given by

$\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}=e^{-i\beta_{p}\hat{H}_{M}}e^{-i\gamma_{p}\hat{H}_{C}}\ldots
e^{-i\beta_{1}\hat{H}_{M}}e^{-i\gamma_{1}\hat{H}_{C}}\ket{s}.$ (17)

  5. 5.

The expectation value of the Hamiltonian $\hat{H}_{C}$ with respect to the
ansatz state $\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}$, which corresponds to
the cost obtained by the quantum algorithm for the underlying problem, is
calculated through repeated measurements of the final state in the
computational basis:

$F_{p}(\bm{\gamma},\bm{\beta})=\expectationvalue{\hat{H}_{C}}{\psi_{p}(\bm{\gamma},\bm{\beta})}$
(18)

  6. 6.

A classical optimization algorithm is employed to iteratively update the
parameters $\bm{\gamma}$ and $\bm{\beta}$. The goal of the aforementioned
routine is to find the optimal set of parameters
$(\bm{\gamma}^{*},\bm{\beta}^{*})$ such that the expectation value
$F_{p}(\bm{\gamma},\bm{\beta})$ is maximized:

$(\bm{\gamma}^{*},\bm{\beta}^{*})=\arg\max_{\bm{\gamma},\bm{\beta}}F_{p}(\bm{\gamma},\bm{\beta})$
(19)

An example of a QAOA circuit instance is shown in Figure 3.

Figure 3: Schematic of the hybrid workflow of QAOA with $p$ layers.

At the end of the optimization procedure, the approximation ratio $\alpha$
will be given by:

$\alpha=\frac{F_{p}(\bm{\gamma}^{*},\bm{\beta}^{*})}{C_{\text{max}}},$ (20)

and the state $\ket{\psi_{p}(\bm{\gamma}^{*},\bm{\beta}^{*})}$ will encode the
solution to the optimization problem.

It is worth noting that, instead of the ground state, QAOA is typically
initialized with the highest energy eigenstate of the mixer Hamiltonian, such
as in the case of MaxCut. Nevertheless, the adiabatic theorem still holds in
such cases. Apart from the digitized adiabatic quantum computing approach,
which the standard QAOA implementation (Section 2.5) is based on, an analog
version of QAOA that can be run on quantum annealers was recently proposed by
Barraza et al. [72].

##  3 QAOA Analysis

Figure 4: General scheme of QAOA and its features.

The QAOA has generated significant interest in the quantum computing community
as a promising method for solving combinatorial optimization problems. This
section comprehensively analyzes QAOA and its various associated aspects
(Figure 4). Our analysis covers a range of topics, including ansatz variants
(Section 3.1), parameter optimization strategies (Section 3.2), computational
resource efficiency (Section 3.3), quality of solution (Section 3.4), noise
and error considerations (Section 3.5), and hardware-specific approaches
(Section 3.6). We evaluate the strengths and limitations of QAOA in light of
recent advancements and studies in the literature. Our analysis aims to
illuminate the capabilities and potential of QAOA and emphasize the challenges
that must be addressed to harness its power in practical applications fully.

###  3.1 Ansatz Variants

An ansatz is an educated guess about the form of an unknown function that is
made in order to facilitate the solution of an equation or other problem. In
the context of QAOA, the ansatz that needs to be made is about the structure
of the quantum circuit, which defines the operators

$\hat{U}(\bm{\gamma},\bm{\beta})=e^{-i\beta_{p}\hat{H}_{M}}e^{-i\gamma_{p}\hat{H}_{C}}\cdots
e^{-i\beta_{1}\hat{H}_{M}}e^{-i\gamma_{1}\hat{H}_{C}},$ (21)

where such operators are layered $p$ times. The choice of ansatz typically
depends on the problem type, such as combinatorial problems represented as
graphs [73], or problems strongly influenced by hardware design [74, 75, 76].
However, ansatz design must balance specificity and generality to avoid
overfitting and maintain applicability to a wide range of problems. For this
reason, designing optimal ansatze for QAOA is an extensively researched and
widely investigated topic. This section introduces and discusses various
prominent designs and variations of the QAOA ansatz. These variations
encompass several approaches to constructing the optimization methodology and
address many of the shortcomings of the original algorithm. These variations
are summarized in Table 1.

Ansatz |  Main Idea |  Enhancement & Applications
---|---|---
ma-QAOA [77] |  Multi-angle ansatz with a unique parameter for each element of cost and mixer Hamiltonians |  Improves approximation ratio for MaxCut while reducing circuit depth
QAOA+ [78] |  Augments traditional QAOA with an additional multi-parameter problem-independent layer |  Higher approximation ratios for MaxCut on random regular graphs
DC-QAOA [79, 80] |  Adds a problem-dependent counterdiabatic driving term to the QAOA ansatz |  Improves the convergence rate of the approximation ratio while reducing circuit depth
ab-QAOA [81] |  Incorporates local fields into the operators to reduce computation time |  Computation time reduction for combinatorial optimization
ADAPT-QAOA [82] |  Iterative version of QAOA with systematic selection of mixers based on gradient criterion |  Can be problem-specific and addresses hardware constraints
Recursive QAOA [83] |  Non-local variant of QAOA that iteratively reduces problem size by eliminating qubits |  Overcomes locality constraints and achieves better performance
QAOAnsatz [84] |  Extends the original formulation with broader families of operators and allows for encoding of constraints |  Adaptable to a wider range of optimization problems with hard and soft constraints
GM-QAOA [85] |  Uses Grover-like selective phase shift mixing operators |  Solves $k$-Vertex Cover, Traveling Salesperson Problem, Discrete Portfolio Rebalancing
Th-QAOA [86] |  Replaces standard phase separator with a threshold function |  Solves MaxCut, Max $k$-Vertex Cover, Max Bisection
Constraint Preserving Mixers [87] |  Constructs mixers that enforce hard constraints |  Solves optimization problems with hard constraints
WS-QAOA [88] |  Modifies the initial state and mixer Hamiltonian based on the optimal solution to the relaxed QUBO problem |  Solutions guaranteed to retain the GW bound for the MaxCut problem
FALQON [66] |  Uses qubit measurements for feedback-based quantum optimization, avoiding classical optimizers |  Produces monotonically improving approximate solutions as circuit depth grows while bypassing classical optimization loops
FALQON+ [89] |  Combines FALQON’s initialization with QAOA for better parameter initialization |  Improves initialization of standard QAOA for non-isomorphic graphs with 8 to 14 vertices
FQAOA [90] |  Utilizes fermion particle number preservation to intrinsically impose constraints in QAOA process |  Improves performance in portfolio optimization, applicable to Grover adaptive search and quantum phase estimation
Quantum Dropout [91] |  Selectively drops out clauses defining the quantum circuit while keeping the cost function intact |  Improves QAOA performance on hard cases of combinatorial optimization problems
ST-QAOA [92] |  Uses an approximate classical solution to construct a problem instance-specific circuit |  Achieves same performance guarantee as the classical algorithm, outperforms QAOA at low depths for MaxCut problem
Modified QAOA [31] |  Modifies cost Hamiltonian with conditional rotations |  Improves approximation ratio for MaxCut at $p=1$
Table 1: Summary of ansatz strategies for improving QAOA.

####  3.1.1 Multi-Angle QAOA

A straightforward approach to enhanced ansatz design was introduced by Herrman
et al. [77]. The authors proposed a multi-angle ansatz for QAOA (ma-QAOA),
which improves the approximation ratio by increasing the number of variational
parameters. In ma-QAOA, new parameters are introduced into the circuit so that
each element of the cost and mixer layers has its angle instead of one angle
for the cost operator and one for the mixer operator, as follows:

$\displaystyle\hat{U}_{C}(\bm{\gamma}_{l})$
$\displaystyle=e^{-i\sum_{a=1}^{m}\gamma_{l,a}\hat{H}_{C,a}}=\prod_{a=1}^{m}e^{-i\gamma_{l,a}\hat{H}_{C,a}}$
(22a) $\displaystyle\hat{U}_{M}(\bm{\beta}_{l})$
$\displaystyle=e^{-i\sum_{v=1}^{n}\beta_{l,v}\hat{H}_{M,v}}=\prod_{v=1}^{n}e^{-i\beta_{l,v}\hat{H}_{M,v}},$
(22b)

where $\bm{\gamma}_{l}=(\gamma_{l,1},\gamma_{l,2},...,\gamma_{l,m})$,
$\bm{\beta}_{l}=(\beta_{l,1},\beta_{l,2},...,\beta_{l,n})$, $l$ is the QAOA
layer, $n$ is the number of qubits (nodes) and $m$ is the number of clauses
(edges) of the problem (graph). The authors referred to the matrices
$\hat{H}_{C}$ and $\hat{H}_{M}$ as $C$ and $B$, respectively. The total number
of circuit parameters becomes $(n+m)p$, where $p$ is the number of QAOA
layers. The vanilla QAOA can be treated as a special case of ma-QAOA, where
all the parameters of a given cost or mixer layer have the same value. As
such, ma-QAOA was revealed to be more potent than the standard algorithm: the
value of the approximation ratio $\alpha$ achieved by the ma-QAOA is better or
equal to that of the vanilla QAOA. Despite a more complex parameter
optimization, empirical results suggest that ma-QAOA may require shallower
circuits. In this regard, a follow-up study by Shi et al. [93] proposed to
reduce the number of ma-QAOA parameters by exploiting the natural symmetries
of the input graphs. This approach reduced approximately 33% of the parameters
while having little to no impact on the objective function. Moreover, a
connection between ma-QAOA and Continuous-Time Quantum Walks (CTQW) on dynamic
graphs was investigated by Herrman [94], who showed that ma-QAOA is equivalent
to a restriction of CTQW on dynamic graphs. A possible advantage of relating
ma-QAOA to CTQW on dynamic graphs is that well-studied CTQW phenomena, such as
hitting times, might be investigated to improve our understanding of ma-QAOA
and help find optimal parameters.

####  3.1.2 QAOA+

Another example of an improvement in the ansatz is the work of Chalupnik et
al. [78]. To address the problem of the originally proposed form of the QAOA
ansatz not providing sufficient performance advantage over classical
counterparts in problems such as MaxCut [95], the authors proposed an
alternative ansatz, which they call QAOA+. This variant augments the
traditional $p=1$ QAOA ansatz with an additional multi-parameter problem-
independent layer of parameterized $ZZ$ gates and a layer of mixer $X$ gates.
The QAOA+ ansatz allows one to obtain higher approximation ratios than $p=1$
QAOA while keeping the circuit depth below that of $p=2$ QAOA with comparable
performance, as benchmarked on the MaxCut problem for random regular graphs.
Moreover, it showed a similar level of performance to $p=2$ QAOA. The added
circuit depth beyond the vanilla QAOA grows only in the number of qubits used
as a set of $2N-1$ parameters for $N$ qubits. They additionally showed that
the proposed QAOA+ ansatz, while using a more significant number of trainable
classical parameters than the standard QAOA, in most cases outperforms the
alternative multi-angle QAOA ansatz in [77].

####  3.1.3 Digitized counterdiabatic QAOA

In pursuit of reducing computational complexity, and thereby circuit depth, of
QAOA, Chandarana et al. [79] propose a new variant of the algorithm coined
Digitized Counterdiabatic QAOA (DC-QAOA). This QAOA variant is built on the
adiabatic evolution of the Hamiltonians in vanilla QAOA resulting in
unnecessary computational cost and circuit depth, which is difficult to
implement on near-term devices. This method utilizes counterdiabatic (CD)
driving to speed up the optimization process of the variational algorithm.
This is achieved through the extension of the time evolution operator to
include an additional variational parameter,

$U(\gamma,\beta)\to U(\gamma,\beta,\alpha),$ (23)

that represents a CD operator. This operator is represented as

$U_{\mathrm{CD}}(\alpha)=\prod_{J=1}^{L}\exp(-i\alpha A_{t}^{q}),$ (24)

where $A_{t}^{q}$ is the respective $q$-local CD operator chosen from the CD
pool $A$. This pool of operators is defined through the nested commutator
approach of the adiabatic gauge potential [96] as

$A_{\lambda}^{(l)}=i\sum_{k=1}^{l}\alpha_{k}(t)\underbrace{{[H_{a},[H_{a},\ldots[H_{a},}}_{2k-1}\partial_{\lambda}H_{a}]]].$
(25)

The authors applied this QAOA variant to problems such as Ising models,
classical optimization problems, and the $k$-spin model, demonstrating that it
outperforms the standard QAOA in all cases.

Wurtz and Love [80] propose a similar algorithm, CD-QAOA, also inspired by the
use of counterdiabaticity to accelerate the convergence of QAOA to minimize
circuit depth and improve solution quality.

####  3.1.4 Adaptive bias QAOA

Inspired by the previous work that introduced bias fields in quantum annealing
[97], Yu et al. [81] proposed a modified version of QAOA called the adaptive
bias QAOA (ab-QAOA), which incorporates the adaptive bias fields into the
mixer operators of QAOA to accelerate the convergence of the algorithm.
Essentially, in this approach, $n$ additional parameters $\\{h_{j}\\}$ that
comprise the bias fields are introduced in the $n$-qubit QAOA circuit, which
enter both the modified mixer Hamiltonian

$\hat{H}_{M}^{\text{ab}}(\\{h_{j}\\})=\sum_{j\in\mathcal{V}}\quantity(X_{j}-h_{j}Z_{j}),$
(26)

and the initial state that is the product ground state of
$\hat{H}_{M}^{\text{ab}}(\\{h_{j}\\})$. These local fields are not optimized
but rather updated according to the following prescription,

$h_{j}\to
h_{j}-\ell\left(h_{j}-\expectationvalue{Z_{j}}{\psi_{p}^{\text{ab}}}\right),$
(27)

where $\ell$ is the learning rate and $\ket{\psi_{p}^{\text{ab}}}$ is the
state output by the level-$p$ ab-QAOA circuit, that is,

$\ket{\psi_{p}^{\text{ab}}}=\prod_{k=1}^{j}e^{-i\beta_{k}\hat{H}_{M}^{\text{ab}}(\\{h_{j}\\})}e^{-i\gamma_{k}\hat{H}_{C}}\ket{\psi_{0}^{\text{ab}}(\\{h_{j}\\})}.$
(28)

The method was shown to substantially reduce the computation time of QAOA for
a fixed level of accuracy and the same number of gates. The computation time
of the ab-QAOA converging to a desired accuracy was polynomially shorter than
that of the vanilla QAOA. Moreover, such improvement further increases with
the problem size, paving the way for the quantum advantage of QAOA in
combinatorial optimization problems.

####  3.1.5 ADAPT-QAOA

Zhu et al. [82] addressed the ansatz selection problem by proposing an
iterative version of QAOA called the Adaptive Derivative Assembled Problem
Tailored-QAOA (ADAPT-QAOA). Instead of the standard mixer Hamiltonian, the
ADAPT-QAOA systematically selects the QAOA mixer from a pre-defined pool of
operators $\hat{A}_{k}$ that changes from one layer to the next:

$\ket{\psi_{p}(\bm{\gamma},\bm{\beta})}=\left(\prod_{k=1}^{p}e^{-i\beta_{k}\hat{A}_{k}}e^{-i\gamma_{k}\hat{H}_{C}}\right)\ket{s}.$
(29)

In each step, the operator $\hat{A}_{k}$ is selected by maximizing the
gradient of the commutator of the pool operator and the cost Hamiltonian over
the ansatz of the previous step, namely maximizing the gradient of

$-i\bra{\psi_{k-1}(\bm{\gamma},\bm{\beta})}e^{i\hat{H}_{C}\gamma_{k}}[\hat{H}_{C},\hat{A}_{k}]e^{-i\hat{H}_{C}\gamma_{k}}\ket{\psi_{k-1}(\bm{\gamma},\bm{\beta})},$

where $\gamma_{k}$ is initialized to a certain value $\gamma_{0}$. Once
$\hat{A}_{k}$ is selected, all parameters are optimized again, and if the cost
function has not reached a target value, a new layer can be added similarly.
In simulations on the MaxCut problems, ADAPT-QAOA converged faster than the
standard QAOA while reducing the number of CNOT gates and optimization
parameters by about 50% each, particularly when entangling gates were included
in the operator pool. Such a speedup is attributed to the concept of shortcuts
to adiabaticity [98, 99]. This concept has been crucial in the enhancement of
many ansatz designs which provide improved variations of QAOA, such as
digitized and counterdiabatic frameworks [100, 79, 80]. However, the drawback
of the method is that the selection of the mixing operators requires an
additional number of measurements that depends on how big the operator pool
is.

####  3.1.6 Recursive QAOA

Performance of QAOA can be limited by the $Z_{2}$ symmetry of the QAOA states
and the geometric locality of the ansatz; that is, the cost operators include
interactions only between nearest neighbor qubits concerning the underlying
graph. To address this, Bravyi et al. [83] proposed the Recursive QAOA (RQAOA)
as a non-local variant of QAOA that iteratively reduces the size of the
problem. At each step, RQAOA uses the output distribution of QAOA to compute
the $ZZ$-correlations of all pairs of edges in the graph, i.e.,
$M_{ij}=\expectationvalue{Z_{i}Z_{j}}{\psi(\bm{\gamma},\bm{\beta})},\
\forall(i,j)\in\mathcal{E}$. Then, it selects the pair(s) with the largest
magnitude of the correlation and imposes a parity constraint,

$Z_{j}=\text{sgn}(M_{ij})Z_{i}.$ (30)

This effectively eliminates one or more qubits from the Hamiltonian by
imposing a constraint on them. RQAOA then reruns the QAOA circuit on the
reduced Hamiltonian and repeats the process until the problem reaches a
predefined cutoff size. At this point, RQAOA solves the remaining problem
exactly using classical methods and reconstructs the final solution by
reinserting the eliminated qubits. While RQAOA is less studied compared with
the vanilla version, research interest is increasing as it emerges as a
promising QAOA variant on NISQ devices [101, 102, 65]. For example, Bae and
Lee [103] compared the performance of the level-1 QAOA with that of the RQAOA
applied to the MaxCut problem on complete graphs with $2n$ vertices. They
analytically demonstrated that in this particular scenario, the level-1 RQAOA
achieves the approximation ratio 1, while the approximation ratio of the
original QAOA at $p=1$ is strictly upper bounded as

$\alpha\leq 1-\frac{1}{8n^{2}}.$

####  3.1.7 Quantum alternating operator ansatzes

The process of ansatz design in QAOA is very versatile and can be extended to
much more far-reaching constructions. One such extension is the remodeling of
QAOA to the Quantum Alternating Operator Ansatz (QAOAnsatz) by Hadfield et al.
[84]. As introduced in Section 2.5, in QAOA, the ansatz structure alternates
between applying unitaries based on the cost and mixer Hamiltonians. The
extended framework allows for alternating between a more general set of
operators. This extension is based on considering general parameterized
families of unitary operators instead of only those corresponding to time
evolution under a fixed local Hamiltonian.

This altered ansatz structure allows for a broader set of problems to be
solved by this family of algorithms, especially in optimization problems that
have hard constraints that always need to be satisfied, defining feasible
subspaces, and soft constraints which need to be minimized in their violations
[84]. This ansatz supports representing a larger, potentially more useful, set
of states than the original formulation, with potential long-term impact on a
broad array of application areas [104].

Figure 5: Representation of the QAOAnsatz.

A novelty of the QAOAnsatzes is their different approach in encoding the
constraints of a graph into the ansatz. While the standard approach is to add
“penalties” to the cost Hamiltonian, Hadfield et al. [104] proposed to modify
the mixer Hamiltonian into XY-mixer, partial mixer, and others to encode
different constraints. It is worth noting that a recent effort to unify these
two different approaches into a single method was carried out by Ruan et al.
[105] in the so-called Unified Quantum Alternating Operator Ansatz (UQAOA).

As depicted in Figure 5, QAOAnsatz proposes an alternative and more generic
way of defining the different parts of the ansatz. A QAOAnsatz circuit is
characterized by two families of parameterized operators in a Hilbert space
$\mathcal{H}$: one of phase-separation operators, $\hat{U}_{P}(\gamma)$, that
depends on the objective function $f$; and one of mixing operators,
$\hat{U}_{M}(\beta)$, which depends on the domain and its structure, where
$\beta$ and $\gamma$ are real parameters. A depth-$p$ circuit consists of $p$
alternating applications of operators from these two families, i.e.,

$Q_{p}(\bm{\gamma},\bm{\beta})=\hat{U}_{M}(\beta_{p})\hat{U}_{P}(\gamma_{p})\cdots\hat{U}_{M}(\beta_{1})\hat{U}_{P}(\gamma_{1}).$
(31)

QAOAnsatz consists of states representable by the application of this type of
circuit to a suitable initial state $\ket{s}$:

$\ket{\psi(\bm{\gamma},\bm{\beta})}=Q_{p}(\bm{\gamma},\bm{\beta})\ket{s}.$
(32)

It provides a framework that allows almost any combinatorial optimization
problem to be modeled as a QAOA problem, with the objective functions encoded
as the sum of Pauli operator-based Hamiltonians, forming the phase separator
and mixing unitary operators. Many combinations and variations of these mixer
unitaries have been analyzed in recent literature. For example, the original
formulation of QAOA [12, 13] made use of transverse field based $X$-mixers for
unconstrained problems, while the XY-model Ring and Clique Mixers are
effective for Hamming weight constrained problems [106, 107]. Cook et al.
[106] compared the efficacy of classical states, and Dicke states as initial
states, assessed the impact of two distinct XY-Hamiltonian mixing operators,
and conducted an analysis of solution distributions via Monte Carlo sampling.
Their findings indicate that Dicke states enhance performance compared to
easily-prepared classical states. They suggest that the complete graph mixer
outperforms the ring mixer, though with a trade-off between improved
performance and more extended circuit depth. An intriguing aspect of their
study was that the standard deviation of solution distributions decreases
exponentially with the number of rounds, which has implications for the
feasibility of finding better solutions in deeper algorithm rounds. Despite
this, they found that high-quality solutions share patterns with a discretized
version of the quantum adiabatic algorithm, suggesting potential avenues for
efficient angle selection strategies.

Below we introduce a few notable QAOAnsatz variants with different mixer/phase
separator designs.

##### Grover Mixer QAOA:

For both constrained and unconstrained optimization problems, the use of
Grover-like selective phase-shifting operators has shown to be effective. One
such example is the work of Bärtschi and Eidenbenz [85], in which the Grover
Mixer QAOA (GM-QAOA) variant is proposed. This variation to QAOAnsatz makes
use of the Grover-like selective phase shift mixing operators, inspired by the
Grover Search quantum algorithm [108, 109]. This variant works for any NP
optimization application, which can be efficiently prepared with an equal
superposition of all feasible solutions. This design works incredibly well for
constraint optimization problems where not all possible variables are feasible
solutions, such as $k$-Vertex-Cover.

The GM-QAOA variant has significant benefits over the original algorithm, such
as not being susceptible to Trotterization errors or any other Hamiltonian
simulation errors, due to its operators being implemented exactly using only
standard gate sets. The design of the variant also allows solutions sharing an
objective value to be sampled with the same amplitude, which significantly
increases efficiency and stability.

The authors demonstrate the prowess of this framework on a set of significant
optimization problems. One such problem is the Traveling Salesman Problem, in
which an efficient algorithm is presented to prepare a superposition of all
possible permutations of $n$ numbers over $O(n^{2})$ qubits. Another problem
to which GM-QAOA is applied in this demonstration is the hard constraint
$k$-Vertex-Cover problem, as a standard benchmark against other combinatorial
optimization problems. Finally, in the problem of discrete portfolio
rebalancing, the application of GM-QAOA is demonstrated to outperform other
existing QAOA approaches, as it can restrict mixing to the feasible subspace
and provide transitions between all feasible states.

##### Threshold QAOA:

Another variation within the alternating operator ansatz framework is provided
by Golden et al. [86], based on the above discussion on various QAOA mixers.
The authors presented a variation of QAOA in which the standard phase
separation operator is replaced by a threshold function, returning a value of
1 for solutions with an objective value above a defined threshold and a value
of 0 otherwise. This variation is coined Threshold QAOA (Th-QAOA), in which
the threshold value is varied to reach a quantum optimization algorithm.
Although this algorithm is versatile enough to be constructed using any
previously studied QAOA mixers, in this work, the authors focused on the
combination with the Grover mixers, which have shown to be effective for
solving constrained [110] and unconstrained [85] optimization problems. This
application of Th-QAOA combined with the Grover mixer is called GM-Th-QAOA. It
was demonstrated that the algorithm could be classically simulated up to 100
qubits with relative ease because of memory optimization techniques applicable
to implementing the algorithm. The authors found that this variation of QAOA
outperforms other variants in terms of the approximation ratio for a range of
optimization problems, including MaxCut, Max-$k$-Vertex-Cover, and Max
Bisection.

##### Constraint Preserving Mixers:

A framework for constructing mixing operators that enforce hard constraints in
quantum optimization problems was introduced by Fuchs et al. [87]. The authors
generalized the XY-mixer, designed to preserve the subspace of “one-hot”
states, to the case of subspaces given by a number of computational basis
states. The underlying mathematical structure is exposed to minimize the cost
of the mixer in terms of CNOT gates, mainly when Trotterization is considered.
This work also introduces efficient decomposition algorithms for basis gates
and analyzes several examples of more general cases. Govia et al. [111]
proposed the free axis mixer quantum alternating operator ansatz called Free
Axis Mixer-QAOA (FAM-QAOA), which adds additional variational parameters in
the XY-plane of the mixer Hamiltonian. They explore the Hilbert space
expansion and the Z-phase error mitigation, showing that the ansatz
outperforms the standard QAOA, especially at low depths.

####  3.1.8 Warm-starting QAOA

Inspired by the recent progress in the study of the continuous relaxations of
NP-hard combinatorial optimization problems, Egger et al. [88] proposed to
“warm-start” the QAOA parameters based on the solution to the relaxed QUBO
problem, i.e., one with continuous variables instead of binary ones. They
considered two types of continuous-value relaxations, quadratic programming
(QP), which corresponds to the cases of QUBO where the matrix $\mathbf{Q}$ in
Eq. (3) is positive semidefinite, and semidefinite programming (SDP) when
$\mathbf{Q}$ is not positive semidefinite. In the simplest variant of Warm
Starting QAOA (WS-QAOA), one replaces the initial $n$-qubit equal-
superposition state $\ket{+}^{\otimes n}$ with the state

$\ket{s^{*}}=\bigotimes_{i=0}^{n-1}\hat{R}_{Y}(\theta_{i})\ket{0}^{\otimes
n},$ (33)

where $\theta_{i}=2\arcsin(\sqrt{c_{i}^{*}})$, with $c_{i}\in[0,1]$ is the
$i$-th coordinate of the optimal solution to the continuous-valued relaxation
QP. Moreover, the mixer Hamiltonian is modified accordingly to
$\hat{H}_{M}^{\text{(ws)}}=\sum_{i=0}^{n-1}\hat{H}_{M,i}^{\text{(ws)}}$, where

$\hat{H}_{M,i}^{\text{(ws)}}=-\sin(\theta_{i})\hat{X}-\cos(\theta_{i})\hat{Z}=\matrixquantity(2c_{i}^{*}-1&-2\sqrt{c_{i}^{*}(1-c_{i}^{*})}\\\
-2\sqrt{c_{i}^{*}(1-c_{i}^{*})}&1-2c_{i}^{*}).$ (34)

Therefore, the action of the mixer unitary
$\hat{U}_{M}^{\text{(ws)}}=e^{-i\beta\hat{H}_{M}^{\text{(ws)}}}$ on qubit $i$
can be implemented via single-qubit rotations
$\hat{R}_{Y}(\theta_{i})\hat{R}_{Z}(-2\beta)\hat{R}_{Y}(-\theta_{i})$.

In another variant of WS-QAOA, the optimum of the continuous-valued relaxation
is randomly rounded before using it as the initial state. A notable example is
the Goemans-Williamson random-hyperplane rounding of SDP relaxations for the
MaxCut problem. The most significant advantage of this approach is that it
provides initial states that already have the best approximation guarantee
available classically in polynomial time and can retain the GW bound at any
number of layers $p$. Therefore, the solution output by WS-QAOA is at least as
good as that given by GW rounding. Furthermore, WS-QAOA can be readily
incorporated into the workflow of recursive QAOA, and this variant (WS-RQAOA)
was shown in numerical simulations to give the best MaxCut results for both
random and full-connected graphs with 20 and 30 nodes. The WS-QAOA approach
thus provides an advantage over the standard QAOA at low depth, which is
particularly important for implementing on the NISQ devices.

####  3.1.9 FALQON

In the literature discussed thus far, the QAOA and its variants have primarily
been hybrid algorithms, using quantum computation alongside classical
optimization of variational parameters. This proves beneficial in the NISQ era
of quantum computers, as they are not fault-tolerant or stable enough to
handle an entire optimization problem independently and do not need to.
However, this may hinder performance in future quantum computers, as there
will be an efficiency bottleneck in passing information back and forth between
quantum and classical computers. The solution to this potential problem lies
in the quantum computer’s ability to encompass the full spectrum of processing
and optimization.

An introduction to this framework is given in the work by Magann et al. [66],
in which the authors introduced a feedback-based strategy for quantum
optimization. This algorithm is designed around qubit measurements to assign
values to quantum circuit variational parameters constructively. This
procedure results in an estimate of combinatorial optimization solutions that
improves monotonically with the circuit depth. Crucially, this measurement-
based feedback loop enables approximate solutions without classical
optimization, as the entire process can be done on the quantum device. This
purely quantum optimization loop is achieved through a direct connection to
Quantum Lyapunov Control (QLC) [89], which is a control strategy that uses
feedback to identify controls to manipulate the drive dynamics of a quantum
system.

The authors demonstrated the capabilities of this algorithm. They coined the
Feedback-based ALgorithm for Quantum OptimizatioN (FALQON) on combinatorial
optimization problems such as MaxCut on 3-regular and randomly generated non-
isomorphic graphs. The FALQON is defined similarly to the original QAOA, with
the “drift” and “control” Hamiltonians, $H_{p}$ and $H_{d}$, respectively,
rather than cost and mixer ones, although they have similar forms. The authors
begin by considering a quantum system whose dynamics are governed by

$i\derivative{t}\ket{\psi(t)}=\left(H_{p}+H_{d}\beta(t)\right)\ket{\psi(t)},$
(35)

and seek to minimise $\langle
H_{p}\rangle=\langle\psi(t)|H_{p}|\psi(t)\rangle$, which is done by designing
$\beta(t)$ such that

$\derivative{t}\langle\psi(t)|H_{p}|\psi(t)\rangle=A(t)\beta(t)\leq 0$ (36)

where $A(t)\equiv\langle\psi(t)|i[H_{d},H_{p}]|\psi(t)\rangle$ and
$\beta(t)=-A(t)$. This is an essential step in circumventing the need for a
classical optimizer since the updated parameters are taken directly from the
expectation value measurements.

Although this algorithm is designed for purely quantum computation for fault-
tolerant devices that do not yet exist, it still finds use in NISQ devices as
a way to improve the initialization of the standard QAOA. In the original
QAOA, the initial parameters are chosen at random. However, with the help of
FALQON, these seed parameters can be better chosen after a few iterations of
the purely quantum algorithm. It was demonstrated that this hybridization of
FALQON and QAOA, coined the FALQON+ [89], allows QAOA to start from a
parameter set that has a higher success probability and smoother solution
landscape. Performing the algorithm on a set of non-isomorphic graphs over 8
to 14 vertices, the authors find a significant increase in approximation ratio
and success probability with a minimal increase in circuit depth and noise
degradation. This makes the FALQON+ algorithm highly suitable for NISQ devices
as a warm-start technique that utilizes the best features of both the fully
quantum and hybrid approaches.

####  3.1.10 Fermionic QAOA

Yoshioka et al. [90] proposed the Fermionic Quantum Approximate Optimization
Algorithm (FQAOA) to solve combinatorial optimization problems with
constraints, utilizing fermion particle number preservation to impose these
constraints intrinsically. Many such problems feature constraints that can
negatively impact optimization algorithms when treated as soft constraints in
the cost function. FQAOA tackles this issue by using fermion particle number
preservation to impose constraints throughout the QAOA process intrinsically.
The authors offer a systematic guideline for designing the “driver”
Hamiltonian ($H_{d}$) for problem Hamiltonians with constraints. In the
context of the quantum adiabatic theorem, the driver Hamiltonian is used to
slowly transform a system Hamiltonian from its initial state to a cost
function-based problem Hamiltonian, ultimately leading to optimal solutions of
the cost function from the ground state of $H_{d}$ (Section 2.4.2). They
suggest choosing the initial state to be a superposition of states satisfying
the constraint and the ground state of the driver Hamiltonian. In the FQAOA
ansatz, the mixer unitary is generated by the driver Hamiltonian which is
carefully designed to satisfy specific conditions, ensuring that the
constraints of the combinatorial optimization problem are intrinsically
imposed. The driver Hamiltonian introduces hybridization between different
basis states by representing non-local fermions with hopping terms. This
hybridization allows the algorithm to effectively explore different solutions
in the search space.

FQAOA has demonstrated substantial performance advantages over existing
methods in portfolio optimization problems. According to the authors, the
Hamiltonian design guideline is valuable for both QAOA and Grover adaptive
search and quantum phase estimation in solving constrained combinatorial
optimization problems. This compatibility enables the application of existing
software tools developed for fermionic systems in quantum computational
chemistry to address constrained optimization challenges.

####  3.1.11 Other approaches

Wang et al. [91] proposed a method to deal with hard combinatorial
optimization problems where the energy landscape is rugged and the global
minimum locates in a narrow region of the cost function landscape. In such a
problem, the global minimum must satisfy a set of clauses $C$, encoded in the
cost Hamiltonian of QAOA. The authors found that the problem mainly originates
from the QAOA circuit rather than the cost function. So they decided to
exploit the combinatorial nature of the problem by selectively dropping out
the clauses defining the quantum circuit,

$\hat{H}_{C^{\prime}}=\sum_{c_{i}\in C^{\prime}\subset C}\hat{H}_{c_{i}},$
(37)

while keeping the cost function intact to ensure the uniqueness of the global
minimum. The quantum dropout of clauses helps smoothen the energy landscape,
making optimizing parameters easier. The numerical results confirmed QAOA’s
performance improvements with various types of quantum dropout implementation
and that the dropout of clauses in the circuit does not affect the solution.

Wurtz and Love [92] introduced the Spanning Tree QAOA (ST-QAOA) to solve
MaxCut problems using an ansatz derived from an approximate classical
solution. In the ST-QAOA ansatz, a classical solver is first used to find an
approximate solution for the MaxCut problem, typically represented by a
spanning tree of the graph. This approximate solution is then used to
construct a problem instance-specific circuit with $r$ rounds of gates. The
circuit is designed to reflect the problem structure, using classical
algorithm insights to tailor the quantum circuit specifically for the given
problem instance. When $r=1$, the ST-QAOA is guaranteed to match the
performance of the classical solver. As the number of rounds increases, the
ST-QAOA ansatz approaches the exact solution to the MaxCut problem. This
approach achieves the same performance guarantee as the classical algorithm
and can outperform the vanilla QAOA at low depths.

An additional modification to the ansatz construction of QAOA is given by the
work of Li et al. [112], in which the authors proposed modifications to both
the QAOA ansatz as well as the prescription for choosing the variational
parameters of the quantum circuit. First, the Gibbs objective function is
defined and shown to be superior to the energy expectation value,
$\expectationvalue{E}$, as an objective function for optimizing variational
parameters. Second, the authors describe an Ansatz Architecture Search (AAS)
algorithm for searching the discrete space of quantum circuit architectures
near QAOA to find a better ansatz. The Gibbs objective function is defined as
follows,

$f=-\log\langle e^{-\eta E}\rangle,$ (38)

where $\eta>0$ is a hyper-parameter based on the general properties of the
class of problems, $E$ is the energy of the Ising model used to encode the
optimization problem, and $f$ has a form similar to the Gibbs free energy in
statistical mechanics; hence the name. The exponential profile rewards the
optimization procedure for increasing the probability of low energy and de-
emphasizes the shape of the probability distribution at higher energies. The
authors propose greedy search as an affordable strategy for AAS. A model
$\mathcal{I}$ is defined on a graph $\mathcal{G}^{\mathcal{I}}$ with $m$
vertices, while $\mathcal{G}^{\mathcal{A}}$ is the ansatz graph obtained from
$\mathcal{G}^{\mathcal{I}}$ by removing some edges. The QAOA prescription is
to set $\mathcal{G}^{\mathcal{A}}=\mathcal{G}^{\mathcal{I}}$ and search
architectures by searching through graphs obtained by removing edges from
$\mathcal{G}^{\mathcal{I}}$. Given an instance $\mathcal{I}$, the search
starts with $\mathcal{G}^{\mathcal{A}}=\mathcal{G}_{m}$ at level 0. Then level
by level, ansatzë are expanded by removing one two-qubit gate from the best
ansatz of the previous level, scored, and the best of them is selected as the
output of this level. The output architectures at level $l$ have $l$ two-qubit
gates (i.e., edges of the graph) removed. It was found that applying these
modifications to a complete graph Ising model results in a 244.7% median
relative improvement in the probability of finding a low-energy state while
using 33.3% fewer two-qubit gates.

Villalba-Diez et al. [31] also proposed a modification to the cost
Hamiltonian. Their improved ansatz, “Modified QAOA”, performs a conditional
rotation of $\gamma$ to each node connected to another if the second is in
state $\ket{1}$. This is done by concatenation of two $U_{3}(\gamma/2,0,0)$
and $U_{3}(-\gamma/2,0,0)$ gates. They follow this with a conditional CX
rotation to each pair of nodes. They tested their approach in simulations for
up to 30 network nodes and for $p=1$ and observed significant increase of the
approximation ratio achieved; compared to the vanilla QAOA.

###  3.2 Parameter Optimization

Problem Addressed |  Approach
---|---
Initial Parameter Search |  Heuristic strategies for initializing optimizations [15]
Layer-by-layer optimization [113]
Warm-start techniques using GNNs [114]
Transferability among different QAOA instances based on local characteristics
of subgraphs [115]
Parameter reusability for similar problem instances [116, 117]
Parameter initialization using TQA method [118]
Gradient-free Parameter Optimization |  Comparison of gradient-based and gradient-free methods [119, 120, 121]
Genetic algorithm approach for optimization [122]
Robust control optimization techniques [123]
Gradient-based Parameter Optimization |  Gradient-based approaches with machine learning techniques [124]
Gradient-based optimization with tensor networks [125]
Stochastic Gradient Descent in quantum context [63]
Surrogate-model based optimization [126]
Policy gradient-based reinforcement learning algorithm for QAOA [127]
BFGS optimization algorithm for QAOA [128]
Machine Learning for Parameter Optimization |  Parameter correlation and machine learning models [129]
Meta-learning for QAOA optimization [130, 131]
Clustering for setting QAOA parameters [19]
GNN-based prediction of QAOA parameters [132]
RL and KDE techniques for parameter optimization [133, 101]
Remedies for Barren Plateaus |  Incremental growth of circuit depth during optimization [134]
Parameter concentraion as an inverse polynomial with respect to the problem
size [135]
Parameter Concentration & Symmetry |  Inverse polynomial concentration of optimal parameters [135]
Exploiting symmetry in objective functions, cost Hamiltonians, and QAOA
parameters to improve optimization [136, 15, 93, 137]
Analytical Solutions for Optimal Parameters |  Deriving analytical solutions for optimal parameters [138]
Table 2: Summary of approaches in QAOA parameter optimization.

In this section, we discuss key aspects of parameter optimization in QAOA.
This covers various approaches to finding good initial parameters, which
becomes increasingly important as the depth and complexity of the QAOA circuit
increase. The original proposal of the algorithm suggests a random selection
of initial parameters within a range believed to be close to the optimal
parameters. However, this method can often hinder the algorithm’s performance,
especially when the cost function landscape is rugged and contains numerous
local minima. Therefore, developing efficient and reliable parameter
optimization strategies is crucial to achieving optimal QAOA performance. This
section also covers the selection of appropriate classical optimization
algorithms for investigating the parameter space and strategies for overcoming
barren plateaus (Table 2).

####  3.2.1 Finding good initial parameters

To address the issue of a random selection of initial parameters, researchers
have proposed various techniques to find better initial parameters. One such
approach is provided by Zhou et al. [15], who developed an efficient parameter
optimization procedure for QAOA applied to MaxCut problems. They proposed
heuristic strategies for initializing optimizations, allowing them to find
quasi-optimal $p$-level QAOA parameters in $O[\text{poly}(p)]$ time compared
to random initialization, which requires $2^{O(p)}$ optimization runs for
similar performance. Their heuristic strategies, such as INTERP and FOURIER
heuristics, showed promising results in finding optimal parameters for large
p-level QAOA.

Lee et al. [113] proposed a parameter fixing strategy for QAOA training to
address the difficulty of finding optimal parameters at large p values and
achieve higher approximation ratios. The algorithm initializes the QAOA
circuit with optimal parameters from previous layers, finds the best
parameters for each layer, fixes them, and then adds another layer on top of
the previous one with new parameter values to optimize.

Jain et al. [114] proposed a more efficient initialization of QAOA using Graph
Neural Networks (GNNs). This approach builds on the precedent of warm-start
techniques, aiming to initiate the initialization process closer to the target
parameters. The GNN approach generalizes across graph instances and increases
graph sizes, speeding up inference time across graphs. After GNN
initialization, the authors explore several optimizers, including quantum
aware/agnostic methods and machine learning techniques such as reinforcement
learning, making the training process an end-to-end differentiable pipeline.

Another technique to improve initial parameters is based on parameter
transferability across graphs, as proposed by Galda et al. [115]. They showed
that optimal QAOA parameters converge around specific values, and their
transferability among different QAOA instances can be predicted based on local
characteristics of the subgraphs composing the original graph. Building on
this idea, Shaydulin et al. [116] proposed reusing optimal QAOA parameters for
a given problem as an initial point for similar problem instances,
demonstrating that this approach not only improves solution quality but also
reduces the number of evaluations required. Shaydulin et al. [117] also
developed QAOAKit, a Python framework that includes a set of pre-optimized
parameters and circuit templates for QAOA, leveraging parameter
transferability to generate high-quality initial guesses for parameter
optimization.

Sack and Serbyn [118] suggested initializing QAOA parameters based on the
Trotterized quantum annealing (TQA) method, parameterized by a single
variable, the Trotter time step. They established a heuristic way of finding
the optimal time step based on TQA protocol performance, showing that this
method of initialization can avoid the issue of false minima for a wide range
of time steps, allowing QAOA to find solutions comparable to the best outcomes
obtained from an exponentially scaling number of random initializations.

####  3.2.2 Selecting an appropriate optimizer

Selecting an appropriate optimization algorithm is crucial for enhancing the
performance of QAOA. This subsection reviews various optimization approaches
for improving QAOA parameters, including gradient descent, policy gradient,
BFGS algorithm, and machine learning techniques. We categorize these methods
into three broad categories: gradient-free, gradient-based, and ML.

##### Gradient-free methods

In optimization algorithms, gradient-free methods have gained attention due to
their computational efficiency. For example, McClean et al. [1] found that
significantly fewer functional evaluations are required when using gradient-
free methods in VQE. Shaydulin et al. [116] were among the first to benchmark
different gradient-free optimizers on QAOA. They compared the solution quality
of QAOA produced by six different gradient-free optimizers, including BOBYQA,
COBYLA, NEWUOA, Nelder-Mead, PRAXIS, and SBPLX. It was found that for a fixed
number of functional evaluations allowed, using BOBYQA within the APOSSM
framework, which allows for parallel optimization, led to the best
performance. Despite this, QAOA’s performance was severely challenged with
increasing layers across all gradient-free optimizers tested, suggesting the
hardness of parameter optimization even at modest circuit depths. More
recently, Fernández-Pendás et al. [119] investigated the performance of twelve
different classical optimizers for QAOA optimization and found that gradient-
based methods like Adam and SPSA have computational times up to two orders of
magnitude higher compared to gradient-free methods such as COBYLA, Powell and
Nelder–Mead, despite achieving similarly good results.

In a broader context of hybrid quantum-classical algorithms, Bonet-Monroig et
al. [120] tested four commonly used gradient-free optimization methods: SLSQP,
COBYLA, CMA-ES, and SPSA, on finding ground-state energies of a range of small
chemistry and material science problems. The study, although not explicitly
focused on QAOA, demonstrated the necessity for tailoring and hyperparameter-
tuning known optimization techniques for inherently-noisy variational quantum
algorithms and highlighted that the variational landscape that one finds in a
VQA is highly problem- and system-dependent.

Similarly, in a study focused on variational hybrid quantum-classical
algorithms, specifically the variational quantum linear solver, Pellow-Jarman
et al. [121] examined the impact of several gradient-free and gradient-based
classical optimizers on the performance of these algorithms. They analyzed
both the average rate of convergence and the distribution of average
termination cost values of the classical optimizers, considering the effects
of noise. Their findings indicate that realistic noise levels on NISQ devices
pose a significant challenge to the optimization process, negatively affecting
all classical optimizers. However, they found that the gradient-free
optimizers, Simultaneous Perturbation Stochastic Approximation (SPSA) and
Powell’s method, and the gradient-based optimizers, AMSGrad and BFGS,
performed the best in the noisy simulation and were less affected by noise
than other methods. In particular, SPSA emerged as the best-performing method.
Conversely, the COBYLA, Nelder–Mead, and Conjugate-Gradient methods were the
most heavily affected by noise, with even slight noise levels significantly
impacting their performance. The study suggests that if noise levels can be
significantly improved, gradient-based methods, which performed better than
the gradient-free methods with only shot-noise present, may be preferred in
the future.

Acampora et al. [122] addressed the remaining shortcomings of the above
gradient-free optimization methods with a new approach. The authors proposed
an evolutionary approach to optimization using genetic algorithms. A genetic
algorithm is a search heuristic that reflects the process of natural selection
where the fittest individuals are selected for reproduction to produce
offspring of the next generation. The authors expressed that such a
population-based heuristic could more efficiently process candidate solutions
and converge to an optimal parameter set for a QAOA circuit. This evolutionary
approach is demonstrated on noisy quantum devices and compared with popular
gradient-free optimizers (COBYLA, Nelder–Mead, Powell’s modified method, and
SPSA) when solving the MaxCut problem for graphs with 5 to 9 nodes. The
authors found that the proposed genetic algorithm statistically outperforms
other gradient-free algorithms in achieving higher approximation ratios for
the same QAOA circuits. Despite these promising results, the authors noted
that genetic algorithms are known to have limitations, such as scalability in
the number of parameters to learn and premature convergence, encouraging more
research to build upon this proposal for a more reliable gradient-free
optimization solution.

In another recent work, Cheng et al. [139] introduced a novel gradient-free
optimizer called Double Adaptive-Region Bayesian Optimization (DARBO), which
demonstrated robustness against measurement noise and quantum noise. This
optimizer explores the QAOA landscape using a Gaussian process surrogate model
and iteratively suggests the optimal parameters restricted to two auto-
adaptive regions. Incorporating the two adaptive regions makes it more robust
to noise and different initial parameters. Upon benchmarking against other
optimizers (Adam, COBYLA, SPSA) for the MaxCut problem on weighted 3-regular
graphs, DARBO showed superior performance in simulations with measurement shot
noise. Furthermore, the authors also demonstrated that DARBO remained
effective on superconducting quantum computers despite hardware noise by
integrating with proper quantum error mitigation techniques.

In addition to the previously discussed methods, robust control optimization
techniques have also been explored in the context of QAOA. Dong et al. [123]
demonstrated that the error of QAOA simulation could be significantly reduced
by robust control optimization techniques, specifically by sequential convex
programming (SCP). This approach ensures error suppression in situations where
the source of the error is known but not necessarily its magnitude. The study
showed that robust optimization improves the objective landscape of QAOA and
overall circuit fidelity in the presence of coherent errors and errors in
initial state preparation.

##### Gradient-based Approaches

Gradient-based strategies are one of the most commonly used methods for
parameter optimization, which come in various flavors. The gradient descent
method is a first-order iterative optimization algorithm for finding a local
minimum of a differentiable function. Gradient descent takes repeated steps in
the opposite direction of the gradient because the direction of the gradient
is the direction toward the local maximum.

Combining the gradient descent method with machine learning, Crooks [124]
optimized QAOA on a classical computer using automatic differentiation and
stochastic gradient descent using QuantumFlow, a quantum circuit simulator
implemented with TensorFlow. Authors amortized the training cost of QAOA
circuits by training variational parameters on batches of problem instances
(graphs), thus alleviating the training procedure. Streif and Leib [125] also
simulated on classical hardware with tensor networks instead of making
parameter updates by repetitive calls of the QPU.

As a notable variant in the gradient descent family, Stochastic Gradient
Descent (SGD) has been widely used in machine learning for training deep
neural networks and made it an option for efficient exploration of quantum
circuits using classical simulation due to accelerated optimization and ease
of use. However, implementing stochastic gradient descent directly on a
quantum computer is demanding, requiring many measurements for each gradient
component, which can be computationally costly and complex. Sweke et al. [63]
makes use of SGD, which replaces the exact partial derivative at each
optimization step with an estimator of the partial derivative to tune the
value and provide numerical results using a gradient, offering a practical way
to utilize SGD in a quantum context. Sung et al. [126] introduced a surrogate-
model-based algorithm called the Model Gradient Descent (MGD), which is also
inherently stochastic. This method incorporates a least-squares quadratic
model to estimate the gradient of the objective function, allowing the
previously evaluated points to be reused and leading to more efficient
optimization. Empirical comparisons with other popular optimizers (SGD, SPSA,
BOBYQA, Nelder-Mead) suggested that stochastic optimizers such as MGD may be
advantageous in realistic settings since they are more robust to variations in
problems and show good tolerance to noise.

The work by Yao et al. [127] is focused on the fact that the original QAOA
selects initial parameters at random and optimizes them through gradient-based
methods, which can be computationally expensive and vulnerable to noise in
NISQ devices and may hinder the optimization process. Noting this, the authors
suggested a new method for selecting and optimizing the variational parameters
of the model. This is achieved by assigning a probability distribution to
randomly selected initial parameters and using this distribution as a basis
for a policy gradient-based reinforcement learning algorithm to find optimal
variational parameters. It was demonstrated that this policy-gradient-based
model (PG-QAOA) does not require derivatives to be computed explicitly and can
perform well even if the objective function is not smooth concerning the
error. This probability-based approach also has the advantage of resisting
perturbations and noise. In this sense, policy-gradient-based reinforcement
learning algorithms are well suited for optimizing the variational parameters
of QAOA in a noise-robust fashion, opening up the way for developing
reinforcement learning techniques for continuous quantum control.
Additionally, similar to the MGD extension for gradient descent, the vanilla
policy gradient method [127] can also be extended with a surrogate model to
reduce the variance in the estimation of the policy gradient, which is dubbed
the Model Policy Gradient (MPG) method [126]. Like MGD, MPG showed good
tolerance to noise and robustness to problem variations.

In the work by Lotshaw et al. [128], the effectiveness of circuit optimization
using BFGS was assessed against exact optimization software and brute force
solutions for several graphs up to $p=2$. Empirical results confirmed that
BFGS could return optimal QAOA angles in all the test cases. However, it is
still unclear how BFGS will behave for larger parameter vectors, i.e., for
$p\geq 3$. The authors also found that optimized angles returned by BFGS
reveal various symmetry patterns, where multiple angle solutions gave the same
expectation value of the cost function. In light of this, they suggest that
appropriate heuristics may be employed to select parameters more efficiently.

##### Machine Learning Approaches

In addition to gradient-based methods, machine learning has been investigated
as a different way to find optimal parameters for QAOA and enhance the
optimization process.

Alam et al. [129] applied machine learning techniques to accelerate QAOA
optimization based on parameters’ correlation. The authors noted a correlation
among parameters of the lower-depth and higher-depth QAOA layers, so they
exploited it by training machine learning models to predict the variational
parameters close to the optimal values. Then, these quasi-optimal parameters
are fine-tuned with classical optimizers to generate the final solution. The
authors trained four machine learning models: Gaussian Process Regression
(GPR), Linear Regression (LM), Regression Tree (RTREE), and Support Vector
Machine Regression (RSVM). They found that the proposed machine learning-based
approaches can shorten the optimization iterations by 44.9% on average.

A meta-learning approach based on classical Long Short-Term Memory (LSTM)
neural networks was also investigated by Wang et al. [130] and Wilson [131],
where similar conclusions were drawn on the goodness of meta-learner
techniques for QAOA optimization. In [130], QAOA with meta-learning (MetaQAOA)
for the MaxCut problem was proposed: an LSTM neural network was used as a
black-box optimizer in order to help find optimal QAOA parameters. Numerical
simulations showed that MetaQAOA converged faster and to a better value than
the vanilla QAOA with local optimization methods such as Nelder–Mead and
L-BFGS-B. Similarly, Wilson [131] compared the performance of an LSTM meta-
learner to evolutionary strategies, L-BFGS-B and Nelder-Mead approaches,
confirming the results of Wang et al. [130] and showing that the meta-learner
applied to a QAOA problem finds the global optima more frequently than all
other optimizers tested in the paper, is more resistant to noise and can
easily generalize to larger problems even if it was trained on small problems.

Moussa et al. [19] made use of unsupervised ML, namely clustering, for setting
the QAOA angles without optimization. They considered several inputs to the
clustering algorithm, including the angle values, instance features, and the
output from a variational graph autoencoder. Their findings demonstrated that
such a method is effective in learning how to set QAOA parameters, reducing
circuit calls while maintaining a relatively small reduction in the
approximation ratio of less than 1–2%. They achieved comparable results to
those obtained through exhaustive angle optimization, translating to
significant reductions in the required circuit calls.

Deshpande and Melnikov [132] used a Graph Neural Network (GNN) to predict
QAOA’s optimal parameters for unseen MaxCut instances, with up to nine
vertices and a depth of $p=3$. The GNN could predict quasi-optimal QAOA’s
parameters within 2.7% of the optimal parameter solution, which could then be
used as a warm-start for QAOA. However, the scalability of this approach is
uncertain, as it requires many training instances for the GNN to perform well
in the prediction tasks.

Reinforcement Learning (RL) has also been investigated in the VQA framework to
improve parameters optimization [140, 141]. On this matter, some papers
explored the potential of RL in assisting QAOA’s optimization for finding
optimal parameters [133, 101]. Khairy et al. [133] try to find optimal QAOA
parameters through two different machine learning methods: an RL technique and
a Kernel Density Estimation (KDE) approach. The RL framework trains a policy
network to optimize QAOA circuits. The network exploits geometrical
regularities in the QAOA energy landscapes to efficiently find high-quality
solutions for unseen test instances with only a few hundred quantum circuit
evaluations. The KDE technique is used to create a generative model of optimal
QAOA parameters, which can be employed to generate new parameters and quickly
solve test instances. Extensive simulations with IBM Qiskit Aer demonstrated
that both the proposed methods are effective in finding good QAOA parameters,
achieving superior approximation ratios compared to other commonly used off-
the-shelf optimizers. Finally, Patel et al. [101] uses RL to enhance the
performance of the RQAOA (Section 3.1.6). In particular, they compared the
original RQAOA [83] with a proposed RL-enhanced RQAOA variant (RL-RQAOA). The
latter trains the circuit’s parameters via RL and uses correlations between
qubits to perform variable elimination at every iteration of the algorithm.
Through simulations over an ensemble of randomly generated weighted
$d$-regular graphs, the authors empirically showed that a $p=1$ RL-RQAOA
consistently outperforms RQAOA and simple classical RL agents.

##### Others

In Barkoutsos et al. [142], they proposed using the Conditional Value-at-Risk
(CVaR) instead of choosing the sample mean of the expectation values as the
objective function. CVaR is a risk metric that estimates the expected loss of
a portfolio under a specified confidence level by focusing on the tail end of
the loss distribution. The researchers demonstrated that employing the CVaR
aggregation function in QAOA enabled the algorithm to achieve optimal
solutions more rapidly in simulations and on real quantum hardware, such as
the IBMQ Poughkeepsie 20-qubit device.

To address the difficulty of finding optimal parameters at large $p$ values
and to achieve a higher approximation ratio, Lee et al. [113] proposed a
parameter fixing strategy for QAOA training. Starting from $p=1$ and
continuing to a desired $p$ level, the algorithm initializes QAOA with the
optimal parameters from previous layers. The algorithm finds the best
parameters for each layer, fixes them, and then adds another layer on top of
the previous one with new parameter values to optimize.

In their study, Lotshaw et al. [128] developed a search heuristic for QAOA
parameter optimization that is effective for a wide range of graphs, which
also significantly decreases computational expenses when compared with the
Broyden-Fletcher-Goldfarb-Shanno (BFGS) search with random seeding, which is a
widely used optimization algorithm. They achieved this by examining how the
optimized angle patterns based on a wide range of graphs can help efficiently
identify suitable approximate angles. They demonstrated that identifying
consistent patterns among the optimized variational parameters is an efficient
heuristic for solving MaxCut problems with up to 9 vertices with up to $p=3$
QAOA.

####  3.2.3 Overcoming barren plateaus

A significant challenge in training parameterized quantum circuits, such as
QAOA, is addressing the issue of barren plateaus in the cost function
landscape (Section 2.4.3). Barren plateaus are regions where the gradients
concerning the trainable parameters vanish exponentially in the number of
qubits, causing the optimization process to stall. To tackle this problem,
several approaches have been proposed in the literature, aiming to improve the
optimization process and help QAOA converge to better solutions.

One promising strategy to overcome this issue is presented in the work of
Skolik et al. [134], in which a layerwise learning strategy is developed.
During optimization, the circuit depth is grown incrementally, with only
subsets of parameters being updated with every training step. In this
approach, the circuit structure and a number of parameters are successively
grown while the circuit is trained, and the randomization effects are
contained in subsets of the parameters in all the training steps. This avoids
initializing on a plateau and reduces the probability of creeping onto a
plateau during training. The authors demonstrate the success of this strategy
in an image classification problem with a general parameterized quantum
circuit, which obtained an average generalization error of 8% lower than in
standard learning schemes, but the methodology applies to all VQAs, such as
QAOA.

The phenomenon of parameter concentration in QAOA circuits has been
investigated by Akshay et al. [135]. They found that optimal parameters
concentrate as an inverse polynomial concerning the problem size, which is
beneficial for improving circuit training. Empirical investigation revealed
two symmetric branches of optimal parameters, within which parameters
concentrated in a fixed range of values as the number of qubits varied. This
concentration effect allows training a depth-$p$ QAOA on a fraction $w<n$ of
qubits and asserting that these parameters are nearly optimal on $n$ qubits
and $p$ layers, thereby reducing training time.

Dupont et al. [143] investigated the growth and spread of the entanglement
resulting from optimized and randomized QAOA circuits to solve the MaxCut
problem on different graphs. The study finds a volume-law entanglement barrier
between the initial and final states. Entanglement barrier $S\sim N$ must be
crossed for large-depth QAOA circuits, making entanglement-based simulation
methods challenging. This study also investigates the entanglement spectrum in
connection with random matrix theory. The results are compared with a quantum
annealing protocol, and implications for the simulation of QAOA circuits with
tensor network-based methods are discussed.

Finally, a promising general attempt at tackling the problem of barren
plateaus stems from the idea of beginning the optimization process closer to
the target parameters (Section 3.2). This may seem like an obvious solution.
However, it is challenging to execute in practice because the solution
landscape is almost entirely unknown in most variational problems.

####  3.2.4 Parameter transferability and reusability

One promising approach to finding optimal QAOA parameters lies in the
transferability and reusability of optimal parameters across different problem
instances. This concept builds on the observation that optimal parameters tend
to concentrate around specific values and that these values can be transferred
from one problem instance to another based on their local characteristics.

Galda et al. [115] provided a theoretical foundation for parameter
transferability in QAOA. They showed that optimal QAOA parameters converge
around specific values, and the transferability of these parameters among
different QAOA instances can be predicted and described based on the local
characteristics of the subgraphs composing the original graph. This
observation provides a method for identifying categories of combinatorial
optimization problems where QAOA and other VQAs can offer significant speedup.

Based on this idea, Shaydulin et al. [116] proposed to reuse the optimal QAOA
parameters for a given problem as an initial point for similar problem
instances. They demonstrated that this not only improves the quality of the
solution by avoiding the local optima but also reduces the number of
evaluations required to reach it. Building on this, Shaydulin et al. [117]
leveraged the property of optimal parameter transfer across similar graphs and
proposed QAOAKit, a Python framework that includes a set of pre-optimized
parameters and circuit templates for QAOA. Given an input graph, quasi-optimal
parameters are obtained through a graph isomorphism certificate for the input
graph, which is then employed as a key to extract the angles from QAOAKit’s
database. If optimal angles are not present in the database for a specific
graph instance, the system will provide the closest fixed angles instead.

####  3.2.5 Leveraging parameter symmetries

Parameter symmetries can be leveraged to simplify the optimization process and
eliminate degeneracies in the parameter space, contributing to more efficient
QAOA performance. This subsection discusses various works exploring and
exploiting QAOA parameters’ symmetries for improved optimization, focusing on
symmetry in objective functions, cost Hamiltonians, and QAOA parameters.

##### Symmetry in Objective Functions and Cost Hamiltonians

Shaydulin and Wild [136] established a connection between the symmetries of
the objective function and the cost Hamiltonian concerning the QAOA energy.
They showed that excluding terms connected by symmetry could significantly
reduce the cost of evaluating the QAOA energy. They used fast graphs and
automorphism solvers to compute the problem’s symmetries. Although their
approach provides a median speedup of 4.06 for $p=1$ on 71.7% of the graphs
considered, on a benchmark where 62.5% of the graphs are known to be hard for
automorphism solvers, the automorphism calculation could require more time
than the one saved by exploiting symmetry in the worst-case scenario.

Shaydulin et al. [137] investigated the correlation between QAOA and the
inherent symmetries of the target function to be optimized. They revealed how
the symmetries of the objective function result in invariant measurement
outcome probabilities among states connected by those symmetries, regardless
of the number of layers or algorithm parameters employed. Using machine
learning techniques, the authors leveraged these symmetry considerations to
predict the QAOA performance accurately—by analyzing a small set of graph
symmetry properties, they could predict the minimum QAOA depth required to
achieve a desired approximation ratio on the MaxCut problem.

##### Symmetry in QAOA Parameters

Akshay et al. [135] investigated the phenomenon of parameter concentration in
QAOA circuits, and they found that the optimal parameters concentrate as an
inverse polynomial concerning the problem size, which is beneficial for
improving circuit training. From empirical investigation, authors identified
two symmetric branches of optimal parameters; within these branches,
parameters concentrated in a fixed range of values as the number of qubits
varied. The concentration effect allows training a depth-$p$ QAOA on a
fraction $w<n$ of qubits and asserting that these parameters are nearly
optimal on $n$ qubits and $p$ layers, thereby reducing training time. In other
words, if parameter concentration occurs, the optimal set of parameters for
$n$ qubits is polynomially close to the optimal set of parameters for $n+1$
qubits.

Shi et al. [93] investigated the connection between symmetries in the input
graphs and redundancy in ma-QAOA parameters [77], revealing that symmetries
can result in a reduction of the number of parameters without decreasing the
quality of the solution. The authors analyzed all the connected, non-
isomorphic graphs with eight nodes, noticing that in over two-thirds of these
graphs, the same accuracy ratio on the MaxCut problem can be obtained by
reducing the number of parameters by 28.1%, exploiting the natural symmetries
of the graphs. Furthermore, they demonstrated that in 35.9% of the graphs, the
aforementioned reduction could be accomplished by utilizing the largest
symmetry. On the other hand, in the cases where the reduction in the number of
parameters led to a decrease in performance, utilizing the largest symmetry
led to a mere 6.1% decrease in the cost while successfully reducing the
parameter count by 37.1%.

Zhou et al. [15] suggested an approach to parameterize QAOA, which could
simplify the optimization process by decreasing the dimension of the search
space. This was achieved by identifying and eliminating degeneracies arising
from inherent symmetries in the parameter space, including time-reversal
symmetry and $\mathbb{Z}_{2}$ symmetry, before searching for patterns in
optimal QAOA parameters. Moreover, for QAOA applied to MaxCut problems on
regular undirected (udR) graphs, there was an additional symmetry due to the
structure of the problem that created redundancy. This process of removing
degeneracies creates a more navigable parameter space, facilitating a smoother
and more effective search for optimal QAOA parameters.

Apart from using classical optimizers in a variational loop, optimal QAOA
parameters can sometimes be derived analytically. Wang et al. [138] derived
analytical expressions to solve optimal parameters for the level-1 QAOA
applied to MaxCut on general graphs. Although the analysis can be extended to
higher $p$ values theoretically, the number of terms involved quickly becomes
intractable for direct calculation. Therefore, the authors proposed a
fermionic representation for a specific instance of MaxCut: the ring of
disagrees, or the one-dimensional antiferromagnetic ring. This approach
translates the QAOA-induced evolution of the system into quantum control of a
group of independent spins, allowing for the derivation of analytical
solutions for any $p$, thus simplifying the search for optimal parameter
values. By exploring symmetries among parameter values, the authors identified
a lower-dimensional sub-manifold that could minimize the search effort.
Furthermore, they conducted a numerical investigation into the parameter
landscape and empirically demonstrated that all minima are global minima.

###  3.3 Computational Resource Efficiency

In this section, we delve into the computational resource efficiency of QAOA,
focusing mainly on the time it takes to reach desired solutions. We explore
the speedup potential of QAOA over classical algorithms, highlighting
instances where it has demonstrated superiority (Section 3.3.1). However,
obstacles that hinder the realization of quantum speedups with QAOA also
exist, such as the challenges in parameter optimization and the overheads of
error correction in early fault-tolerant quantum computers (Section 3.3.2).
Moreover, we highlight several strategies aimed at enhancing the runtime
performance of QAOA (Section 3.3.3), in addition to the ones that focus on
improving parameter optimization discussed in Section 3.2. By examining these
aspects, we aim to provide a comprehensive analysis of the computational
resource efficiency of QAOA, offering insights into its potential for enabling
quantum advantage in optimization problems.

####  3.3.1 Speedup potential

The QAOA is considered one of the leading candidate algorithms to achieve a
quantum advantage over classical algorithms and quantum annealing. One key
aspect in determining this advantage is the ability of the QAOA to solve
problems faster than other algorithms, thereby achieving a quantum speedup.
This subsection will explore recent research efforts that shed light on the
QAOA’s potential for achieving quantum speedup in different problem domains.

Based on the amortization of the training cost by optimizing batches of MaxCut
problem instances, Crooks [124] argued that an analysis of the computational
complexity of QAOA hinges on the number of gates needed to implement a single
instance of the quantum evolution. Since the required number of QAOA steps for
a given performance does not appear to be strongly correlated with the problem
size, the primary limiting factor on a gate-based quantum computer is the
number of two-qubit gates required to implement a single round of the
algorithm. Based on their analysis, QAOA for MaxCut on an $n$-node graph is
expected to require $O(n^{2}p)$ gates and have a run time of $O(np)$ (assuming
$O(n)$ gates can be applied in parallel), where $p$ is the number of layers in
the QAOA circuit. In contrast, the classical Goemans-Williamson (GW) algorithm
requires a run time of $O(nm)$ for irregular graphs (ignoring logarithmic
factors), where $m$ is the number of edges. These findings suggest that QAOA,
even at modest depths, may offer a speedup over its classical counterpart for
dense graphs.

QAOA also exhibits a speedup potential in the Minimum Vertex Cover (MVC)
problem, as demonstrated by Zhang et al. [144]. In their study, they applied
QAOA with varying numbers of layers ($2\leq p\leq 10$) to find the MVC on an
undirected graph consisting of 10 vertices and 16 edges. They found that QAOA
was able to effectively solve the MVC problem within a computational time
complexity of $O[\text{poly}(k)+\text{poly}(p)]$, where $k$ represents the
number of iterations in the optimization process. In contrast, the time
complexity of a competitive decision algorithm for MVC is $O(2n^{2}+n^{4})$,
with $n$ being the total number of vertices in the graph. Based on this
comparison, the authors concluded that QAOA provides an exponential
acceleration for large MVC problems.

In another study, Ebadi et al. [26] implemented QAOA on 2D Rydberg atom arrays
with up to 289 qubits. In their experiment, QAOA was applied to find the
Maximum Independent Set (MIS) on 115 randomly generated graphs of various
sizes, with the number of vertices ranging from 80 to 289. They benchmarked
the results of the quantum algorithm against a classical counterpart,
Simulated Annealing (SA) [145]. On graph instances in the deep-circuit regime,
where $\delta_{\text{min}}>1/T$, that is, the minimum energy gap
$\delta_{\text{min}}$ of a graph is large enough to be resolved in the
duration of the quantum evolution $T$, QAOA exhibited a superlinear quantum
speedup compared to SA. Specifically, for SA, the probability of observing an
MIS scales as $P_{\text{MIS}}=1-\exp(-C\eta^{-1.03})$, where $\eta$ is a
parameter characterizing the difficulty to reach the global optimum for a
particular graph. On the other hand, QAOA gave rise to an improved scaling,
$P_{\text{MIS}}=1-\exp(-C\eta^{-0.63})$. Since the runtime needed to find a
solution is proportional to $1/P_{\text{MIS}}$ by repeating the experiment,
the smaller exponent in the scaling for QAOA thus implies a quantum speedup
over SA. However, it should be noted that the observed speedup is specific to
graph instances in the deep-circuit regime, and it remains an open question
whether this advantage can be extended to more general cases.

QAOA has demonstrated its ability to provide quantum speedup in optimization
problems and other domains. One notable example is the unstructured search
problem, where Jiang et al. [5] proposed a novel quantum algorithm by
incorporating the QAOA circuit and replacing the original diffusion operator
in Grover’s algorithm with the transverse field. Their approach showcased the
potential of QAOA in unstructured search, achieving a near-optimal query
complexity of $T\sim O(\sqrt{N})$ with an intermediate number of layers ($p\gg
1$), where $N$ represents the search space size. This result demonstrates a
quadratic quantum speedup similar to Grover’s original algorithm. In a
separate study, Niu et al. [146] investigated the dependence of the success
probability of the QAOA on its circuit depth $p$ by analyzing its performance
for the state transfer problem in a one-dimensional qubit chain of length $N$
using two-qubit XY Hamiltonians and single-qubit Hamiltonians. The authors
derived analytical expressions for QAOA’s success probability scaling as a
function of the circuit depth. Interestingly, they established a connection
between the state transfer problem and Grover’s search algorithm, where the
$p$-th Grover iteration for searching the transferred state from an initial
state can be represented by the unitary realized by a depth-$p$ QAOA circuit.
In the low-depth limit, $p\to 1$, the total number of steps required to
achieve the target state is of order $O(N)$, producing the quadratic Grover-
like speedup. More recently, An and Lin [147] demonstrated that QAOA could
also solve a Quantum Linear System Problem (QLSP) nearly optimally, with
$O(\kappa\;\text{poly}(\log(\kappa/\epsilon)))$ runtime, where $\kappa$ is the
condition number and $\epsilon$ is the target accuracy. In contrast, the best
classical algorithm, the conjugate gradient method, has a time complexity
$O(N\sqrt{\kappa}\log(1/\epsilon))$, where $N=2^{n}$ is the size of the
system. QAOA thus has an exponential advantage concerning $N$ over the
classical algorithm. It also outperforms various quantum algorithms for this
problem, such as the HHL algorithm [148] and those based on Linear Combination
of Unitaries (LCU) [149] Quantum Signal Processing (QSP) [150].

####  3.3.2 Obstacles to quantum speedup

While the QAOA has demonstrated quantum speedup in specific problem domains
(see Section 3.3.1), it is crucial to recognize that there are still numerous
obstacles to overcome in achieving a quantum advantage in a more general
context. Challenges related to circuit depth, entanglement, optimization of
variational parameters, and noise pose significant hurdles.

For example, Guerreschi and Matsuura [151] attempted to assess the feasibility
of achieving a quantum speedup using QAOA in a more realistic setting that
accounts for decoherence and dissipation effects. They aimed to determine the
minimum number of qubits required for QAOA running on a quantum computer to
outperform state-of-the-art classical solvers on combinatorial problems. They
concluded that, in such a scenario, QAOA must run in a maximum of a minute to
compete with classical solvers on problems with less than 400 variables. It
would only be possible to achieve a quantum speedup for a specific
combinatorial problem once several hundreds of qubits are available. They