* [134] W. Yang, S. Li, W. Ouyang, H. Li, X. Wang, Learning feature pyramids for human pose estimation, in: proceedings of the IEEE international conference on computer vision, 2017, pp. 1281–1290.
  * [135] H. Zhang, C. Wu, Z. Zhang, Y. Zhu, Z. Zhang, H. Lin, Y. Sun, T. He, J. Muller, R. Manmatha, M. Li, A. Smola, Resnest: Split-attention networks, arXiv preprint arXiv:2004.08955 (2020).
  * [136] H. Zhang, H. Chang, B. Ma, N. Wang, X. Chen, Dynamic R-CNN: Towards high quality object detection via dynamic training, arXiv preprint arXiv:2004.06002 (2020).
  * [137] K. Chen, J. Wang, J. Pang, Y. Cao, Y. Xiong, X. Li, S. Sun, W. Feng, Z. Liu, J. Xu, et al., Mmdetection: Open mmlab detection toolbox and benchmark, arXiv preprint arXiv:1906.07155 (2019).
  * [138] S. Wu, J. Yang, X. Wang, X. Li, Iou-balanced loss functions for single-stage object detection, arXiv preprint arXiv:1908.05641 (2019).


††thanks: corresponding author

# QAOA with random and subgraph driver Hamiltonians

Anthony Wilkie  Department of Industrial and Systems Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996  Igor Gaidai  Department of Industrial and Systems
Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996  James Ostrowski  Department of Industrial and Systems
Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996  Rebekah Herrman<EMAIL_ADDRESS>Department of
Industrial and Systems Engineering
University of Tennessee at Knoxville
Knoxville, TN 37996

###### Abstract

The quantum approximate optimization algorithm (QAOA) is a promising quantum
algorithm that can be used to approximately solve combinatorial optimization
problems. The usual QAOA ansatz consists of an alternating application of the
cost and mixer Hamiltonians. In this work, we study how using Hamiltonians
other than the usual cost Hamiltonian, dubbed custom driver Hamiltonians, can
affect the performance of QAOA. We derive an expected value formula for QAOA
with custom driver Hamiltonians at p = 1 and show numerically that some of
these custom drivers can achieve higher approximation ratio than the original
algorithm implementation. Out of all the graphs tested, 0.036% of the random
custom drivers, 75.9% of the subgraph custom drivers, 95.1% of the triangle-
removed custom drivers, and 93.9% of the maximal degree edge-removed custom
drivers have a higher approximation ratio than the original QAOA
implementation. This finding opens up the question of whether better driver
Hamiltonians can be designed to further improve the performance of QAOA.

##  I Introduction

The quantum approximate optimization algorithm (QAOA) is an algorithm
consisting of a parameterized quantum circuit that is well-suited to
approximate solutions to combinatorial optimization (CO) problems
Farhi2014FQAOA . The algorithm evolves a given input state under the
alternating action of cost and mixing Hamiltonians for variable amounts of
time that are selected to optimize the expectation of the cost Hamiltonian.
QAOA can be used to find an approximate solution to any CO problem that can be
formulated as an Ising problem Ozaeta_2022 , among which the most studied is
the MaxCut problem herrman2021impact ; farhi2020quantum ; FixedAngleWurtz ;
Guerreschi_2019 ; wang2018quantum . The goal of MaxCut is to partition the
vertices of a given graph $G=(V,E)$ into two sets to maximize the number of
edges between the sets.

QAOA can be implemented on noisy intermediate scale quantum (NISQ) devices for
some small-scale problems zhou2020quantum ; harrigan2021quantum ;
earnest2021pulse , but it is challenging to extend it to larger problems due
to the depth limitations of the current generation of NISQ devices. Several
variations of QAOA have been developed that attempt to reduce the required
hardware resources, such as multi-angle QAOA and XQAOA herrman2022multi ;
wurtz2021classically ; vijendran2023expressive ; shi2022multi , but hardware
implementation remains challenging. As a result, the performance of QAOA is
often studied through the classical simulations of the algorithm. In
particular, closed-form equations for the expected value of the MaxCut cost
Hamiltonian $C$ have been derived for the special case when only one layer of
QAOA is applied wang2018quantum ; herrman2022multi . Furthermore, more general
closed-form equations for all combinatorial optimization problems that have an
Ising formulation have also been derived by Ozaeta et. al Ozaeta_2022 . Closer
inspection of these equations reveals that the expectation value of the cost
Hamiltonian may be negatively affected by the presence of triangles in the
graph or may be impacted by the maximum degree of the graph. As such, removing
one of the terms that correspond to an edge in a triangle or an edge incident
to a maximal degree vertex of the graph might improve the performance of QAOA.
Furthermore, one can consider other modifications of the QAOA circuit,
detailed below, and their effect on the performance of QAOA. One such
modification is to use a subgraph of the original graph to generate the
circuit. Using subgraphs for QAOA has been explored in zhou2023qaoa ;
li2022large ; ponce2023graph  in order to solve large instances of the MaxCut
problem using fewer quantum resources. The main focus of this paper is to
investigate these possibilities.

The paper is structured as follows. First, we provide QAOA and MaxCut
background, discuss how circuit choice impacts the algorithm, and derive the
expected value formula for QAOA with circuit choices that do not necessarily
correspond to graph structure in Section II. Then, we calculate the expected
value of the cost Hamiltonian for the MaxCut problem using this formula for
all non-isomorphic eight-vertex graphs in Section III. Finally, we discuss
this work and future research directions in Section IV.

##  II Cost and driver Hamiltonians

The state vector prepared by the QAOA circuit can be written as

${\left|\vec{\gamma},\vec{\beta}\right\rangle}=U(B,\beta_{p})U(C,\gamma_{p})\cdots
U(B,\beta_{1})U(C,\gamma_{1}){\left|s\right\rangle}$

where $U(B,\beta)$ and $U(C,\gamma)$ are the unitary evolution operators under
the action of the corresponding Hamiltonians $B$ and $C$, and
${\left|s\right\rangle}$ is a maximum (or minimum) energy eigenstate of $B$.
The mixer Hamiltonian $B$ is usually defined as a sum of Pauli-X operators on
each qubit

$B=\sum X_{i},$

although other mixers have been considered wang2020x ; bartschi2020grover .
The driver Hamiltonian $C$ is usually taken to be equal to the cost
Hamiltonian $C^{\prime}$, i.e. the Hamiltonian whose expectation needs to be
minimized by QAOA

$\mathrm{min}{\left\langle\vec{\gamma},\vec{\beta}\right|}C^{\prime}{\left|\vec{\gamma},\vec{\beta}\right\rangle}.$

For the MaxCut problem, the cost Hamiltonian is defined as:

$C^{\prime}=\sum_{uv\in E}C^{\prime}_{uv}=\sum_{uv\in
E}\frac{1}{2}(\mathbb{I}-Z_{u}Z_{v})$ (1)

However, it is not clear if different choices of the driver Hamiltonian
($C\neq C^{\prime}$) can result in better performance.

Thus, in this work we compare the standard ($C=C^{\prime}$) formulation to a
“random driver” formulation, where we take $C=C_{\text{{rand}}}$, defined as

$C_{\text{rand}}=\sum_{ab}\frac{1}{2}\left(\mathbb{I}-Z_{a}Z_{b}\right),$

where each pair $(u,v)\in E$ from Eq. (1) is replaced by a random pair of
indices $(a,b)$, with $a\neq b$. Note that one can imagine a driver
Hamiltonian with $Z_{i}Z_{j}$ interactions as a graph with edges $Z_{i}Z_{j}$,
hence we may also talk about driver graphs occasionally throughout the text.

We also consider the case where some fraction of the terms in the cost
$C^{\prime}$ Hamiltonian are used to generate the driver Hamiltonian
$C_{\text{sub}}^{\alpha}$, where $\alpha$ represents the fraction of terms
selected from the original Hamiltonian $C^{\prime}$. If $G$ is quite dense and
$\alpha$ is small, the number of terms and, correspondingly, gates in the
circuit can be significantly reduced, therefore lowering the error in the
circuit.

Lastly, there is evidence that triangles in problem graphs affect the QAOA
MaxCut approximation ratio farhi2020quantum ; farhi2020quantumwhole ;
wurtz2021maxcut ; herrman2021impact . Thus, we consider a special case of the
driver Hamiltonian that corresponds to the original graph $G$ with a subset of
triangles removed. The resulting graph is then used to generate the driver
Hamiltonian.

###  II.1 Derivation of analytical MaxCut expected value with custom driver
Hamiltonians

Using the Pauli-solver algorithm detailed in hadfield2018quantum , the
expected value of $\langle C^{\prime}_{uv}\rangle$ from Eq. (1) after 1 layer
of QAOA with a random Hamiltonian is:

${\left\langle s\right|}e^{i\gamma C_{\text{rand}}}e^{i\beta
B}C_{uv}e^{-i\beta B}e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}=\frac{1}{2}-\frac{1}{2}{\left\langle
s\right|}e^{i\gamma C_{\text{rand}}}e^{i\beta B}Z_{u}Z_{v}e^{-i\beta
B}e^{-i\gamma C_{\text{rand}}}{\left|s\right\rangle}.$ (2)

Most terms of the mixer commute to leave

$e^{i\beta B}Z_{u}Z_{v}e^{-i\beta
B}=\cos^{2}(2\beta)Z_{u}Z_{v}+\sin(2\beta)\cos(2\beta)(Y_{u}Z_{v}+Z_{u}Y_{v})+\sin^{2}(2\beta)Y_{u}Y_{v}.$
(3)

The first term of this sum commutes with $e^{-i\gamma C_{\text{rand}}}$ and
does not contribute to the expected value of the sum, i.e.

${\left\langle s\right|}e^{i\gamma C_{\text{rand}}}Z_{u}Z_{v}e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}=0$

Let us look at the effect of conjugation on the second term of Eq. (3)

$\displaystyle{\left\langle s\right|}e^{i\gamma
C_{\text{rand}}}Y_{u}Z_{v}e^{-i\gamma C_{\text{rand}}}{\left|s\right\rangle}.$

$C_{\text{rand}}$ has terms of the form
$\frac{1}{2}\left(\mathbb{I}-Z_{a}Z_{b}\right)$, however all terms that do not
have the form $Z_{u}Z_{c}$ for some $c$ commute and cancel, so

$\displaystyle{\left\langle s\right|}e^{i\gamma
C_{\text{rand}}}Y_{u}Z_{v}e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}={\left\langle
s\right|}e^{-i\gamma\sum_{c}(Z_{u}Z_{c})}Y_{u}Z_{v}{\left|s\right\rangle}.$

If $Z_{u}Z_{v}$ is not a term of $C_{\text{rand}}$, then there is no
contribution to the expected value and

${\left\langle
s\right|}e^{-i\gamma\sum_{c}(Z_{u}Z_{c})}Y_{u}Z_{v}{\left|s\right\rangle}=0$

Otherwise,

$\displaystyle{\left\langle
s\right|}e^{-i\gamma\sum_{c}(Z_{u}Z_{c})}Y_{u}Z_{v}{\left|s\right\rangle}$
$\displaystyle={\left\langle s\right|}e^{-i\gamma
Z_{u}Z_{v}}e^{-i\gamma\sum_{c\neq
v}(Z_{u}Z_{c})}Y_{u}Z_{v}{\left|s\right\rangle}$ $\displaystyle={\left\langle
s\right|}(\cos(\gamma)\mathbb{I}-i\sin(\gamma)Z_{u}Z_{v})\prod_{i=1}^{d}(\cos(\gamma)\mathbb{I}-i\sin(\gamma)Z_{u}Z_{c_{i}})Y_{u}Z_{v}{\left|s\right\rangle}$

where $d$ is the number of terms of the form $Z_{u}Z_{c}$ in
$C_{\text{rand}}$, with $c\neq v$. The only term that contributes to the
expected value is
$-i\sin(\gamma)Z_{u}Z_{v}\cos^{d}(\gamma)Y_{u}Z_{v}=-\sin(\gamma)\cos^{d}(\gamma)X_{u}$,
which implies

${\left\langle s\right|}e^{i\gamma C_{\text{rand}}}Y_{u}Z_{v}e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}={\left\langle
s\right|}-\sin(\gamma)\cos^{d}(\gamma)X_{u}{\left|s\right\rangle}=-\sin(\gamma)\cos^{d}(\gamma).$

By symmetry, the third term of Eq. (3) is also 0 if $Z_{u}Z_{v}$ is not a term
of $C_{\text{rand}}$, otherwise:

${\left\langle s\right|}e^{i\gamma C_{\text{rand}}}Z_{u}Y_{v}e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}={\left\langle
s\right|}-\sin(\gamma)\cos^{e}(\gamma)X_{v}{\left|s\right\rangle}=-\sin(\gamma)\cos^{e}(\gamma).$

where $e$ is the number of terms of the form $Z_{h}Z_{v}$ in
$C_{\text{rand}}$, where $h\neq u$.

Hence, we have

${\left\langle s\right|}e^{i\gamma
C_{\text{rand}}}\left(Y_{u}Z_{v}+Z_{u}Y_{v}\right)e^{-i\gamma
C_{\text{rand}}}{\left|s\right\rangle}=-\chi_{uv}\sin(\gamma)(\cos^{d}(\gamma)+\cos^{e}(\gamma)),$

where $\chi_{uv}=1$ if $Z_{u}Z_{v}$ is a term in $C_{\text{rand}}$ and 0
otherwise.

Let us look at the effect of conjugation on the last term of Eq. (3)

$\displaystyle{\left\langle s\right|}e^{i\gamma
C_{\text{rand}}}Y_{u}Y_{v}e^{-i\gamma C_{\text{rand}}}{\left|s\right\rangle}$
$\displaystyle={\left\langle s\right|}e^{i\gamma\sum_{b\neq
v}Z_{u}Z_{b}}e^{i\gamma\sum_{a\neq
u}Z_{a}Z_{v}}Y_{u}Y_{v}{\left|s\right\rangle}$ $\displaystyle={\left\langle
s\right|}\prod_{i=1}^{d}(\cos(\gamma)\mathbb{I}-i\sin(\gamma)Z_{u}Z_{b_{i}})\prod_{j=1}^{e}(\cos(\gamma)\mathbb{I}-i\sin(\gamma)Z_{a_{j}}Z_{v})Y_{u}Y_{v}{\left|s\right\rangle}.$

By approaches similar to those in hadfield2018quantum , the expected value
contribution from this term is
$\frac{1}{2}\cos^{d+e-2f}(\gamma)(1-\cos^{f}(2\gamma))$, where $f$ is the
number of pairs of terms that satisfy the triangle condition for edge $(u,v)$.
We say two terms $Z_{u}Z_{w}$ and $Z_{w}Z_{v}$ for $w\neq u,v$ in the driver
Hamiltonian $C_{\text{rand}}$ satisfy the triangle condition if $(u,v)$ is an
edge in the graph of interest.

Combining the above terms yields

$\langle
C^{\prime}_{uv}\rangle=\frac{1}{2}+\frac{\chi_{uv}}{4}\sin(4\beta)\sin(\gamma)(\cos^{d}(\gamma)+\cos^{e}(\gamma))-\frac{1}{4}\sin^{2}(\beta)\cos^{d+e-2f}(\gamma)(1-\cos^{f}(2\gamma)).$
(4)

### Example: An eight-vertex graph where a subgraph driver Hamiltonian
achieves an approximation ratio of 1

Fig. 1 shows a graph $G$ where there exists a subgraph $G^{\prime}$ consisting
of only the dashed edges such that using the corresponding driver Hamiltonian
yields a higher approximation ratio compared to the usual QAOA driver
Hamiltonian. The approximation ratio for this graph using the original QAOA
driver is 0.934, as found with the code from maqaoarepo .

$v_{0}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$ Figure 1: An eight-
vertex graph where a subgraph driver Hamiltonian achieves an approximation
ratio of 1. The subset of edges included in the subgraph driver is marked by
red color. The diamond and round vertices mark the two subsets that achieve
the maximum cut. Note that the red edges form a perfect matching.

The driver Hamiltonian in this case is given by:

$C=Z_{0}Z_{7}+Z_{1}Z_{4}+Z_{2}Z_{5}+Z_{3}Z_{6}.$

From Eq. (4), one can see that the cost expectation of edges in $G$ that are
not in $G^{\prime}$ is 0.5. The edges that are in $G^{\prime}$ do not form
triangles, therefore it is easy to see that their cost expectation becomes
equal to 1 for $\gamma=\pi/2$ and $\beta=\pi/8$. There are 6 edges that are in
$G$ but not in $G^{\prime}$ and 4 edges in $G^{\prime}$, therefore the total
cost expectation, 7, in this case coincides with the maximum cut for this
graph.

### Example: A family of graphs and circuits with an approximation ratio of
0.5

The star graph on $n$ vertices is a connected $n$-vertex graph that has
exactly one vertex of degree $n-1$ and $n-1$ vertices of degree one. An
example of a star graph is depicted in Fig. 2.

$v_{4}$$v_{0}$$v_{3}$$v_{2}$$v_{1}$ Figure 2: The star graph, which consists
of vertices and the solid edges. The dashed red edges are the terms included
in the driver Hamiltonian. This choice of driver Hamiltonian yields an
approximation ratio of 0.5.

Consider a star graph with 3 or more leaves. Label the center vertex of the
star $n-1$ and the other vertices $0$ to $n-2$ in clockwise order, starting at
some arbitrary leaf. Now consider the driver Hamiltonian with the terms of the
form $Z_{i}Z_{i+1}$ modulo $n-2$, which has $n-1$ terms, the same as the cost
Hamiltonian. With this choice of the driver Hamiltonian, the last term of Eq.
(4) for all edges of the graph is 0, since none of them satisfy the triangle
condition. Furthermore, the second term in Eq. (4) is also zero since none of
edges are chosen as a term in the driver Hamiltonian. Therefore, all edges in
the graph have the cost expectation of 0.5, and the overall cost expectation
for a star graph with this driver Hamiltonian is $\frac{|E|}{2}$. In general,
if the edges of the graph do not correspond to the terms of the driver
Hamiltonian and do not satisfy the triangle condition, the approximation ratio
will always be 0.5. Note if the star has two leaves, this driver Hamiltonian
construction contains a multi-edge, and thus requires additional parameter
optimization considerations.

##  III Results

In this work, we considered QAOA with random driver Hamiltonians, subgraph
driver Hamiltonians, a special case of subgraph driver Hamiltonians in which a
subset of triangles are removed (abbreviated TR-driver Hamiltonian for
triangle-removed), and a subcase of random subgraph where edges that are
incident to maximal degree vertices are removed (abbreviated MDER-driver for
maximum degree edge removal) for solving the MaxCut problem on a collection of
all non-isomorphic eight vertex graphs. The simulations were performed by
maximizing the expected value formula in Eq. (4) over the parameters $\gamma$
and $\beta$. In each simulation, the optimization is done using the code
provided at wilkiecode . The optimizer used was the L-BFGS algorithm with 100
random parameter initialization seeds.

###  III.1 Random driver Hamiltonians

First, we consider random driver Hamiltonians and analyze the effect of driver
Hamiltonian structure on the approximation ratio. In order to create the
driver graphs, we randomly selected $m$ of the $8\choose 2$ possible edges of
the complete graph on eight vertices, where $m$ is the number of edges in the
original graph. For each graph, up to 10 non-isomorphic random drivers were
considered. Note that in some cases, such as the complete graph $K_{8}$, we
cannot select 10 non-isomorphic driver Hamiltonians, since we keep the same
number of edges in the driver graph. However, when possible, we generated 10
non-isomorphic random driver Hamiltonians and evaluated the approximation
ratio for each.

Out of all the random driver Hamiltonians tested, 0.036% of the graphs had at
least one random driver that gave a higher approximation ratio than the cost
driver. The random graphs are not guaranteed to have any structure with
respect to the original graph, so it is not surprising that the random driver
Hamiltonians typically perform worse. Furthermore, there are far more than 10
non-isomorphic driver Hamiltonians that can be generated in most cases, so it
is of course possible that the remaining graphs have better driver
Hamiltonians. Table 1 shows the maximum, minimum, and average AR that was
achieved by using random driver Hamiltonians as opposed to the cost driver. On
average, the random driver Hamiltonians resulted in significantly lower
approximation ratios.

Driver type | Max AR | Min AR | Average AR | % Graphs Better
---|---|---|---|---
Random | 0.946 | 0.5 | 0.710 | 0.036%
Subgraph | 1.0 | 0.563 | 0.771 | 75.9%
TR-Most | 0.972 | 0.686 | 0.813 | 90.5%
TR-2 Most | 0.972 | 0.711 | 0.820 | 89.2%
TR-All | 0.973 | 0.686 | 0.817 | 83.0%
TR-Random | 0.972 | 0.670 | 0.807 | 29.3%
MDER-1 | 0.972 | 0.657 | 0.805 | 90.7%
MDER-2 | 0.971 | 0.651 | 0.802 | 81.6%
MDER-All | 0.959 | 0.5 | 0.777 | 0.711%
Cost (regular QAOA) | 0.973 | 0.662 | 0.806 | —
Table 1: Comparison of the maximum, minimum, and average AR achieved by the
random, subgraph, triangle-removed, max degree edge removed, and cost drivers
as well as the percentage of graphs that had at least one driver that
performed better than the cost driver.

###  III.2 Subgraph driver Hamiltonians

The subgraph driver Hamiltonians differ from the purely random ones in that we
choose a random subgraph of the original graph $G$ and add to the driver
Hamiltonian $Z_{i}Z_{j}$ only the terms corresponding to edges of this
subgraph. In other words, only a subset of terms from the cost Hamiltonian can
be considered for the driver.

In this experiment, we select random driver subgraphs that contain
$\lceil\alpha|E(G)|\rceil$ edges of $G$ for
$\alpha\in\left\\{\frac{1}{4},\frac{1}{3},\frac{1}{2},\frac{2}{3},\frac{3}{4}\right\\}$.
Similar to before, we choose up to 10 non-isomorphic subgraphs for each
$\alpha$ and use 100 parameter initialization seeds.

Compared to the purely random driver Hamiltonians, the subgraph driver
Hamiltonians yielded higher approximation ratios. Out of all the subgraph
drivers tested, 75.9% of the considered graphs had at least one subgraph
driver with a higher approximation ratio. Since only 10 non-isomorphic
subgraph driver Hamiltonians were tested, it is possible that there exist
driver Hamiltonians that have even better performance. Table 1 shows the
maximum, minimum, and average AR that was achieved by using subgraph driver
Hamiltonians as opposed to the cost Hamiltonian for MaxCut.

One interesting note is that there were 10 driver subgraphs that achieved an
AR of 1, meaning that the optimal MaxCut value was found. The structure of
these subgraphs all have the same form, where the subgraph is a perfect
matching as in Fig. 1. A perfect matching $M\subset E$ is a subset of graph
edges such that every vertex in $G$ is incident to exactly one edge in $M$.
While interesting to note, this condition is not necessary or sufficient to
define subgraph drivers that achieve an approximation ratio of 1. However, if
the MaxCut value is $\frac{|V|}{4}+\frac{|E|}{2}$, then a perfect matching
driver, if it exists, does yield an approximation ratio of 1. In general, this
information is not known a priori.

###  III.3 TR-driver Hamiltonians

The TR-driver Hamiltonians are a special case of the subgraph driver
Hamiltonians in which one or more triangles is removed from the original
graph. All edges that are not in triangles remain in the driver Hamiltonian.
The importance of this case is to reduce the number of triangles so that the
last term of Eq. (4) is $0$ for a larger number of edges in the graph, with
the hope is that this increases the overall expected value. This experiment
examines four types of TR-driver Hamiltonians. The first type, named “most”,
removes a single edge that is contained in the most triangles in the graph.
The second type, named “2 most”, implements the same “most” rule, but applied
consecutively 2 times. The third type, named “all”, iteratively removes edges
until there are no more triangles left in the graph. The final type, named
“random”, just chooses a single random edge included in a random triangle and
removes it.

Out of all the TR-driver Hamiltonians tested, 95.1% of the considered graphs
had at least one TR-driver that yielded a higher approximation ratio. Table 1
depicts the maximum, minimum, and average AR that was achieved by TR-drivers
as opposed to the cost drivers. These results indicate that removing triangles
from the cost driver can improve the approximation ratio, while also using
fewer gates in the circuit. However, comparing the performance of “all” and “2
most” types, one can see that removing all the triangles in the graph does not
always give a higher approximation ratio. This may be due to the fact that
removing all triangles may result in new structure, such as an increase in the
diameter of the graph, that may be difficult for QAOA to see. Additionally,
the expectation of the removed edges tends to decrease, which offsets the gain
from the remaining edges. Among the considered cases, removing the two edges
that form the most triangles yields the highest approximation ratio.

###  III.4 MDER-driver Hamiltonians

The MDER-driver Hamiltonians are subcases of the subgraph driver Hamiltonian
in which at least one edge that is incident to maximum degree vertices are
removed from the original graph. We examine this type of driver because the
exponents of the trigonomeric functions in the expected value equation depend
on degree of the vertex incident to each edge. Removing edge with high degree
drives down the degree of a subset of the trigonometric functions in Eq. (4).
This may slightly increase the expected value of all edges that share a common
vertex with the removed edge at the cost of setting the expected value of the
removed edge to 0.5 plus possibly the triangle term in the expected value.
Thus, edges incident to high degree vertices are removed. This experiment
considers 3 types of MDER-drivers: MDER-1-driver where we find the maximal
degree vertex and remove the edge incident to it, MDER-2-driver where we take
the MDER-1-driver and find the maximal degree vertex of the remaining graph
and remove the edge incident to it, and MDER-all-driver where we find the
maximal degree vertex and remove all the edges incident to it.

Out of all the MDER-driver Hamiltonians tested, 93.9% of the considered graphs
had at least one MDER-driver that yielded a higher approximation ratio. Table
1 depicts the maximum, minimum, and average AR that was achieved by MEER-
drivers as opposed to the cost drivers. We can also see the percentages of
graphs that had at least one driver that performed better than the cost
driver. These results indicate that removing edges incident to maximum degree
vertices can improve the approximation ratio, while also using fewer gates in
the circuit. However, removing all the edges incident to the maximum degree
vertex can lead to worse performance.

##  IV Discussion

In this work, we examined the impact of QAOA driver Hamiltonian design on the
approximation ratio. In general, removing a subset of triangles from the
driver Hamiltonian tends to yield a higher average approximation ratio.
Furthermore, using a random driver Hamiltonian tends to result in a lower
approximation ratio than the approximation ratio yielded by the cost driver.

The main implication of this work is that, on average, fewer gates can be used
in the QAOA circuit and a comparable approximation ratio can be attained. This
can provide a modest noise reduction when implementing the algorithm on NISQ
devices. Future work may include multiple directions. First, one can examine
how the subgraph driver Hamiltonians affect the optimization landscape, as
there could be a risk that modifying the driver Hamiltonian results in more
barren plateaus. Second, it is important to consider the scalability of the
custom driver Hamiltonians with respect to the number of layers of QAOA.
Another direction includes characterizing of when removing gates will improve
the approximation ratio. We will also consider using MA-QAOA with the subgraph
driver Hamiltonians to see if the approximation ratio of a given problem can
be increased even further. Since the subgraph driver Hamiltonians have fewer
gates, there would be fewer angles to optimize. Thus, the parameter
optimization of these multi-angle circuits should be easier, which overcomes
one of the challenges of MA-QAOA implementationgaidai2023performance .

One possible application of this work is in the area of privacy. In
upadhyay2023obfuscating , the authors explore creating multiple circuits with
various gates removed from the QAOA cost Hamiltonian in order to protect the
privacy of the problem at hand at the cost of having to run multiple circuits
on different third party hardware and recombining the results. Our work shows
that we can remove certain gates from the cost Hamiltonian, thus increasing
the privacy of the original problem, and have comparable results without
relying on multiple circuits.

## Acknowledgements

J.O. acknowledges DARPA ONISQ program under award W911NF-20-2-0051. R. H., J.
O., and A. W. acknowledge NSF CCF 2210063.

## References Cited

  * (1) E. Farhi, J. Goldstone, and S. Gutmann, “A quantum approximate optimization algorithm,” 2014. [Online]. Available: https://arxiv.org/abs/1411.4028
  * (2) A. Ozaeta, W. van Dam, and P. L. McMahon, “Expectation values from the single-layer quantum approximate optimization algorithm on ising problems,” _Quantum Science and Technology_ , vol. 7, no. 4, p. 045036, sep 2022. [Online]. Available: https://doi.org/10.1088%2F2058-9565%2Fac9013
  * (3) R. Herrman, L. Treffert, J. Ostrowski, P. C. Lotshaw, T. S. Humble, and G. Siopsis, “Impact of graph structures for qaoa on maxcut,” _Quantum Information Processing_ , vol. 20, no. 9, pp. 1–21, 2021.
  * (4) E. Farhi, D. Gamarnik, and S. Gutmann, “The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples,” _arXiv preprint arXiv:2005.08747_ , 2020.
  * (5) J. Wurtz and D. Lykov, “The fixed angle conjecture for qaoa on regular maxcut graphs,” 2021. [Online]. Available: https://arxiv.org/abs/2107.00677
  * (6) G. G. Guerreschi and A. Y. Matsuura, “QAOA for max-cut requires hundreds of qubits for quantum speed-up,” _Scientific Reports_ , vol. 9, no. 1, may 2019. [Online]. Available: https://doi.org/10.1038%2Fs41598-019-43176-9
  * (7) Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, “Quantum approximate optimization algorithm for maxcut: A fermionic view,” _Physical Review A_ , vol. 97, no. 2, p. 022304, 2018.
  * (8) 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.
  * (9) M. P. Harrigan, K. J. Sung, M. Neeley, K. J. Satzinger, F. Arute, K. Arya, J. Atalaya, J. C. Bardin, R. Barends, S. Boixo _et al._ , “Quantum approximate optimization of non-planar graph problems on a planar superconducting processor,” _Nature Physics_ , vol. 17, no. 3, pp. 332–336, 2021.
  * (10) N. Earnest, C. Tornow, and D. J. Egger, “Pulse-efficient circuit transpilation for quantum applications on cross-resonance-based hardware,” _Physical Review Research_ , vol. 3, no. 4, p. 043088, 2021.
  * (11) R. Herrman, P. C. Lotshaw, J. Ostrowski, T. S. Humble, and G. Siopsis, “Multi-angle quantum approximate optimization algorithm,” _Scientific Reports_ , vol. 12, no. 1, pp. 1–10, 2022.
  * (12) J. Wurtz and P. J. Love, “Classically optimal variational quantum algorithms,” _IEEE Transactions on Quantum Engineering_ , vol. 2, pp. 1–7, 2021.
  * (13) V. Vijendran, A. Das, D. E. Koh, S. M. Assad, and P. K. Lam, “An expressive ansatz for low-depth quantum optimisation,” _arXiv preprint arXiv:2302.04479_ , 2023.
  * (14) K. Shi, R. Herrman, R. Shaydulin, S. Chakrabarti, M. Pistoia, and J. Larson, “Multi-angle qaoa does not always need all its angles,” _arXiv preprint arXiv:2209.11839_ , 2022.
  * (15) Z. Zhou, Y. Du, X. Tian, and D. Tao, “Qaoa-in-qaoa: solving large-scale maxcut problems on small quantum machines,” _Physical Review Applied_ , vol. 19, no. 2, p. 024027, 2023.
  * (16) J. Li, M. Alam, and S. Ghosh, “Large-scale quantum approximate optimization via divide-and-conquer,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , 2022.
  * (17) M. Ponce, R. Herrman, P. C. Lotshaw, S. Powers, G. Siopsis, T. Humble, and J. Ostrowski, “Graph decomposition techniques for solving combinatorial optimization problems with variational quantum algorithms,” _arXiv preprint arXiv:2306.00494_ , 2023.
  * (18) Z. Wang, N. C. Rubin, J. M. Dominy, and E. G. Rieffel, “X y mixers: Analytical and numerical results for the quantum alternating operator ansatz,” _Physical Review A_ , vol. 101, no. 1, p. 012320, 2020.
  * (19) A. Bärtschi and S. Eidenbenz, “Grover mixers for qaoa: Shifting complexity from mixer design to state preparation,” in _2020 IEEE International Conference on Quantum Computing and Engineering (QCE)_. IEEE, 2020, pp. 72–82.
  * (20) E. Farhi, D. Gamarnik, and S. Gutmann, “The quantum approximate optimization algorithm needs to see the whole graph: A typical case,” _arXiv preprint arXiv:2004.09002_ , 2020.
  * (21) 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.
  * (22) S. Hadfield, “Quantum algorithms for scientific computing and approximate optimization,” _arXiv preprint arXiv:1805.03265_ , 2018.
  * (23) https://github.com/GaidaiIgor/MA-QAOA.
  * (24) A. Wilkie, “Random circuit qaoa,” 2024. [Online]. Available: https://github.com/Vilcius/MA-QAOA
  * (25) I. Gaidai and R. Herrman, “Performance analysis of multi-angle qaoa for $p>1$,” _arXiv e-prints_ , pp. arXiv–2312, 2023.
  * (26) S. Upadhyay and S. Ghosh, “Obfuscating quantum hybrid-classical algorithms for security and privacy,” _arXiv preprint arXiv:2305.02379_ , 2023.