##  Appendix B Expansion properties of a random bipartite graph

We will first present a technical lemma that we need to use.

######  Lemma B.1 ( ).

Let $1\leq s\leq\frac{2}{3}N$ and $\delta=1/(2\log N)$ Let
$p_{s}=\frac{(N-s)!\left((1+\delta)s)!\right)^{2}}{s!(N-\delta
s)!\left((\delta s)!\right)^{3}}$, then

$\log p_{s}\lesssim\log(3/2)(\delta-1)s.$

We omit the proof of this lemma because it follows almost exactly the analysis
of the proof in [Kow19, Theorem 4.1.1].

Next, we show $D$-regular random bipartite graph is a mild expander graph as
stated in Lemma 3.4. We restate the lemma here:

######  Lemma (Lemma 3.4 in Section 3).

Let $L$ and $R$ be two sets of vertices with $|L|=|R|=N$. Link $L$ and $R$
through $D\geq 3$ random perfect matchings. Denote the resulting graph by
$G_{B}=(V_{B},E_{B})$, and let $\chi=2/3$, $\delta=1/(2\log N)$. Then $G_{B}$
has the following expansion properties with probability
$1-\Theta(1/N^{2\log(3/2)(1-\delta)})$:

  * (i)

For any subset $L^{\prime}\subseteq L$ and $|L^{\prime}|\leq\chi N$, we have
$|\Gamma(L^{\prime})\backslash L^{\prime}|\geq(1+\delta)|L^{\prime}|$, where
$\Gamma(L^{\prime})$ denotes the neighborhood of $L^{\prime}$ as defined in
Definition 2.1.

  * (ii)

For any subset $T\subseteq L\cup R$ and $|T|\leq N$, we have
$|\Gamma(T)\backslash T|\geq\frac{\delta}{2}|T|$.

In other words, with probability $1-\Theta(1/N^{2\log(3/2)(1-\delta)})$, this
bipartite regular graph is a mild expander graph.

###### Proof.

To prove (i), it suffices to show that the probability of there existing
$L^{\prime}\subset L$ such that $|L^{\prime}|\leq\chi N$ and
$|\Gamma(L^{\prime})\backslash L^{\prime}|<(1+\delta)|L^{\prime}|$ is small.
For simplicity and slight abuse of the notation, in the rest of the proof, we
use $\delta|L|$ to represent $\lfloor\delta|L|\rfloor$.

In one of the random perfect matchings, let the neighbors of $L^{\prime}$ in
$R$ be $I_{1}$, then $|I_{1}|=|L^{\prime}|$. Therefore
$|\Gamma(L^{\prime})\backslash L^{\prime}|\geq|L^{\prime}|$. If
$|\Gamma(L^{\prime})\backslash L^{\prime}|\leq(1+\delta)|L^{\prime}|$ with the
$D$ random perfect matchings, it is necessary that at most
$\delta|L^{\prime}|$ of the values of the other $D-1$ random perfect matchings
are outside the set $I_{1}$. Each random perfect match is chosen independently
with probability $1/N!$. For a specific set $I_{\delta}$ of size
$\delta|L^{\prime}|$ , the probability that $\Gamma(L^{\prime})\backslash
L^{\prime}\subseteq I_{1}\cup I_{\delta}$ is bounded as follows:

$\displaystyle Pr[\Gamma(L^{\prime})\backslash L^{\prime}\subseteq I_{1}\cup
I_{\delta}]$
$\displaystyle\leq\left(\frac{((1+\delta)|L^{\prime}|)((1+\delta)|L^{\prime}|-1)\cdots((1+\delta)|L^{\prime}|-|L^{\prime}|+1)!}{N!}\right)^{D-1}$
$\displaystyle=\left(\frac{((1+\delta)|L^{\prime}|)!}{(\delta|L^{\prime}|)!N!}\right)^{D-1}.$

Note that this probability decreases with $D$. For the choice of the
additional set of $I_{\delta}$ in $R$ of size $\delta|L^{\prime}|$, there are
in total $\binom{N}{\delta|L^{\prime}|}$ options. Therefore,

$\displaystyle\Pr[\text{There exists $L^{\prime}\subseteq L$ with
$|\Gamma(L^{\prime})\backslash L^{\prime}|<(1+\delta)|L^{\prime}|$ }]$
$\displaystyle\leq\sum_{L^{\prime}\subset L,|L^{\prime}|\leq\chi
N}\binom{N}{\delta|L^{\prime}|}\Pr[\Gamma(L^{\prime})\subseteq I_{1}\cup
I_{\delta}]$ $\displaystyle=\sum_{s=1}^{\chi N}\binom{N}{s}\binom{N}{\delta
s}\left(\frac{(N-s)!((1+\delta)s)!}{(\delta s)!N!}\right)^{D-1}$
$\displaystyle=\sum_{s=1}^{\chi
N}\left(\frac{(N-s)!}{N!}\right)^{D-3}\frac{(N-s)!\left((1+\delta)s)!\right)^{D-1}}{s!(N-\delta
s)!\left((\delta s)!\right)^{D}}$ $\displaystyle\leq\sum_{s=1}^{\chi
N}\frac{(N-s)!\left((1+\delta)s)!\right)^{2}}{s!(N-\delta s)!\left((\delta
s)!\right)^{3}}.$

To upper bound the probability, we will bound the value of each term
$p_{s}=\frac{(N-s)!\left((1+\delta)s)!\right)^{2}}{s!(N-\delta
s)!\left((\delta s)!\right)^{3}}$. Let $\delta=1/(2\log N)$, we consider the
following two cases of $s$,

  1. 1.

$1\leq s\leq 2\log N$, we have $p_{s}=\frac{(N-s)!s!}{N!}=\frac{s(s-1)\cdots
2\cdot 1}{N(N-1)\cdots(N-s+1)}$ and

$\sum_{s=1}^{2\log N}p_{s}=\Theta(1/N).$

  2. 2.

$2\log N\leq s\leq\chi N$, using the Stirling Formula $\log(k!)=k\log
k-k+\frac{1}{2}\log(2\pi k)+O(1/k)$ and following Lemma B.1, we know that
$\log p_{s}\lesssim\log(3/2)(\delta-1)s$. That is $p_{s}\approx
2^{-\log(3/2)(1-\delta)s}=a^{s}$, where $a=2^{-\log(3/2)(1-\delta)}<1$ is a
constant. Thus

$\sum_{s=2\log N}^{\chi N}a^{s}=a^{2\log N}\left(\frac{1-a^{\chi N-2\log
N+1}}{1-a}\right)=\Theta(N^{2\log a})=\Theta(1/N^{2\log(3/2)(1-\delta)}).$

Combine the two cases, we have

$\Pr[\text{There exists $L^{\prime}\subseteq L$ with
$|\Gamma(L^{\prime})\backslash L^{\prime}|<(1+\delta)|L^{\prime}|$
}]=\Theta(1/N^{2\log(3/2)(1-\delta)}).$

In other words, with probability at least
$1-\Theta(1/N^{2\log(3/2)(1-\delta)})$, for any subset $L^{\prime}\subset L$
and $|L^{\prime}|\leq\chi N$, we have $|\Gamma(L^{\prime})\backslash
L^{\prime}|\geq(1+\delta)|L^{\prime}|$.

Next we prove (ii), that is, for any subset $T\subseteq L\cup R$ with $|T|\leq
N$, with high probability, we have $\Gamma(T)\geq\delta|T|/2$. This provides
us with the expansion property of an arbitrary subgraph of $G_{B}$ of size at
most $N$. Let $T=L^{\prime}\cup R^{\prime}$ with $L^{\prime}=T\cap L$ and
$R^{\prime}=T\cap R$. Without loss of generality, assume that
$|L^{\prime}|\geq|R^{\prime}|$, then $|L^{\prime}|\geq|T|/2$.

  * •

If $\chi N\leq|L^{\prime}|\leq N$, by the injection property of a perfect
matching and $|T|\leq N$, we know that $|\Gamma(L^{\prime})\backslash
L^{\prime}|\geq|L^{\prime}|\geq\chi N$ and $|R^{\prime}|\leq(1-\chi)N$.
Therefore, there are at least $|L^{\prime}|-|R^{\prime}|\geq(2\chi-1)N$
neighbors of $L^{\prime}$ out of $T$, that is $|\Gamma(T)\backslash
T|\geq(2\chi-1)N$.

  * •

If $|L^{\prime}|\leq\chi N$, we know that $|\Gamma(L^{\prime})\backslash
L^{\prime}|\geq(1+\delta)|L^{\prime}|$. In addition to the vertices in the set
$L^{\prime}$, there are at most $|R^{\prime}|$ neighbors of $L^{\prime}$ that
are in $T$. Therefore $L^{\prime}$ has at least
$|L^{\prime}|-|R^{\prime}|\geq\delta|L^{\prime}|\geq\frac{\delta}{2}|T|$
neighbors that are not contained in $T$. As a result, for any subset
$T\subseteq L\cup R$ and $|T|\leq N$, we have$|\Gamma(T)\backslash
T|\geq\frac{\delta}{2}|T|$. In other words, for any subset $T\subseteq L\cup
R$, we have

$|\Gamma(T)\backslash T|\geq\frac{\delta}{2}|T|.$

Thus, for any subset $T\subseteq L\cup R$ with $|T|\leq N$, with probability
$1-1/\Theta(N^{2\log(3/2)(1-\delta)})$, we have $|\Gamma(T)\backslash
T|\geq\delta|T|/2$. ∎

##  Appendix C Robust subspace eigenstate filtering

We will use the quantum singular value transformation (QSVT) technique
[GSLW19, LC17], and the minimax filtering polynomial proposed in [LT19] to
implement the projection operator to the $0$-eigenspace of the effective
Hamiltonian. The filtering polynomial takes the form

$R_{\ell}(x;\delta)=\frac{T_{\ell}\left(-1+2\frac{x^{2}-\delta^{2}}{1-\delta^{2}}\right)}{T_{\ell}\left(-1+2\frac{-\delta^{2}}{1-\delta^{2}}\right)},$
(42)

where $T_{\ell}(x)$ is the $\ell$th Chebysehv polynomial of the first kind,
and the degree of the polynomial is therefore $\ell$. This polynomial peaks at
$x=0$ and is close to $0$ for $\delta\leq|x|\leq 1$. It is minimax in the
sense that the deviation from $0$ for $\delta\leq|x|\leq 1$ is minimal among
all polynomials of degree $\ell$ that take value $1$ at $x=0$.

The properties of $R_{\ell}(x;\delta)$ are stated in [LT19, Lemma 2], which we
restate here:

######  Lemma C.1 (Lemma 2 of [LT19]).

Let $R_{\ell}(x;\delta)$ be as defined in (42). It satisfies the following:

  * (i)

$R_{\ell}(x;\delta)$ solves the minimax problem

$\underset{p(x)\in\mathbb{P}_{2\ell}[x],p(0)=1}{\mathrm{minimize}}\max_{x\in\mathcal{D}_{\delta}}|p(x)|.$

  * (ii)

$|R_{\ell}(x;\delta)|\leq 2e^{-\sqrt{2}\ell\delta}$ for all
$x\in\mathcal{D}_{\delta}$ and $0<\delta\leq 1/\sqrt{12}$. Also
$R_{\ell}(0;\delta)=1$.

  * (iii)

$|R_{\ell}(x;\delta)|\leq 1$ for all $|x|\leq 1$.

A fact that we will use later is that, by Markov brothers’ inequality,

$\max_{-1\leq x\leq
1}\left|\frac{\mathrm{d}}{\mathrm{d}x}R_{\ell}(x;\delta)\right|\leq
4\ell^{2}\max_{-1\leq x\leq 1}|R_{\ell}(x;\delta)|\leq 4\ell^{2},$ (43)

where we have used the fact that the degree of $R_{\ell}(x;\delta)$ is
$2\ell$.

We will use the above polynomial to construct the projection operator.

######  Lemma C.2.

Let $A$ be a Hermitian matrix acting on the Hilbert space $\mathcal{H}$, with
$\|A\|\leq\alpha$. Let $\mathcal{S}$ be an invariant subspace of $A$. Let $H$
be the restriction of $A$ to $\mathcal{S}$. We assume that $0$ is an
eigenvalue of $H$ (can be degenerate), and is separated from the rest of the
spectrum of $H$ by a gap at least $\Delta$. Then

$\|R_{\ell}(A/\alpha;\delta)\Pi_{\mathcal{S}}-\Pi_{0}\Pi_{\mathcal{S}}\|\leq
2e^{-\sqrt{2}\ell\delta},$

where $R_{\ell}(x;\delta)$ is defined in (42),
$\delta=\min\\{\Delta/\alpha,1\sqrt{12}\\}$,
$\Pi_{0}:\mathcal{S}\to\mathcal{S}$ is the projection operator into the
$0$-eigenspace of $H$, and $\Pi_{\mathcal{S}}:\mathcal{H}\to\mathcal{S}$ is
the projection operator into the invariant subspace $\mathcal{S}$.

###### Proof.

We first note that because $\mathcal{S}$ is an invariant subspace of $A$, and
therefore is an invariant subspace of $A^{k}$. As a result, we have

$A^{k}\Pi_{\mathcal{S}}=H^{k}\Pi_{\mathcal{S}},$

where we have used the fact that the image of $\Pi_{\mathcal{S}}$ is
$\mathcal{S}$ and that $H$ is the restriction of $A$ to $\mathcal{S}$. By
linearity, this extends to all polynomials of $A$: for any polynomial $p(x)$,

$p(A)\Pi_{\mathcal{S}}=p(H).$

Because $R_{\ell}(A/\alpha;\delta)$ is a polynomial of $A$, we have

$R_{\ell}(A/\alpha;\delta)\Pi_{\mathcal{S}}=R_{\ell}(H/\alpha;\delta).$

Therefore

$R_{\ell}(A/\alpha;\delta)\Pi_{\mathcal{S}}-\Pi_{0}\Pi_{\mathcal{S}}=(R_{\ell}(H/\alpha;\delta)-\Pi_{0})\Pi_{\mathcal{S}}.$

because $\|\Pi_{\mathcal{S}}\|=1$ it suffices to prove that

$\|R_{\ell}(H/\alpha;\delta)-\Pi_{0}\|\leq 2e^{-\sqrt{2}\ell\delta},$ (44)

which can be done by examining each eigenstate of $H$, given that both
$R_{\ell}(H/\alpha;\delta)$ and $\Pi_{0}$ are diagonal in the eigenbasis of
$H$. For an eigenstate $\ket{\Psi}$ of $H$ and its corresponding eigenvalue
$\lambda$, if $\lambda=0$, then

$(R_{\ell}(H/\alpha;\delta)-\Pi_{0})\ket{\Psi}=R_{\ell}(0;\delta)\ket{\Psi}-\ket{\Psi}=0.$

If $\lambda\neq 0$, then by the assumption of the spectral gap, we have
$|\lambda|\geq\Delta/\alpha\geq\delta$. We therefore have

$\|(R_{\ell}(H/\alpha;\delta)-\Pi_{0})\ket{\Psi}\|=\|(R_{\ell}(\lambda/\alpha;\delta)\ket{\Psi}\|=|R_{\ell}(\lambda/\alpha;\delta)|\leq
2e^{-\sqrt{2}\ell\delta},$

where we have used (C.1) (ii) and the fact that $\delta\leq 1/\sqrt{12}$.
Therefore we have proved (44). ∎

We will then combine the above lemmas with QSVT to provide a robust
implementation of the $0$-eigenspace projection operator of $\tilde{H}$, as
stated in Theorem 5.1, which we restate here.

######  Theorem C.3 (Robust subspace eigenstate filtering).

Let $A$ be a Hermitian matrix acting on the Hilbert space $\mathcal{H}$, with
$\|A\|\leq\alpha$. Let $\mathcal{S}$ be an invariant subspace of $A$. Let $H$
be the restriction of $A$ to $\mathcal{S}$. We assume that $0$ is an
eigenvalue of $H$ (can be degenerate), and is separated from the rest of the
spectrum of $H$ by a gap at least $\Delta$.

We also assume that $A$ can be accessed through its
$(\alpha,\mathfrak{m},\epsilon_{A})$-block encoding $U_{A}$ acting on
$\beta_{1},\beta_{2}$ as defined in Definition 2.8. Then there exists a
unitary circuit $\mathcal{V}_{\mathrm{circ}}$ on registers
$\alpha,\beta_{1},\beta_{2}$ such that

$\|(\bra{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}})\mathcal{V}_{\mathrm{circ}}(\ket{0}_{\alpha\beta_{1}}\otimes\Pi_{\mathcal{S}})-\Pi_{0}\Pi_{\mathcal{S}}\|\leq\epsilon+\varsigma,$
(45)

where

$\varsigma=\frac{16\ell^{2}\epsilon_{A}}{\alpha}\left[\log\left(\frac{2\alpha}{\epsilon_{A}}+1\right)+1\right]^{2},$
(46)

and it uses $2\ell=\mathcal{O}((\alpha/\Delta)\log(1/\epsilon))$ queries to
(control-) $U_{A}$ and its inverse, as well as $\mathcal{O}(\ell\mathfrak{m})$
other single- or two-qubit gates. In the above
$\Pi_{0}:\mathcal{S}\to\mathcal{S}$ is the projection operator into the
$0$-eigenspace of $H$, and $\Pi_{\mathcal{S}}:\mathcal{H}\to\mathcal{S}$ is
the projection operator into the invariant subspace $\mathcal{S}$.

###### Proof.

Similar to Lemma C.2, we let $\delta=\min\\{\Delta/\alpha,1\sqrt{12}\\}$.
First, we denote $\tilde{A}=\alpha(\bra{0}_{\beta_{1}}\otimes
I_{\beta_{2}})U_{A}(\ket{0}_{\beta_{1}}\otimes I_{\beta_{2}})$, then according
to Definition 2.8 we have

$\|\tilde{A}-A\|\leq\epsilon_{A}.$

Moreover, $U_{A}$ is now a $(\alpha,\mathfrak{m},0)$-block encoding of
$\tilde{A}$. Therefore we can implement a singular value transformation
$R^{\mathrm{SV}}_{\ell}(\tilde{A}/\alpha;\delta)$ using quantum singular value
transformation [GSLW19, Theorem 2].333For an even function $f$, the singular
value transformation of $A$ with singular value decomposition $A=U\Sigma
V^{\dagger}$ is defined to be $f^{\mathrm{SV}}(A)=Vf(\Sigma)V^{\dagger}$
[GSLW18]. More precisely, we can construct a circuit
$\mathcal{V}_{\mathrm{circ}}$ such that

$(\bra{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}})\mathcal{V}_{\mathrm{circ}}(\ket{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}})=R^{\mathrm{SV}}_{\ell}(\tilde{A}/\alpha;\delta).$ (47)

The same theorem also tells us that this circuit uses the block encoding
$U_{A}$ $d=2\ell$ times, which is the degree of the polynomial
$R_{\ell}(\cdot;\delta)$.444The readers may find [GSLW19, Theorem 2] ambiguous
in the parameters used in the block encoding. We remark that in [GSLW19], they
use “block encoding of $A$” to mean an $(1,m,0)$-block encoding in the context
of our work. See [GSLW19, Eq. (1)].

Note that instead of the singular value transformation of $\tilde{A}$, we
actually want to implement an eigenvalue transformation of $A$. We observe
that because $A$ is Hermitian, its singular value transformation coincides
with its eigenvalue transformation, i.e.,
$R^{\mathrm{SV}}_{\ell}(A/\alpha;\delta)=R_{\ell}(A/\alpha;\delta)$. Moreover,
$R^{\mathrm{SV}}_{\ell}(A/\alpha;\delta)$ is not far from
$R^{\mathrm{SV}}_{\ell}(\tilde{A}/\alpha;\delta)$, which we will show next.

By (43) and the intermediate value theorem, we have

$|R_{\ell}(x;\delta)-R_{\ell}(y;\delta)|\leq 4\ell^{2}|x-y|$

for any $x,y\in[-1,1]$. Since $R_{\ell}(\cdot;\delta)$ is an even polynomial,
from [GSLW18, Corollary 21] we know that

$\|R_{\ell}(A/\alpha;\delta)-R^{\mathrm{SV}}_{\ell}(\tilde{A}/\alpha;\delta)\|=\|R^{\mathrm{SV}}_{\ell}(A/\alpha;\delta)-R^{\mathrm{SV}}_{\ell}(\tilde{A}/\alpha;\delta)\|\leq\varsigma,$

for $\varsigma$ given in (29). Combined with (47), we have

$\|(\bra{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}}){\mathcal{V}}_{\mathrm{circ}}(\ket{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}})-R_{\ell}(A/\alpha;\delta)\|\leq\varsigma.$ (48)

By Lemma C.2, we have

$\|R_{\ell}(A/\alpha;\delta)\Pi_{\mathcal{S}}-\Pi_{0}\Pi_{\mathcal{S}}\|\leq
2e^{-\sqrt{2}\ell\delta}.$

Combining the above inequality with (48) via the triangle inequality, we then
have

$\|(\bra{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}}){\mathcal{V}}_{\mathrm{circ}}(\ket{0}_{\alpha\beta_{1}}\otimes
I_{\beta_{2}})\Pi_{\mathcal{S}}-\Pi_{0}\Pi_{\mathcal{S}}\|\leq\varsigma+2e^{-\sqrt{2}\ell\delta}.$
(49)

In order to make $2e^{-\sqrt{2}\ell\delta}\leq\epsilon$, it suffices to choose

$\ell=\mathcal{O}\left(\frac{1}{\delta}\log(1/\epsilon)\right)=\mathcal{O}\left(\frac{\alpha}{\Delta}\log(1/\epsilon)\right).$

We therefore have (45). ∎

##  Appendix D Spectrum estimates

We will use the following lemma to upper bound the matrix spectral norm.

######  Lemma D.1.

Let $A=(A_{ij})_{n\times n}$ be a Hermitian matrix. Then

$\|A\|\leq\max_{\ket{x}:\|\ket{x}\|_{\infty}\leq
1}\|A\ket{x}\|_{\infty}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|A_{ij}|,$

where $\|\cdot\|_{\infty}$ denotes the infinity norm.

This result in fact holds for any general matrix. To prove that we only need
to dilate the matrix $A$ to be $\begin{pmatrix}0&A\\\
A^{\dagger}&0\end{pmatrix}$. We will not discuss the detail because we are
only going to use the Hermitian version.

###### Proof.

Because $A$ is Hermitian, either $\|A\|$ or $-\|A\|$ must be an eigenvalue of
$A$. Therefore there exists $\ket{\phi}$ such that
$A\ket{\phi}=\pm\|A\|\ket{\phi}$ and $\|\ket{\phi}\|_{\infty}=1$. Consequently
$\|A\ket{\phi}\|_{\infty}=\|A\|$, and this proves the inequality. The equality
can be easily checked and we omit the proof. ∎

We will then prove Lemma 4.7 in the main text, which we restate below:

######  Lemma.

Let

$D_{1}=\begin{pmatrix}0&t_{1}&&&\\\ t_{1}&0&t_{2}&&\\\ &t_{2}&0&\ddots&\\\
&&\ddots&\ddots&t_{m-1}\\\ &&&t_{m-1}&0\end{pmatrix}_{m\times m}$ (50)

as defined in (50), in which $t_{1}=\sqrt{d-2}$,
$t_{2}=\cdots=t_{m-1}=\sqrt{d-1}$. Then $D_{1}$ has a non-degenerate
0-eigenstate $\ket{\Psi}=(\Psi_{1},\Psi_{2},\cdots,\Psi_{m})^{\top}$ where

$\Psi_{j}=\prod_{k=1}^{(j-1)/2}\left(-\frac{t_{2k-1}}{t_{2k}}\right)\Psi_{1}=(-1)^{(j-1)/2}\sqrt{\frac{d-2}{d-1}}\Psi_{1},\quad\text{for
all odd }j\geq 2,$

and $\Psi_{j}=0$ for even $j$. Moreover, 0 is separated from the rest of the
spectrum of $D_{1}$ by a gap of at least $2\sqrt{d-2}/(m-1)$.

###### Proof.

First, we prove that 0 is an eigenvalue of $D_{1}$. The can be done by
verifying $D_{1}\ket{\Psi}=0$ for the $\ket{\Psi}$ given above.

We then prove the non-degeneracy of the eigenvalue 0 and the spectral gap. We
do this through the eigenvalue interlacing theorem, which tells us that the
eigenvalues of $D_{1}$ must interlace those of $D_{1}^{\prime}$, where
$D_{1}^{\prime}$ is the $(m-1)\times(m-1)$ sub-matrix of $D_{1}$ on the upper-
left corner, i.e.,

$D_{1}^{\prime}=\begin{pmatrix}0&t_{1}&&&\\\ t_{1}&0&t_{2}&&\\\
&t_{2}&0&\ddots&\\\ &&\ddots&\ddots&t_{m-2}\\\
&&&t_{m-2}&0\end{pmatrix}_{(m-1)\times(m-1)}.$ (51)

We will therefore first study the spectrum of $D_{1}^{\prime}$.

We observe that $D_{1}^{\prime}$ is in fact an invertible matrix. Consider the
linear system $D_{1}^{\prime}\ket{x}=\ket{y}$, where
$\ket{x}=(x_{1},\cdots,x_{m-1})^{\top}$ and
$\ket{y}=(y_{1},\cdots,y_{m-1})^{\top}$, then we can compute the solution
$\ket{x}$ using the following recursion:

$\displaystyle x_{2k+2}$
$\displaystyle=\frac{y_{2k+1}}{t_{2k+1}}-\frac{t_{2k}}{t_{2k+1}}x_{2k},\quad\forall
k\geq 1,$ (52) $\displaystyle x_{2}$ $\displaystyle=\frac{y_{1}}{t_{1}},$
$\displaystyle x_{m-2k}$
$\displaystyle=\frac{y_{m-2k+1}}{t_{m-2k}}-\frac{t_{m-2k+1}}{t_{m-2k}}x_{m-2k+2},\quad\forall
k\geq 1$ $\displaystyle x_{m-2}$ $\displaystyle=\frac{y_{m-1}}{t_{m-2}}.$

Given the values of $t_{j}$, we observe that

$\frac{t_{2k}}{t_{2k+1}}=1,\quad\frac{t_{m-2k+1}}{t_{m-2k}}=\begin{cases}1,&\text{
if }k<(m-1)/2,\\\ \sqrt{\frac{d-1}{d-2}},&\text{ if }k=(m-1)/2.\\\
\end{cases}$

Therefore, for even entries we have

$|x_{2k+2}|\leq\left|\frac{y_{2k+1}}{t_{2k+1}}\right|+|x_{2k}|\leq\frac{(k+1)\|\ket{y}\|_{\infty}}{\sqrt{d-2}},$

For odd entries we have

$|x_{m-2k}|\leq\left|\frac{y_{m-2k+1}}{t_{m-2k}}\right|+|x_{m-2k+2}|\leq\frac{k\|\ket{y}\|_{\infty}}{\sqrt{d-1}},$

for $k<(m-1)/2$. For $k=(m-1)/2$, we have

$|x_{1}|\leq\left|\frac{y_{2}}{t_{1}}\right|+\sqrt{\frac{d-1}{d-2}}|x_{3}|\leq\frac{\|\ket{y}\|_{\infty}}{\sqrt{d-2}}+\frac{\|\ket{y}\|_{\infty}(m-3)/2}{\sqrt{d-2}}=\frac{\|\ket{y}\|_{\infty}(m-1)/2}{\sqrt{d-2}}.$

Therefore we have

$|x_{j}|\leq\frac{(m-1)\|\ket{y}\|_{\infty}}{2\sqrt{d-2}}$

for all $j$. From this we can see that if $\|\ket{y}\|_{\infty}\leq 1$, then

$\|(D_{1}^{\prime})^{-1}\ket{y}\|_{\infty}=\max_{j}|x_{j}|\leq\frac{(m-1)}{2\sqrt{d-2}}.$

Therefore by Lemma D.1 we have
$\|(D_{1}^{\prime})^{-1}\|\leq(m-1)/(2\sqrt{d-2})$. As a result the
eigenvalues of $D_{1}^{\prime}$ must be bounded away from 0 by at least
$2\sqrt{d-2}/(m-1)$.

Because by the eigenvalue interlacing theorem the eigenvalues of $D_{1}$
interlace those of $D_{1}^{\prime}$, if $0$ is a degenerate eigenvalue of
$D_{1}$, then there must exists an eigenvalue of $D_{1}^{\prime}$ between two
0’s, i.e., this eigenvalue of $D_{1}^{\prime}$ must also be 0. This is
impossible because we have just shown that $D_{1}^{\prime}$ is invertible.
This proves the non-degeneracy of 0 as an eigenvalue of $D_{1}$. If there is
an eigenvalue $\lambda$ of $D_{1}$ such that $|\lambda|<2\sqrt{d-2}/(m-1)$,
then there must exist an eigenvalue $\lambda^{\prime}$ of $D_{1}^{\prime}$
between 0 and $\lambda$, and therefore $|\lambda^{\prime}|<2\sqrt{d-2}/(m-1)$.
This is again impossible because we have just shown that all eigenvalues of
$D_{1}^{\prime}$ must be bounded away from 0 by at least $2\sqrt{d-2}/(m-1)$.
Therefore all non-zero eigenvalues of $D_{1}$ must be bounded away from 0 by
at least $2\sqrt{d-2}/(m-1)$. ∎

######  Lemma D.2 (Inverse of a nonsingular tridiagonal matrix [DFP01, Theorem
2.1]).

Let $H_{1}(a,b)$ be as defined in (24). Let $\sigma$, $\delta$ be the two $m$
dimensional vectors defined as follows:

  1. 1.

$\sigma_{m}=b$, $\sigma_{i}=-t_{i}^{2}/\sigma_{i+1}$ for $i=m-1,\ldots,2$,
$\sigma_{1}=a-t_{1}^{2}/\sigma_{2}$.

  2. 2.

$\delta_{1}=a$, $\delta_{i}=-t_{i-1}^{2}/\delta_{i-1}$ for $i=2,\ldots,m-1$,
$\delta_{m}=b-t_{m-1}^{2}/\sigma_{m-1}$.

Then the matrix element of the inverse of $H_{1}(a,b))$ is

$(H_{1}^{-1}(a,b))_{i,j}=\left\\{\begin{array}[]{ll}(-1)^{i+j}t_{i}\cdots
t_{j-1}\frac{\sigma_{j+1}\cdots\sigma_{m}}{\delta_{i}\cdots\delta_{m}}&\mbox{if
}i\leq j\\\ (-1)^{i+j}t_{j}\cdots
t_{i-1}\frac{\sigma_{i+1}\cdots\sigma_{m}}{\delta_{j}\cdots\delta_{m}}&\mbox{if
}i>j\\\ \end{array}\right.,$ (53)

with the convention that the empty product equals 1.

######  Corollary D.3.

Let $t_{1}=\sqrt{d-2}$, $t_{2}=t_{3}=\dots=t_{m-1}=\sqrt{d-1}$,
$\gamma=\frac{d-1}{2}$, for integer $d\geq 3$, and let $m$ be an odd integer.
Let $\mu_{l}=2\cos(2\pi l/n)$ with $l=0,1\ldots,n-1$ satisfying $\mu_{l}\neq
0$. Let $a=\mu_{l}$ and $b=\gamma\mu_{l}$. Then we have

$\max_{i,j}(H_{1}^{-1}(a,b))_{i,j}=O(1/|a|^{2})=O(n^{2}).$ (54)

###### Proof.

Since $t_{1}=\sqrt{d-2}$, $t_{2}=t_{3}=\ldots=t_{m-1}=\sqrt{d-1}$,
$\gamma=\frac{d-1}{2}$ and $m$ is an odd integer, we have
$t_{1}t_{2}=\sqrt{(d-2)(d-1)}$, $t_{i}t_{i+1}=(d-1)$ for $2\leq i\leq m-1$,
$\sigma_{1}=a\left(1+\frac{\gamma(d-1)}{d-2}\right)$,
$|\sigma_{i}\sigma_{i+1}|=(d-1)$ for $i=2,\ldots,m-1$ and $\delta_{1}=a$,
$|\delta_{i}\delta_{i+1}|=(d-1)$ for $2\leq i\leq m-2$,
$\delta_{m}=a(1+\frac{\gamma(d-1)}{d-2})$. We can then compute the two $m$
dimensional vectors $\sigma,\delta$ in Lemma D.2 to be:

  1. 1.

$\sigma_{i}=-\frac{(d-1)}{b},\sigma_{i+1}=b,$ for $i$ to be an even integer
from $m-1$ to $2$, $\sigma_{1}=a+\frac{b(d-1)}{(d-2)}$.

  2. 2.

$\delta_{1}=a$, $\delta_{i}=-(d-2)/a$, $\delta_{i+1}=\frac{a(d-1)}{(d-2)}$ for
$i$ to be an even integer from $2$ to $m-1$,
$\delta_{m}=b+\frac{a(d-1)}{(d-2)}$.

Using the results above we will compute upper bounds for the matrix entries
$(H_{1}^{-1}(a,b))_{i,j}$. Note that because $H_{1}(a,b)$ is Hermitian, we
only need to consider the case of $i\leq j$. By Lemma D.2 we have

$|(H_{1}^{-1}(a,b))_{i,j}|=\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\cdot\frac{1}{\delta_{j}}\cdot\frac{\sigma_{j+1}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+1}\delta_{j+2}\cdots\delta_{m}}.$
(55)

We will next deal with the three parts on the right-hand side separately.

For the first part $\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}$, we consider two different
cases. If $j-i$ is even, then

$\displaystyle\left|\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\right|$
$\displaystyle=\left|\frac{(t_{i}t_{i+1})(t_{i+2}t_{i+3})\cdots(t_{j-2}t_{j-1})}{(\delta_{i}\delta_{i+1})(\delta_{i+2}\delta_{i+3})\cdots(\delta_{j-2}\delta_{j-1})}\right|$
(56)
$\displaystyle=\left|\frac{t_{i}t_{i+1}}{t_{i}^{2}}\frac{t_{i+2}t_{i+3}}{t_{i+2}^{2}}\cdots\frac{t_{j-2}t_{j-1}}{t_{j-2}^{2}}\right|$
$\displaystyle=\left|\frac{t_{i+1}}{t_{i}}\frac{t_{i+3}}{t_{i+2}}\cdots\frac{t_{j-1}}{t_{j-2}}\right|$
$\displaystyle=\begin{cases}\sqrt{\frac{d-1}{d-2}}&\text{ if }i=1,\\\ 1&\text{
if }i\geq 2.\end{cases}$

Therefore

$\left|\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\right|\leq\sqrt{\frac{d-1}{d-2}},$
(57)

when $j-i$ is even.

When $j-i$ is odd, then

$\left|\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\right|=\left|\frac{t_{i}t_{i+1}\cdots
t_{j-2}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-2}}\right|\left|\frac{t_{j-1}}{\delta_{j-1}}\right|\leq\sqrt{\frac{d-1}{d-2}}\left|\frac{t_{j-1}}{\delta_{j-1}}\right|,$

where we have used (57). Note that

$\left|\frac{t_{j-1}}{\delta_{j-1}}\right|=\begin{cases}\frac{a\sqrt{d-1}}{d-2},&\text{
if }j\text{ is odd,}\\\ \frac{\sqrt{d-2}}{a},&\text{ if }j=2,\\\
\frac{d-2}{a\sqrt{d-1}},&\text{ otherwise.}\end{cases}$ (58)

Therefore

$\left|\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\right|\leq\max\left\\{\frac{a(d-2)}{(d-2)^{3/2}},\frac{\sqrt{d-1}}{a}\right\\},$
(59)

when $j-i$ is odd. Combining the above inequality with (57), we have

$\left|\frac{t_{i}t_{i+1}\cdots
t_{j-1}}{\delta_{i}\delta_{i+1}\cdots\delta_{j-1}}\right|=\mathcal{O}(1/a),$
(60)

for all pairs of $i\leq j$.

For the third part
$\frac{\sigma_{j+1}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+1}\delta_{j+2}\cdots\delta_{m}}$
in (55), when $m-j$ is even, which implies that $j$ is odd, we use the fact
that $\sigma_{l}\sigma_{l+1}=\delta_{l}\delta_{l+1}$ for $l\geq 2$ to show
that

$\frac{\sigma_{j+1}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+1}\delta_{j+2}\cdots\delta_{m}}=1.$

When $m-j$ is odd, which implies that $j$ is even,

$\frac{\sigma_{j+1}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+1}\delta_{j+2}\cdots\delta_{m}}=\frac{\sigma_{j+1}}{\delta_{j+1}}\frac{\sigma_{j+2}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+2}\delta_{j+2}\cdots\delta_{m}}=\frac{\sigma_{j+1}}{\delta_{j+1}}.$

Note that

$\left|\frac{\sigma_{j+1}}{\delta_{j+1}}\right|=\begin{cases}\frac{b(d-2)}{a(d-1)}=\frac{\gamma(d-2)}{d-1},&\text{
if }j<m-1,\\\ \frac{b(d-2)}{b(d-2)+a(d-a)}\leq 1,&\text{ if
}j=m-1.\end{cases}$

Therefore $\left|\frac{\sigma_{j+1}}{\delta_{j+1}}\right|=\mathcal{O}(1)$.
Consequently

$\left|\frac{\sigma_{j+1}\sigma_{j+2}\cdots\sigma_{m}}{\delta_{j+1}\delta_{j+2}\cdots\delta_{m}}\right|=\mathcal{O}(1).$
(61)

For the second part in (55), we readily have
$1/|\delta_{j}|=\mathcal{O}(1/a)$. Combining this with (60) and (61), we have
through (55),

$|(H_{1}^{-1}(a,b))_{i,j}|=\mathcal{O}(1/|a|^{2}).$ (62)

Note that because $a=2\cos(2l\pi/n)$, the smallest possible $|a|$ is

$|a|=2\sin(2\pi/n)=\Omega(1/n).$

Therefore we have the result as stated in this corollary. ∎

We will then prove the Lemma 4.6 in the main text, which we restate here:

######  Lemma.

Let $H_{1}(a,b)$ be as defined in (24), with odd $m$, $t_{1}=\sqrt{d-2}$,
$t_{2}=t_{3}=\dots=t_{m-1}=\sqrt{d-1}$, $\gamma=\frac{d-1}{2}$, for integer
$d\geq 3$. Let $\mu_{l}=2\cos(2\pi l/n)$ with $l=0,1\ldots,n-1$ satisfying
$\mu_{l}\neq 0$. Let $a=\mu_{l}$ and $b=\gamma\mu_{l}$. Then
$\|H_{1}^{-1}(a,b)\|=\mathcal{O}(mn^{2})$.

###### Proof.

This lemma is directly proved by combining Corollary D.3 with Lemma D.1. ∎


# Stabilizer Approximation III: Maximum Cut

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

###### Abstract

We apply the stabilizer formalism to the Maximum Cut problem, and obtain a new
greedy construction heuristic. It turns out to be an elegant synthesis of the
edge-contraction and differencing edge-contraction approaches. Though we are
unable to derive a theoretical approximation ratio, numerical results show
that the heuristic has very nice performance for graphs with about 100
vertices.

###### Contents

  1. I Introduction
  2. II Stabilizer Heuristic
    1. II.1 Max-Cut
    2. II.2 Edge Contraction
    3. II.3 Differencing Edge Contraction
    4. II.4 Stabilizer
      1. II.4.1 Example
  3. III Numerical Results
    1. III.1 Comparison with SG3
    2. III.2 Comparison with GW
    3. III.3 Further test
  4. IV Discussion

##  I Introduction

The Maximum Cut problem for weighted undirected graphs, Max-Cut, is NP-hard.
On the contrary, the Minimum Cut problem, Min-Cut, can be solved in polynomial
time when the weights are non-negative. Typical algorithms for solving Min-Cut
utilize the vertex-identifying and edge-contraction operations Cook-1998 . So
one may wonder, can we use these operations to construct approximate
algorithms for Max-Cut?

In 2007 a greedy heuristic for Max-Cut was conceived using Edge Contraction
(EC) Kahruman-2007 . The approximation ratio was prove to be at least $1/3$.
However, numerical results show that the heuristic performs worse than the
very first Sahni-Gonzalez (SG) algorithm SG-1976  and its improved versions
Kahruman-2007 .

A variation of the EC heuristic, Differencing Edge-Contraction (DEC), was
proposed recently in Hassin-2021 . The relation between EC and DEC is clear:
while EC is a “worst-out” approach, DEC is a “best-in” one. Moreover, even if
the original weights are non-negative, negative weights could appear during
DEC. This makes it difficult to derive a theoretical approximation ratio for
the algorithm. However, numerical analysis shows that its performance could
even compete with perhaps the best version of the Sahni-Gonzalez algorithm,
SG3 Kahruman-2007 .

Could we make a synthesis of these two heuristics and obtain a “best-in-worst-
out” approach? Yes! In the following sections we present the details of such
an approach. But before that, we would like to briefly explain how the idea
comes out. It has long been known that Max-Cut is closely related to the
classical Ising model in statistical physics. In Ising model one tries to
obtain the spin state with the lowest energy, the ground state. The spin
states could be specified by the spins at the vertices, or by their relations
on the edges. Roughly speaking, independent operators generating these
relations are defined as “stabilizer generators”, or simply “stabilizers”. For
an introduction to the stabilizer formalism, see ref. Gottesman98 , Chapter 10
of Nielsen-Chuang-2010  and references therein. Our heuristic thus proceeds by
searching these stabilizers greedily to minimize the total energy of the Ising
model. After translating the whole process back into Max-Cut, we forget all
these physical interpretations and get a pure graphical algorithm, which we
still call “Stabilizer”.

##  II Stabilizer Heuristic

###  II.1 Max-Cut

Given a weighted undirected graph $G=(V,E,w)$ with $V=\\{1,2,...,n\\}$ and
weights $w:E\to\mathbb{R}$, an assignment $z:V\to\\{-1,+1\\}$ defines a cut of
$G$

$c(z):=\\{(i,j)|z_{i}z_{j}=-1,i,j=1,2,...,n\\},$ (1)

and the corresponding cut weight

$w(z):=\sum_{(i,j)\in c(z)}w_{i,j}=\frac{1}{2}\sum_{1\leq i<j\leq
n}w_{ij}(1-z_{i}z_{j}).$ (2)

The Max-Cut problem aims to find the cut with the maximum weight.

Define

$U:=\\{i|z_{i}=+1,i=1,2,...,n\\},\quad D:=\\{i|z_{i}=-1,i=1,2,...,n\\},$ (3)

then a cut of $G$ can also be expressed as

$c(U,D):=E(U,D):=\\{(i,j)|i\in U,j\in D\\},$ (4)

with the weight

$w(U,D):=\sum_{i\in U,j\in D}w_{ij}.$ (5)

One may conceive approximate algorithms by constructing $U$ and $D$
iteratively, such as the Sahni-Gonzalez algorithm SG-1976  and its improved
versions Kahruman-2007 . The original SG algorithm operates in a pre-chosen
order, and at each step makes the assignment according to the rule SG-1976 :

$\mbox{if}\quad w(i,U)<w(i,D),\leavevmode\nobreak\ \mbox{then}\quad
U\leftarrow U\cup\\{i\\},\leavevmode\nobreak\ \mbox{else}\quad D\leftarrow
D\cup\\{i\\}.$ (6)

Here $w(i,U)$ and $w(i,D)$ are defined for $i\in V\setminus(U\cup D)$ as:

$w(i,U):=\sum_{j\in U}w_{ij},\quad w(i,D):=\sum_{j\in D}w_{ij}.$ (7)

The improved versions Kahruman-2007  differ from the original SG by the
construction order. In SG3 one first chooses the vertex

$i^{*}=\arg\max_{i\in V\setminus(U\cup D)}|w(i,U)-w(i,D)|$ (8)

at each step. Then one makes the update of $U$ and $D$ according to (6) as in
SG. Both SG and SG3 have the approximation ratio $1/2$, but SG3 outperforms SG
a lot numerically Kahruman-2007 .

###  II.2 Edge Contraction

The EC heuristic bears remarkable similarity to the vertex-identifying and
random contraction algorithms for Min-Cut Cook-1998 . At each step, EC chooses
the edge, say $(i,j)$, with the minimum weight, and contracts it. Then
vertices $i$ and $j$ are replaced by a new vertex $ij$. Multiple edges appear
after this operation. For a vertex $k$ distinct from $i$ and $j$, the
resulting multiple edge between $k$ and $ij$ is replaced by a new edge, with
the updated weight

$w_{ij,k}=w_{i,k}+w_{j,k}.$ (9)

The algorithm terminates when there is only one edge left, say $(u,d)$. Then
all the vertices contracted to give $u$ forms $U$, and those contracted to
give $d$ forms $D$. The cut weight is simply $w(u,d)$.

The approximation ratio of EC, taking the total weight as reference, is proved
to be at least $1/3$. Numerical analysis verifies that it is strictly smaller
than $1/2$. For concrete instances, the heuristic could occasionally
outperform SG, but on average it performs worse than SG, and much worse than
SG3.

###  II.3 Differencing Edge Contraction

Obviously EC belongs to the “worst-out” approaches for Max-Cut. The
corresponding “best-in” approach gives the DEC algorithm. Therefore, at east
step DEC chooses the edge with the maximum positive weight, and contracts it
in a differencing way. Contrary to EC, DEC needs to be done with a direction
for the edge. For example, if we merge $j$ to $i$, the new vertex will be
labeled by the expression $i-j$, and the weight of the resulting multiple edge
is updated as

$w_{i-j,k}=w_{i,k}-w_{j,k}.$ (10)

So the resulting weights depend on the contraction directions. It turns out
that if one chooses the direction to maximize the total weight, the
performance of the algorithm would be better. The algorithm terminates when
there is no positive-weight edge remaining. Then $U$ are formed by those
vertices with even numbers of minus signs in the contraction labels, and $D$
by those with odd numbers of minus signs.

DEC does not guarantee a lower bound for the approximation ratio. Numerically,
it perform strictly better than SG3 for certain instances, but worse for some
others.

###  II.4 Stabilizer

The stabilizer heuristic could be viewed as a synthesis of EC and DEC, even
though it does not come out in this way. So it is a “best-in-worst-out”
approach. The idea is very simple: at each step one chooses the edge in such a
way that the absolute value of its weight is maximized. Then, if the weight is
negative, we perform EC; if it is positive, we perform DEC. When doing DEC,
the direction will be arbitrarily chosen. The details of the algorithm are
summarized in the following pseudo-code.

Algorithm 1 The Stabilizer Heuristic

Input: A complete weighted graph $G=(V,E,w)$ with $V=\\{1,2,...,n\\}$ and
$w:E\to\mathbb{R}$

Output: A cut $z:V\to\\{-1,+1\\}$ and the cut weight $w(z)$

$V^{\prime}\leftarrow V$, $E^{\prime}\leftarrow E$

$S\leftarrow\varnothing$

while $E^{\prime}\neq\varnothing$ and $\max_{e\in E^{\prime}}|w(e)|\neq 0$ do

$(i,j)\leftarrow\arg\max_{e\in E^{\prime}}|w(e)|$

$z_{ij}\leftarrow-\frac{w_{ij}}{|w_{ij}|}$, $S\leftarrow S\cup\\{(i,j)\\}$

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

for $k\in V^{\prime}\setminus\\{j\\}$ do

$w_{jk}\leftarrow w_{jk}+z_{ij}w_{ik}$

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

end for

end while

Partition forest $(V,S)$ into trees $(V_{l},S_{l}),l=1,...,m$,
$V=\uplus_{1\leq l\leq m}V_{l}$, $S=\uplus_{1\leq l\leq m}S_{l}$

for $1\leq l\leq m$ do

choose a base vertex $i_{l}\in V_{l}$

$z_{i_{l}}\leftarrow+1$

for $j_{l}\in V_{l}\setminus\\{i_{l}\\}$ do

$z_{j_{l}}\leftarrow+1$

find the $(i_{l},j_{l})$-path $P\subset(V_{l},S_{l})$

for edge $e\in E(P)$ do

$z_{j_{l}}\leftarrow z_{j_{l}}z_{e}$

end for

end for

end for

$w(z)\leftarrow\frac{1}{2}\sum_{1\leq i<j\leq n}w_{ij}(1-z_{i}z_{j})$

The assertion that the resulting graph $(V,S)$ is a forest is obvious from the
construction. We may call $(V,S)$ the stabilizer forest. It is also not quite
difficult to figure out that the choice of the DEC direction does not matter
here. Thus we settle the direction problem raised in Hassin-2021 . The time
complexity of the algorithm is the same as EC and DEC. Therefore, in a naive
implementation, the complexity is $\mbox{O}(n^{3})$. This can be reduced to
$\mbox{O}(n^{2}\log n)$ if we use a sorted data structure.

####  II.4.1 Example

We take the example in Hassin-2021  to illustrate the procedure. We
intentionally choose different contraction directions from those in DEC, to
show that the results do not depend on the choices. Notice that different
choices may result in different operation steps.

The whole procedure is listed step by step in Figure. 9:
Step 1: input the original graph.
Step 2: pick out edge $(2,4)$ as the absolute value of its weight is largest,
set $z_{24}=-\frac{w_{24}}{|w_{24}|}=-1$.
Step 3: select vertex $4$ incident to $(2,4)$. For all the other edges
incident to vertex $4$, transfer them to vertex $2$ along $(2,4)$, merge them
with the original edges, and update the weights as: $w_{2k}\leftarrow
w_{2k}+z_{24}w_{4k}$, $k=1,3,5$. Since $(2,5)$ does not exist in the original
graph, set its initial weight to $w_{25}=0$.
Step 4: pick out $(1,5)$, set $z_{15}=-1$.
Step 5: select vertex $1$, transfer $(1,2)$ to $(2,5)$, and update the weight
as $w_{25}\leftarrow w_{25}-w_{12}$.
Step 6: pick out $(2,5)$, set $z_{25}=+1$.
Step 7: select vertex $2$, transfer $(2,3)$ to $(3,5)$, and update the weight
as $w_{35}\leftarrow w_{35}+w_{23}$. The initial weight of $(3,5)$ is again
set to $w_{35}=0$, since $(3,5)$ does not exist in the original graph.
Step 8: pick out $(3,5)$, set $z_{35}=+1$.
The resulting graph is a tree, and all the edges of it have been assigned a
definite sign. From these information it is not difficult to figure out the
corresponding cut is given by $U=\\{2,3,5\\},D=\\{1,4\\}$. The cut weight can
then be calculated to be $w(U,D)=30$.

Figure 1: Step 1

Figure 2: Step 2

Figure 3: Step 3

Figure 4: Step 4

Figure 5: Step 5

Figure 6: Step 6

Figure 7: Step 7

Figure 8: Step 8

Figure 9: Illustration of the Stabilizer Heuristic procedure.

##  III Numerical Results

Now we apply the stabilizer heuristic to some concrete instances to test its
performance. The heuristic was implemented in the Python programming language
(v3.6.13), and tested on a PC equipped with a 3.3GHz AMD Zen 3 Ryzen 9
processor (only use 1 core) and 2GB of RAM operating under the Microsoft
Windows 11 environment. We list the computation time for some instances to
show how they vary with the graph sizes.

###  III.1 Comparison with SG3

Since EC performs worse than SG3 and DEC has roughly similar performance as
SG3, it will be interesting to see if the stabilizer heuristic, as a synthesis
of the two, outperforms SG3. As in Kahruman-2007 , we take some Traveling
Salesman Problem (TSP) instances from the TSPLIB TSPLIB  to make the
comparison.

Instance | Size | Total weight | Stabilizer cut weight | Stabilizer cut ratio | SG3 cut ratio | Stabilizer time (s)
---|---|---|---|---|---|---
gr17 | $17$ | $37346$ | $24986$ | $0.669$ | $0.669$ | $0.07$
bayg29 | $29$ | $66313$ | $42693$ | $0.644$ | $0.564$ | $0.47$
hk48 | $48$ | $1153784$ | $771712$ | $0.669$ | $0.669$ | $2.91$
berlin52 | $52$ | $762783$ | $470726$ | $0.617$ | $0.617$ | $3.86$
brazil58 | $58$ | $3523646$ | $2208793$ | $0.627$ | $0.564$ | $5.81$
Table 1: Summary of results of the Stabilizer and SG3 algorithms on TSPLIB
instances.

In Table 1 we list the results calculated with the stabilizer heuristic and
the SG3 algorithm. We do not include the other 4 TSP instances presented in
Kahruman-2007  because the corresponding graphs have been updated. And for
“berlin52” we round off all the weights to integers, so that the total weight
agrees with that in Kahruman-2007 . All the cut ratios are defined using the
total weight as reference. Out of the 5 instances included in Table 1, the
stabilizer heuristic gives the same results as SG3 for 3 of them, and much
better results for the remaining 2, namely “bayg29” and “brazil58”.

###  III.2 Comparison with GW

We make further comparison with the results from the Goemans-Williamson (GW)
algorithm GW-1995  based on semi-definite programming (SDP). We take the same
TSPLIB instances as in GW-1995  except “gr96", which has been updated. The
results from both algorithms are summarized in Table 2.

Instance | Size | Optimal cut weight | GW cut weight | Stabilizer cut weight | Stabilizer time (s)
---|---|---|---|---|---
dantzig42 | $42$ | $42638$ | $42638$ | $42638$ | $1.61$
gr48 | $48$ | $320277$ | $320277$ | $320277$ | $2.69$
hk48 | $48$ | $771712$ | $771712$ | $771712$ | $2.69$
kroA100 | $100$ | $5897392$ | $5897392$ | $5897392$ | $44.62$
kroB100 | $100$ | $5763047$ | $5763047$ | $5763047$ | $44.90$
kroC100 | $100$ | $5890760$ | $5890760$ | $5890760$ | $44.74$
kroD100 | $100$ | $5463250$ | $5463250$ | $5463250$ | $44.61$
kroE100 | $100$ | $5986591$ | $5986591$ | $5986591$ | $44.62$
gr120 | $120$ | $2156667$ | $2156667$ | $2156667$ | $91.53$
Table 2: Summary of results of Stabilizer and GW algorithms on TSPLIB
instances.

Quite unexpectedly, the stabilizer heuristic gives the optimal cut for all the
instances, the same as the GW algorithm. This is a remarkable achievement,
considering the performance of various other heuristics on these instances
Commander-2008 .

###  III.3 Further test

It is not difficult to devise graphs that get all the EC, DEC and Stabilizer
heuristics into trouble. This is a typical example:

Figure 10: A special instance for which EC, DEC and Stabilizer heuristics all
fail to give the optimal cut.

The optimal cut value is $4$, while all three heuristics give $3.5$. Actually,
the approximation ratio can approach $3/4$ from above if the weight of the
central edge approaches $1$ from above. So even if we could derive a
theoretical approximation ratio for the stabilizer heuristic, it would be at
most $3/4$, much lower than the ratio $.878$ of the GW algorithm.

To see the performance of the stabilizer heuristic beyond TSPLIB instances, we
test it on the Balasundaram-Butenko instances constructed in BB-2005 . The
results are summarized in Table 3.

Instance | Size | Optimal Value | Stabilizer Value
---|---|---|---
G5-1 | $5$ | $126$ | $126$
G5-2 | $5$ | $40$ | $40$
G8-1 | $8$ | $1987$ | $1987$
G8-2 | $8$ | $1688$ | $1688$
G10-1 | $10$ | $1585$ | $1585$
G10-2 | $10$ | $1377$ | $1351$
G15-1 | $15$ | $399$ | $390$
G15-2 | $15$ | $594$ | $594$
G20-1 | $20$ | $273$ | $271$
G20-2 | $20$ | $285$ | $282$
Table 3: Summary of results of Stabilizer Heuristic on Balasundaram-Butenko
instances BB-2005 .

Out of the $10$ instances, the stabilizer heuristic only give the optimal cut
for $6$ instances. The maximum deviation occurs for “G15-1”, and the deviation
is about $2.3\%$. This is not too bad, compared to the results from the other
approaches Commander-2008 .

##  IV Discussion

The stabilizer formalism is utilized to find approximate solutions of the Max-
Cut problem. Quite unexpectedly, this leads to an elegant construction
heuristic, which perfectly integrates the EC and DEC approaches together. For
diverse instances, the new heuristic outperforms the improved versions of the
SG algorithm, and can even compete with the renowned GW algorithm based on
SDP. Although we are unable to derive a constant approximation ratio for it,
its elegancy and remarkable performance indicates that it would be “fast,
simple and effective in practice” Kahruman-2007 .

Why would the stabilizer formalism, a formalism developed for quantum
computation specifically, finds use in such a classical problem as Max-Cut?
The answer is very simple: the classical world is just a special limit of the
quantum world. In principle, all classical problems could be lifted to a
proper quantized version. A typical example is the quantum lifting of the Max-
kSAT problem to the k-LOCAL HAMILTONIAN problem Kitaev-2002 . Quantum thinking
for the lifted problem could provide new ideas and approaches for the original
problem. The stabilizer heuristic presented here is just a manifestation of
such a logic.

Of course the influence should be bidirectional. Many results and proofs in
Kitaev-2002  are obtained following the classical line, especially the Cook-
Levin theorem Cook-1971 ; Levin-1973 . Thus one may wonder, could we develop a
kind of quantum GW algorithm for Max-Cut or its quantum version?

## References

  * (1) William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver, 1998,  Combinatorial Optimization.  John Wiley & Sons, Inc.
  * (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 (3) 211-218.
  * (3) S. Sahni, T. Gonzales, 1976,  P-complete approximation problems, Journal of the ACM, 23 (3) 555-565.
  * (4) Refael Hassin, Nikita Leshenko, 2021,  Greedy Differencing Edge-Contraction heuristic for the Max-Cut problem, Operations Research Letters 49 (2021) 320-325.
  * (5) Daniel Gottesman, 1998,  The Heisenberg Representation of Quantum Computers, [https://arxiv.org/abs/quant-ph/9807006].
  * (6) Michael A. Nielsen, Isaac L. Chuang, 2010,  Quantum Computation and Quantum Information, 10th Anniversary Edition,  Cambridge University Press.
  * (7) G. Reinelt,1991,  TSPLIB - a traveling salesman problem library, ORSA Journal on Computing, 3:376-384, [http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/].
  * (8) M. Goemans and D.P. Williamson, 1995,  Improved approximation algorithms for MAX-CUT and satisfiability problems using semidefinite programming, Journal of the ACM, 42:1115-1145, 1995.
  * (9) Clayton W. Commander, 2008,  Maximum Cut Problem, MAX-CUT. In:  Encyclopedia of Optimization,  C. Floudas, P. Pardalos (eds), Springer, Boston, MA.
  * (10) B. Balasundaram and S. Butenko, 2005,  Constructing test functions for global optimization using continuous formulations of graph problems, Journal of Optimization Methods and Software, 20(4-5):439-452, 2005.
  * (11) A. Yu Kitaev, A. Shen, M. N. Vyalyi, 2002,  Classical and Quantum Computation,  American Mathematical Society.
  * (12) S. A. Cook, 1971,  The complexity of theorem-proving procedures, In  Proc. 3rd Ann. ACM Symp. on Theory of Computing, pages 151-158, Association for Computing Machinery, New York, 1971.
  * (13) L. Levin, 1973,  Universal sorting problems, Probl. Peredaci Inf., 9:115-116, 1973. Original in Russian. English translation in Probl. Inf. Transm. USSR 9:265-266 (1973).