# More on greedy construction heuristics for the MAX-CUT problem

Jianan Wang  Chuixiong Wu  Fen Zuo111Email<EMAIL_ADDRESS>Hefei MiQro
Era Digital Technology Co. Ltd., Hefei, China

###### Abstract

A cut of a graph can be represented in many different ways. Here we propose to
represent a cut through a “relation tree”, which is a spanning tree with
signed edges. We show that this picture helps to classify the main greedy
heuristics for the maximum cut problem, in analogy with the minimum spanning
tree problem. Namely, all versions of the Sahni-Gonzalez (SG) algorithms could
be classified as the Prim class, while various Edge-Contraction (EC)
algorithms are of the Kruskal class. We further elucidate the relation of this
framework to the stabilizer formalism in quantum computing, and point out that
the recently proposed ADAPT-Clifford algorithm is a reformulation of a refined
version of the SG algorithm, SG3. Numerical performance of the typical
algorithms from the two classes are studied with various kinds of graphs. It
turns out that, the Prim-class algorithms perform better for general dense
graphs, and the Kruskal-class algorithms performs better when the graphs are
sparse enough.

###### Contents

  1. I Introduction
  2. II Relation Tree
  3. III Tree Algorithms
    1. III.1 Prim class
      1. III.1.1 Approximation Ratio
    2. III.2 Kruskal class
      1. III.2.1 Approximation Ratio
  4. IV Stabilizer Formalism
    1. IV.1 From Bit to Qubit
    2. IV.2 Stabilizer States
    3. IV.3 SEC revisited
      1. IV.3.1 Approximation Ratio
    4. IV.4 SG revisited
    5. IV.5 ADAPT-Clifford
  5. V Numerical Performance
    1. V.1 Complete graphs
      1. V.1.1 Positive weights
      2. V.1.2 Signed weights: the Sherrington-Kirkpatrick model
    2. V.2 Sparse graphs
      1. V.2.1 $k$-regular graphs
      2. V.2.2 Erdös-Rényi graphs
  6. VI Summary

##  I Introduction

Finding the maximum-weight cut for a weighted undirected graph, MAX-CUT for
short, is a celebrated NP-hard problem. This hardness persists even in the
unweighted case. Thus we have to turn to approximate algorithms. Up to now,
the best theoretical approximation ratio is provided by the Goemans-Williamson
(GW) algorithm GW-1995 , which is based on semi-definite programming (SDP).
However, as emphasized in Kahruman-2007 , the time and space requirements for
SDP approaches limit their applicability in practice. Therefore, development
of fast and simple heuristics would still be of practical importance.

There are two main classes of greedy construction heuristics for MAX-CUT: the
Sahni-Gonzalez (SG) approach and the Edge-Contraction (EC) approach. The
original SG algorithm was proposed in 1976 SG-1976 , which is perhaps the
first algorithm for MAX-CUT. While the original algorithm deals with the
vertices in a fixed order, some deliberate criterions for vertex-selecting
were made in Kahruman-2007 , which greatly improve the performance. Ref.
Kahruman-2007  also proposed a new construction heuristic: Edge Contraction.
This bears remarkable similarity to the random contraction algorithm for the
Minimum Cut problem (MIN-CUT) KS-1993 . While the original EC is a “worst-out”
approach, in ref. Hassin-2021  the corresponding “best-in” approach is
developed, and named “Differencing Edge Contraction” (DEC). More
interestingly, recently we find that these two could be unified into a single
“best-in-worst-out” algorithm SAIII , which could be properly named as “Signed
Edge Contraction” (SEC). Are these two kinds of heuristics related to each
other? One may think that the two are so different that no relation of any
kind could exist. However, we show in this paper that they could actually be
unified into a single framework. This is achieved by representing the cut with
a “relation tree”, then the SG and EC approaches are simply different ways to
generate the tree.

In fact, the concept of “relation tree” has already appeared in our
implementation of the SEC heuristic SAIII . Even more importantly, the SEC
heuristic is not developed by generalizing the EC and DEC approach, but from a
completely different way of thinking. It originates from a very disparate
area, quantum computing. More precisely, it is a manifestation of the
stabilizer formalism in graph theory. This is why SEC is originally called
“stabilizer heuristic”, and the relation tree called “stabilizer tree” in
SAIII . We elucidate the relation between the graph formulation and the
stabilizer formulation here. With this relation clarified, we then examine
another recently proposed algorithm based on the stabilizer formalism, ADAPT-
Clifford ADAPT-Clifford , and show that it is just a reformulation of a
refined version of SG.

In the remaining part we analyze the performance of these algorithms with
various graphs. These include complete graphs with positive weights or signed
weights, randomly generated (un)weighted $k$-regular graphs, and (un)weighted
Erdös-Rényi graphs $G(n,p)$. The results from the GW algorithm are taken as
references, when they are available. We are mainly interested in two
questions: when would these greedy algorithms be competitive to GW? and which
of them would perform best? In seeking the answers to these questions, we
discover some new features of these algorithms not noticed before.

The arrangement of the paper is as follows. In section II we introduce the
concept of a relation tree, and use this concept in section III to classify
the usual greedy algorithms for MAX-CUT. In section IV we introduce the
stabilizer formalism, and revisit the previous algorithms and the recently
proposed ADAPT-Clifford. The performance of these algorithms is analyzed in
section V in detail. In the final section we give a short summary.

##  II Relation Tree

Given an undirected weighted graph $G=(V,E,w)$, an edge set $C\subset E$ is
called a cut if for some $A\subset V$,

$C=\delta(A)\equiv\\{(i,j)\in E|i\in A,j\in V\setminus A\\}.$ (1)

So in order to specify the cut $C$, we just need to specify $A$. A common way
to do this is to use the characteristic vector $x$ of $A$. Let
$V=\\{1,...,n\\}$, then $x$ is an $n$-dimensional vector with its elements
taking binary values:

$\displaystyle x_{i}=1,$ $\displaystyle\text{if}\quad i\in A$ (2)
$\displaystyle x_{i}=0,$ $\displaystyle\text{otherwise}.$ (3)

Notice that $x$ and its negation $\neg x$ (with elements $1-x_{i}$) give rise
to the same cut. With this characterization, the weight of a cut $C$ can be
expressed as

$w(x)=\sum_{i,j}w_{ij}x_{i}(1-x_{j}).$ (4)

And the maximum cut problem requires to find a cut with the maximum cut
weight.

Of course the binary-valued vector is not the unique choice to represent the
cut. It has been known for a long time that MAX-CUT is equivalent to the Ising
model in physics BGJR-1988 . Ising model is naturally expressed with spin
values $z_{i}\in\\{-1,+1\\}$. Therefore, we could also use a spin-valued
vector to characterize the cut:

$\displaystyle z_{i}=-1,$ $\displaystyle\text{if}\quad i\in A$ (5)
$\displaystyle z_{i}=+1,$ $\displaystyle\text{otherwise}.$ (6)

That is, we could turn the vector $x$ into $z$ with the relation:

$z_{i}=1-2x_{i}.$ (7)

Then the negation of $x$, $\neg x$, corresponds to $-z$. Of course $-z$ also
represents the same cut as $z$. With the spin values, we may express the cut
weight as

$w(z)=\frac{1}{2}\sum_{i<j}w_{ij}(1-z_{i}z_{j}).$ (8)

Interestingly, the celebrated GW algorithm is based on a relaxation of this
expression GW-1995 . Moreover, the spin representation is very convenient to
distinguish the edges inside and outside the cut. We just need to evaluate the
product of the spin values of the vertices incident with the edge. The edge
$(i,j)\in E$ is in the cut if and only if $z_{i}z_{j}=-1$.

We could also reverse the process: in order to obtain all the spin values, we
could first seek the relations between them. The total number of relations is
certainly much larger than the number of vertices. For $n$ vertices we would
have in total $n(n-1)/2$ relations. But they are correlated; only $n-1$ of
them are independent. These must have support on the edges of a spanning tree.
Therefore we have the following definition:
Definition 1:
For an undirected graph $G=(V,E)$ with $|V|=n$, a relation tree $H=(V,T,s)$ is
a spanning tree $(V,T)$ of $K_{n}$ together with an assignment of relations on
its edges:

$s:T\to\\{-1,+1\\}.$ (9)

When the edge is assigned a “+1” value, we call it “positive”, and “negative”
otherwise. The definition looks a little weird: the relation tree needs not be
a spanning tree of $G$ itself. However, we could engineer it using the
information of $G$. It is not difficult to prove that such a relation tree
generates a unique cut. To explicitly obtain the cut, one could apply the
graph-scanning algorithm for $H$ SAIII . In order for the cut to be
nontrivial, the values $s$ should not be all positive. Notice that the
relation tree is different from the cut tree in the famous Gomory-Hu algorithm
GH-1961  for the Multi-terminal MIN-CUT problem. Also notice that the relation
on an edge should not be considered as a direction.

Let us give an example of this. For the following graph,

Figure 1: A weighted graph.

the maximum cut is given by $\\{1,4\\}$ and $\\{2,3,5\\}$. We may express such
a cut with the relation tree:

Figure 2: A relation tree of the graph in Fig. 1.

The relation tree gives a nice visualization of the cut. Of course such a tree
is not unique. A specific cut may be represented by many different but
equivalent relation trees.

##  III Tree Algorithms

So what is the usefulness of such a concept, a relation tree? Once the focus
is put on the relations trees, many nice properties of spanning trees could be
employed. In particular, we could use the wellknown algorithms for the minimum
spanning tree (MST) as a guide to classify the MAX-CUT algorithms. As we know,
MST has two celebrated algorithms: the Prim algorithm Prim-1957  and the
Kruskal algorithm Kruskal-1956 . Roughly speaking, Prim algorithm is vertex-
oriented, while Kruskal algorithm is edge-oriented. Accordingly, the MAX-CUT
algorithms based on the relation tree can also be decomposed into two classes:
the Prim class and the Kruskal class. We will discuss them one by one.

###  III.1 Prim class

For the sake of clarity, we give the pseudo-code of the original Prim
algorithm here:

Algorithm 1 Prim’s Algorithm for MST

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A minimum spanning tree $H=(V,T)$

Initialize $H=(V(H),T)$ as $(\\{r\\},\varnothing)$ with $r$ a randomly chosen
vertex

while $H$ is not a spanning tree do

Adding to $T$ a minimum-weight edge from $\delta(V(H))$.

end while

As we have mentioned, the essence of the Prim algorithm is vertex-orientation.
It starts with a vertex, and at each step adds a new vertex through a minimum-
weight edge. Meanwhile, $H$ is a tree from the beginning to the end. This
reminds us of the SG algorithm SG-1976 , which we rewrite here:

Algorithm 2 SG Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A partition $V=V_{1}\uplus V_{2}$ and the cut weight $w(V_{1},V_{2})$

Order the vertex set as $V=\\{1,2,...,n\\}$

Initialize $V_{1}=\\{1\\},V_{2}=\\{2\\}$

$w(V_{1},V_{2})\leftarrow w_{12}$

for $i=3:n$ do

$w(i,V_{1})=\sum_{(i,j)\in E,j\in V_{1}}w(i,j)$

$w(i,V_{2})=\sum_{(i,j)\in E,j\in V_{2}}w(i,j)$

if $w(i,V_{1})>w(i,V_{2})$ then

$V_{2}\leftarrow V_{2}\cup\\{i\\}$

else

$V_{1}\leftarrow V_{1}\cup\\{i\\}$

end if

$w(V_{1},V_{2})\leftarrow w(V_{1},V_{2})+\max\\{w(i,V_{1}),w(i,V_{2})\\}$

end for

Here the first two vertices are always assigned to different sets, because in
the original SG formulation all the weights are assumed to be non-negative. If
we allow the weights to be negative, such an assignment may not be proper. It
is not difficult to see that the SG algorithm is actually building a relation
tree step by step: first choose edge $(1,2)$ as a negative leaf, then connect
the other vertices to vertex $1$ or $2$ with positive edges. At each step, the
choice between vertex $1$ and $2$ is made to maximize the current cut weight.
For example, applying SG to Fig. 1, we get the following relation tree:

Figure 3: Relation tree obtained by applying SG to the graph in Fig. 1.

However, SG is not really a Prim-type algorithm: it is not as “greedy” as the
Prim algorithm! This is because in SG all the vertices are examined in a fixed
order, which makes it very efficient but maybe not so efficacious. Indeed, if
the graph has $m$ edges, the complexity of SG is $O(n+m)$ SG-1976 , which
could even be lower than that of the Prim algorithm, which is at best
$O(n^{2})$.

To make SG more Prim-like, we could discard the ordering of the vertices, and
add some criterion for the selection of the vertex at each step. For the
initial vertex, it seems that no vertex will have priority and we have to
randomly select one as the starting point. This is exactly what the Prim
algorithm begins with. Alternatively, one could eliminate the randomness by
choosing the maximum weighted edge first. Since this weight must be positive
(otherwise the problem would be easy to solve by reducing it to MIN-CUT), one
includes this edge in the cut. Warning here: this may not always be a good
initialization. As for the criterion of vertex-selecting in the next steps, we
have three different choices, namely “best-in”, “worst-out”, and “best-in-
worst-out”. Correspondingly, we have three modified versions of SG, SG1, SG2
and SG3 respectively Kahruman-2007 . See also Bian-2019  for some related
discussion. The pseudo-code of SG1 reads:

Algorithm 3 SG1 Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A partition $V=V_{1}\uplus V_{2}$ and the cut weight $w(V_{1},V_{2})$

Pick the maximum weighted edge $(i_{1},i_{2})$

$V_{1}\leftarrow\\{i_{1}\\},V_{2}\leftarrow\\{i_{2}\\}$

$w(V_{1},V_{2})\leftarrow w_{i_{1}i_{2}}$

$V^{\prime}\leftarrow V\setminus\\{i_{1},i_{2}\\}$

for $j=1:n-2$ do

for $i\in V^{\prime}$ do

$w(i,V_{1})=\sum_{(i,j)\in E,j\in V_{1}}w(i,j)$

$w(i,V_{2})=\sum_{(i,j)\in E,j\in V_{2}}w(i,j)$

$\textrm{score}(i)=\max\\{w(i,V_{1}),w(i,V_{2})\\}$

end for

$i^{*}\leftarrow\arg\max_{i\in V^{\prime}}{\textrm{score}(i)}$

if $w(i^{*},V_{1})>w(i^{*},V_{2})$ then

$V_{2}\leftarrow V_{2}\cup\\{i^{*}\\}$

else

$V_{1}\leftarrow V_{1}\cup\\{i^{*}\\}$

end if

$V^{\prime}\leftarrow V^{\prime}\setminus\\{i^{*}\\}$

$w(V_{1},V_{2})\leftarrow
w(V_{1},V_{2})+\max\\{w(i^{*},V_{1}),w(i^{*},V_{2})\\}$

end for

Again we are actually building a relation tree here: first find the maximum
weighted edge $(i_{1},i_{2})$ and set it as negative; then at each step add a
new positive leaf to $i_{1}$ or $i_{2}$, depending on the benefit of the cut
weight. Applying SG1 to Fig. 1, we get the following relation tree:

Figure 4: Relation tree obtained by applying SG1 to the graph in Fig. 1.

Alternatively, SG2 uses a “worst-out” criterion:

$\displaystyle\textrm{{score}}(i)$ $\displaystyle=$
$\displaystyle\min\\{w(i,V_{1}),w(i,V_{2})\\},$ (10) $\displaystyle i^{*}$
$\displaystyle\leftarrow$ $\displaystyle\arg\min_{i\in
V^{\prime}}{\textrm{score}(i)}.\ $ (11)

And SG3 is a clever combination of them, and uses a “best-in-worst-out”
criterion:

$\displaystyle\textrm{score}(i)$ $\displaystyle=$
$\displaystyle|w(i,V_{1})-w(i,V_{2})|,$ (12) $\displaystyle i^{*}$
$\displaystyle\leftarrow$ $\displaystyle\arg\max_{i\in
V^{\prime}}{\textrm{score}(i)}.$ (13)

All three algorithms have time complexity $O(n^{2})$, as pointed out in
Hassin-2021 .

####  III.1.1 Approximation Ratio

The approximation ratio is usually defined with respect to the optimal cut
weight $w_{opt}$. If all the edge weights are nonnegative, $w_{opt}$ is
bounded from above by the total weight $w_{tot}$:

$w_{opt}\leq w_{tot}\equiv\sum_{i<j}w_{ij}.$ (14)

So if the optimal cut is not known in advance, we could use $w_{tot}$ instead
to define the approximation ratio:

$R_{\mathcal{A}}\equiv w_{\mathcal{A}}/w_{tot},$ (15)

where $w_{\mathcal{A}}$ is the cut weight obtained by algorithm $\mathcal{A}$.
With such a definition the approximation ratio can not be strictly greater
than $1/2$ theoretically, because there exist graphs whose optimal cut value
approaches $w_{tot}/2$ from above.

We will show that all the four versions of SG algorithms have an approximation
ratio $1/2$ in the above sense. Since the vertex set in the original SG
algorithm can actually be given any order, and SG1-3 differ from SG only by
vertex ordering, it suffices to prove this for SG itself. For this we define
the current total edge weight as $w_{0}(V_{1},V_{2})$, and initiate it as
$w_{12}$. We assume $w_{12}\geq 0$, so initially we have

$w(V_{1},V_{2})=w_{12}\geq\frac{w_{12}}{2}=\frac{1}{2}w_{0}(V_{1},V_{2}).$
(16)

At each step the current total weight is updated as

$w_{0}(V_{1},V_{2})\leftarrow w_{0}(V_{1},V_{2})+w(i,V_{1})+w(i,V_{2}).$ (17)

Since

$\max\\{w(i,V_{1}),w(i,V_{2})\\}\geq\frac{1}{2}(w(i,V_{1})+w(i,V_{2})),$ (18)

we have at every step

$w(V_{1},V_{2})\geq\frac{1}{2}w_{0}(V_{1},V_{2}).$ (19)

When finally we get the cut $V=V_{1}\uplus V_{2}$, we have
$w_{0}(V_{1},V_{2})=w_{tot}$, and thus

$R_{SG}=\frac{1}{2}.$ (20)

Numerically, it is shown in Kahruman-2007  that SG3 performs much better than
SG. We will discuss this in more detail later.

###  III.2 Kruskal class

Now we turn to the Kruskal-class algorithms. First we repeat the original
Kruskal algorithm for MST:

Algorithm 4 Kruskal’s Algorithm for MST

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A minimum spanning tree $H=(V,F)$

Keep a spanning forest $H=(V,F)$ of $G$, with $F=\varnothing$ initially

At each step add to $F$ a minimum-weight edge $e\not\in F$ such that $H$
remains a forest

Stop when $H$ is a spanning tree

As far as we know, De Quincey-2019  first uses the Kruskal approach explicitly
to get a $1/2$-approximation algorithm for MAX-CUT. The algorithm follows
exactly the Kruskal procedure, but applies to unweighted graphs:

Algorithm 5 De Quincey’s Algorithm for MAX-CUT

Input: An unweighted graph $G=(V,E)$

Output: A partition $V=V_{1}\uplus V_{2}$

Keep a spanning forest $H=(V,F)$ of $G$, with $F=\varnothing$ initially

At each step add to $F$ an edge $e\not\in F$ randomly such that $H$ remains a
forest

Stop when $H$ is a spanning tree

Return the partition $V=V_{1}\uplus V_{2}$ such that $F$ is within the cut
$\delta(V_{1})$

Actually the corresponding relation tree here is just $H=(V,F)$ together with
$s\equiv-1)$.

However, for MAX-CUT, we have better ways to avoid cycles: we could eliminate
the correlation between the selected edges and the remaining ones by updating
the graph. As long as we make the updating procedure properly, the maximum cut
would be unchanged. Such an updating strategy has already been commonly used
in solving MIN-CUT, and called “Edge-Contraction (EC)” KS-1993 . Integrating
the EC operation into the Kruskal algorithm, we would get another class of
algorithms for MAX-CUT Kahruman-2007 . Still we could have different
criterions for the selection of the edge at each step, “best-in”, “worst-out”,
and “best-in-worst-out”. With the “worst-out” criterion, we immediately
recover the original EC algorithm for MAX-CUT Kahruman-2007 :

Algorithm 6 EC Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A relation tree $H=(V,F,s)$

$F\leftarrow\varnothing$

$E^{\prime}\leftarrow E$

while $E^{\prime}$ has more than one edges do

Find the edge $(i,j)$ with the minimum weight in $E^{\prime}$, add it to $F$

$s_{ij}\leftarrow+1$

Shift all the edges $(i,k)$ with $k\neq j$ from $i$ to $j$

Merge multiple edges in $E^{\prime}$, and add up the weights

$E^{\prime}\leftarrow E^{\prime}\setminus\\{(i,j)\\}$

end while

Add the last edge $e_{0}$ in $E^{\prime}$ to $F$

$s_{e_{0}}\leftarrow-1$

$H\leftarrow(V,F,s)$

Here we have rewritten the original EC algorithm in the language of relation
tree on purpose. In this form the algorithm may be better called “Edge
Shifting”, rather than “Edge Contraction”, but we keep the original name. When
contracting the edges we actually have two choices, from $x$ to $y$ or from
$y$ to $x$, but both give the same result.

Alternatively, one could use a “best-in” criterion for the selection of the
edge at each step. The resulting algorithm is called “Differencing Edge-
Contraction” (DEC) Hassin-2021 , which we also rewritten in the language of
relation tree here:

Algorithm 7 DEC Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A relation tree $H=(V,F,s)$

$F\leftarrow\varnothing$

$E^{\prime}\leftarrow E$

while $E^{\prime}$ contains edges with positive weights do

Find the edge $(i,j)$ with the maximum weight in $E^{\prime}$, add it to $F$

$s_{ij}\leftarrow-1$

Select one endpoint of $(i,j)$, say $i$

Reverse the signs of the weights of all edges $(i,k)$ with $k\neq j$

Shift all the edges $(i,k)$ with $k\neq j$ from $i$ to $j$

Merge multiple edges in $E^{\prime}$, and add up the weights

$E^{\prime}\leftarrow E^{\prime}\setminus\\{(i,j)\\}$

end while

while $E^{\prime}$ is not empty do

Randomly choose an edge $(i,j)$ in $E^{\prime}$, add it to $F$

$s_{ij}\leftarrow+1$

Shift all the edges $(i,k)$ with $k\neq j$ from $i$ to $j$

Merge multiple edges in $E^{\prime}$, and add up the weights

$E^{\prime}\leftarrow E^{\prime}\setminus\\{(i,j)\\}$

end while

$H\leftarrow(V,F,s)$

In contrast to EC, here the contraction direction does matter when the
selected edges have positive weights, and affects the algorithm performance. A
post-selection criterion is used in Hassin-2021 , where the contraction
direction is chosen to maximize the total weight of the resulting graph.

Similar as SG3, we could take a delicate combination of the above two, and
obtain a “best-in-worst-out” algorithm, which we call “Signed-Edge-
Contraction” (SEC) SAIII :

Algorithm 8 SEC Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A relation tree $H=(V,F,s)$

$F\leftarrow\varnothing$

$E^{\prime}\leftarrow E$

while $E^{\prime}$ is not empty do

Find the edge $(i,j)$ such that the absolute value of its current weight
$|\tilde{w}_{ij}|$ is maximized in $E^{\prime}$

add $(i,j)$ to $F$

$s_{ij}\leftarrow-\textrm{sgn}(\tilde{w}_{ij})$

for $(i,k)\in E^{\prime}$ with $k\neq j$ do

Multiply $\tilde{w}_{ik}$ by $s_{ij}$

Shift $(i,k)$ from $i$ to $j$

Merge multiple edges, and add up the weights

end for

$E^{\prime}\leftarrow E^{\prime}\setminus\\{(i,j)\\}$

end while

$H\leftarrow(V,F,s)$

One can see that SEC is extremely simply, compared to EC and DEC. The reason
is that, both EC and DEC deal with different edge relations separately, while
SEC deals with them in a uniform way. Moreover, SEC solves the contraction
direction problem in DEC, since contraction along both directions gives
weights with the same absolute value. This is why in the algorithm we do not
have to make any choice with respect to the contraction direction. As an
example, we apply SEC to the graph in Fig. 1, and get the relation tree in
Fig. 2. An obvious fact is that, the tree in Fig. 2 contains more than one
negative edges, while in both Fig. 3 and Fig. 4 only one negative edge
appears.

How about the time complexities of the Kruskal-class algorithms? Intuitively,
since the original Kruskal algorithm has complexity $O(m\log m)$ ($m=|E|$),
one may guess that all the algorithms here inherit such a complexity. However,
while in the original Kruskal algorithm we have to make sure no cycle is
formed at each step, this is not the case for the EC algorithms here. In spite
of this, previous studies claim higher complexities: $O(mn^{2})$ for De
Quincey De Quincey-2019 , $O(n^{3})$ for EC Kahruman-2007 , and $O(n^{2}\log
n)$ for DEC Hassin-2021 . In SAIII  we claim that SEC has the complexity
$O(n^{2})$, the same as those SG algorithms. This is based on a “label and
update” trick, which is commonly used in the Prim algorithm. We believe all
the other algorithms in the Kruskal class could be improved to such a
complexity.

####  III.2.1 Approximation Ratio

While in all Prim-class algorithms we could easily trace the change of the cut
weight at each step, this is not the case in the Kruskal-class algorithms.
Only when the selected edge is set as negative and included into the cut, this
can be done by a careful analysis of all involved edges De Quincey-2019 ;
Hassin-2021 . In De Quincey’s algorithm, all selected edges are included into
the cut finally, and thus one could trace the change of the cut weight from
beginning to end. With this, it is proved that De Quincey’s Algorithm has an
approximation ratio $1/2$ De Quincey-2019 . Obviously this method can not be
generalized to the other three algorithms listed above, which makes the
derivation of the approximation ratio complicated. The approximation ratio of
EC is estimated to be larger than $1/3$ Kahruman-2007 , which is not so
satisfactory. As for DEC, it is completely unknown Hassin-2021 .

Quite unexpectedly, in SAIII  it is proved that SEC has an approximation ratio
$1/2$, just as the SG algorithms. The derivation is very straightforward and
elegant, but to elucidate it clearly we will need a formulation of the problem
more algebraic. This is done with the so-called “Stabilizer formalism”
proposed by the quantum computing community. Using such an algebraic
formulation one could easily obtain the cut weight at each step of the
algorithm. In fact, the whole algorithm is first conceived in the stabilizer
formalism, and then translated back into the graphic language. We will briefly
introduce such a formalism in the next section.

##  IV Stabilizer Formalism

The stabilizer formalism is an important framework in quantum computation,
first proposed in the late 90s Gottesman-1996 ; Gottesman-1997 ;
Gottesman-1998 . A nice introduction is given in Nielsen-Chuang-2010 . Here we
will only mention some structures and properties related to MAX-CUT.

###  IV.1 From Bit to Qubit

As we show previously, using the spin variable the cut weight can be expressed
as:

$w(z)=\frac{1}{2}\sum_{i<j}w_{ij}(1-z_{i}z_{j}).$ (21)

Since the spin variable takes values in $\\{+1,-1\\}$, we could combine both
values into a single diagonal matrix, the Pauli-$Z$ matrix:

$Z\equiv\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix}$ (22)

The corresponding eigenstates are defined as

$|0\rangle\equiv\begin{pmatrix}1\\\
0\end{pmatrix},\quad|1\rangle\equiv\begin{pmatrix}0\\\ 1\end{pmatrix}$ (23)

so that

$Z|0\rangle=|0\rangle,\quad Z|1\rangle=-|1\rangle,$ (24)

or more compactly,

$Z|x\rangle=z|x\rangle,\quad z=1-2x.$ (25)

While $|x\rangle$ is simply the quantum promotion of the classical bit $x$, an
intrinsic quantum bit $|\psi\rangle$ could be any complex linear combination
of the classical state $|x\rangle$:

$|\psi\rangle\equiv\alpha|0\rangle+\beta|1\rangle,$ (26)

satisfying the normalization condition:

$\langle\psi|\psi\rangle\equiv|\alpha|^{2}+|\beta|^{2}=1.$ (27)

So a single qubit is a normalized vector in $\mathbb{C}^{2}$. If we further
ignore an overall phase factor of $|\psi\rangle$, the single-qubit state could
be parameterized as

$|\psi\rangle\simeq\cos\frac{\theta}{2}|0\rangle+\mathrm{e}^{i\varphi}\sin\frac{\theta}{2}|1\rangle.$
(28)

This is the Bloch sphere representation of a single qubit, with
$(\theta,\phi)$ the elevation and azimuth. In such a representation the
classical bit state $|x\rangle$ lies on the $z$-axis. The states lying on the
$x$ and $y$-axis are eigenstates of the Pauli-$X$ and Pauli-$Y$ matrices:

$X\equiv\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\quad
Y\equiv\begin{pmatrix}0&-i\\\ i&0\end{pmatrix}$ (29)

To transform states from one axis to another, we will need another two
matrices:

$H\equiv\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\ 1&-1\end{pmatrix},\quad
S\equiv\begin{pmatrix}1&0\\\ 0&i\end{pmatrix},$ (30)

called Hadamard matrix and phase matrix.

When we have $n$ qubits, the entire state is described by a normalized vector
in the tensor product space ${(\mathbb{C}^{2}})^{\otimes n}$. We will omit the
tensor product symbol between different qubits later, both for the states and
the matrices.

###  IV.2 Stabilizer States

While MAX-CUT is indeed a classical problem and the solution is definitely a
classical $n$-bit state $x$, it turns out to be more convenient to consider
more general $n$-qubit states. As a hint of this, $x$ and its negation $\neg
x$, both describing the same cut, could be simultaneously represented with a
single $n$-qubit state.

But we do not really want to consider all $n$-qubit states, we just need some
specific states of them. To specify such a subspace, we first define the Pauli
group. The one qubit Pauli group is defined to be:

$G_{1}\equiv\\{\pm I,\pm iI,\pm X,\pm iX,\pm Y,\pm iY,\pm Z,\pm iZ\\}.$ (31)

Then the $n$-qubit Pauli group is defined as its $n$-fold tensor product:

$G_{n}\equiv G_{1}^{\otimes n}$ (32)

So an element in $G_{n}$ is actually an $n$-fold tensor product of Pauli
matrices, together with an overall factor of $\pm 1,\pm i$.

Next we seek a special class of subgroups $S_{n}$ of $G_{n}$ to characterize
the special states we want. These are defined as:
Definition 2:
A stabilizer group $S_{n}$ is a subgroup of $G_{n}$ such that:
1\. $S_{n}$ is commutative;
2\. $-I\not\in S_{n}$;
3\. $S_{n}$ has exactly $n$ generators, or $S_{n}=<s_{1},...,s_{n}>$.
Correspondingly, we define the stabilizer state as:
Definition 3:
A $n$-qubit state $|\psi\rangle$ is called a stabilizer state if there is a
stabilizer group $S_{n}$, such that:

$s|\psi\rangle=|\psi\rangle,\quad\forall s\in S_{n}.$ (33)

Let us give some typical examples of this. The well-known Einstein-Podolsky-
Rosen (EPR) pair/Bell state

$|\psi\rangle=\frac{|00\rangle+|11\rangle}{\sqrt{2}}$ (34)

is a stabilizer state with the stabilizer group $\langle ZZ,XX\rangle$. Also
any classical state $|x\rangle$ is a stabilizer state, with individual
stabilizer generator given by $Z$ or $-Z$.

###  IV.3 SEC revisited

Now we try to formulate MAX-CUT in the stabilizer formalism. First, we could
promote the weight function $w(z)$ into a matrix function, or in physical
language, the Hamiltonian operator:

$H(Z)=-w(Z)=-\frac{1}{2}\sum_{i<j}w_{ij}(1-Z_{i}Z_{j}).$ (35)

Here an additional minus has been included so that the maximum cut corresponds
to the ground state of $H(Z)$ with the lowest eigenvalue. Since MAX-CUT is a
classical problem, the corresponding ground state must be a classical state,
and thus a stabilizer state. Therefore we could approach the ground state
within the subspace of stabilizer states.

Such a state could be engineered by choosing each stabilizer generators one by
one. The individual terms in the Hamiltonian would be natural candidates for
the stabilizers. The criterion for the choice of the generators is such that
the Hamiltonian is as negative as possible. If we do this greedily, we
immediately recover the SEC algorithm. To see this, let’s define the set of
nontrivial Pauli operators appearing in the Hamiltonian as $P$. Initially, we
have

$P=\\{Z_{i}Z_{j}|(i,j)\in E\\}.$ (36)

We also define the coefficients of those Pauli terms as a function on $P$:

$c_{P}:P\to\mathbb{R},$ (37)

initiated as $c_{ij}=w_{ij}/2$. Finally, we use $H_{0}$ to store the constant
term of $H(Z)$, which is initially $H_{0}=-\frac{1}{2}\sum_{i<j}w_{ij}$. Each
time a new Pauli term (or its opposite) is chosen as a generator, it could be
identified as the identity operator, and $H_{0}$ changes accordingly. With
these definitions, we could reformulate SEC as:

Algorithm 9 SEC Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: Generators for a stabilizer group $S_{n}$ and the cut weight $w(S)$

Initiate the Pauli set as $P\leftarrow\\{Z_{i}Z_{j}|(i,j)\in E\\}$

Initiate the coefficient set as $c_{P}\leftarrow\\{c_{ij}=w_{ij}/2|(i,j)\in
E\\}$

$H_{0}\leftarrow-\frac{1}{2}\sum_{i<j}w_{ij}$

for $l=1:n-1$ do

Find $Z_{i}Z_{j}$ in $P$ such that the absolute value of its current
coefficient $|\tilde{c}_{ij}|$ is maximized in $c_{P}$

$s_{l}\leftarrow-\textrm{sgn}(\tilde{c}_{ij})Z_{i}Z_{j}$

for $k\neq j$ such that $Z_{i}Z_{k}\in P$ do

Multiply $\tilde{c}_{ik}$ by $-\textrm{sgn}(\tilde{c}_{ij})$

Multiply $Z_{i}Z_{k}\in P$ by $Z_{i}Z_{j}$

Merge identical terms in $P$ and add up the coefficients in $c_{P}$

end for

$P\leftarrow P\setminus\\{Z_{i}Z_{j}\\}$

$H_{0}\leftarrow H_{0}-|\tilde{c}_{ij}|$

end for

$s_{n}\leftarrow Z_{1}$

$S_{n}\leftarrow<s_{1},s_{2},...,s_{n}>$

$w(S)\leftarrow-H_{0}$

Almost all the steps here parallel those in SEC. We could even prove that at
each step, the current weights of edges and current coefficients of Pauli
terms are related to each other exactly:

$\tilde{c}_{ij}=\tilde{w}_{ij}/2.$ (38)

Moreover, each edge $(i,j)$ in the relation tree, together with its sign
assignment $s_{ij}$, corresponds to a stabilizer generator $s_{ij}Z_{i}Z_{j}$
here. This gives in total $n-1$ stabilizer generators. Of course these are
enough to determine the cut. We formally include an extra generator $Z_{1}$ to
fix the stabilizer group completely. To explicitly give the cut, one could
simply replace all $Z_{i}$ matrices in these generators by its eigenvalue
$z_{i}$, and solve the $n$ coupled equations $s_{l}=1,\leavevmode\nobreak\
(l=1,...n)$ accordingly. Of course this is equivalent to scanning the
corresponding relation tree.

However, there is an additional operation in the above algorithm: we could
easily trace the change of the cut at each step, which allows us to easily
derive its approximation ratio. As we said, this is not easy for all the
Kruskal-class algorithms.

####  IV.3.1 Approximation Ratio

From the above algorithm, we could actually get a compact expression for the
final cut. For this, let us denote the current coefficient selected at step
$l$ as $\tilde{c}^{l}$. Then

$w(S)=-H_{0}=\frac{1}{2}\sum_{i<j}w_{ij}+\sum_{l=1}^{n-1}|\tilde{c}^{l}|.$
(39)

Alternatively, since the $n-1$ generators and edges in the relation tree
$H=(V,F,s)$ are in one-to-one correspondence, we could rewrite the weight as

$w(F)=\frac{1}{2}\sum_{i<j}w_{ij}+\frac{1}{2}\sum_{(i,j)\in
F}|\tilde{w}_{ij}|.$ (40)

Again $\tilde{w}_{ij}$ is the current weight of edge $(i,j)$ when it is
chosen. From this expression one immediately gets the conclusion: SEC has
approximation ratio $1/2$.

How about the other Kruskal-class algorithms? In analyzing the SG algorithms
we know that all of them have approximation ratio $1/2$, as long as we assign
each vertex greedily. Different strategies to select the vertices do not
affect the approximation ratio theoretically. Could we get the same conclusion
here? The answer is yes. To ensure a $1/2$ approximation ratio here, we must
make sure that at each step, the cut weight is changed by a positive quantity,
rather than a negative one. This can be guaranteed if we properly assign the
sign $s_{ij}$ of the edge $(i,j)$: it must be opposite to the sign of the
current weight $\tilde{w}_{ij}$. The meaning of this rule is clear: if the
edge has a positive weight, we include it into the cut; otherwise we discard
it. As long as this rule is obeyed, the cut weight will always be of the same
form as in the above expression. Different strategies to select the edges only
change the relation tree itself, or the summation indices, not the form of the
above expression.

Now we could check if such an edge-assignment rule is obeyed in all the
Kruskal-class algorithms. Clearly, De Quincey, DEC and SEC all obey this rule,
and all have the approximation ratio $1/2$. EC could violate this rule
severely, and thus may not guarantee an approximation ratio of $1/2$.

###  IV.4 SG revisited

We could also rewrite the SG algorithms in such a formalism, which also helps
to determine the approximation ratio. Let’s take the original SG algorithm as
an example.

Assume that we have ordered the vertices as $1,2,...,n$. For each vertex
$1\leq j\leq n$, we have to choose the stabilizer as $Z_{j}$ or $-Z_{j}$.
Correspondingly, the eigenvalue of the $Z_{j}$ matrix would be $z_{j}=1$ and
$z_{j}=-1$. To make the criterion clear, we rewrite eq.( 35) as

$\displaystyle w(Z)$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i<j}w_{ij}(1-Z_{i}Z_{j})$ (41) $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i<j}w_{ij}-\frac{1}{2}\sum^{n}_{j=2}(\sum_{i<j}w_{ij}Z_{i})Z_{j}$

At step $j$, all the eigenvalues $z_{i},i<j$ would have been determined. So we
could formally write the cut weight as

$w(Z)=\frac{1}{2}\sum_{i<j}w_{ij}-\frac{1}{2}\sum_{j=2}^{n}(\sum_{i<j}w_{ij}z_{i})Z_{j}$
(42)

Since $Z_{1}$ now does not appear, we may fix $z_{1}$ arbitrarily. At step
$j>1$, we make the choice as

$z_{j}=-\textrm{sgn}(\sum_{i<j}w_{ij}z_{i}),\quad 2\leq j\leq n,$ (43)

It is easy to check that such a choice agrees with that in the original SG
algorithm when $w_{12}\geq 0$.. Then we get the final cut weight:

$w(z)=\frac{1}{2}\sum_{i<j}w_{ij}+\frac{1}{2}\sum_{j=2}^{n}\big{|}\sum_{i<j}w_{ij}z_{i}\big{|}.$
(44)

Obviously the weight is larger than one half of the total weight, and thus the
approximation ratio is $1/2$. Notice that the above procedure is slightly
different from the original SG algorithm: it starts with a single vertex,
rather than two vertices or an edge. This seems to be more natural, and could
properly deal with the situation when $w_{12}<0$. We will come back to this
later.

###  IV.5 ADAPT-Clifford

Now we turn to a recently proposed algorithm for MAX-CUT, ADAPT-Clifford
ADAPT-Clifford , which is also formulated in the stabilizer formalism. The
algorithm construct the stabilizer state explicitly, and thus is a little
complicated. Let us introduce the algorithm first, and then explain the steps
in graphical language.

Algorithm 10 ADAPT-Clifford Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A stabilizer state $\psi_{n}$ and the cut $V=A\uplus\bar{A}$

Prepare the initial state $|\psi_{0}\rangle=H^{n}|0^{n}\rangle$

Select a vertex $i_{1}$ and prepare the state
$|\psi_{1}\rangle=Z_{i_{1}}|\psi_{0}\rangle$

$V^{\prime}\leftarrow V\setminus\\{i_{1}\\}$

Find the edge $(i_{1},i_{2})$ of largest positive weight incident with $i_{1}$

$|\psi_{2}\rangle\leftarrow\mathrm{e}^{i\frac{\pi}{4}Z_{i_{2}}Y_{i_{1}}}|\psi_{1}\rangle$

$V^{\prime}\leftarrow V^{\prime}\setminus\\{i_{2}\\}$

for $r=3:n$ do

for $i\in V^{\prime}$ do

$g_{ii_{1}}\leftarrow-\sum_{l\in V\setminus V^{\prime}}w_{il}\langle
Z_{l}X_{i}Z_{i_{1}}\rangle_{\psi_{r-1}}$

$g_{ii_{2}}\leftarrow-\sum_{l\in V\setminus V^{\prime}}w_{il}\langle
Z_{l}X_{i}Z_{i_{2}}\rangle_{\psi_{r-1}}$

$\textrm{score}(i)\leftarrow\max\\{g_{ii_{1}},g_{ii_{2}}\\}$

end for

$i^{*}\leftarrow\arg\max_{i\in V^{\prime}}{\textrm{score}(i)}$

if $g_{i^{*}i_{1}}>0$ then

$|\psi_{r}\rangle\leftarrow\mathrm{e}^{i\frac{\pi}{4}Y_{i^{*}}Z_{i_{1}}}|\psi_{r-1}\rangle$

else

$|\psi_{r}\rangle\leftarrow\mathrm{e}^{i\frac{\pi}{4}Y_{i^{*}}Z_{i_{2}}}|\psi_{r-1}\rangle$

end if

$V^{\prime}\leftarrow V^{\prime}\setminus\\{i^{*}\\}$

end for

Measure $|\psi_{n}\rangle$ to get the classical state $|x\rangle$

$A\leftarrow\\{i\in V|x_{i}=1\\}$

$\bar{A}\leftarrow\\{i\in V|x_{i}=0\\}$

To see how the cut is actually constructed, it would be better to trace the
stabilizer generators step by step. The update of the generators has been
partially explained in ADAPT-Clifford , which we will elucidate in more
detail.

Step 0:
Initially we have

$|\psi_{0}\rangle=H^{n}|0^{n}\rangle=|+^{n}\rangle,$ (45)

where $+\rangle\equiv\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle$. Since
$X|+\rangle=|+\rangle$, the initial generators are $X_{1},X_{2},...,X_{n}$.
That is to say, all the vertices are undetermined.

Step $1$:
Then we randomly select an initial vertex $i_{1}$, and apply $Z_{i_{1}}$ to
$|\psi_{0}\rangle$. This turns generator $X_{i_{1}}$ into $-X_{i_{1}}$, while
the other generators are unchanged. We exclude $i_{1}$ from $V$ to indicate
vertex $i_{1}$ has been dealt with, and denote the remaining set as
$V^{\prime}$.

Step $2$:
Choose vertex $i_{2}$ such that the weight of edge $(i_{1},i_{2})$ is
maximized among all the incident edges of $i_{1}$. In special cases we may
still have $w_{i_{1}i_{2}}<0$, but we may neglect such subtlety and assume
$w_{i_{1}i_{2}}>0$. We then apply
$\mathrm{e}^{i\frac{\pi}{4}Z_{i_{2}}Y_{i_{1}}}$ to the previous state and get

$|\psi_{2}\rangle=\mathrm{e}^{i\frac{\pi}{4}Z_{i_{2}}Y_{i_{1}}}|\psi_{1}\rangle.$
(46)

A little work shows that with this operation, generator $-X_{i_{1}}$ changes
into $-X_{i_{1}}X_{i_{2}}$, and $X_{i_{2}}$ changes into
$-Z_{i_{1}}Z_{i_{2}}$. The other generators remain the same. This means
vertices $i_{1}$ and $i_{2}$ are to be put into different sets. Following SG3,
we still use $V_{1}$ and $V_{2}$ to denote the two sets, and initiate
$V_{1}=\\{i_{1}\\}$ and $V_{2}=\\{i_{2}\\}$. Then the remaining vertex set is
$V^{\prime}=V\setminus(V_{1}\uplus V_{2})$. We may further write the generator
$-X_{i_{1}}X_{i_{2}}$ as $-\prod_{l\in V_{1}\uplus V_{2}}X_{l}$.

Step $3$ to $n$:
Now at each step we have to determine which vertex to select. The criterion to
make the choice is based on the score of each undetermined vertex $i$ in
$V^{\prime}$:

$\displaystyle g_{ii_{1}}=-\sum_{l\in V\setminus V^{\prime}}w_{il}\langle
Z_{l}X_{i}Z_{i_{1}}\rangle_{\psi_{r-1}}$ $\displaystyle g_{ii_{2}}=-\sum_{l\in
V\setminus V^{\prime}}w_{il}\langle Z_{l}X_{i}Z_{i_{2}}\rangle_{\psi_{r-1}}$
$\displaystyle\textrm{score}(i)=\max\\{g_{ii_{1}},g_{ii_{2}}\\}.$ (47)

We need to simplify the above expressions to see what do they really
calculate. Firstly, since $i\in V^{\prime}$ has stabilizer $X_{i}$, so $X_{i}$
can be trivially factored out. Next, since $V\setminus V^{\prime}=V_{1}\uplus
V_{2}$, we may do the calculation separately for $V_{1}$ and $V_{2}$, and find

$\displaystyle\langle
Z_{l}Z_{i_{1}}\rangle_{\psi_{r-1}}=1,\leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \langle
Z_{l}Z_{i_{2}}\rangle_{\psi_{r-1}}=-1,\quad l\in V_{1},$ $\displaystyle\langle
Z_{l}Z_{i_{1}}\rangle_{\psi_{r-1}}=-1,\leavevmode\nobreak\
\leavevmode\nobreak\ \langle
Z_{l}Z_{i_{2}}\rangle_{\psi_{r-1}}=1,\leavevmode\nobreak\ \leavevmode\nobreak\
\quad l\in V_{2}$ (48)

With these relations we may simplify the expressions in Eqs. 47 as:

$\displaystyle g_{ii_{1}}=w(i,V_{2})-w(i,V_{1})$ $\displaystyle
g_{ii_{2}}=w(i,V_{1})-w(i,V_{2})$
$\displaystyle\textrm{score}(i)=\max\\{g_{ii_{1}},g_{ii_{2}}\\}=|w(i,V_{1})-w(i,V_{2})|.$
(49)

So the score function is exactly the same as SG3! This guarantees that at each
step the same vertex $i^{*}$ is chosen. Then we have to check if the same
assignment as SG3 has been performed. Without loss of generality, assume
$g_{i^{*}i_{1}}>0$ or $w(i^{*},V_{2})>w(i^{*},V_{1})$, so we apply the matrix
$\mathrm{e}^{i\frac{\pi}{4}Y_{i^{*}}Z_{i_{1}}}$ to the previous state. Some
matrix multiplication shows that it turns generator $X_{i^{*}}$ into
$Z_{i^{*}}Z_{i_{1}}$. This means we have included $i^{*}$ into $V_{1}$,
exactly the same as in SG3. The operation also updates another generator
$-\prod_{l\in V_{1}\uplus V_{2}}X_{l}$, which does not affect the cut.

Finally, the stabilizer state $|\psi_{n}\rangle$ is determined by the
generators

$-Z_{i_{1}}Z_{i_{2}},Z_{r}Z_{i_{1}}/Z_{r}Z_{i_{2}}\leavevmode\nobreak\
(r=3,...,n),-\prod_{l\in V}X_{l}.$ (50)

Due to the presence of the generator $-\prod_{l\in V}X_{l}$,
$|\psi_{n}\rangle$ is a superposition of a state $|x\rangle$ and its negation
$|\neg x\rangle$:

$|\psi_{n}\rangle=\frac{1}{\sqrt{2}}(|x\rangle-|\neg x\rangle).$ (51)

Measuring $|\psi_{n}\rangle$ gives either $x$ or $\neg x$, and correspondingly
$A$. Since the final cut $V=A\uplus\bar{A}$ must be the same as $V=V_{1}\uplus
V_{2}$, we would simply get $A=V_{1}$ or $A=V_{2}$.

In conclusion, the ADAPT-Clifford algorithm is just a reformulation of SG3 in
the stabilizer formalism. However, ADAPT-Clifford  reports a rather high
complexity, $O(n^{5})$, while SG3’s complexity is of $O(n^{2})$. This means,
most of operations in ADAPT-Clifford  are redundant, and could be removed or
simplified. Nevertheless, the ADAPT-Clifford algorithm does give some hints
that all the SG algorithms, as of Prim-class, should better start from a
vertex rather than an edge, even though this may introduce some randomness.

##  V Numerical Performance

Now we turn to the numerical performance of these algorithms. Previous study
in Kahruman-2007  shows that for the SG algorithms, the “best-in-worst-out”
version, namely SG3, performs much better than the others. Similarly, SEC as a
“best-in-worst-out” synthesis of EC and DEC, is expected to perform best in
the Kruskal class. So we will mainly focus on these two algorithms. But before
doing the numerical calculation, we would like to modify the initialization of
SG3 slightly, following the choice made in ADAPT-Clifford . Namely, we would
start from an initial vertex, as the original Prim algorithm does, rather than
from the maximum-weight edge. Then the algorithm reads:

Algorithm 11 SG3 Algorithm for MAX-CUT

Input: A weighted graph $G=(V,E,w)$ with $w:E\to\mathbb{R}$

Output: A partition $V=V_{1}\uplus V_{2}$ and the cut weight $w(V_{1},V_{2})$

Choose an initial vertex $r$

$V_{1}\leftarrow\\{r\\},V_{2}\leftarrow\varnothing$

$w(V_{1},V_{2})\leftarrow 0$

$V^{\prime}\leftarrow V\setminus\\{r\\}$

for $j=1:n-1$ do

for $i\in V^{\prime}$ do

$w(i,V_{1})=\sum_{(i,j)\in E,j\in V_{1}}w(i,j)$

$w(i,V_{2})=\sum_{(i,j)\in E,j\in V_{2}}w(i,j)$

$\textrm{score}(i)=|w(i,V_{1})-w(i,V_{2})|$

end for

$i^{*}\leftarrow\arg\max_{i\in V^{\prime}}{\textrm{score}(i)}$

if $w(i^{*},V_{1})>w(i^{*},V_{2})$ then

$V_{2}\leftarrow V_{2}\cup\\{i^{*}\\}$

else

$V_{1}\leftarrow V_{1}\cup\\{i^{*}\\}$

end if

$V^{\prime}\leftarrow V^{\prime}\setminus\\{i^{*}\\}$

$w(V_{1},V_{2})\leftarrow
w(V_{1},V_{2})+\max\\{w(i^{*},V_{1}),w(i^{*},V_{2})\\}$

end for

Now the performance of the algorithm would depend on the choice of the initial
vertex $r$. We could use an exhaustive search to find the best choice for $r$,
at the price of increasing the time complexity by one factor of $n$. We call
such an approach “deterministic SG3” (SG3-d). Alternatively, we may choose $r$
randomly, and then repeat the whole algorithm $t$ times. We call this
“randomized SG3” (SG3-r). we fix $t$ to be $t=[2\log_{2}n]$, so that it could
be much faster than the deterministic one, while somehow maintaining the
performance. Since the modified SG3 now differs from ADAPT-Clifford only by
complexity, some of the following results for SG3-d and SG3-r in the small-
size region may coincide with those in ADAPT-Clifford .

###  V.1 Complete graphs

####  V.1.1 Positive weights

We start with complete graphs with positive weights, and sample each weight
independently from the uniform distribution $U[0,1]$. The graph size $n$ is
chosen to range from $100$ to $400$. For comparison, we first run the SDP-
based GW algorithm using the Julia implementation GW-Julia , fixing the number
of rounding times of GW to be $100$ 222The performance of GW could be slightly
improved if we increase the rounding times to $10^{3}$ or $10^{4}$ ADAPT-
Clifford . However, since here we only use GW for graphs with hundreds of
vertices, repeating the rounding procedure $100$ times seems reasonable.. For
each $n$, we generate $50$ instances, and run GW on each of them. The ratio of
the predicted cut weight to the SDP upper bound, $w_{ub}$, is used to
characterize the performance on each instance. This ratio is then averaged
over all $50$ instances to give the final prediction. All the other algorithms
are analyzed in the same way, taking the corresponding SDP upper bound
$w_{ub}$ as reference. The final results for all the algorithms are presented
in Fig. 5.

Figure 5: Average performance of various algorithms for complete graphs with
positive weights. For each $n$, we generate $50$ instances with the weights
sampled independently from $U[0,1]$, calculate the ratio $w/w_{ub}$ for each
instance, and finally take the average over all instances. Here $w_{ub}$ is
the SDP upper bound from the GW procedure. Left: results from the original SG3
and SEC algorithm, in comparison with GW. Right: comparison of results from
the improved SG3-d and SG3-r algorithms and GW.

From the left figure, we see that the results from the original SG3 algorithm
and SEC are almost the same. They are not as good as GW, but as the graph size
increases they gradually get close. When $n$ is bigger than $300$, they are
almost as accurate as GW. Comparing the curves from the left and right
figures, one finds significant improvement from SG3 to SG3-r and SG3-d. Both
of them outperform GW in the whole size region, and SG3-d performs extremely
well. At $n=400$, the prediction of SG3-d is almost $99\%$ of the SDP upper
bound, indicating that it could be very close to the optimal value. These
results demonstrate that, for the vertex-oriented algorithm such as SG3,
starting from a maximum-weight edge is indeed not a good choice. Also, the
randomized algorithm SG3-r could be further improved, for example by
increasing the number of repeating times from $[2\log_{2}n]$ to $[\sqrt{n}]$.

In short, modifying the initialization from an edge to a vertex greatly
improves the performance of the SG3 algorithm, making it much better than GW
and SEC. The superiority of SG3-d/r over SEC on complete graphs is expected:
Prim-class algorithms ought to perform better than Kruskal-class algorithms
for dense graphs. Still, their superiority over GW is unexpected and
noteworthy.

####  V.1.2 Signed weights: the Sherrington-Kirkpatrick model

Next we consider graphs with both positive and negative weights. We will focus
on a specific model, the Sherrington-Kirkpatrick (SK) model, described by the
following Hamiltonian on a complete graph:

$H_{\rm{SK}}=\sum_{i<j}w_{ij}z_{i}z_{j},$ (52)

where each weight is sampled independently from a symmetric distribution
satisfying

$\overline{w_{ij}}=0,\quad\overline{w_{ij}^{2}}=1,\quad w_{ij}=w_{ji}.$ (53)

As a special instance of the Ising-type Hamiltonian, the SK model could be
related to a MAX-CUT problem for a graph with edge weights $\\{w_{ij}\\}$. One
could first solve the MAX-CUT problem and then extract the ground state energy
$E_{\rm{SK}}$ through Eq. (8). Alternatively, one could exactly solve the
model in the thermodynamic limit Parisi-1979 , getting

$\lim_{n\to\infty}\frac{E_{\rm{SK}}}{n^{3/2}}=\Pi^{*}\approx-0.763.$ (54)

This limiting value is called the Parisi value. Some other approaches give
rise to less accurate limiting values. For example, using similar derivation
as in subsection (IV.4) one finds for the original SG algorithm Aizenman-1987
; Rigetti-2023 :

$\Pi_{\rm{SG}}=-\frac{2}{3}\sqrt{\frac{2}{\pi}}\approx-0.532.$ (55)

The SDP method gives a better value Aizenman-1987 :

$\Pi_{\rm{SDP}}=-\frac{2}{\pi}\approx-0.637.$ (56)

We will use all three limiting values as references to assess various
algorithms.

We generate $10$ instances for each graph size $n$, and sample the edge
weights independently from the normal distribution $\mathcal{N}(0,1)$. We
calculate the average cut value over all instances, and then extract the
ground state energy of the SK model through the relation (LABEL:eq.wz). For
SEC, SG3 and SG3-r, we do the calculation for $n$ as large as $10000$, while
for SG3-d we manage to perform the calculation up to $n=2000$. The results are
summarized in Fig. 6 and Fig. 7.

Figure 6: Average performance of various algorithms for the SK model. For each
$n$, we generate $10$ instances with $\\{w_{ij}\\}$ sampled independently from
$\mathcal{N}(0,1)$, calculate the regularized energy $\bar{E}/n^{3/2}$ for
each instance, and finally take the average over all instances.  Figure 7:
Average performance of various algorithms for the SK model. For each $n$, we
generate $10$ instances with $\\{w_{ij}\\}$ sampled independently from
$\mathcal{N}(0,1)$, calculate the regularized energy $\bar{E}/n^{3/2}$ for
each instance, and finally take the average over all instances.

From the above figures we can see similar patterns as the previous case with
only positive weights: the original SG3 and SEC have nearly the same
performance, while SG3-d outperform them a lot. SG3-r stays somewhere in
between, and may be further improved by increasing the repeating times. The
limiting value of SG3 and SEC is about $-0.68$, already surpasses the SDP
limit. SG3-d seems to converge at a value around $-0.70$, while SG3-r manages
to get a value around $-0.686$. Both of them are still far from the Parisi
value, making clear that more advanced techniques are further needed to
approach the true ground state. We also notice that the results at small $n$
suffer from large finite-size fluctuations, and naively extrapolating those
results to large $n$ could lead to inaccurate answers ADAPT-Clifford .

###  V.2 Sparse graphs

While the vertex-oriented Prim-class algorithms may perform better for dense
graphs, one expects the edge-oriented Kruskal-class to win out for sparse
enough graphs. In particular, when the edge number $m$ is of the same order as
the vertex number $n$, the Kruskal-class algorithm should exhibit some
advantage. Nevertheless, the dependence of different algorithms on the
sparsity could be entangled with the dependence on the weight distribution.
Therefore, we consider both weighted and unweighted graphs next, all with
fixed average degree.

####  V.2.1 $k$-regular graphs

We start with $k$-regular random graphs. When $k$ is large enough, we should
get similar results as the previous case of complete graphs. To confirm this,
we consider random $8$-regular graphs first. We generate $40$ instances for
various $n$ in the range $[60,410]$, calculate the ratio of the obtained cut
to the total weight for each instance, and finally take the average over all
instances. Here we choose the total weight rather than the SDP upper bound to
calculate the cut ratio, because this ratio could be estimated with a
large-$k$ expansion, and stays almost as a constant when $n$ is varied
Dembo-2017 .

We plot the results for weighted and unweighted $8$-regular graphs in Fig. 8
and Fig. 9. For the weighted case, we sample the edge weights independently
from the uniform distribution $U[0,1]$.

Figure 8: Average performance of various algorithms for the weighted
$8$-regular graphs. For each $n$, we generate $40$ instances with
$\\{w_{ij}\\}$ sampled independently from $U[0,1]$, calculate the cut ratio
$w/w_{tot}$ for each instance, and finally take the average over all
instances. Left: results from SEC, SG3 and GW are plotted; Right: results from
SG3-d and SG3-r and GW results are shown. Figure 9: Average performance of
various algorithms for the unweghted $8$-regular graphs. For each $n$, we
generate $40$ instances, calculate the cut ratio $w/w_{tot}$ for each
instance, and finally take the average over all instances. Left: results from
SEC, SG3 and GW are plotted; Right: results from SG3-d and SG3-r and GW
results are shown.

As expected, the pattern shown in Fig. 8 is very similar to the previous case
of complete graphs in Fig. 5: SEC and SG3 perform roughly the same, and both
are worse than GW, while SG3-d and SG3-r surpass GW, especially in the large
$n$ region. When the weights are removed, SEC and SG3 deteriorate further.
Although SG3-r also becomes worse than GW, SG3-d still keeps its advantage in
the whole region. Therefore the general pattern in Fig. 8 is roughly
maintained in Fig. 9. This is reasonable: turning off weights makes the edge-
oriented algorithms difficult to proceed, but has relatively weaker effects on
vertex-oriented algorithms.

Clearly $8$-regular graphs are not sparse enough. So we decrease the degree to
$k=3$, and repeat all the calculations for both weighted and unweighted
graphs. The results are plotted in Fig. 10 and Fig. 11 below.

Figure 10: Average performance of various algorithms for the weighted
$3$-regular graphs. For each $n$, we generate $40$ instances with
$\\{w_{ij}\\}$ sampled independently from $U[0,1]$, calculate the cut ratio
$w/w_{tot}$ for each instance, and finally take the average over all
instances. Left: results from SEC, SG3 and GW are plotted; Right: results from
SG3-d and SG3-r and GW results are shown. Figure 11: Average performance of
various algorithms for the unweighted $3$-regular graphs. For each $n$, we
generate $40$ instances, calculate the cut ratio $w/w_{tot}$ for each
instance, and finally take the average over all instances. Left: results from
SEC, SG3 and GW are plotted; Right: results from SG3-d and SG3-r and GW
results are shown.

First we see dramatic changes for the weighted $3$-regular graphs in Fig. 10:
SG3 now catches up with GW when $n$ is large, and SEC dominates over GW in the
whole region. Meanwhile, both SG3-d and SG3-r deteriorate and are overtaken by
GW when $n$ is small. Most importantly, SEC surpasses SG3-d almost in the
whole region, as expected.

However, when the weights are turned off, a disaster occurs, as shown in Fig.
11 : all the four greedy algorithms deteriorate a lot, and fall far below GW.
The situation with SEC and SG3 is the worst. Such a deterioration has been
noticed in ADAPT-Clifford .

####  V.2.2 Erdös-Rényi graphs

It will be natural to extend the previous study to more general sparse graphs,
those with fixed average degree. As a typical representative, we consider
random Erdös-Rényi (ER) graphs with fixed edge density, $G(n,p)$. Then the
average degree would approximately be $\bar{k}\approx np$ when $n$ is not too
small.

We consider two situations: varying $n$ with fixed $p$, and varying $p$ with
fixed $n$. In both cases we make sure that the range of the average degree
$\bar{k}$ covers the interval $[3,8]$. For each parameter set $(n,p)$, we
generate $40$ instances, calculate the ratio $w/w_{ub}$ with respect to the
SDP upper bound, and finally take the average over all instances. Here we
choose the SDP upper bound rather than the total weight as the denominator,
because it helps to discriminate various algorithms. We start with the
unweighted case, first vary $p$ and then vary $n$, and plot the results in
Fig. 12 and Fig. 13 respectively.

Figure 12: Average performance of various algorithms for the unweighted ER
graphs $G(n,p)$ with fixed size $n=400$. For each $p$, we generate $40$
instances, calculate the cut ratio $w/w_{ub}$ for each instance, and finally
take the average over all instances. Left: results from SEC, SG3 and GW are
plotted; Right: results from SG3-d and SG3-r and GW results are shown. Figure
13: Average performance of various algorithms for the unweighted ER graphs
$G(n,p)$ with fixed density $p=0.02$. For each $n$, we generate $40$
instances, calculate the cut ratio $w/w_{ub}$ for each instance, and finally
take the average over all instances. Left: results from SEC, SG3 and GW are
plotted; Right: results from SG3-d and SG3-r and GW results are shown.

The results in the above two figures confirm the conclusions made in the
previous subsection. Namely, when the average degree decreases, performance of
vertex-oriented algorithms deteriorates, while that of the edge-oriented
algorithms improves. This is clearly seen in the right part of Fig. 12: at
large $p$, and thus large $\bar{k}$, SG3-d is superior to GW; when $p$ and
$\bar{k}$ decrease, SG3-d deteriorates and becomes worse than GW. A kind of
“phase transition” occurs at $\bar{k}_{c}\approx 4$. Similar phase transitions
have been studied extensively in the literature, especially in the
propositional satisfiability (SAT) problems Monasson-1999 . On the left part
of Fig. 12, we find the improvement of SEC as $p$ and $\bar{k}$ decrease,
which exceeds SG3 when $\bar{k}$ is smaller than $\bar{k}_{c}\approx 4$. The
results in Fig. 13 exhibits almost the same pattern as Fig. 12, where now $n$
is varied instead of $p$. And the phase transition point is again around the
critical degree $\bar{k}_{c}\approx 4$.

Next we turn on the edge weights by sampling them independently from $U[0,1]$.
The results with varying $p$ and $n$ are shown in Fig. 14 and Fig. 15
respectively.

Figure 14: Average performance of various algorithms for the weighted ER
graphs $G(n,p)$ with fixed size $n=400$. For each $p$, we generate $40$
instances with the edge weights $\\{w_{ij}\\}$ sampled independently from
$U[0,1]$, calculate the cut ratio $w/w_{ub}$ for each instance, and finally
take the average over all instances. Left: results from SEC, SG3 and GW are
plotted; Right: results from SG3-d and SG3-r and GW results are shown. Figure
15: Average performance of various algorithms for the weighted ER graphs
$G(n,p)$ with fixed density $p=0.02$. For each $n$, we generate $40$ instances
with the edge weights $\\{w_{ij}\\}$ sampled independently from $U[0,1]$,
calculate the cut ratio $w/w_{ub}$ for each instance, and finally take the
average over all instances. Left: results from SEC, SG3 and GW are plotted;
Right: results from SG3-d and SG3-r and GW results are shown.

From the left part of Fig. 14, we see that the improvement of SEC with
decreasing $\bar{k}$ is enhanced when the edge weights are introduced. SEC now
exceeds GW when $\bar{k}\leq 4$. In the right part, the deterioration of SG3-d
with decreasing $\bar{k}$ is now mitigated with the weights turned on. The
cross of SG3-d and GW now disappears. We may also compare the results of SEC
with SG3-d directly. It turns out that even in the region $\bar{k}<4$, SEC
does not strictly surpass SG3-d, as in the $3$-regular graphs. This should not
be surprising: a nonzero distribution for the degree helps mitigate the
sparsity problem for SG3-d. The results in Fig. 15 are similar to Fig. 14:
below $\bar{k}_{c}\approx 4$, the results of SEC almost coincides with that of
GW, although do not strictly surpass the latter.

In summary, a kind of phase transition is found to occur at the critical
average degree $\bar{k}_{c}\approx 4$. This is mostly clearly seen from the
crossing of the SG3-d and GW curves in the unweighted case, and that of SEC
and GW in the weighted case.

##  VI Summary

A new concept, relation tree, is introduced to represent graph cut. With this,
various greedy heuristics for MAX-CUT could be classified as two different
classes of tree algorithms: the vertex-oriented Prim class, and the edge-
oriented Kruskal class. The SG series of algorithms belong to the Prim class,
while the EC series belong to the Kruskal class. We also give an algebraic
formulation of this framework, based on the stabilizer formalism in quantum
computing. Such an algebraic formulation helps to derive the approximation
ratio of various algorithms. It also helps to extend these algorithms to more
general cases, especially to the intrinsic quantum problems SA-I .

The classification base on relation tree is then utilized to improve present
algorithms. We show that modifying the initialization of SG3 from the maximum
edge to an arbitrary vertex greatly improves the performance. Such an
improvement is so significant that on most graphs the modified algorithms,
SG3-d and SG3-r, outperform the GW algorithm based on SDP. In particular, in
the SK model SG3-d could achieve a regularized energy as low as $-0.70$ at
large size, which is nearly $92\%$ of the Parisi value and far below the SDP
limit. For a greedy heuristic, such a performance is quite remarkable.

We also use such a classification to assess the performance of different
classes of algorithms. It turns out that their performance mainly depend on
the average degree of a graph. In general, a phase transition occurs around a
critical degree $\bar{k}_{c}\approx 4$. Above this degree, Prim-class
algorithms such as SG3-d outperforms all others and even GW. Below this degree
SG3-d gradually deteriorates. The Kruskal-class algorithms, such as SEC,
behave in the opposite way: below the critical degree, SEC could be
competitive with GW, and could even surpass SG3-d if the degree distribution
is sharp; when the average degree increases above $\bar{k}_{c}$, SEC quickly
deteriorates. For SG3-d, the phase transition is significant in the unweighted
case, which would be smoothed out when the edge weights are included. And for
SEC, the phase transition is more clearly seen in the weighted case, and less
significant when the weights are turned off.

## References

  * (1) M. Goemans and D.P. Williamson, 1995,  Improved approximation algorithms for MAX-CUT and satisfiability problems using semidefinite programming, Journal of the ACM, 42 (1995), 1115-1145.
  * (2) Sera Kahruman, Elif Kolotoglu, Sergiy Butenko, Illya V. Hicks, 2007,  On greedy construction heuristics for the MAX-CUT problem, Int. J. Comput. Sci. Eng. 3 (2007) 211-218.
  * (3) S. Sahni, T. Gonzales, 1976,  P-complete approximation problems, Journal of the ACM, 23 (1976), 555-565.
  * (4) D. R. Karger and C. Stein, 1993,  An $\tilde{O}(N^{2})$ Algorithm for Minimum Cuts, in Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, ACM Press, 1993, pp. 757-765.
  * (5) Refael Hassin, Nikita Leshenko, 2021,  Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem, Operations Research Letters 49 (2021) 320-325.
  * (6) Chuixiong Wu, Jianan Wang, Fen Zuo, 2023,  Stabilizer Approximation III: Maximum Cut, [https://arxiv.org/abs/2303.17215].
  * (7) M. H. Muñoz-Arias, S. Kourtis, and A. Blais, 2023,  Low-depth Clifford circuits approximately solve MaxCut, [https://arxiv.org/abs/2310.15022].
  * (8) F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt, 1988,  An application of connbinatorial optimization to statistical physics and circuit layout design, Oper. Res. 36, 493-513.
  * (9) R. E. Gomory abd T. C. Hu, 1961,  Multi-Terminal Network Flows, SIAM Journal on Applied Mthematics, 9 (1961) 551-556.
  * (10) R. C. Prim,  Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957) 1389-1401.
  * (11) J. B. Kruskal,  On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical Society, 7 (1956) 48-50.
  * (12) Provable Non-Convex Optimization and Algorithm Validation via Submodularity, Doctor Thesis, ETH Zurich, [https://arxiv.org/abs/1912.08495].
  * (13) Martin de Quincey,  On the maximum cut problem: A new $0.5$-approximation algorithm, Bachelor Thesis, Eindhoven University of Technology, 2019.
  * (14) Daniel Gottesman, 1996,  Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A54 (1996) 1862, [https://arxiv.org/abs/quant-ph/9604038].
  * (15) Daniel Gottesman, 1997,  Stabilizer Codes and Quantum Error Correction, Ph.D. thesis, California Institute of Technology, Pasadena, CA, 1997, [https://arxiv.org/abs/quant-ph/9705052].
  * (16) Daniel Gottesman, 1998,  The Heisenberg Representation of Quantum Computers, [https://arxiv.org/abs/quant-ph/9807006].
  * (17) Michael A. Nielsen, Isaac L. Chuang, 2010,  Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press.
  * (18) A Julia implementation of Goemans-Williamson algorithm, [https://github.com/ericproffitt/maxcut.jl].
  * (19) G. Parisi,  Infinite number of order parameters for spin glasses, Phys. Rev. Lett. 43 (1979) 1754.
  * (20) M. Aizenman, J. L. Lebowitz, and D. Ruelle, 1987,  Some rigorous results on the sherrington-kirkpatrick spin glass model, Comm. Math. Phy. 112 (1987), 3.
  * (21) M. Dupont, B. Evert, et al., 2023,  Quantum-enhanced greedy combinatorial optimization solver, Science Advances 9 (2023), 45, [https://arxiv.org/abs/2303.05509].
  * (22) A. Dembo, A. Montanari, and S. Sen, 2017,  Extremal cuts of sparse random graphs, The Annals of Probability, 45 (2017), 1190.
  * (23) R. Monasson, R. Zecchina, S. Kirkpatrick, B. Selman, and L. Troyanskyk, 1999,  Determining computational complexity from characteristic ‘phase transitions’, Nature 400 (1999), 133-137.
  * (24) Xinying Li, Jianan Wang, Chuixiong Wu, Fen Zuo, 2022,  Stabilizer Approximation, [https://arxiv.org/abs/2209.095643].