# Augmenting QAOA Ansatz with Multiparameter Problem-Independent Layer

Michelle Chalupnik1,2, Hans Melo2, Yuri Alexeev3, and Alexey Galda2 Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS>1Department of Physics,
Harvard University, Cambridge, MA 02138, USA  2Menten AI, Inc., San Francisco,
CA 94111, USA  3Computational Science Division, Argonne National Laboratory,
Lemont, IL 60439, USA

###### Abstract

The quantum approximate optimization algorithm (QAOA) promises to solve
classically intractable computational problems in the area of combinatorial
optimization. A growing amount of evidence suggests that the originally
proposed form of the QAOA ansatz is not optimal, however. To address this
problem, we propose an alternative ansatz, which we call QAOA+, that augments
the traditional $p=1$ QAOA ansatz with an additional multiparameter problem-
independent layer. The QAOA+ ansatz allows obtaining higher approximation
ratios than $p=1$ QAOA while keeping the circuit depth below that of $p=2$
QAOA, as benchmarked on the MaxCut problem for random regular graphs. We
additionally show that the proposed QAOA+ ansatz, while using a larger number
of trainable classical parameters than with the standard QAOA, in most cases
outperforms alternative multiangle QAOA ansätze.

##  I Introduction

As the noisy intermediate-scale quantum (NISQ) computing era matures, more and
more powerful quantum computers become available, making steady progress
toward surpassing the computational capabilities of classical computers in
solving some important real-world problems. In the field of biochemistry
alone, quantum annealers have been used to solve the protein-folding problem
[1, 2], and gate-based quantum computers have been used to calculate the
ground state energies of molecules [3, 4, 5, 6, 7]. Despite the ongoing
advancements in quantum hardware, however, quantum circuits that can be
executed reasonably well by modern quantum computers are still severely
limited in the maximum number of qubits, qubit connectivity, and maximum
circuit depth, because of the compounded noise, reducing algorithmic
performance well below the best-case theoretical predictions [8, 9, 10, 11].

Hybrid quantum-classical algorithms attack problems through a combination of
quantum and classical computational resources and are leading candidates for
achieving quantum advantage in near-term devices [12]. Hybrid quantum-
classical algorithms range from quantum machine learning techniques [13] to
parameterized quantum circuits, which are quantum circuits with gate
parameters that are obtained by using iterative classical optimization
routines. Parameterized quantum circuits include quantum variational
eigensolvers [14, 15], quantum autoencoders [16], and the quantum approximate
optimization algorithm (QAOA) [17].

QAOA in particular has drawn interest for its potential to show quantum
advantage in NISQ devices as well as its numerous practical applications. QAOA
solves the combinatorial optimization problem of finding the bitstring
corresponding to the lowest energy eigenstate of a Hamiltonian [17].
Performance of QAOA has been improved by exploiting symmetries of graph
structures [18, 19, 20, 21], by introducing classical neural networks or other
classical methods to assist in parameter optimization [22, 23], by modifying
the circuit ansatz [24, 25, 26], and by increasing circuit parameterization,
at the expense of increased classical optimization [27]. Although increasing
the number of independent parameters in QAOA circuits can improve performance
in some instances, as the number of parameters increases, nonconvex
optimization landscapes can hamper parameter optimization [28, 29, 30, 31,
32].

In this work we introduce the technique of augmenting the standard QAOA ansatz
for the MaxCut problem with a problem-independent layer to improve the
performance of $p=1$ QAOA while keeping the circuit depth below that of $p=2$
QAOA. The added layer consists of a sequence of two-qubit gates entangling all
qubits with the minimum possible number of operations, followed by the second
mixing layer of one-qubit gates. We test the performance of our ansatz, which
we call QAOA+, on the MaxCut problem for random regular graphs with up 14
nodes, and we show that it yields approximation ratio improvements at the
expense of increasing the number of classical optimization parameters. We also
compare QAOA+ with another QAOA variant, multiangle QAOA (ma-QAOA) [27] and
show that for a low number of independent parameters QAOA+ in general results
in higher approximation ratios than does ma-QAOA on the MaxCut problem for
random regular graphs with up to 14 nodes.

##  II Background

In this section we introduce the notation used in this work and briefly review
the relevant prior results and approaches for solving the MaxCut problem using
QAOA.

###  II-A QAOA

QAOA is a variational algorithm inspired by the adiabatic evolution principle.
In its original formulation [33] it can be seen as a Trotterized version of
quantum annealing evolution with a finite number of steps, $p$. QAOA can be
used to solve a broad class of general unconstrained combinatorial problems,
seeking the solution represented as a bitstring that maximizes the cost
function. This is achieved by preparing a parameter-dependent $n$-qubit
quantum state using a sequence of alternating operators:

$\ket{\vec{\beta},\vec{\gamma}}:=U_{B}(\beta_{p})U_{C}(\gamma_{p})\ldots
U_{B}(\beta_{1})U_{C}(\gamma_{1})\ket{s},$ (1)

where $U_{C}(\gamma)=e^{-i\gamma C}$ is the phase operator, $C$ is the problem
Hamiltonian, $U_{B}(\beta)=e^{-i\beta B}$ is the mixing operator,
$B=\sum_{j}X_{j}$, and $\ket{s}=\ket{+}^{\otimes n}$ is the initial uniform
superposition product state, the exited state of $B$ with maximum energy. The
evolution is followed by the measurement in the computational basis, with
measurement outcome probabilities following the Born rule:

$\mathsf{Pr}(x)=|\braket{x}{\vec{\beta},\vec{\gamma}}|^{2},\quad
x\in\\{0,1\\}^{n}.$ (2)

The classical parameters $\vec{\beta},\vec{\gamma}$ are updated in the outer
loop to maximize the expected objective value of the quantum evolution
measurement outcomes:

$\langle
C\rangle:=\bra{\vec{\beta},\vec{\gamma}}C\ket{\vec{\beta},\vec{\gamma}}=\sum_{x\in\\{0,1\\}^{n}}\mathsf{Pr}(x)f(x).$
(3)

The performance of QAOA relies on the choice of these parameters. The problem
of identifying optimal QAOA parameters has generated a large amount of
theoretical [34, 35, 36, 37] and computational [38, 39, 40, 41, 42, 43, 44]
work, including such methods as reinforcement learning [45, 46] and reusing
preoptimized QAOA parameters from related problem instances [47, 48, 49, 50])
to significantly reduce the computational cost of parameter optimization.

###  II-B MaxCut

MaxCut is an archetypal NP-complete combinatorial problem. Consider an
undirected graph $G$ with a set of vertices $V$ and a set of edges $E$. The
objective of MaxCut is to find an assignment of vertices into two disjoint
subsets such that the number of edges spanning both subsets is maximized. The
goal of MaxCut is to maximize the following objective function:

$C_{\text{MaxCut}}=\frac{1}{2}\sum_{(j,k)\in
E}(\textsc{i}-\textsc{z}_{j}\textsc{z}_{k}).$ (4)

The performance of QAOA is evaluated with a metric called the approximation
ratio (AR). This is defined as the expectation value of the cost Hamiltonian
divided by the maximum Hamiltonian energy.

$\displaystyle AR=\langle C\rangle/C_{\text{max}}$

Gradient-based approaches are often used for QAOA parameter optimization.
Unfortunately, the linearly growing number of optimization parameters with the
number of QAOA layers, together with the phenomenon of exponentially vanishing
gradients, called Barren plateaus [51, 29, 52, 53, 54], makes this
optimization task, in general, an NP-hard nonconvex optimization problem in
itself. Increasing the number of QAOA layers also leads to quantum circuits
that significantly exceed the capabilities of NISQ hardware, because of
limited coherence times and relatively large two-qubit error rates. At the
same time, shallow QAOA circuits do not have the capacity to achieve high
approximation ratios. It is therefore important to adapt the QAOA approach for
the most efficient use on modern quantum processors

###  II-C Alternative QAOA ansätze

The originally proposed form of the QAOA ansatz [17] has not been proven to be
optimal for any particular class of optimization problems. In fact, a growing
amount of research suggests that alternative QAOA ansätze [55, 27] outperform
the standard QAOA approach, either by requiring shallower quantum circuits to
match the performance of standard QAOA or by offering better results for the
same circuit depth, or both. In the former case, these improvements can be
achieved by developing a tailored problem- and hardware-specific ansatz, as in
the case of ADAPT-QAOA [55]. This approach uses a gradient-based criterion to
build a custom QAOA mixer layer from a predefined operator pool,
systematically growing the ansatz one layer at a time. This was shown to
improve MaxCut approximation ratios for circuit depths $p>4$, while also
resulting in a lower number of variational parameters and a lower CNOT gate
count.

Another alternative QAOA ansatz, multiangle QAOA [27] (ma-QAOA), produces
improvements in the approximation ratio for the MaxCut problem at the expense
of increasing the number of variational parameters without altering the shape
of the standard QAOA ansatz. This, however, significantly increases the
computational cost of the classical optimization process. Multiangle QAOA
independently parameterizes each gate in both the phase separation and mixing
layers of the standard QAOA circuit. It has the benefit of requiring lower
circuit depths to produce approximation ratios similar to or higher than those
achieved with a standard QAOA ansatz. As a result, ma-QAOA offers higher
performance than standard QAOA achieves on modern quantum hardware, where
increasing circuit depth beyond a certain point leads to a sharp drop in
algorithm performance due to decoherence.

##  III QAOA+

We present an alternative QAOA ansatz, called QAOA+, that consists of the
standard $p=1$ QAOA layer followed by an additional problem-independent
circuit ansatz (see Fig. 1). The appended layer has the form of the standard
QAOA layer for MaxCut on a $n$-node line graph; in other words, the phase
separation layer sequentially connects all qubits from the first to the last.
This problem-independent layer uses a minimum possible number $n-1$ of two-
qubit gates connecting all qubits. Additionally, similarly to ma-QAOA, we
allow all variational parameters in the appended layer to be independent. Note
that the number of classical parameters in the QAOA+ ansatz is almost always
smaller than in ma-QAOA for the same graph.

| n = 8 | n = 10 | n = 12 | n=14
---|---|---|---|---
| 3-reg | 4-reg | 5-reg | 3-reg | 4-reg | 5-reg | 3-reg | 4-reg | 5-reg | 3-reg | 4-reg | 5-reg
QAOA (p=1) | 0.783 | 0.785 | 0.796 | 0.793 | 0.803 | 0.807 | 0.768 | 0.816 | 0.814 | 0.782 | 0.812 | 0.798
QAOA+ (p=1) | 0.838 | 0.867 | 0.866 | 0.833 | 0.844 | 0.844 | 0.800 | 0.847 | 0.848 | 0.815 | 0.843 | 0.827
QAOA (p=2) | 0.870 | 0.884 | 0.864 | 0.868 | 0.874 | 0.873 | 0.840 | 0.884 | 0.882 | 0.856 | 0.883 | 0.862
Table I:  Approximation ratios for all 3-, 4-, and 5-regular graphs for $n=8$,
$n=10$, $n=12$, and $n=14$ nodes, for $p=1$ QAOA, QAOA+, and $p=2$ QAOA.

For dense graphs, in which the number of edges approaches quadratic scaling
with the number of nodes, the additional circuit depth associated with the
appended linear ansatz layer of QAOA+ is significantly smaller than that of
one additional QAOA layer of $p=2$ QAOA. As a result, QAOA+ offers a favorable
compromise between improving the MaxCut approximation ratio, as we show below,
and increasing the total circuit depth. This remains true for sparse graphs,
although with a lesser effect. Only for MaxCut on linear graphs, when the
shape of the standard QAOA ansatz matches that of the additional layer in
QAOA+, does the circuit depth advantage of QAOA+ over QAOA disappear. Instead,
for linear graphs, the QAOA+ ansatz has the same shape as the standard $p=2$
QAOA, minus the number of variational parameters.

Figure 1: Circuit layout for QAOA+ consisting of a standard $p=1$ QAOA layer,
followed by an additional problem-independent layer consisting of of $ZZ$
gates, and an additional mixer layer with $X$ gates. All single- and two-qubit
gates in the additional layers are independently parameterized.

Table I compares the mean approximation ratios for MaxCut on non-isomorphic
3-, 4-, and 5-regular 8-, 10-, 12-, and 14-node graphs for $p=1$ QAOA, QAOA+,
and $p=2$ QAOA. The results were averaged over 10 non-isomorphic random graphs
of each type, whenever available. We used the Broyden–Fletcher–Goldfarb–Shanno
(BFGS) algorithm [56] to optimize the QAOA parameters, selecting the best
solution from 10 optimization runs with random initial parameters for each
graph. QAOA energy expectation values were calculated by using the tensor-
network quantum simulator QTensor [38, 57, 58]. The approximation values for
the standard $p=1$ and $p=2$ QAOA were obtained from the QAOAKit database
[59]. Across all considered graph types, the QAOA+ ansatz yields approximation
ratio values between those of $p=1$ and $p=2$ QAOA, while also using an
intermediate number of two-qubit gates; see Fig. 2 for a more detailed
comparison of the number of optimized parameters, two-qubit gates, and
approximation ratios for 8-node graphs. Since two-qubit gates are the primary
source of errors in quantum circuits, the QAOA+ ansatz has the potential of
producing better results than the standard $p=2$ QAOA produces when executed
on NISQ devices because of the smaller number of two-qubit gates.

Figure 2: Number of parameters, number of two-qubit gates, and averaged
approximation ratio for all 3-reg, 4-reg, or 5-reg 8-qubit graphs, plotted for
four different QAOA variants: QAOA ($p=1$), QAOA+ $(p=1)$, multiangle QAOA
($p=1$), and QAOA ($p=2$).

The introduced QAOA+ ansatz not only provides a good compromise between the
$p=1$ and $p=2$ QAOA in terms of the MaxCut solution quality and the
associated QAOA circuit depth, it also offers additional flexibility in the
complexity of classical optimization of the QAOA parameters. The additional
layer of gates in QAOA+ can be designed to have anywhere between 2 and $2n+1$
parameters (2 in the standard $p=1$ QAOA, $n-1$ in the problem-independent
layer of two-qubit gates, and $n$ in the additional mixer layer), where $n$ is
the number of qubits. However, the standard QAOA ansatz can also be modified
to have more than 2 parameters per single QAOA layer [27]. In that work the
authors introduced the ma-QAOA ansatz that allows all parameters in the
standard QAOA layer to be different. Because the original ma-QAOA ansatz has
no fewer than $2n-1$ parameters, however, in order to compare the performance
of QAOA+ with ma-QAOA, we have modified both ansätze to have an adjustable
number of parameters, ranging from 4 to $2n+1$ for QAOA+ and from 2 to the
maximum problem-dependent number of parameters in ma-QAOA. Moreover, because
the number of parameters can be unevenly distributed between the two-qubit and
mixer layers, for both QAOA+ and ma-QAOA we have averaged the approximation
ratios over QAOA instances with all possible distributions of the optimization
parameters between. For each instance, we have optimized all five possible
non-isomorphic 8-node 3-regular graphs using the BFGS algorithm with 10
restarts. The results are shown in Fig. 3.

Figure 3: Comparison of approximation ratios for ma-QAOA, standard QAOA ($p=1$
and $p=2$), and QAOA+ for all 8-qubit 3-reg graphs. For ma-QAOA and QAOA+, the
number of independent parameters are varied to compare algorithm performance
at equal parameter number.

The number of independent optimization parameters determines the complexity of
classical optimization of QAOA. We have observed that QAOA+ always gives
higher approximation ratios than ma-QAOA does at equal parameter numbers,
despite the fact that with the full 20 parameters ma-QAOA outperforms the
maximally parameterized 17-parameter QAOA+. The gap in performance between
QAOA+ and ma-QAOA increases as the number of optimization parameters is
reduced. In fact, the 4-parameter QAOA+ performs better on average than
14-parameter ma-QAOA does, while still doing worse than $p=2$ QAOA with a
larger circuit depth; see Fig. 3.

We have not observed any significant difference in performance between ma-QAOA
ansätze with the same number of parameters but distributed differently between
the cost and mixing layers; see Fig. 4. While the figure does not make clear
whether the QAOA+ ansatz favors circuit parameterizations with any particular
distribution of the number of parameters between the auxiliary two-qubit layer
and the second mixing layer, one can clearly see that QAOA+ yields higher
approximation ratios than ma-QAOA+ does for all possible combinations of
parameters.

Figure 4: Average approximation ratio for all non-isomorphic 8-node 3-regular
graphs, using ma-QAOA with varied number of parameters. The total number of
independent circuit parameters equals $n_{\gamma}$ \+ $n_{\beta}$. Figure 5:
Average approximation ratio for all non-isomorphic 8-node 3-regular graphs,
using QAOA+ with varied number of parameters. Here, $\beta$ and $\gamma$ refer
to the number of optimized parameters in the ansatz layer. The total number of
independent circuit parameters equals $n_{\gamma}$ \+ $n_{\beta}$.

While Fig. 2 presents a compelling case that QAOA+ with 4 optimization
parameters, which we will call QAOA+(4) for brevity, gives higher
approximation ratios than does ma-QAOA with significantly more parameters,
these results are limited to the MaxCut problem on 3-regular 8-node graphs. To
establish this fact for larger MaxCut instances, we calculated the
approximation ratio for the QAOA+(4) ansatz for all types of 8- and 10-node
random regular graphs, averaged over 10 graphs of each type and using the BFGS
optimization with 10 restarts. We then perform the same averaging procedure
for the ma-QAOA ansatz on the same graphs with an increasing number of
optimization parameters from 2 until the approximation ratio of QAOA+(4) is
exceeded, recording that minimum number of parameters in ma-QAOA necessary to
outperform QAOA+(4). The results are shown in Fig. 6. Unlike in Fig. 3, only
one parameter distribution between the cost and mixing layers in the ma-QAOA
ansatz is considered: for every even number of parameters, they are split
equally between the two layers, while for an odd total number of parameters
the cost layer had one more parameter. The thresholds after which ma-QAOA
yields higher approximation ratios are averaged over up to 10 random regular
graphs of each type. At parameter numbers below this threshold, QAOA+(4)
outperforms ma-QAOA, while above the threshold, ma-QAOA starts to produce
higher approximation ratios, at the expense of a significantly large-
dimensional search space of QAOA parameters. As the size of regular graphs is
increased from 8 to 10 nodes, the threshold values rise, indicating that the
performance of our QAOA+ ansatz scales favorably with problem size, compared
with ma-QAOA.

Figure 6: Minimum number of parameters required for ma-QAOA to match the
performance of QAOA+(4) for $d$-regular 8-node and 10-node graphs.

##  IV Discussion

Increasing the circuit depth by increasing the number of QAOA layers is
necessary in order to improve the approximation ratio achievable with the
standard QAOA approach. When executing on NISQ hardware, however, the
increased circuit depth comes with a severe penalty of decreasing performance
due to decoherence. Alternative QAOA ansätze aim to modify the QAOA approach
to increase MaxCut approximation ratios at reduced costs in terms of circuit
depth. In this work we have introduced the QAOA+ as an alternative ansatz that
improves approximation ratios compared with the standard $p=1$ QAOA by adding
an auxiliary layer of gates that is smaller than a full additional QAOA layer.
We have shown that QAOA+ provides a viable alternative for an intermediate
ansatz with approximation ratios and circuit depth between those of $p=1$ and
$p=2$ QAOA.

Because the introduced QAOA+ ansatz allows for a large number of classical
optimization parameters, as a baseline we compared QAOA+ with ma-QAOA, another
alternative QAOA ansatz with low circuit depth and high number of parameters.
While ma-QAOA generally yields higher approximation ratios than does QAOA+
when all optimization parameters are utilized, we have demonstrated that when
the number of parameters in QAOA+ and ma-QAOA is the same, QAOA+ significantly
outperforms ma-QAOA, with the performance gap growing with the problem size.
In particular, we considered QAOA+ with 4 parameters and demonstrated that ma-
QAOA requires significantly more optimization parameters to match the
performance of QAOA+, which comes at large classical computation overhead.
Therefore, in general, QAOA+ requires fewer parameters than does ma-QAOA for
the same level of performance, while having a larger circuit depth. When
minimizing the objective function for many parameters is difficult, QAOA+ will
be a valuable option. The reduction in circuit depth from using QAOA+ compared
with the standard $p=2$ QAOA is particularly noticeable for MaxCut instances
on dense graphs.

This work does not present an exhaustive study on all possible alternative
QAOA ansätze. We have considered only a single shape of the additional
problem-independent layer of two-qubits gates, defined by the minimum possible
number of gates that entangle all qubits. Other shapes of the QAOA+ ansatz
will be considered elsewhere, including more hardware-efficient ansätze that
respect the possible connectivity constraints of quantum processors. One can
also consider such modification as creating a hybrid ma-QAOA/QAOA+ ansatz
consisting of both the multiparameter ma-QAOA and the additional
multiparameter problem-independent QAOA+ ansatz layers, in order to shift the
improvements in the MaxCut approximation ratio even more toward the classical
computation instead of increasing the QAOA circuit depth. The study of the
necessary computational resources required for optimization of the increased
number of optimization parameters in the proposed QAOA+ ansatz, as well as the
associated challenged of Barren plateaus, was also beyond the scope of this
work. Performance comparisons presented here were done under the assumption of
equal computational limitation on optimization across all optimization
instances regardless of the number of parameters. Additionally, we considered
only the $p=1$ case, and performance can be analyzed at larger circuit depths.
Moreover, because this work was motivated by potential performance
improvements during execution on NISQ hardware, noisy simulations and
comparisons on modern quantum processors will need to be performed to validate
the proposed approach.

When high-fidelity quantum computing hardware capable of executing large-scale
QAOA instances with $p\gg 1$ becomes available, the true value of alternative
QAOA ansätze will be revealed. The optimal balance between the computational
complexity of parameter optimization and the acceptable depth of quantum
circuits will be determined through extensive experimentation. Until then, it
is crucial to continue improving the capacity of the QAOA approach to solve
NP-hard combinatorial optimization problems by developing novel ansätze. We
are hopeful that the approach introduced in our paper will help advance the
standard QAOA of today toward the next-generation QAOA of tomorrow capable of
unlocking practical quantum advantage.

## Acknowledgments

We thank Gavin Crooks, Vikram Mulligan, and Ian MacCormack for helpful
discussions and feedback on the manuscript. M.C. was supported by funding
provided during an internship at Menten AI and partially supported by the
Department of Defense (DoD) through the National Defense Science and
Engineering Graduate (NDSEG) Fellowship Program, and acknowledges support from
her PhD advisor Marko Lončar. This material is partially based upon work
supported by the Defense Advanced Research Projects Agency (DARPA) under
Contract No. HR001120C0068. Y.A.’s work at Argonne National Laboratory was
supported by the U.S. Department of Energy, Office of Science, under contract
DE-AC02-06CH11357.

## References

  * [1] M. W. Johnson _et al._ , “Quantum annealing with manufactured spins,” _Nature_ , vol. 473, p. 194, 2011.
  * [2] V. K. Mulligan _et al._ , “Designing peptides on a quantum computer,” _https://doi.org/10.1101/752485_ , 2020.
  * [3] B. Lanyon _et al._ , “Towards quantum chemistry on a quantum computer,” _Nature Chemistry_ , vol. 2, p. 106, 2010.
  * [4] A. Peruzzo _et al._ , “A variational eigenvalue solver on a photonic quantum processor,” _Nature Communications_ , vol. 5, 2014.
  * [5] P. O’Malley _et al._ , “Scalable quantum simulation of molecular energies,” _Phys. Rev. X_ , vol. 6, p. 031007, 2016.
  * [6] A. Kandala _et al._ , “Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets,” _Nature_ , vol. 549, p. 242, 2017\.
  * [7] J. Arguello-Luengo, A. Gonzalez-Tudela, T. Shi, P. Zoller, and J. Cirac, “Analogue quantum chemistry simulation,” _Nature_ , vol. 574, p. 215, 2019\.
  * [8] J. Preskill, “Quantum computing in the NISQ era and beyond,” _Quantum_ , vol. 2, p. 79, 2018.
  * [9] J. Sun, X. Yuan, T. Tsunoda, V. Vedral, S. C. Benjamin, and S. Endo, “Mitigating realistic noise in practical noisy intermediate-scale quantum devices,” _Physical Review Applied_ , vol. 15, p. 034026, 2021.
  * [10] R. Herrman, J. Ostrowski, T. S. Humble, and G. Siopsis, “Lower bounds on circuit depth of the quantum approximate optimization algorithm,” _Quantum Inf. Process._ , vol. 20, p. 59, 2021.
  * [11] Y. Alexeev _et al._ , “Quantum computer systems for scientific discovery,” _PRX Quantum_ , vol. 2, no. 1, p. 017001, 2021.
  * [12] S. Sim, P. D. Johnson, and A. Aspuru-Guzik, “Expressibility and entangling capability of parameterized quantum circuits for hybrid quantum-classical algorithms,” _Adv. Quantum Technol._ , vol. 2, p. 1900070, 2019.
  * [13] J. Biamonte, P. Wittek, N. Pancotti, P. Rebentrost, N. Wiebe, and S. Lloyd, “Quantum machine learning,” _Nature_ , vol. 549, p. 195, 2017.
  * [14] J. R. McClean, J. Romero, R. Babbush, and A. Aspuru-Guzik, “The theory of variational hybrid quantum-classical algorithms,” _New Journal of Physics_ , vol. 18, p. 023023, 2016.
  * [15] N. Moll _et al._ , “Quantum optimization using variational algorithms on near-term quantum devices,” _Quantum Sci. Technol._ , vol. 3, p. 030503, 2018\.
  * [16] J. Romero, J. Olson, and A. Aspuru-Guzik, “Quantum autoencoders for efficient compression of quantum data,” _Quantum Science and Technology_ , vol. 2, p. 045001, 2017.
  * [17] E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” _arXiv:1411.4028_ , 2014.
  * [18] D. S. Franca and R. Garcia-Patron, “Limitations of optimization algorithms on noisy quantum devices,” _arXiv:2009.05532_ , 2020.
  * [19] R. Shaydulin and A. Galda, “Error mitigation for deep quantum optimization circuits by leveraging problem symmetries,” in _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2021, pp. 291–300.
  * [20] R. Herrman, L. Treert, J. Ostrowski, P. C. Lotshaw, T. S. Humble, and G. Siopsis, “Impact of graph structures for QAOA on MaxCut,” _arXiv:2102.05997_ , 2021.
  * [21] Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, “Quantum approximate optimization algorithm for MaxCut: A fermionic view,” _Phys. Rev. A_ , vol. 97, p. 022304, 2018.
  * [22] G. Verdon _et al._ , “Learning to learn with quantum neural networks via classical neural networks,” _arXiv:1907.05415_ , 2019.
  * [23] Y. Dong, X. Meng, L. Lin, R. Kosut, and K. B. Whaley, “Robust control optimization for quantum approximate optimization algorithms,” _IFACPapersOnLine_ , vol. 53, p. 242, 2020.
  * [24] D. Egger, J. Marecek, and S. Woerner, “Warm-starting quantum optimization,” _Quantum_ , vol. 5, p. 479, 2021.
  * [25] L. Zhu _et al._ , “Improving the performance of quantum approximate optimization algorithm through an adaptive, problem-tailored ansatz,” _Bulletin of the American Physical Society_ , 2021.
  * [26] X. Liu, A. Angone, R. Shaydulin, I. Safro, Y. Alexeev, and L. Cincio, “Layer VQE: A variational approach for combinatorial optimization on noisy quantum computers,” _IEEE Transactions on Quantum Engineering_ , vol. 3, pp. 1–20, 2022.
  * [27] R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, “Multi-angle quantum approximate optimization algorithm,” _arXiv:2109.11455v1_ , 2021.
  * [28] R. Wiersema, C. Zhou, Y. de Sereville, J. F. Carrasquilla, Y. B. Kim, and H. Yuen, “Exploring entanglement and optimization within the Hamiltonian variational ansatz,” _PRX Quantum_ , vol. 1, p. 020319, 2020.
  * [29] S. Wang _et al._ , “Noise-induced barren plateaus in variational quantum algorithms,” _arXiv:2007.14384_ , 2020.
  * [30] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” _Nature communications_ , vol. 9, p. 1, 2018.
  * [31] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, “Cost function dependent barren plateaus in shallow parameterized quantum circuits,” _Nature Communications_ , vol. 12, p. 1, 2021.
  * [32] R. Shaydulin and Y. Alexeev, “Evaluating quantum approximate optimization algorithm: A case study,” in _2019 tenth international green and sustainable computing conference (IGSC)_. IEEE, 2019, pp. 1–6.
  * [33] E. Farhi, D. Gamarnik, and S. Gutmann, “The quantum approximate optimization algorithm needs to see the whole graph: A typical case,” _arXiv:2004:09002_ , 2020.
  * [34] J. Wurtz and P. J. Love, “Counterdiabaticity and the quantum approximate optimization algorithm,” _Quantum_ , vol. 6, p. 635, 2022.
  * [35] S. Boulebnane and A. Montanaro, “Predicting parameters for the quantum approximate optimization algorithm for MAX-CUT from the infinite-size limit,” _arXiv preprint arXiv:2110.10685_ , 2021.
  * [36] E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, “The quantum approximate optimization algorithm and the Sherrington–Kirkpatrick model at infinite size,” _arXiv preprint arXiv:1910.08187_ , 2019.
  * [37] J. Wurtz and P. Love, “MaxCut quantum approximate optimization algorithm performance guarantees for $p>1$,” _Physical Review A_ , vol. 103, no. 4, p. 042612, 2021.
  * [38] D. Lykov, R. Schutski, A. Galda, V. Vinokur, and Y. Alexeev, “Tensor network quantum simulator with step-dependent parallelization,” _arXiv preprint arXiv:2012.02430_ , 2020.
  * [39] M. Medvidović and G. Carleo, “Classical variational simulation of the quantum approximate optimization algorithm,” _npj Quantum Information_ , vol. 7, no. 1, pp. 1–7, 2021.
  * [40] R. Shaydulin, S. Hadfield, T. Hogg, and I. Safro, “Classical symmetries and the quantum approximate optimization algorithm,” _Quantum Information Processing_ , vol. 20, no. 11, pp. 1–28, 2021.
  * [41] L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, “Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near-term devices,” _Physical Review X_ , vol. 10, no. 2, p. 021067, 2020.
  * [42] G. E. Crooks, “Performance of the quantum approximate optimization algorithm on the maximum cut problem,” _arXiv preprint arXiv:1811.08419_ , 2018.
  * [43] R. Shaydulin, I. Safro, and J. Larson, “Multistart methods for quantum approximate optimization,” in _2019 IEEE high performance extreme computing conference (HPEC)_. IEEE, 2019, pp. 1–8.
  * [44] R. Shaydulin and S. M. Wild, “Exploiting symmetry reduces the cost of training QAOA,” _IEEE Transactions on Quantum Engineering_ , vol. 2, pp. 1–9, 2021\.
  * [45] M. M. Wauters, E. Panizon, G. B. Mbeng, and G. E. Santoro, “Reinforcement-learning-assisted quantum optimization,” _Physical Review Research_ , vol. 2, p. 033446, 2020.
  * [46] Y. Alexeev, S. Khairy, R. Shaydulin, L. Cincio, and P. Balaprakash, “Reinforcement learning for finding QAOA parameters,” _Bulletin of the American Physical Society_ , vol. 65, 2020.
  * [47] P. C. Lotshaw, T. S. Humble, R. Herrman, J. Ostrowski, and G. Siopsis, “Empirical performance bounds for quantum approximate optimization,” _Quantum Information Processing_ , vol. 20, no. 12, pp. 1–32, 2021.
  * [48] A. Galda, X. Liu, D. Lykov, Y. Alexeev, and I. Safro, “Transferability of optimal QAOA parameters between random graphs,” in _2021 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2021, pp. 171–180.
  * [49] J. Wurtz and D. Lykov, “The fixed angle conjecture for QAOA on regular MaxCut graphs,” _arXiv preprint arXiv:2107.00677_ , 2021.
  * [50] F. G. Brandao, M. Broughton, E. Farhi, S. Gutmann, and H. Neven, “For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances,” _arXiv preprint arXiv:1812.04170_ , 2018.
  * [51] A. Uvarov and J. Biamonte, “On barren plateaus and cost function locality in variational quantum algorithms,” _arXiv:2011.10530_ , 2020.
  * [52] E. Grant, L. Wossnig, M. Ostaszewski, and M. Benedetti, “An initialization strategy for addressing barren plateaus in parametrized quantum circuits,” _Quantum_ , vol. 3, 2019.
  * [53] J. R. McClean, S. Boixo, V. N. Smelyanskiy, R. Babbush, and H. Neven, “Barren plateaus in quantum neural network training landscapes,” _Nature Communications_ , vol. 9, no. 1, pp. 1–6, 2018.
  * [54] M. Cerezo, A. Sone, T. Volkoff, L. Cincio, and P. J. Coles, “Cost function dependent barren plateaus in shallow parametrized quantum circuits,” _Nature Communications_ , vol. 12, no. 1, pp. 1–12, 2021.
  * [55] L. Zhu _et al._ , “An adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer,” _arXiv preprint arXiv:2005.10258_ , 2020.
  * [56] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, _Numerical Recipes in Fortran 90_. Cambridge University Press, 1996, vol. 2.
  * [57] D. Lykov _et al._ , “Performance evaluation and acceleration of the qtensor quantum circuit simulator on gpus,” in _2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS)_. IEEE, 2021, pp. 27–34.
  * [58] D. Lykov and Y. Alexeev, “Importance of diagonal gates in tensor network simulations,” in _2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI)_. IEEE, 2021, pp. 447–452.
  * [59] R. Shaydulin, K. Marwaha, J. Wurtz, and P. C. Lotshaw, “QAOAKit: A Toolkit for Reproducible Study, Application, and Verification of the QAOA,” in _2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS)_. IEEE, 2021, pp. 64–71.

The submitted manuscript has been created by UChicago Argonne, LLC, Operator
of Argonne National Laboratory (“Argonne”). Argonne, a U.S. Department of
Energy Office of Science laboratory, is operated under Contract No. DE-
AC02-06CH11357. The U.S. Government retains for itself, and others acting on
its behalf, a paid-up nonexclusive, irrevocable worldwide license in said
article to reproduce, prepare derivative works, distribute copies to the
public, and perform publicly and display publicly, by or on behalf of the
Government. The Department of Energy will provide public access to these
results of federally sponsored research in accordance with the DOE Public
Access Plan http://energy.gov/downloads/doe-public-access-plan.