# Small-Signal Stability and SCR Enhancement of Offshore WPPs with Synchronous
Condensers

Sulav Ghimire123, Kanakesh V. Kkuni1, Emerson D. Guest1, Kim H. Jensen1,
Guangya Yang2  1Siemens Gamesa Renewable Energy A/S, 7330 Brande, Denmark
2Technical University of Denmark, 2800 Kgs Lyngby, Denmark  3Correspondence
via<EMAIL_ADDRESS>
###### Abstract

Synchronous condensers (SCs) have been reported to improve the overall
stability and short-circuit power of a power system. SCs are also being
integrated into offshore wind power plants (WPPs) for the same reason. This
paper, investigates the effect of synchronous condensers on an offshore wind
power plant with grid-following (GFL) and grid-forming (GFM) converter
controls. Primarily, the effect of synchronous condensers can be two-fold: (1)
overall stability enhancement of the WPP by providing reactive power support,
(2) contribution to the effective short circuit ratio (SCR) of the WPP by
fault current support. Therefore, this paper focuses on studies concerning
these effects on an aggregated model of a WPP connected to the grid. To that
end, a state-space model of the test system is developed for small-signal
stability assessment and the synchronous condenser’s effect on its stability.
In addition, a mathematical explanation of SCR enhancement with synchronous
condenser is provided and is verified with time-domain electromagnetic
transient simulations.

###### Index Terms:

Stability, weak grids, offshore WPP, synchronous condensers, grid-forming,
grid-following.

##  I Introduction

Modern offshore wind power plants (WPPs) are connected to the grid via long
sea-cables characterized by their low X/R ratio and low short circuit ratio
(SCR) [1]. The low SCR (and low inertia of the existing power grid) implies
lower fault current contribution from the grid, and thus the grid connection
is termed as a weak-grid. Small-signal stability studies have shown that low
SCR weak-grid connections can introduce an open-loop zero in the right half
plane of the system leading to oscillations which are poorly-damped or
undamped [2]. The low X/R ratio also enhances the P-V and Q-f coupling which
otherwise would be negligible in a grid with high X/R ratio since the
resistance is negligible in comparison to the reactance [1]. In a weakly-
connected offshore WPP, a reactive power support device at the point of common
coupling (PCC) helps to supply higher fault currents [3], provide better
reactive power support, and aid in post-fault voltage recovery [4]. This
further aids the WPP to operate smoothly during steady state as well as during
fault-ride through (FRT.)

Synchronous condensers (SCs) have been known to stabilize power systems by
providing damping to generator power swings and reactive power injection [5].
There has been some examples of stability enhancement of offshore WPPs with
the help of a reactive power support device such as STATCOM, static var
compensator (SVC,) or SC. e.g. A WPP connected to Texas’ ERCOT grid
experienced low frequency oscillations due to weak-grid connections which was
subsequently seen to be damped by SVCs and SCs [6]. SCs can also help control
the wind-farm transient voltage under communication failure by using an
‘online sequential extreme learning machine’ based voltage prediction method
[4].

In a comparative analysis between STATCOM and SCs for wind-farm applications,
results presented by [7] show that a SCs can improve the stability of a WPP
with GFL type-IV wind turbines (WTs) connected to a weak-grid; it is seen to
improve the system stability even when it is not injecting any reactive power.
On the other hand a STATCOM improves the stability of a WPP only by injecting
reactive power.

Previous work supports the use of SCs in modern power systems as they increase
the short-circuit performance, overload capabilities, inertial support, and
also facilitate the integration of more inverter based resources [8]. Weak-
grid applications of SCs have been proposed along with battery energy storage
system (BESS) in [9] where the SC provided a significant improvement in
overload capacity while retaining the fast response of a converter-integrated
BESS. A similar application could be found for offshore WPPs with weak-grid
connections. Although SCs can enhance the protection performance of a type-IV
WPP, it has been seen that the converter control strategy also highly affects
the overall performance of the WPP [10].

The key contributions of this paper are summarized as:

  * •

Small-signal stability quantification of an offshore WPP with the addition of
SCs.

  * •

Quantification of SCR enhancement of an offshore WPP with the addition of SCs.

The paper layout is as follows: Section II describes the system setup, its
modelling (time-domain and frequency-domain small-signal model development,)
and adopted methodology (small-signal stability analysis and time-domain fault
simulation.) Section III describes the equivalent SCR formulation including
the effect of synchronous condenser. Section IV provides the results obtained
and a detailed analysis and discussion on the results. Finally, Section V
summarizes the findings and provides a conclusion based on the studies
presented in the paper.

##  II System Setup and Modelling

The system under study consists of an aggregated WPP connected to a grid
through an array cable and a transformer as shown in figure 1. The array cable
has an impedance $Z_{a}$, and the grid has an impedance $Z_{g}=R_{g}+jX_{g}$.
A synchronous condenser with sub-transient reactance $Z_{sc}=jX^{"}_{sc}$ is
connected at the PCC.

All parameters are represented in pu, and differential and algebraic variables
are represented in small-signal pu when denoted by a lowercase letter, and are
in large-signal SI units when denoted by an uppercase letter.

Figure 1: Aggregated WPP layout with synchronous condenser connected at PCC.

###  II-A Grid and Synchronous Condenser Model

The grid is modelled as a Thevenin equivalent source, i.e. an ideal voltage
source ($\tilde{V}_{g}=1\angle 0^{\circ}$) behind an impedance $Z_{g}$. The
load-flow behavior of a grid thus modelled would be that of a $P-\delta$ bus.
The mathematical model of the grid used to build its time-domain model can be
written as:

$\displaystyle\tilde{V}_{g}$ $\displaystyle=$ $\displaystyle 1\angle
0^{\circ}$ (1) $\displaystyle\tilde{I}_{g}$ $\displaystyle=$
$\displaystyle\frac{\tilde{V}_{g}-\tilde{V}_{pcc}}{R_{g}+jX_{g}}$ (2)
$\displaystyle S_{g}$ $\displaystyle=$ $\displaystyle
P_{g}+jQ_{g}=\tilde{V}_{g}\tilde{I}_{g}^{*}$ (3)

where, $\tilde{V}_{g}$ is the grid voltage, $\tilde{V}_{pcc}$ is the PCC
voltage, $Z_{g}=R_{g}+jX_{g}$ is the grid impedance, $\tilde{I}_{g}$ is the
current flowing from the grid towards PCC, and $S_{g}=P_{g}+jQ_{g}$ is the
grid apparent power whose real part $P_{g}$ is the active power and imaginary
part $Q_{g}$ is the reactive power. The $\tilde{(\cdot)}$ above the variables
indicate that they are phasor variables.

The state equation relating to the small-signal model of the grid is,

$L_{g}\dot{i}_{g,dq}=-R_{g}i_{g,dq}+jX_{g}i_{g,dq}+v_{g,dq}-v_{pcc,dq}$ (4)

Similar to the grid, a synchronous condenser is also modelled as a Thevenin
equivalent model, i.e. an ideal voltage source behind the sub-transient
reactance. This modelling approach is valid for small-signal stability and
fault studies since during the fault cases and fast transients, the sub-
transient reactance of the synchronous condenser becomes active [11, 12]. This
approach has been adopted in the academic literature as well [13].

Synchronous condenser controls are bypassed for this study as their responses
are very slow and only impact on the low-frequency ranges. The load-flow
behavior of the synchronous condenser is that of a $P-V$ bus with a small
active power loss $|P|<<1$ pu. The mathematical model of the synchronous
condenser is thus given as,

$\displaystyle\tilde{V}_{sc}$ $\displaystyle=$ $\displaystyle
1\angle\varphi_{sc}$ (5) $\displaystyle\tilde{I}_{sc}$ $\displaystyle=$
$\displaystyle\frac{\tilde{V}_{sc}-\tilde{V}_{pcc}}{jX_{sc}^{"}+R_{tr}+jX_{tr}}$
(6) $\displaystyle S_{sc}$ $\displaystyle=$ $\displaystyle
P_{sc}+jQ_{sc}=\tilde{V}_{sc}\tilde{I}_{sc}^{*}\approx Q_{sc}$ (7)

where $\tilde{V}_{sc}$ is the synchronous condenser voltage, $\tilde{I}_{sc}$
the current, $X_{sc}^{"}$ the sub-transient reactance, and $Q_{sc}$ is its
reactive power contribution. The transformer is also modelled inside of the
aforementioned equations and $R_{tr}+jX_{tr}$ represent the transformer
impedance. The transformer used in this paper is a $Y-Y$ transformer, thus no
phase-shift adjustment is necessary.

Now, the state equation relating to the small-signal model of the synchronous
condenser is written as,

$\frac{X_{sc}^{"}}{\omega_{0}}\dot{i}_{sc,dq}=R_{tr}i_{sc,dq}+j(X_{sc}^{"}+X_{tr})i_{sc,dq}+v_{sc,dq}-v_{pcc,dq}$
(8)

The equivalent circuit of the power grid and synchronous condenser thus
modelled are shown in Fig. 2.

Figure 2: Thevenin equivalent models for (a) power grid, and (b) synchronous
condenser and transformer used in the study.

###  II-B WPP Converter Models

Two different control methods for the WPP converters are selected for the
studies, namely grid-following (GFL) control and grid-forming (GFM) control as
shown in Figure 1. Although the detailed modelling of these controls are not
included, an averaged state-space model is presented in this paper.

####  II-B1 Grid-Following Control (GFL)

The grid-following (GFL) control includes a phase-locked loop (PLL) as the
synchronizing unit which drives the power and current controllers. The
converter control model used is derived from [14] and readers are requested to
refer to the same for details.

The linearized state-space equations of the GFL converter can be summarized
as:

$\displaystyle\dot{\theta}_{pll}$ $\displaystyle=$
$\displaystyle\omega_{0}+K_{p}^{(pll)}v_{q}+K_{i}^{(pll)}\mathcal{S}$ (9)
$\displaystyle\dot{\mathcal{S}}$ $\displaystyle=$ $\displaystyle v_{q}$ (10)
$\displaystyle\dot{\gamma}$ $\displaystyle=$
$\displaystyle-\frac{K_{i}^{(pc)}}{K_{p}^{(pc)}}\gamma+\frac{1}{K_{p}^{(pc)}}i_{dq}^{*}$
(11) $\displaystyle\dot{\mathcal{O}}_{dq}$ $\displaystyle=$ $\displaystyle
i_{dq}^{*}-i_{dq}$ (12)

where, $\theta_{pll}$ is the PLL phase angle, $\omega_{0}=2\pi f_{0}$ is the
nominal angular frequency, and $K_{p}^{(pll)}$ and $K_{i}^{(pll)}$ are the PLL
proportional and integral gains respectively. $\gamma$ is the power controller
state given as the integral of small-signal power mismatch, i.e.
$\dot{\gamma}=p^{*}-p_{pc}$, $K_{p}^{(pc)}$ and $K_{i}^{(pc)}$ are the PI-
gains of the power controller. $p_{pc}$ and $q_{pc}$ are the small-signal
active and reactive powers of the converter, $v_{dq}$ and $i_{dq}$ represent
the voltage and current at the measurement points, $\mathcal{S}$ is a PLL-
state which is given as $\dot{\mathcal{S}}=v_{q}$, and $\mathcal{O}_{dq}$ are
the current controller states. Now, the converter voltage reference signals
can be written as:

$v_{idq}^{*}=v_{dq}^{(pcc)}+K_{p}^{(cc)}(i_{dq}^{*}-i_{dq})+K_{i}^{(cc)}\mathcal{O}_{dq}$
(13)

####  II-B2 Grid-Forming Control (GFM)

A virtual synchronous machine (VSM) based GFM control is implemented. For
detailed model of the GFM converter control used in this paper, readers are
requested to refer to [15].

The linearized state-space equations of the GFM converter are given as:

$\displaystyle\dot{\theta}_{pc}$ $\displaystyle=$ $\displaystyle\omega_{pc}$
(14) $\displaystyle J\dot{\omega}_{pc}$ $\displaystyle=$ $\displaystyle
p^{*}-p_{pc}-D_{p}\omega_{pc}$ (15) $\displaystyle\dot{\mathcal{M}}_{dq}$
$\displaystyle=$ $\displaystyle v_{dq}^{*}-v_{dq}$ (16)
$\displaystyle\dot{\mathcal{O}}_{dq}$ $\displaystyle=$ $\displaystyle
i_{dq}^{*}-i_{dq}$ (17)

where, $J$ is the VSM inertia constant, $D_{p}$ is the VSM damping term,
$\theta_{pc}$ is the angle given by the power controller, and
$\mathcal{M}_{dq}$ and $\mathcal{O}_{dq}$ are the voltage controller and
current controller states respectively. The voltage controller and current
controller output equations are written as follows respectively.

$\displaystyle i_{dq}^{*}$ $\displaystyle=$ $\displaystyle
i_{dq}^{(pcc)}+G_{piv}(s)(v_{dq}^{*}-v_{dq})+\frac{jv_{dq}}{X_{C_{f}}}$ (18)
$\displaystyle v_{idq}^{*}$ $\displaystyle=$ $\displaystyle
v_{dq}^{(pcc)}+G_{pic}(s)(i_{dq}^{*}-i_{dq})+jX_{f}i_{dq}$ (19)

####  II-B3 Filter and Array Cable Model

Based on Kirchhoff’s voltage and current laws, the state-space model of the
converter’s filter and array cable can be written as a set of differential-
algebraic equations and are given as:

$\displaystyle L_{f}\dot{i}_{f,dq}$ $\displaystyle=$ $\displaystyle-
R_{f}i_{f,dq}+jX_{f}i_{f,dq}-v_{c,dq}+v_{inv,dq}$ (20) $\displaystyle
C_{f}\dot{v}_{c,dq}$ $\displaystyle=$ $\displaystyle
i_{f,dq}+j\omega_{0}C_{f}v_{c,dq}-i_{a,dq}$ (21) $\displaystyle
L_{a,tf}\dot{i}_{a,dq}$ $\displaystyle=$ $\displaystyle
v_{c,dq}-R_{a,tf}i_{a,dq}+jX_{a,tf}i_{a,dq}-v_{pcc,dq}$ (22)

Here, $R_{f},\ L_{f},\ C_{f}$ are the filter resistance, inductance, and
capacitance, $L_{a},\ R_{a}$ are the array cable inductance and resistance,
and $L_{tf},\ R_{tf}$ are the transformer inductance and resistance
respectively. Also, $R_{a,tf}$ and $L_{a,tf}$ are given as $R_{a}+R_{tf}$ and
$L_{a}+L_{tf}$ respectively and $X_{a,tf}=\omega_{0}L_{a,tf}$.

##  III SCR Enhancement

The short-circuit ratio of a WPP at any given point is given as the ratio of
the grid’s fault MVA contribution to the WPP rated power.

$\text{i.e. }SCR=\frac{S_{g,f}}{S_{WPP}}$ (23)

where, $S_{g,f}$ is the grid fault contribution and $S_{WPP}$ is the WPP’s
rated apparent power.

Assuming $1$ pu voltage being maintained at the grid during the fault, and
$S_{WPP}=1$ pu, we can rewrite the system SCR as:

$SCR=\frac{V_{g,pu}^{2}/|Z_{g,pu}|}{1\ pu}=\frac{1}{|Z_{g,pu}|}$ (24)

Assuming 1 pu voltage behind the sub-transient reactance, a synchronous
condenser can be aggregated with the grid to observe an effective rise in the
equivalent short circuit ratio (ESCR) at PCC.

From (24), we know that the SCR of a WPP at PCC can be given as the reciprocal
of the pu grid impedance at $1$ pu grid voltage. In a WPP, the base SCR value
at WT MV terminals without considering the synchronous condenser is be written
as:

$\text{i.e. }SCR_{o}=\frac{1}{Z_{g,pu}+Z_{a,tf,pu}}$ (25)

Here, the impedance $Z_{g,pu}:=|Z_{g,pu}|$ and
$Z_{a,tf,pu}:=|Z_{a,pu}+Z_{tf,pu}|$ are the absolute value of the sum of the
respective impedances. The same convention is followed for all other
impedances henceforth unless otherwise stated.

Considering the stabilizing effect and fault MVA contribution of a synchronous
condenser on SCR evaluation, we can view the grid and synchronous condenser
pair from PCC as two voltage sources in parallel. Thus we can write for the pu
impedance seen at PCC as:

$Z_{PCC,pu}=\frac{Z_{g,pu}\cdot
Z_{sc,pu}}{Z_{g,pu}+Z_{sc,pu}}<\min{(Z_{g,pu},Z_{sc,pu})}$ (26)

The effective SCR at WT MV terminal can now be written as:

$SCR_{sc}=\frac{1}{Z_{PCC,pu}+Z_{a,tf,pu}}$ (27)

Here, since $Z_{PCC,pu}<Z_{g,pu}$, it implies that SCR${}_{sc}>SCR_{o}$. Thus
effective SCR at the WT MV terminal considering the synchronous condenser is
higher than that without the synchronous condenser. The physical
interpretation of this is that the short-circuit MVA contribution of the
synchronous condenser increases the overall fault MVA of the system, thus
increasing the effective SCR.

We can now write for this new effective SCR including the effect of the
synchronous condenser as:

$SCR_{sc}=\frac{Z_{g,pu}+Z_{sc,pu}}{Z_{g,pu}\cdot
Z_{sc,pu}+Z_{a,tf,pu}(Z_{g,pu}+Z_{sc,pu})}$ (28)

The SCR enhancement quantification provided here in equation 28 is verified
with SCR values calculated from time-domain fault simulations including the
effect of SC in the system.

##  IV Results and Discussion

The small-signal and time-domain simulation models developed for the test
system presented in Fig. 1 are subjected to different tests. Frequency domain
studies involving the step-responses of power and voltage controllers of the
converter controls are presented in this section where small-signal stability
information are observed, e.g. controller reference tracking, oscillations and
damping based on step responses, and stability/instability based on eigenvalue
plots. The WPP’s SCR is calculated before and after the addition of the
synchronous condenser based on (a) fault simulations and (b) theoretical
calculations based on the method described in Section III, and are presented
in this section.

###  IV-A Small Signal Stability Analysis

For the frequency-domain analysis and studies, different grid conditions and
operating points are chosen. IEEE guidelines [16] classify system strength in
terms of SCR: a very weak grid has very low SCR$<2$, a weak grid has
$2<SCR\leq 3$, and a strong grid has SCR$\geq 3$. An offshore WPP’s SCR is
measured from the turbine MV terminals. SCR has a critical effect on system
stability and study for extreme SCR cases become necessary for such systems.
In order to study the effect of synchronous condensers on stability of a WPP
for different grid strengths, three grid strength cases are chosen and
summarized in Table I in terms of system SCR and X/R ratio.

TABLE I: Grid cases in terms of SCR at WT MV terminal. Grid Case | Base-Case SCR | X/R Ratio
---|---|---
Weak Grid | 1.6 | 5
Normal Grid | 3.2 | 14.8
Strong Grid | 4.12 | 14.8

The step responses of the power and voltage controllers for each of these
cases are presented in Fig. 3 (weak grid,) Fig. 4 (normal grid,) and Fig. 5
(strong grid.) System references/operating points for the presented step
responses are grid reference voltage $V_{g}^{*}=1$ pu, turbine reference
voltage $V_{turb}^{*}=1$ pu, and turbine reference power $P_{turb}^{*}=1$ pu
respectively.

Figure 3: Power and voltage controller step response of GFL and GFM converters
in a weakly connected WPP with and without synchronous condenser.

The step responses in Fig. 3 show that for the provided system responses in a
weakly connected WPP with GFL control, adding a synchronous condenser at PCC
can stabilize the previously unstable system. Furthermore, although
instability is not observed in the response of GFM control, the inset in the
power controller step responses shows that the initial oscillations are damped
with the addition of synchronous condenser.

Figure 4: Power and voltage controller step response of GFL and GFM converters
in a normal-grid connected WPP with and without synchronous condenser.

For the given operating point in a normal grid connected GFM WPP, Fig. 4 shows
that no instability issue is seen in the base case and there is no significant
effect on power and voltage controller step responses after the addition of
the synchronous condenser. The inset on the power controller step response
plot also clarifies that apart from minor differences in the transient
behavior of the controller, there is no major impact on system performance.
The voltage controller response shown in Fig. 4 shows that synchronous
condenser has made the voltage controller response slower. However, no further
noticeable difference on dynamic or steady-state performance is seen to have
been introduced by the synchronous condenser, suggesting that synchronous
condenser can enhance the system damping.

Figure 5: Power and voltage controller step response of GFL and GFM converters
in a strongly connected WPP with and without synchronous condenser.

The system is further tested on a high SCR grid (strong-grid case with
SCR$=4.12$.) The step plots shown in 5 show that in a strongly connected WPP,
addition of synchronous condenser doesn’t change the system stability and
small-signal performance in any significant way.

To better understand the impact of synchronous condensers on WPP stability,
further analysis are presented in terms of system eigenvalues for different
operating points. For each of the sub-cases in Table I, eigenvalue analysis
are performed for a range of 27 different operating points defined as grid
voltage reference($V_{g}^{*}$,) wind turbine voltage reference
($V_{turb}^{*}$,) and wind turbine power references ($P_{turb}^{*}$) as shown
in Table II.

TABLE II: Operating Points Reference | Values
---|---
Grid Voltage Reference ($V_{g}^{*}$) | $\begin{bmatrix}0.92&1.0&1.08\end{bmatrix}$
Turbine Voltage Reference ($V_{turb}^{*}$) | $\begin{bmatrix}0.92&1.0&1.08\end{bmatrix}$
Turbine Power Reference ($P_{turb}^{*}$) | $\begin{bmatrix}0.1&0.5&1.0\end{bmatrix}$

The eigenvalues of the system for the 27 operating points given in II are
coalesced in one figure and plotted in Fig. 6 for weak-grid case, Fig. 7 for
normal-grid case, and 8. Eigenvalue damping is also defined and marked in the
eigenvalue plots with dotted lines. The eigenvalue damping is given as:

$\zeta_{i}=-\frac{\Re\\{\lambda_{i}\\}}{|\lambda_{i}|}$ (29)

where $\lambda_{i}$ is the $i^{th}$ eigenvalue. Eigenvalue damping ratio are
marked in the plots are helpful for understanding system stability as low and
near-synchronous frequency oscillations with higher than $20\%$ damping ratio
ensure well-damped oscillations during normal operating condition.

Figure 6: Eigenvalues for weak-grid case (27 standard operating points
superimposed)

The poles on the right hand side of the $s-$plane in figure 6 suggest that
irrespective of GFL or GFM control, for operating points with low grid and
turbine voltage references ($V_{turb}^{*}=0.92$ pu, $V_{g}^{*}=0.92$ pu,) the
weakly connected offshore WPP exhibits small-signal instability. For the
nominal operating point, the step responses in Fig. 3 showed that the GFM WPP
system stayed stable even without the addition of the synchronous condenser.
However, for other operating points, as seen from Fig. 6, the system goes
unstable and it is stabilized by the addition of synchronous condenser at the
PCC. Near-synchronous frequency modes with poor damping (i.e. poles with
$\zeta<20\%)$ are also seen in cases where turbine and grid voltage references
were at their lower levels, i.e. $V_{turb}^{*}=0.92$ pu, $V_{g}^{*}=0.92$ pu.

Figure 7: Eigenvalues for normal-grid case (27 standard operating points
superimposed)

The normal-grid connected case for the offshore WPP did not exhibit any
stability issues with or without the synchronous condenser across the selected
27 operating points. There are some changes in the eigenvalues location as
shown in Fig. 7, however, the eigenvalue damping and frequencies change only
slightly and there is no significant change in system stability. This was also
observed in the step responses calculated for the nominal case in Fig. 4.
Further, the low-damped, near-synchronous eigenvalues from weak-grid case are
seen to be well-damped in this case. This further suggests that some unstable
system modes are stabilized with synchronous condensers in a weakly connected
system, while a normal-grid connection do not necessarily require synchronous
condensers to enhance system stability. Furthermore, poorly damped near-
synchronous oscillatory modes (not prevalent in normal grids) are not strongly
affected by synchronous condensers in weak grids; grid strength play a crucial
role for the elimination/damping of near-synchronous modes than synchronous
condensers do.

Figure 8: Eigenvalues for Strong-grid case (27 standard operating points
superimposed)

Further eigenvalue analysis for a strong-grid with SCR$=4.12$ is performed on
all the predefined operating points (see Table II.) The eigenvalue plots for
this case presented in figure 8 also show that for a strongly connected
offshore WPP, adding a synchronous condenser does not change the system poles
in any discernible way.

###  IV-B Equivalent Short Circuit Ratio

The ESCR of the system before and after the addition of the synchronous
condenser calculated using the time-domain simulation models as well as based
on the procedure described in III. Short-circuit levels for both these methods
are presented in figure 9. The short-circuit MVA is presented in pu with the
base of the WPP apparent power rating $S_{WPP}$. A summary of the SCR values
based on these results are summarized in Table III below. In either of these
cases, the contribution of converters on the effective SCR is not considered.

Figure 9: SCMVA levels based on theoretical calculation and time-domain simulations. TABLE III: SCR enhancement of a WPP at WT MV terminals based on theoretical calculation vs fault MVA simulations: with and without synchronous condenser (SC.) Grid Case | W/O SC | W/ SC (theoretical) | W/ SC (simulation)
---|---|---|---
Weak Grid | SCR = 1.6 | SCR = 2.67 | SCR = 2.58
Normal Grid | SCR = 3.2 | SCR = 4.28 | SCR = 4.11
Strong Grid | SCR = 4.12 | SCR = 5.71 | SCR = 5.37

From 9 and Table III, the effective SCR of the WPP is seen to have increased
significantly after the introduction of the synchronous condenser. This also
shows a good match between the theoretical calculation and time-domain
simulation based results. Since converter control can interact with
synchronous condenser control, further detailed information on the overall
system stability needs to be gathered with a more detailed synchronous
condenser model including its control dynamics and immitance-based stability
analysis methods.

##  V Conclusion

A state-space and time-domain model of the aggregated offshore WPP was
constructed and the effect of addition of a synchronous condenser in such a
system was studied for different cases. The analysis shows that for a weakly
connected offshore WPP, synchronous condenser can have significant positive
impact on stability. It can enhance the small-signal stability, improve the
system response by damping out oscillations, and enhance the SCR of the
system. The stabilizing effect is more significant for GFL WPPs than for GFM
WPPs. For a normal-grid connected and strongly connected offshore WPP, no
significant stability improvements were observed for the tested 27 operating
points. However, the effective SCR of the system was seen to have been
improved due to the addition of the synchronous condenser in both these cases.
Even though frequency domain analysis didn’t show significant improvement in
small signal stability of the WPPs in these two cases, the synchronous
condenser can still aid in the overall fault response of the WPP and improve
the dynamic stability.

With GFM control of the turbines, the stability issues were observed for fewer
number of operating points. Further analysis seems necessary to fully
understand the stability performance of both synchronous condensers and GFM
converters, and to investigate if a GFM converter can have same or better
stability performance as a GFL converter and synchronous condenser pair. A
stability region in parametric domain (e.g. SCR vs X/R) can also be plotted
for system with and without synchronous condensers and the overlapping zones
could be analyzed.

Small-signal stability quantification was provided for offshore WPPs with both
GFL and GFM control with the addition of synchronous condensers. Effect of
synchronous condensers on the SCR and SCMVA level for such systems were
defined, mathematically described, and validated with time-domain fault
simulations.

##  VI Legal Disclaimer

This work was supported by Innovation Fund Denmark under the project Ref. no.
0153-00256B. Figures and values presented in this paper should not be used to
judge the performance of Siemens Gamesa Renewable Energy technology as they
are solely presented for demonstration purpose. Any opinions or analysis
contained in this paper are the opinions of the authors and not necessarily
the same as those of Siemens Gamesa Renewable Energy.

## References

  * [1] Working Group on Wind Farm Connection, “Connection of wind farms to weak ac networks,” technical brochures, CIGRE Study Committee WG B4.62, 2016.
  * [2] L. Fan and Z. Miao, “An explanation of oscillations due to wind power plants weak grid interconnection,” IEEE Transactions on Sustainable Energy, vol. 9, no. 1, pp. 488–490, 2018.
  * [3] P. S. Kundur, N. J. Balu, and M. G. Lauby, “Power system dynamics and stability,” Power system stability and control, vol. 3, pp. 700–701, 2017.
  * [4] W. Li, Z. Qian, Q. Wang, Y. Wang, F. Liu, L. Zhu, and S. Cheng, “Transient voltage control of sending-end wind farm using a synchronous condenser under commutation failure of hvdc transmission system,” IEEE Access, vol. 9, pp. 54900–54911, 2021.
  * [5] Y. Katsuya, Y. Mitani, and K. Tsuji, “Power system stabilization by synchronous condenser with fast excitation control,” in PowerCon 2000. 2000 International Conference on Power System Technology. Proceedings (Cat. No.00EX409), vol. 3, pp. 1563–1568 vol.3, 2000.
  * [6] S.-H. Huang, J. Schmall, J. Conto, J. Adams, Y. Zhang, and C. Carter, “Voltage control challenges on weak grids with high penetration of wind generation: Ercot experience,” in 2012 IEEE Power and Energy Society General Meeting, pp. 1–7, 2012.
  * [7] L. Bao, L. Fan, and Z. Miao, “Comparison of synchronous condenser and statcom for wind farms in weak grids,” in 2020 52nd North American Power Symposium (NAPS), pp. 1–6, 2021.
  * [8] K. V. Kkuni, M. Nuhic, and G. Yang, “Power system stability impact assessment for the current limits of grid supporting voltage-source converters,” in 2021 IEEE Power and Energy Society General Meeting (PESGM), pp. 1–5, 2021.
  * [9] M. Nuhic and G. Yang, “A hybrid system consisting of synchronous condenser and battery - enhanced services for weak systems,” in 2019 IEEE PES Innovative Smart Grid Technologies Europe (ISGT-Europe), pp. 1–5, 2019.
  * [10] J. Jia, G. Yang, A. H. Nielsen, and P. Rønne-Hansen, “Impact of vsc control strategies and incorporation of synchronous condensers on distance protection under unbalanced faults,” IEEE Transactions on Industrial Electronics, vol. 66, no. 2, pp. 1108–1118, 2019.
  * [11] H. Saadat, “Power system analysis,” 2010, USA: PSA Publishing LLC, Arlington, VA.
  * [12] T. J. E. Miller, Reactive Power Control in Electric Systems.  John Wiley and Sons, 1982.
  * [13] J. Jia, G. Yang, A. H. Nielsen, E. Muljadi, P. Weinreich-Jensen, and V. Gevorgian, “Synchronous condenser allocation for improving system short circuit ratio,” in 2018 5th International Conference on Electric Power and Energy Conversion Systems (EPECS), pp. 1–5, 2018.
  * [14] S. Ghosh, M. K. Bakhshizadeh, G. Yang, and Łukasz Kocewiak, “An improved nonlinear stability assessment methodology for type-4 wind turbines via time reversal trajectory,” 2023.
  * [15] S. Ghimire, K. V. Kkuni, S. C. Jakobsen, T. Knueppel, K. H. Jensen, E. Guest, T. W. Rasmussen, and G. Yang, “Grid-forming control methods for weakly connected offshore wpps,” 22nd Wind and Solar Integration Workshop, 2023.
  * [16] IEEE, “Ieee guide for planning dc links terminating at ac locations having low short-circuit capacities,” IEEE Std 1204-1997, pp. 1–216, 1997.


# Impact of Graph Structures for QAOA on MaxCut

Rebekah Herrman<EMAIL_ADDRESS>Department of Industrial and Systems
Engineering, The University of Tennessee
Knoxville, Tennessee 37996-2315 USA  Lorna Treffert  Department of Industrial
and Systems Engineering, The University of Tennessee
Knoxville, Tennessee 37996-2315 USA  James Ostrowski<EMAIL_ADDRESS>Department of Industrial and Systems Engineering, The University of Tennessee
Knoxville, Tennessee 37996-2315 USA  Phillip C. Lotshaw  Quantum Computing
Institute
Oak Ridge National Laboratory
Oak Ridge, Tennessee 37830 USA  Travis S. Humble  Quantum Computing Institute
Oak Ridge National Laboratory
Oak Ridge, Tennessee 37830 USA  George Siopsis<EMAIL_ADDRESS>Department of Physics and Astronomy, The University of Tennessee
Knoxville, Tennessee 37996-1200 USA

###### Abstract

The quantum approximate optimization algorithm (QAOA) is a promising method of
solving combinatorial optimization problems using quantum computing. QAOA on
the MaxCut problem has been studied extensively on specific families of
graphs, however, little is known about the algorithm on arbitrary graphs. We
evaluate the performance of QAOA at depths at most three on the MaxCut problem
for all connected non-isomorphic graphs with at most eight vertices and
analyze how graph structure affects QAOA performance. Some of the strongest
predictors of QAOA success are the existence of odd-cycles and the amount of
symmetry in the graph. The data generated from these studies are shared in a
publicly-accessible database to serve as a benchmark for QAOA calculations and
experiments. Knowing the relationship between structure and performance can
allow us to identify classes of combinatorial problems that are likely to
exhibit a quantum advantage.

##  I Introduction

Quantum computing has been shown to provide a theoretical advantage over
classical computing in different areas such as machine learning and algorithms
on shallow circuits bravyi2018quantum ; riste2017demonstration , and noisy
intermediate-scale quantum (NISQ) devices provide an opportunity to test this
advantage. The quantum approximate optimization algorithm (QAOA) is a
promising application of NISQ devices developed by Farhi, Goldstone, and
Gutmann to solve combinatorial optimization problems farhi2014quantum .
Unfortunately, large scale testing of QAOA has been difficult, as the size of
problems that can be tested on NISQ hardware is limited and quantum
simulations can be time consuming for small problems.

The current literature has mostly focused on examining graphs with a
predetermined structure. The impact of problem structure on computational
efficiency is well understood in optimization community conforti2014integer :
it is common for a difficult class of problems to become easy when a certain
structure is imposed. By focusing on graphs with a predetermined structure in
QAOA, there is a risk that conclusions made will not extend to the broader
class of problems. In this paper, we seek to remedy this issue by performing
an exhaustive analysis of how graph structure can impact QAOA on small MaxCut
problems.

While there are numerous classes of combinatorial optimization problems, the
MaxCut problem has been the major focus of quantum computing research. The
MaxCut problem on an undirected, simple graph $G=(V(G),E(G))$ is to determine
how to partition $V(G)$ into two sets such that the number of edges between
them is maximized. This problem is classically hard, however, heuristics exist
that find near optimal solutions festa2002randomized ; goemans1994879 .

QAOA for MaxCut has been studied on two and three regular graphs
farhi2014quantum ; brandao2018concentration ; Medvidovic2020QAOA54qubit ;
zhou2018quantum ; akshay2020reachability , and random regular bipartite graphs
farhi2020quantumwholegraph , which are families that are not representative of
the vast majority of graphs. Other work has focused on more general graphs,
for instance Erdős-Rényi random graphs farhi2020quantum , but over small
samples. Additionally, some of the more commonly studied measure of QAOA
success are the expected value of $C$, $\langle C\rangle$, and the
approximation ratio ozaeta2020expectation , which is $\frac{\langle
C\rangle}{C_{max}}$, where $C_{max}$ is the size of the cut in an optimal
solution. Our goal is to look at general graphs and determine which structures
correlate to better performances of QAOA on MaxCut for not only $\langle
C\rangle$ and $\frac{\langle C\rangle}{C_{max}}$ but also the probability of
measuring an optimal solution and the change in the approximation ratio from
level $p$ QAOA to level $p+1$.

To this end, we analyze graph structures and compare them to simulations of
the algorithm on MaxCut at one, two, and three levels for all non-isomorphic,
connected graphs on up to eight vertices. Additionally, we examine
correlations between the structures and the probability of obtaining an
optimal solution with QAOA. We also look at correlations between the expected
value of the cost operator $C$, the ratio of $\langle C\rangle$ to the optimal
solution, and the percent difference in these ratios for consecutive
iterations of QAOA in order to determine which problems are solved well on
quantum computers. A summary of the results is found in Table 2. Finally, we
created a database containing all connected graphs on at most eight vertices
and the structures that were examined. The details for accessing the database
is found in Appendix B.

This paper is organized as follows. In Sec. II, we discuss graph
characteristics and their correlations to QAOA performance metrics. We then
summarize the results and discuss future work in Sec. III.

##  II Graph Structures

In previous work, we ran numerical simulations of QAOA solving the MaxCut
problem on all non-isomorphic graphs with the number of vertices, $n$, ranging
between three and eight QAOABFGS ; lotshawdataset . The angles that maximize
$\langle C\rangle$ after one iteration of QAOA were solved using the open
source software Couennebelotti2009couenne . For larger $p$, we used the
angles, values of $\langle C\rangle$ and probabilities of measuring an optimal
solution found in QAOABFGS . The BFGS algorithm NumericalRecipesBFGS  was used
as a heuristic to determine optimized angles using hundreds of random seeds
for each graph. The optimized results are consistent between different
implementations and are confirmed to be global optimal solutions in small
cases with $n\leq 6$ and $p=2$ by comparing against a brute force method.
Thus, the correlations we draw can be thought of as applying to “best-case”
results for QAOA. Using the numerical simulations from earlier work, we
determine QAOA metrics of interest. The metrics used are:

  * •

$\langle C\rangle$: The expected value of $C$

  * •

$P(C_{max})$: The probability of measuring a state that represents a maximum
cut

  * •

Level $p$ approximation ratio: $\frac{\langle C\rangle_{p}}{C_{max}}$

  * •

Percent change in approximation ratio ($\Delta$ ratio) at $p$:
$\frac{\frac{\langle C\rangle_{p}}{C_{max}}-\frac{\langle
C\rangle_{p-1}}{C_{max}}}{1-\frac{\langle
C\rangle_{p-1}}{C_{max}}}=\frac{\langle C\rangle_{p}-\langle
C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$

where $\langle C\rangle_{p}$ is the expected value of $C$ after $p$ iterations
of QAOA. $\langle C\rangle$ can be written as the sum of expected values for
the operator acting on each edge in the graph, where each edge expectation
value at $p$ iterations depends on vertices up to $p$ edges away, so more
iterations of QAOA allows the algorithm to “see” more of the graph structure.
The level $p$ approximation ratio is the expected value of the cost function
for MaxCut for QAOA performed at level $p$ as a percentage of the optimal
solution, and the $\Delta$ ratio tells us the rate of change of the level per
iteration.

For three vertex graphs, QAOA was only run on two levels, as the correct
solution was found with two iterations. Larger graphs were run on three
levels. Table 1 lists the number of connected, non-isomorphic graphs on $n$
vertices. As there are only two connected graphs on three vertices, the data
for $n=3$ does not give much insight into the correlations between the
structures and different QAOA properties, so we exclude the data for three
vertex graphs from all tables. We study only connected graphs because if the
graph is disconnected, each component has fewer vertices, and we can
independently solve each subproblem. We also study non-isomorphic graphs, as
isomorphic graphs have the same properties and result in the same solutions.

$n$ |  Number of Connected, Non-isomorphic Graphs on $n$ vertices, $N_{n}$
---|---
3 | 2
4 | 6
5 | 21
6 | 112
7 | 853
8 | 11117
Table 1: The number of connected, non-isomorphic graphs on $n$ vertices for $3\leq n\leq 8$.  Graph Property | $\langle C\rangle$ | $P(C_{max})$ | $\frac{\langle C\rangle_{p}}{C_{max}}$ | $\frac{\langle C\rangle_{p}-\langle C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$
---|---|---|---|---
Edges | = | - | - | =
Diameter | = |  | - | =
Clique number | - | - | - |
Bipartite | - |  | - |
Eulerian | = |  | = |
Distance regular | = | = | = |
Number of cut vertices | = | = | + | =
Number of minimal odd cycles | - | - | - | -
Group size | = | = | = |
Number of orbits | = | - | - | -
Table 2: The trends in correlations between the group properties and each QAOA
metric. The symbol “+” refers to correlations that tend to increase, “-”
refers to a correlation that tend to decrease, and “=” refers to correlations
that tend to stay constant for fixed $n$ as $p$ increases. An empty space
refers to a property with no strong correlation or discernible trend.

We collected properties of the tested graphs and found the Pearson’s
correlation coefficient between them and each metric. The properties examined
were:

  * •

Number of edges

  * •

Diameter

  * •

Clique number

  * •

Number of cut vertices

  * •

Number of minimal odd cycles

  * •

Group size

  * •

Number of orbits

  * •

Bipartite (boolean)

  * •

Distance regularity (boolean)

  * •

Eulerian (boolean)

(a)

(b)

Figure 1: $\langle C\rangle$ and the approximation ratio, denoted “A.R.”,
plotted against the total number of edges in the graph for $p=3$. There is a
strong positive correlation, with $r=.875$ in 2(a) and lack of correlation in
2(b), with coefficient $r=.042$.

(a) Correlation with $\langle C\rangle$

(b) Correlation with $P(C_{max})$

(c) Correlation with $\frac{\langle C\rangle_{p}}{C_{max}}$

(d) Correlation with $\frac{\langle C\rangle_{p}-\langle
C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$

Figure 2: The correlations between the number of edges for each $n$ vertex
graph and each of the QAOA metrics for $p$.

Throughout the text and charts, $r$ denotes the correlation coefficient and
$n$ denotes the number of vertices. Definitions of the graph theory terms are
presented in Appendix A. These properties are a subset of all the possible
graph properties, but were chosen because they are commonly studied. We are
providing the database to enable others to identify other structures of
interest. The tables listing correlation coefficients are found in Appendix C.
The graphs and numbering system are from the connected graph files by Brendan
McKay mckay . In the following subsections, we discuss graph properties and
their correlations with different QAOA metrics. Throughout each section, we
will focus on the behavior of $r$ as $n$ and $p$ increase, as these are small
graphs that would not be representative of interesting problems that can
provide a quantum advantage. Additionally, there are few graphs on four and
five vertices compared to $n\in\\{6,7,8\\}$, so data points for
$n\in\\{4,5\\}$ may not be representative of the trends in correlations. Thus,
we will focus our analysis on $n\geq 6$.

###  II.1 Edges, clique number, and minimal odd cycles

The correlation between number of edges and the metrics computed varies
greatly. There is a very strong correlation between the number of edges and
$\langle C\rangle$, which can be seen in Fig. 1 and Fig. 2(a). This makes
intuitive sense for the following reason. Arbitrarily adding edges to a given
graph will not decrease the objective value of any given solution, only
potentially increase it, so we would expect that denser graphs will have
higher $\langle C\rangle$ values. However, the results in Fig. 2(b) shows that
the number of edges is negatively correlated with the probability of sampling
an optimal solution for large $n$ and $p$. We believe this is in part because
the more edges that are added in a graph, the more near optimal solutions
there are that QAOA may favor over the optimal solution. These near-optimal
solutions compete with exact optimal solutions in sampling, as QAOA optimizes
$\langle C\rangle$, it can favor near optimal states over truly optimal ones.

Note that as $n$ increases, the correlation coefficient between edges and
$\langle C\rangle$ increases towards $1$ for fixed $p$, while the coefficients
with $P(C_{max})$, the approximation ratio, and the $\Delta$ ratio slightly
decrease, as seen in Fig. 2. It is unclear why the size of $n$ impacts the
correlation coefficient. At large $p$, we would expect that $\langle C\rangle$
would take the value of $C_{max}$, so eventually, all of the approximation
ratios will reach one, making them independent of the number of edges. The
negative correlation in the change in approximation ratios can be explained as
follows. As previously mentioned, denser graphs have high $\langle C\rangle$,
and thus tend to have good approximation ratios. Hence, there is less room for
improvement, whereas sparser graphs have more. We expect that for a fixed
$n\geq 6$, $\Delta$ will approach zero as the number of iterations increases,
based on Fig. 2(d). The correlation is determined by the values of $\Delta$
and the fluctuations in $\Delta$ between graphs with various numbers of edges.
When $\Delta$ becomes small, the fluctuations between graphs overwhelm the
typical variations in $\Delta$ with the number of edges, so the correlation
tends to zero.

Figure 3: The correlation coefficients of number of edges with clique number
and number of minimal odd cycles.

Since the edge density, clique number, and number of minimal odd cycles are
correlated for small $n$, as seen in Fig. 3, it is no surprise that they have
strong correlations with the same QAOA metrics. Refer to Tables 4-7 to view
their correlation coefficients. The properties become less correlated as $n$
increases so it is unclear if the properties will have similar $r$ values for
higher vertex graphs. The properties may need separate analyses for larger
graphs. It could be that even though the properties become less correlated
with each other, they remain highly correlated with some of the QAOA metrics.

(a) Correlation with $\langle C\rangle$

(b) Correlation with $P(C_{max})$

(c) Correlation with $\frac{\langle C\rangle_{p}}{C_{max}}$

(d) Correlation with $\frac{\langle C\rangle_{p}-\langle
C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$

Figure 4: The correlations between the diameter for each $n$ vertex graph and
each of the QAOA metrics for $p$. Figure 5: The correlation coefficients
between diameter and number of cut vertices for graphs on $n$ vertices.

In summary, the highest correlation between edges and the QAOA metrics is with
$\langle C\rangle$. Thus, if a high expected value is the desired metric for
success, graphs that are dense are optimal for QAOA. Edge density does not
appear to have a large impact on $P(C_{max})$ and the approximation ratio,
however simulations of larger graphs are needed to determine if the
correlations between edges and these metrics tends towards a limit between
zero and negative one, or instead continues towards it. If the limit
approaches negative one, then graphs with low edge density may yield higher
probabilities of measuring an optimal solution or obtaining a high
approximation ratio.

###  II.2 Diameter and number of cut vertices

For the most part, the diameter of a graph, $d$, correlates negatively with
the QAOA metrics, but the correlation becomes less negative as $n$ increases,
which is the reverse of the correlations with the number of edges. The
correlation is particularly strong with $\langle C\rangle$ for low values of
$p$, as seen in Fig. 4(a). This is not unexpected as diameter is negatively
correlated with edge density. As seen in Fig. 4(b), the correlation between
diameter and probability of measuring an optimal state is stronger for smaller
$n$, and tends to approach zero for fixed $n$ as $p$ increases. Similarly to
the probability, the correlation between $d$ and the approximation ratio is
stronger for smaller $n$, and tends to approach zero for fixed $n$ as $p$
increases, as does the correlation between $d$ and the $\Delta$ ratio. This is
seen in Figs. 4(c) and 4(d).

The number of cut vertices, like the diameter, correlates negatively with QAOA
metrics, which makes sense as the two properties are positively correlated, as
seen in Fig. 5, however the correlation weakens as $n$ increases. Thus, the
two quantities may not correlate similarly with all of the QAOA metrics for
larger $n$. See Tables 4-7 to see how the correlation coefficients compare
between diameter and number of cut vertices.

As $n$ increases, the correlation coefficient between diameter and $\langle
C\rangle$ decreases as $p$ increases, while the other metrics tend to
increase, as seen in Fig. 4. In fact, the correlation with the other metrics
approaches zero for high $n$ and $p$. If these trends continue for $n\geq 9$,
it would imply that diameter is not indicative of the success QAOA has when
solving a MaxCut problem.

(a) Correlation with $\langle C\rangle$

(b) Correlation with $P(C_{max})$

(c) Correlation with $\frac{\langle C\rangle_{p}}{C_{max}}$

(d) Correlation with $\frac{\langle C\rangle_{p}-\langle
C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$

Figure 6: The correlations between the number of orbits for each $n$ vertex
graph and each of the QAOA metrics for $p$.

###  II.3 Group Size

The group size of a graph tends to have high positive correlations with all
QAOA properties for small $n$. However as $n$ increases, the correlations tend
to zero. A zero correlation, however, might not indicate that the two are
unrelated in this case. The size of the symmetry groups range from $1$ to
$2^{n}$ for all graphs on $n$ vertices. Correlations are intended to measure
linear relationships, so using data that is scaled exponentially on $n$ could
“wash out” the correlations. Instead of group size, we look at the number or
orbits to better investigate the relationship between symmetry and QAOA
performance.

###  II.4 Number of orbits

An automorphism of a graph is a relabeling of vertices that preserves edges,
and therefore is a type of symmetry. An orbit of a vertex $v$ is the set of
vertices with which $v$ can be swapped in an automorphism. Thus, if there are
two vertices in the same orbit but in different sets of an optimal MaxCut
solution, there is a possibility that they can be swapped to give another
optimal solution. If there are fewer large orbits, there are more possible
symmetries than with many small orbits.

All vertices in the same orbit have the same degree, else the edges cannot be
preserved. If there are more orbits, there are fewer symmetries, as there are
fewer potential vertex mappings that preserve edges. It is not obvious why
fewer orbits tends to produce better expected values and better approximation
ratios. In Figs. 6(a), 6(b), 6(c), and 6(d), we see that, upon discarding
$n=4$, the correlation coefficient between number of orbits and the QAOA
metrics tends to increase as $n$ increases. Additionally, the correlation
coefficient with the approximation ratio becomes more negative as $p$
increases. Hence, graphs with small group sizes and larger orbits should
achieve higher approximation ratios after several iterations of QAOA. Thus,
group size and symmetry should play an important role in the quality of
solution, which has been noted by Shaydulin, Hadfield, Hogg, and Safro
shaydulin2020symmetry .

###  II.5 Bipartite

Since there are so few bipartite graphs compared to non-bipartite for fixed
$n$, looking at the average of each QAOA metric offers more insight into how a
graph being bipartite affects the quality of QAOA solution. The average for
all QAOA metrics are lower for bipartite graphs than non-bipartite when $p=1$
for fixed $n$, however, the probability and change in approximation ratio are
higher for bipartite graphs for larger $p$ as seen in Table 8 and Figure 7.
Depending on the preferred metric of success, bipartite graphs either perform
worse than non-bipartite, as in the case for the approximation ratio and
$\langle C\rangle$, or better, as in the case of probability of measuring an
optimal solution or $\Delta$ ratio. The average $\Delta$ ratio being higher
for bipartite graphs suggests that a low approximation ratio at $p=1$ does not
imply that the approximation ratio at larger iterations cannot surpass those
of non-bipartite graphs. The fact that the approximation ratio tends to be
lower for bipartite graphs agrees with previous literature
farhi2020quantumwholegraph . In fact, Wurtz and Love conjecture that for $p$
iterations of QAOA on any graph, the approximation ratio of an $n$ vertex
graph is lower when there are no odd cycles of length at most $2p+1$ than
graphs that have length at most $2p+1$ wurtz2020bounds .

Figure 7: The fraction of eight vertex bipartite and non-bipartite graphs with
a given probability of finding an optimal solution for $p=3$.

###  II.6 Eulerian

Figure 8: The fraction of eight vertex Eulerian and non-Eulerian graphs with a
given probability of finding an optimal solution for $p=3$.

There are so few Eulerian graphs in the data set that the correlation
coefficients are not particularly helpful, however plotting the performance of
Eulerian graphs makes the relationship between them and the QAOA metrics more
evident. As seen in Table 9, the average maximum probability, level $p$
approximation ratio, and $\Delta$ ratios are significantly higher for Eulerian
graphs than for non-Eulerian for most $n$ and $p$, while the averages are
comparable for the expected value of $C$. Figure 8 shows a histogram of the
number of Eulerian and non-Eulerian graphs on eight vertices and the
probability of obtaining an optimal solution. As seen in the histogram, for
any given graph, the probability of measuring an optimal MaxCut solution is
higher for Eulerian graphs than non-Eulerian.

###  II.7 Distance regular

Similarly to Eulerian graphs, distance regularity does not appear to have a
strong correlation with any of the QAOA metrics because there are so few
distance regular graphs compared to non-distance regular ones, so we do not
make a chart of the correlations. In particular, there are only ten distance
regular graphs on fewer than seven vertices. We also do not make a histogram
with the probabilities as we did for Eulerian and bipartite graphs because the
average probability of measuring an optimal solution for only a handful of
distance regular graphs cannot be compared as well to the average probability
of thousands of non-distance regular graphs. However, graphs with
$n\in\\{4,5\\}$ vertices that are distance regular have a probability of one
of obtaining the optimal solution when $p=2$. These graphs in particular are
$C_{4}$, $K_{4}$, $C_{5}$ and $K_{5}$, where $C_{n}$ denotes the cycle on $n$
vertices and $K_{m}$ denotes the complete graph on $m$ vertices. These are the
only distance regular graphs on four or five vertices, up to isomorphism.
Interestingly enough, when $n=7$, both distance regular graphs, $C_{7}$ and
$K_{7}$ obtain a probability of one of being in the optimal state when $p=3$,
however, this is not the case for $n=6$. When $n=6$, three of the four
distance regular graphs have a probability greater than $0.99$ of giving the
correct solution, however the complete bipartite graph with partitions both
containing three vertices ($K_{3,3}$) achieves a probability of $0.97$. This
is far higher than the average for arbitrary graphs with $n=6$ and $p=3$.
These results lead us to believe that distance regular graphs on $n$ vertices
achieve a high probability of obtaining the optimal solution when
$p\geq\lfloor\frac{n}{2}\rfloor$, however more testing and a rigorous
mathematical proof would be needed to confirm this.

##  III Conclusion

The quantum approximate optimization algorithm has been studied in detail for
the MaxCut problem on graphs with rigid structures including degree regularity
and whether or not a graph is bipartite farhi2014quantum ;
brandao2018concentration ; Medvidovic2020QAOA54qubit ; zhou2018quantum . While
the studies give insight into how the algorithm works, examining graphs with
specific structures excludes the vast majority of graphs. Thus, we looked at
properties of all connected graphs on at most eight vertices and found the
correlation between different graph properties and the probability of finding
an optimal solution, the expected value of $C$, the level $p$ approximation
ratio, and the change in ratio from $p-1$ to $p$ for $p$ at most three.

There are two metrics that strongly correspond with the graph properties
studied, namely $\langle C\rangle$ and $P(C_{max})$. Graphs that have a lot of
edges have a high positive correlation with with $\langle C\rangle$. Diameter,
clique size, number of cut vertices, and number of small odd cycles also
correlate with $\langle C\rangle$, either positively or negatively. This is
expected because these properties correlate positively or negatively with the
number of edges for small $n$. Trends in the data for fixed $n$ and increasing
$p$ are summarized in Table 2. The probability of measuring the optimal
solution, expected value of $C$, and optimal angles were taken from QAOABFGS ;
lotshawdataset .

Bipartite, Eulerian, and distance regular graphs tend to have higher
probabilities of measuring the optimal solution than graphs that do not have
any of these properties. For bipartite, this occurs for $p\geq 2$. Previous
work shows that the approximation ratio for bipartite graphs tends to be worse
than non-bipartite farhi2020quantumwholegraph , so depending on the metric of
success, bipartite graphs may or may not be suitable graphs for testing.
Similarly, for larger $p$, Eulerian and distance regular graphs tend to have
higher probabilities of measuring the optimal solution than non-Eulerian and
non-distance regular graphs. Thus, we expect that QAOA for MaxCut on highly
symmetric graphs, which are those with larger orbits, bipartite, Eulerian, and
distance regular graphs will have a relatively high probability of measuring
the optimal solution. Table 3 gives a summary of the average correlation
coefficient over all $p\geq 1$ for each graph property and each QAOA metric on
graphs with eight vertices.

Graph Property | $\langle C\rangle$ | $P(C_{max})$ | $\frac{\langle C\rangle_{p}}{C_{max}}$ | $\frac{\langle C\rangle_{p}-\langle C\rangle_{p-1}}{C_{max}-\langle C\rangle_{p-1}}$
---|---|---|---|---
Edges | + | - | + | -
Diameter | - |  | - |
Clique number | + | - | + | -
Bipartite | + |  | + |
Eulerian |  | - |  | -
Distance regular |  |  |  |
Number of cut vertices | - |  |  |
Number of minimal odd cycles | + | - | + | -
Group size |  |  |  |
Number of orbits | - | - |  |
Table 3: A summary of graph properties and average correlation coefficient
over all $p\geq 1$ to QAOA metrics for $n=8$. A “$+$” means a strong positive
average coefficient, “$-$” represents a strong average negative correlation
coefficient, and an empty space means the average correlation coefficient is
in the interval $(-.1,.1)$, which is not significant.

Additionally, we created a dataset containing the graphs and their properties.
The dataset information is located in Appendix B. For future work, a similar
data set for other problems, such as maximum independent set or problems with
low circuit depth Herrman2020depth  would be useful to create benchmarks for
experiments on NISQ devices. Other avenues of future work include using
machine learning to determine if MaxCut on a graph will have a high
probability of measuring the optimal solution after $p$ rounds of QAOA.
Mathematically proving if QAOA for MaxCut on distance regular graphs with $n$
vertices gives better solutions than non distance regular graphs after
$\lfloor\frac{n}{2}\rfloor$ iterations would be of interest, as well.

## Acknowledgements

The authors would like to thank Ryan Bennink for his helpful comments on early
drafts of this manuscript.

This work was supported by DARPA ONISQ program under award W911NF-20-2-0051.
J. Ostrowski acknowledges the Air Force Office of Scientific Research award,
AF-FA9550-19-1-0147. G. Siopsis acknowledges the Army Research Office award
W911NF-19-1-0397. J. Ostrowski and G. Siopsis acknowledge the National Science
Foundation award OMA-1937008.

This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-
AC05-00OR22725 with the U.S. Department of Energy. The United States
Government retains and the publisher, by accepting the article for
publication, acknowledges that the United States Government retains a non-
exclusive, paid-up, irrevocable, world-wide license to publish or reproduce
the published form of this manuscript, or allow others to do so, for United
States Government purposes. 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).

##  Appendix A Graph Theory Definitions

In this section, we define some of the less common graph theory terms that
appear in the paper.

######  Definition A.1 (Diameter).

The diameter of a graph $G=(V,E)$ is $\max_{u,v}d(u,v)$, where $d(u,v)$
denotes the distance between $u,v\in V$.

######  Definition A.2 (Distance).

The distance between two vertices, $u$ and $v$, of a graph $G=(V,E)$ is the
number of edges in the shortest path between $u$ and $v$.

######  Definition A.3 (Clique number).

The clique number of a graph is the size of the largest complete subgraph.

######  Definition A.4 (Bipartite).

A graph is bipartite if the vertices can be partitioned into two sets such
that all edges are incident to a vertex in both sets.

######  Definition A.5 (Eulerian cycle).

An Eulerian cycle is a cycle that uses all edges of a graph exactly once.

######  Definition A.6 (Eulerian).

A graph is Eulerian if it is connected and contains an Eulerian cycle.

######  Definition A.7 (Distance Regular).

A graph $G=(V,E)$ is distance regular if for any pair of vertices $x,y\in V$,
the number of vertices that are distance $i$ from $x$ equals the number of
vertices that are distance $i$ from $y$, for $i\in\\{1,2,...,d\\}$, where $d$
is the diameter of $G$.

######  Definition A.8 (Cut vertex).

A cut vertex of a connected graph is a vertex whose removal disconnects the
graph.

######  Definition A.9 (Graph Automorphism).

A graph automorphism is a relabeling of vertices that preserves the set of
edges. Mathematically, it is a map $\alpha:V\longrightarrow V$ such that
$ij\in E$ if and only if $\alpha(i)\alpha(j)\in E$.

######  Definition A.10 (Automorphism Group).

The set of all graph automorphisms of $G$ forms an automorphism group of $G$.

######  Definition A.11 (Group Size).

The group size of $G$ is the size of the automorphism group of $G$.

######  Definition A.12 (Orbit).

An orbit of a vertex $v$ is the set of all vertices $\alpha(v)$ where $\alpha$
is an automorphism of $G$.

##  Appendix B Database Details

The data generated from these studies are shared in a publicly-accessible
GitHub Repository to serve as a benchmark QAOA calculations and experiments.
This data set consists of csv files for each set of graphs on $n$ vertices for
$3\leq n\leq 8$. The generated graph entries, which populate each set, are
indexed by a graph number and include the following properties: bipartite
(boolean), number of edges, diameter, clique number, distance regular
(boolean), eulerian (boolean), list of cut vertices, number of cut vertices,
cycle basis, degree sequence, automorphism group generator, automorphism group
size, orbits, number of orbits, and the number of small cycles on 3 to $n$
vertices. In addition to the dataset, we have provided two options for storing
and sorting this data by desired graph properties. The first option is to
insert the data into a MySQL database structure. The user can then query the
database to select the desired data and insert new columns for additional
properties, calculations, and experimental results. We have provided scripts
for creating the database tables, populating the tables using the csv files,
querying the database, and inserting new columns. For additional information
on how to download and use MySQL, see the MySQL Documentation.To work with the
dataset directly, we have also included a python script which utilizes the
data analysis library $pandas$. Pandas is a library which allows the user to
store and manipulate data in 2-dimensional, labeled data structures called
DataFrames. We have provided a python script which allows the user to import
the csv data into pandas DataFrames and create new DataFrames with the desired
graph properties. For more information on how to use and install pandas, see
the Pandas Documentation. Both MySQL and Pandas are free, open-source software
packages. This data set, the MySQL Scripts, and python script can be accessed
through the QAOA Small Graph GitHub Repository.

##  Appendix C Data Tables

In this section, we include the tables containing all correlations between
different graph properties and metrics. For the boolean properties, we assign
“1” to TRUE and “0” to FALSE.

$n:p$ | Edges | Diam. | Clique num. | Bipartite | Eulerian | Dist. reg. | Num. cut vertices | Num. min. odd cycles | Grp. size | Num. orbits
---|---|---|---|---|---|---|---|---|---|---
4:0 | -.781 | .577 | -.894 | -1 | -.447 | 0 | .447 | -.866 | -.307 | -.243
4:1 | .363 | -.535 | .558 | .398 | .030 | .437 | -.085 | .346 | .507 | .015
4:2 | .561 | -.830 | .421 | .247 | -.512 | .809 | -.769 | .354 | .663 | -.513
4:3 | .462 | -.786 | .386 | .410 | -.222 | .352 | -.772 | .355 | .359 | -.121
5:0 | .505 | -.287 | .444 | -.141 | -.214 | .450 | -.152 | .479 | .767 | -.417
5:1 | .166 | -.387 | .243 | .238 | -.662 | .661 | -.110 | .217 | .531 | -.619
5:2 | .018 | -.339 | -.016 | .047 | -.447 | .441 | -.128 | .004 | .411 | -.675
5:3 | .071 | -.233 | .040 | -.027 | -.371 | .277 | -.127 | .056 | .296 | -.619
6:0 | .300 | -.177 | .209 | -.027 | -.371 | .155 | -.147 | .301 | .191 | -.271
6:1 | -.016 | -.170 | .043 | .112 | -.301 | .222 | .011 | .012 | .232 | -.221
6:2 | -.094 | -.183 | -.123 | -.069 | -.281 | .252 | .011 | -.148 | .272 | -.324
6:3 | -.059 | -.131 | -.126 | -.153 | -.271 | .263 | -.031 | -.147 | .209 | -.441
7:0 | .297 | -.189 | .287 | .007 | -.220 | .015 | -.133 | .326 | .043 | -.208
7:1 | -.110 | -.027 | -.037 | .050 | -.354 | .216 | .052 | -.058 | .202 | -.224
7:2 | -.140 | -.012 | -.167 | -.058 | -.298 | .150 | .053 | -.158 | .148 | -.309
7:3 | -.145 | .024 | -.207 | -.100 | -.252 | .101 | .066 | -.201 | .104 | -.344
8:0 | .256 | -.192 | .239 | .028 | -.131 | .003 | -.115 | .286 | .015 | -.045
8:1 | -.198 | .056 | -.124 | .009 | -.198 | .029 | .067 | -.158 | .056 | -.101
8:2 | -.194 | .062 | -.210 | -.061 | -.191 | .047 | .066 | -.223 | .057 | -.178
8:3 | -.201 | .094 | -.237 | -.092 | -.169 | .046 | .078 | -.258 | .040 | -.214
Table 4: The Pearson product moment correlation between the probability of getting an optimal solution with $p$ iterations of QAOA on an $n$ vertex graph with the graph properties in columns two through eleven. $n:p$ | Edges | Diam. | Clique num. | Bipartite | Eulerian | Dist. reg. | Num. cut vertices | Num. min. odd cycles | Grp. size | Num. orbits
---|---|---|---|---|---|---|---|---|---|---
4:0 | 1 | -.812 | .908 | .781 | .070 | .552 | -.768 | .947 | .746 | -.417
4:1 | .983 | -.786 | .824 | .672 | -.101 | .669 | -.819 | .876 | .761 | -.548
4:2 | .799 | -.639 | .479 | .355 | -.481 | .761 | -.920 | .583 | .608 | -.725
4:3 | .783 | -.586 | .450 | .338 | -.448 | .709 | -.901 | .579 | .572 | -.725
5:0 | 1 | -.673 | .845 | .558 | -.247 | .267 | -.691 | .951 | .527 | -.424
5:1 | .989 | -.671 | .774 | .495 | -.255 | .305 | -.739 | .908 | .527 | -.464
5:2 | .889 | -.641 | .571 | .256 | -.118 | .180 | -.781 | .730 | .456 | -.463
5:3 | .844 | -.564 | .514 | .234 | -.087 | .072 | -.757 | .679 | .353 | -.369
6:0 | 1 | -.673 | .768 | .466 | -.052 | .189 | -.684 | .933 | .323 | -.277
6:1 | .991 | -.676 | .697 | .401 | -.073 | .221 | -.729 | .886 | .319 | -.305
6:2 | .926 | -.662 | .544 | .250 | -.087 | .256 | -.750 | .749 | .312 | -.351
6:3 | .875 | -.618 | .468 | .178 | -.098 | .264 | -.747 | .676 | .274 | -.372
7:0 | 1 | -.683 | .722 | .329 | -.079 | .056 | -.655 | .924 | .147 | -.225
7:1 | .994 | -.695 | .663 | .295 | -.081 | .057 | -.698 | .884 | .142 | -.227
7:2 | .953 | -.684 | .558 | .214 | -.074 | .044 | -.711 | .790 | .132 | -.245
7:3 | .916 | -.651 | .500 | .169 | -.067 | .030 | -.697 | .731 | .116 | -.252
8:0 | 1 | -.691 | .682 | .222 | -.021 | .024 | -.603 | .913 | .050 | -.123
8:1 | .995 | -.707 | .629 | .203 | -.024 | .028 | -.646 | .876 | .048 | -.117
8:2 | .967 | -.698 | .550 | .158 | -.026 | .034 | -.652 | .803 | .046 | -.136
8:3 | .936 | -.671 | .507 | .125 | -.028 | .040 | -.640 | .752 | .042 | -.153
Table 5: The Pearson product moment correlation between $\langle C\rangle_{p}$ for an $n$ vertex graph with the graph properties in columns two through eleven. $n:p$ | Edges | Diam. | Clique num. | Bipartite | Eulerian | Dist. reg. | Num. cut vertices | Num. min. odd cycles | Grp. size | Num. orbits
---|---|---|---|---|---|---|---|---|---|---
4:0 | .857 | -.740 | .988 | .926 | .414 | .252 | -.446 | .926 | .602 | .017
4:1 | .635 | -.576 | .886 | .819 | .515 | .125 | -.133 | .753 | .491 | .206
4:2 | .747 | -.800 | .552 | .440 | -.512 | .810 | -.882 | .525 | .630 | -.520
4:3 | .466 | -.785 | .389 | .416 | -.219 | .347 | -.777 | .360 | .356 | -.119
5:0 | .770 | -.592 | .856 | .744 | -.414 | .389 | -.397 | .849 | .499 | -.421
5:1 | .428 | -.400 | .569 | .599 | -.510 | .549 | -.164 | .546 | .421 | -.463
5:2 | .125 | -.390 | .152 | .091 | -.335 | .483 | -.154 | .147 | .424 | -.648
5:3 | .138 | -.350 | .103 | .060 | -.373 | .318 | -.206 | .116 | .329 | -.666
6:0 | .720 | -.530 | .800 | .681 | -.040 | .061 | -.350 | .822 | .246 | -.116
6:1 | .374 | -.314 | .539 | .541 | -.066 | .051 | -.103 | .515 | .192 | -.071
6:2 | .166 | -.300 | .218 | .234 | -.133 | .140 | -.050 | .193 | .258 | -.212
6:3 | .042 | -.231 | -.035 | -.057 | -.256 | .298 | -.099 | -.033 | .234 | -.420
7:0 | .687 | -.489 | .727 | .494 | -.120 | .074 | -.337 | .794 | .127 | -.158
7:1 | .315 | -.258 | .442 | .387 | -.140 | .112 | -.113 | .462 | .107 | -.116
7:2 | .143 | -.210 | .182 | .207 | -.164 | .134 | -.063 | .206 | .130 | -.202
7:3 | .035 | -.128 | -.015 | .028 | -.182 | .117 | -.023 | .010 | .112 | -.305
8:0 | .671 | -.469 | .666 | .347 | -.032 | -.007 | -.314 | .778 | .039 | -.034
8:1 | .299 | -.247 | .383 | .276 | -.042 | -.009 | -.129 | .443 | .031 | .024
8:2 | .157 | -.197 | .163 | .175 | -.063 | .004 | -.082 | .227 | .037 | -.015
8:3 | .051 | -.115 | -.002 | .043 | -.090 | .031 | -.037 | .043 | .039 | -.107
Table 6: The Pearson product moment correlation between the level $p$ approximation ratio on an $n$ vertex graph with the graph properties in columns two through eleven. $n:p$ | Edges | Diam. | Clique num. | Bipartite | Eulerian | Dist. reg. | Num. cut vertices | Num. min. odd cycles | Grp. size | Num. orbits
---|---|---|---|---|---|---|---|---|---|---
4:1 | .295 | -.362 | .619 | .513 | .451 | .079 | .192 | .418 | .368 | .288
4:2 | .701 | -.766 | .412 | .192 | -.567 | .897 | -.901 | .465 | .742 | -.809
4:3 | .362 | -.979 | .483 | .483 | NA | NA | -.682 | .362 | .511 | .422
5:1 | .175 | -.276 | .305 | .306 | -.612 | .645 | -.001 | .271 | .487 | -.495
5:2 | .015 | -.347 | -.045 | -.140 | -.490 | .571 | -.140 | -.011 | .507 | -.710
5:3 | .204 | -.251 | .177 | .095 | -.423 | NA | -.114 | .158 | .700 | -.623
6:1 | -.045 | -.053 | .139 | .209 | -.110 | .112 | .149 | .077 | .200 | -.078
6:2 | -.153 | -.124 | -.240 | -.203 | -.228 | .310 | .045 | -.252 | .395 | -.318
6:3 | -.003 | -.152 | -.139 | -.206 | -.393 | .438 | -.099 | -.119 | .337 | -.545
7:1 | -.157 | .045 | .018 | .122 | -.182 | .180 | .148 | -.025 | .160 | -.090
7:2 | -.235 | .012 | -.324 | -.146 | -.244 | .226 | .080 | -.315 | .235 | -.237
7:3 | -.114 | .029 | -.210 | -.159 | -.308 | .211 | .069 | -.208 | .176 | -.392
8:1 | -.237 | .090 | -.078 | .078 | -.057 | .007 | .124 | -.104 | .041 | .053
8:2 | -.259 | .048 | -.389 | -.091 | -.102 | .045 | .077 | -.361 | .079 | -.077
8:3 | -.187 | .107 | -.279 | -.159 | -.166 | .082 | .088 | -.302 | .083 | -.226
Table 7: The Pearson product moment correlation between the $\Delta$ ratio at $p$ on an $n$ vertex graph with the graph properties in columns two through eleven. $n:p$ |  B. $P(C_{max})$ |  N.B. $P(C_{max})$ |  B. $\langle C\rangle$ |  N.B.$\langle C\rangle$ |  B. Level $p$ A.R. |  N.B. Level $p$ A.R. |  B. $\Delta$ ratio $p-1$ to $p$ |  N.B. $\Delta$ ratio $p-1$ to $p$
---|---|---|---|---|---|---|---|---
4:0 | .125 | .0625 | 1.667 | 2.5 | .5 | .681 | NA | NA
4:1 | .481 | .602 | 2.566 | 3.216 | .772 | .879 | .544 | .634
4:2 | .889 | .928 | 3.180 | 3.586 | .949 | .978 | .762 | .825
4:3 | .993 | .999 | 3.326 | 3.666 | .998 | 1.000 | .973 | .994
5:0 | .0625 | .049 | 2.3 | 3.344 | .5 | .658 | NA | NA
5:1 | .368 | .495 | 3.436 | 4.323 | .750 | .857 | .500 | .605
5:2 | .746 | .725 | 4.222 | 4.685 | .918 | .928 | .661 | .587
5:3 | .907 | .900 | 4.470 | 4.926 | .970 | .974 | .731 | .744
6:0 | .031 | .028 | 3.118 | 4.447 | 0.500 | 0.644 | NA | NA
6:1 | .260 | .311 | 4.542 | 5.672 | .733 | .826 | .465 | .522
6:2 | .586 | .549 | 5.449 | 6.179 | .873 | .900 | .519 | .442
6:3 | .818 | .744 | 5.949 | 6.506 | .951 | .946 | .620 | .511
7:0 | .016 | .016 | 3.875 | 5.693 | .067 | .074 | NA | NA
7:1 | .182 | .213 | 5.554 | 7.187 | .438 | .482 | .182 | .213
7:2 | .469 | .424 | 6.598 | 7.827 | .851 | .886 | .464 | .396
7:3 | .691 | .605 | 7.201 | 8.225 | .927 | .930 | .519 | .409
8:0 | .008 | .011 | 4.797 | 7.246 | .5 | .646 | NA | NA
8:1 | .133 | .139 | 6.773 | 9.022 | .710 | .808 | .420 | .462
8:2 | .385 | .317 | 7.983 | 9.801 | .832 | .877 | .420 | .367
8:3 | .606 | .482 | 8.762 | 10.273 | .911 | .920 | .467 | .350
Table 8: The average value of bipartite graphs versus non-bipartite graphs, where the columns beginning with “B.” refer to bipartite graphs, and those with “N.B.” refer to non-bipartite graphs. The abbreviation “A.R.’ stands for the approximation ratio. Three vertex graphs are excluded since there is one bipartite three vertex graph and one non-bipartite. $n:p$ |  E. $P(C_{max})$ |  N.E. $P(C_{max})$ |  E. $\langle C\rangle$ |  N.E.$\langle C\rangle$ |  E. Level $p$ A.R. |  N.E. Level $p$ A.R. |  E. $\Delta$ ratio $p-1$ to $p$ |  N.E. $\Delta$ ratio $p-1$ to $p$
---|---|---|---|---|---|---|---|---
4:0 | .125 | .088 | 2 | 2.1 | .5 | .608 | NA | NA
4:1 | .531 | .543 | 3.000 | 2.869 | .75 | .841 | .5 | .607
4:2 | 1 | .890 | 4 | 3.260 | 1 | .956 | 1 | .752
4:3 | 1 | .995 | 4 | 3.395 | 1 | .998 | 1 | .980
5:0 | .070 | .048 | 3.5 | 3 | .698 | .602 | NA | NA
5:1 | .775 | .392 | 4.513 | 4.017 | .912 | .813 | .764 | .537
5:2 | .913 | .687 | 4.762 | 4.531 | .960 | .918 | .831 | .551
5:3 | .990 | .881 | 4.965 | 4.782 | .994 | .968 | .963 | .689
6:0 | .078 | .025 | 4.438 | 4.231 | .633 | .621 | NA | NA
6:1 | .481 | .290 | 5.766 | 5.480 | .827 | .811 | .552 | .510
6:2 | .749 | .539 | 6.397 | 6.043 | .915 | .894 | .566 | .445
6:3 | .925 | .742 | 6.816 | 6.391 | .976 | .945 | .796 | .507
7:0 | .041 | .015 | 6.054 | 5.578 | .075 | .074 | NA | NA
7:1 | .431 | .201 | 7.570 | 7.081 | .843 | .807 | .569 | .475
7:2 | .666 | .415 | 8.203 | 7.744 | .912 | .883 | .518 | .394
7:3 | .833 | .600 | 8.597 | 8.153 | .955 | .929 | .609 | .406
8:0 | .027 | .011 | 7.438 | 7.202 | .656 | .643 | NA | NA
8:1 | .276 | .137 | 9.245 | 8.981 | .820 | .806 | .491 | .461
8:2 | .525 | .315 | 10.067 | 9.766 | .893 | .876 | .426 | .366
8:3 | .708 | .480 | 10.580 | 10.242 | .937 | .919 | .472 | .350
Table 9: The average value of Eulerian graphs versus non-Eulerian graphs,
where the columns beginning with “E.” refer to Eulerian graphs, and those with
“N.E.” refer to non-Eulerian graphs. The abbreviation “A.R.” stands for the
approximation ratio. Three vertex graphs are excluded since there is one
Eulerian three vertex graph and one non-Eulerian. The entries for Eulerian
$4:3$ are are the same as Eulerian $4:2$ since the only Eulerian graph on four
vertices achieves its maximum values after two iterations.

## References

  * [1] Sergey Bravyi, David Gosset, and Robert König.  Quantum advantage with shallow circuits.  Science, 362(6412):308–311, 2018.
  * [2] Diego Riste, Marcus P da Silva, Colm A Ryan, Andrew W Cross, Antonio D Córcoles, John A Smolin, Jay M Gambetta, Jerry M Chow, and Blake R Johnson.  Demonstration of quantum advantage in machine learning.  npj Quantum Information, 3(1):1–5, 2017.
  * [3] Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.  A quantum approximate optimization algorithm.  arXiv preprint arXiv:1411.4028, 2014.
  * [4] Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli, et al.  Integer programming, volume 271.  Springer, 2014.
  * [5] Paola Festa, Panos M Pardalos, Mauricio GC Resende, and Celso C Ribeiro.  Randomized heuristics for the MAX-CUT problem.  Optimization methods and software, 17(6):1033–1058, 2002.
  * [6] Michel X Goemans and David P Williamson.  . 879-approximation algorithms for max cut and max 2sat.  In Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, pages 422–431, 1994.
  * [7] Fernando G. S. L. Brandão, Michael Broughton, Edward Farhi, Sam Gutmann, and Hartmut Neven.  For fixed control parameters the quantum approximate optimization algorithm’s objective function value concentrates for typical instances.  arXiv preprint arXiv:1812.04170, 2018.
  * [8] Matija Medvidović and Giuseppe Carleo.  Classical variational simulation of the quantum approximate optimization algorithm.  arXiv preprint arXiv:2009:01760v1, 2020.
  * [9] Leo Zhou, Sheng-Tao Wang, Soonwon Choi, Hannes Pichler, and Mikhail D Lukin.  Quantum approximate optimization algorithm: performance, mechanism, and implementation on near-term devices.  arXiv preprint arXiv:1812.01041, 2018.
  * [10] V Akshay, H Philathong, I Zacharov, and J Biamonte.  Reachability deficits implicit in google’s quantum approximate optimization of graph problems.  arXiv preprint arXiv:2007.09148, 2020.
  * [11] Edward Farhi, David Gamarnik, and Sam Gutmann.  The quantum approximate optimization algorithm needs to see the whole graph: Worst case examples.  arXiv preprint arXiv:2005.08747, 2020.
  * [12] Edward Farhi, David Gamarnik, and Sam Gutmann.  The quantum approximate optimization algorithm needs to see the whole graph: A typical case.  arXiv preprint arXiv:2004.09002, 2020.
  * [13] Asier Ozaeta, Wim van Dam, and Peter L McMahon.  Expectation values from the single-layer quantum approximate optimization algorithm on ising problems.  arXiv preprint arXiv:2012.03421, 2020.
  * [14] Phillip C. Lotshaw, Travis S. Humble, Rebekah Herrman, and James Ostrowski.  Empirical performance bounds for quantum approximate optimization.  (in preparation, 2021).
  * [15] Phillip C. Lotshaw and Travis S. Humble.  QAOA dataset.  Found at https://code.ornl.gov/qci/qaoa-dataset-version1.
  * [16] Pietro Belotti.  Couenne: a user’s manual.  Technical report, Technical report, Lehigh University, 2009.
  * [17] William H. Press, Brian P. Flannery, and Saul A. Teukolsky.  Numerical Recipes in Fortran 77: The Art of Scientific Computing.  Cambridge University Press, second edition, 1993.  https://people.sc.fsu.edu/ inavon/5420a/DFP.pdf.
  * [18] Brendan McKay.  Graphs [data set].  Found at http://users.cecs.anu.edu.au/ bdm/data/graphs.html.
  * [19] Ruslan Shaydulin, Stuart Hadfield, Tad Hogg, and Ilya Safro.  Classical symmetries and QAOA.  arXiv preprint arXiv:2012.04713, 2020.
  * [20] Jonathan Wurtz and Peter J Love.  Bounds on MAXCUT QAOA performance for p$>$ 1\.  arXiv preprint arXiv:2010.11209, 2020.
  * [21] Rebekah Herrman, James Ostrowski, Travis S. Humble, and George Siopsis.  Lower bounds on circuit depth of the quantum approximate optimization algorithm.  Quantum Information Processing, 20(59), 2021.