# Equivariant QAOA and the Duel of the Mixers

Boris Tsvelikhovskiy  Department of Mathematics, University of California,
Riverside, CA, USA  Ilya Safro  Department of Computer and Information
Sciences, University of Delaware, Newark, DE, USA  Yuri Alexeev  Computational
Science Division, Argonne National Laboratory, Argonne, IL, USA

###### Abstract

Abstract. Constructing an optimal mixer for Quantum Approximate Optimization
Algorithm (QAOA) Hamiltonian is crucial for enhancing the performance of QAOA
in solving combinatorial optimization problems. We present a systematic
methodology for constructing the QAOA tailored mixer Hamiltonian, ensuring
alignment with the inherent symmetries of classical optimization problem
objectives. The key to our approach is to identify an operator that commutes
with the action of the group of symmetries on the QAOA underlying Hilbert
space and meets the essential technical criteria for effective mixer
Hamiltonian functionality.

We offer a construction method specifically tailored to the symmetric group
$S_{d}$, prevalent in a variety of combinatorial optimization problems. By
rigorously validating the required properties, providing a concrete formula
and corresponding quantum circuit for implementation, we establish the
viability of the proposed mixer Hamiltonian. Furthermore, we demonstrate that
the classical mixer $B$ commutes only with a subgroup of $S_{d}$ of
significantly smaller order than the group itself, enhancing the efficiency of
the proposed approach.

To evaluate the effectiveness of our methodology, we compare two QAOA variants
utilizing different mixer Hamiltonians—conventional $B=\sum X_{i}$ and the
newly proposed $H_{M}$ — in edge coloring and graph partitioning problems
across various graphs. We observe statistically significant differences in
mean values, with the new variant consistently demonstrating superior
performance across multiple independent simulations. Additionally, we analyze
the phenomenon of poor performance in alternative warm-start QAOA variants,
providing a conceptual explanation supported by recent literature findings.

Keywords: quantum approximate optimization algorithm, mixer Hamiltonians,
warm-start QAOA

##  I Introduction

In this paper we consider the optimization problem of finding extremal values
of a function $F:\mathbb{D}^{n}\rightarrow\mathbb{R}$, where $\mathbb{D}^{n}$
represents the set of $n$-element $d$-ary strings and $\mathcal{S}$ is the
group of permutations acting on these $d^{n}$ elements. The Quantum
Approximate Optimization Algorithm (QAOA), proposed in QAOA , is a widely used
approach for solving the quantum version of the optimization problem. This
approach is considered as one of the main candidates to demonstrate practical
quantum advantage in future in several areas herman2023quantum . Consequently,
there is a growing interest to enhance its performance. To bridge the
classical and quantum realms, one employs the following correspondences:

  * •

$\mathbb{D}^{n}\rightsquigarrow$ vector space $W$ of dimension $d^{n}$ with
basis $\\{v_{x}\\}$ indexed by elements $x\in\mathbb{D}^{n}$,

  * •

Objective function $F\rightsquigarrow$ linear operator $H_{P}$ acting on $W$,

  * •

Minima of $F$ on $\mathbb{D}^{n}\rightsquigarrow$ lowest energy states of
$H_{P}$ in $W$.

Here, the Hamiltonian $H_{P}$ represents the objective function $F$, meaning
it satisfies the equation $H_{P}(v_{x})=F(x)v_{x}$ for any string
$x\in\mathbb{D}^{n}$. Another important component of the QAOA approach is an
operator referred to as the mixer Hamiltonian $H_{M}$. This operator plays a
pivotal role in the optimization process, as it possesses an easily
identifiable ground state, which aids in initializing the optimization
process.

The QAOA algorithm involves a multistep transformation of $H_{M}$ into
$H_{P}$, aiming to obtain a lowest energy state for the latter Hamiltonian.
This is achieved by alternately applying exponentials of $H_{M}$ and $H_{P}$,
with the number of iterations denoted by $p$ (known as QAOA depth). We express
this transformation as:

$\mathfrak{Q}_{p}=e^{-i\beta_{1}H_{M}}e^{-i\gamma_{1}H_{P}}\ldots
e^{-i\beta_{p}H_{M}}e^{-i\gamma_{p}H_{P}}.$ (1)

The algorithm concludes with a measurement of the resulting state in the
standard basis.

While the problem Hamiltonian $H_{P}$ is uniquely determined by the classical
original problem (unless it is decided to be changed, e.g., by sparsification
liu2022quantum ), there is a flexibility in choosing the mixer Hamiltonian
$H_{M}$. The convergence of QAOA is ensured by the adiabatic theorem if
$H_{M}$ satisfies certain conditions. For example, the assumptions outlined in
the Perron-Frobenius theorem (Theorem III.1) are sufficient.

A commonly used mixer Hamiltonian consists of Pauli $X$-gates,
$B=\sum\limits_{j=0}^{\ell-1}X_{j}$, where $\ell$ is the number of qubits
required for the problem. However, this choice may not exploit problem-
specific attributes. The choice of mixer Hamiltonian has been discussed in the
literature. In HWORVB , the authors introduced a quantum alternating operator
ansatz to allow more general families of Hamiltonian operators. The mixers in
that article are useful for optimization problems with hard constraints that
must always be satisfied (thus defining a feasible subspace of $W$) and soft
constraints whose violation needs to be minimized.

In GPSK , it was experimentally verified (via numerical simulations) that
linear combinations of $X$\- and $Y$-Pauli gates as mixers can outperform the
standard low depth QAOA. More examples can be found in BFL ; GBOE ; SW ;
ZLCMBE  and subsequent references.

Constructing an optimal mixer for QAOA Hamiltonian is crucial for enhancing
the performance of QAOA in solving combinatorial optimization problems.
Optimal mixers not only enforce hard constraints and align with the initial
state for improved performance but also contribute to the universality and
computational efficiency of QAOA, enabling the algorithm to exploit the
structure of optimization problems for significant speed-ups and to adapt
effectively to constrained problems. Here are a few of the examples:

  1. 1.

Enforcing Hard Constraints: The application of QAOA to problems with
constraints presents a notable challenge, especially for near-term quantum
resources. Utilizing $XY$ Hamiltonians as mixers has been shown to enforce
hard constraints effectively. These mixers can be implemented without Trotter
error in certain cases, and they demonstrate significant improvement in
performance over traditional $X$ mixers in solving graph-coloring problems, a
known challenge for classical algorithms wang2020xy .

  2. 2.

Alignment with Initial State: The alignment between the initial state and the
ground state of the mixing Hamiltonian has been observed to improve QAOA
performance. This alignment, mimicking the adiabatic algorithm’s requirements,
has been particularly beneficial in constrained portfolio optimization,
showcasing that an optimal mixer enhances results across different QAOA depths
he2023alignment .

  3. 3.

Universality and Computational Efficiency: The universality of QAOA with
optimal mixers extends its applicability across a broader spectrum of
problems. Optimal mixers contribute to the quantum computational universality,
enabling the solution of complex optimization problems with high efficiency
and precision. This universality underpins QAOA’s potential in leveraging
quantum computing for practical applications morales2020universality .

  4. 4.

Exploiting Problem Structure for Speed-Up: Recent studies have provided
numerical evidence that QAOA, with appropriately chosen mixers and phase
separators, can significantly outperform classical unstructured search
algorithms in finding approximate solutions to constrained optimization
problems. This suggests that optimal mixers are key to leveraging the
structure of optimization problems for computational speed-up
golden2022speedup .

  5. 5.

Custom Mixers for Constrained Problems: For constrained optimization problems,
especially those involving network flows, custom mixers inspired by quantum
electrodynamics (QED) have been shown to preserve flow constraints, leading to
an exponential reduction in the configuration space to be explored. This
adaptation results in higher quality approximate solutions, underscoring the
importance of mixer customization zhang2020qed .

In this paper, we extend various investigation into tailoring the mixer
Hamiltonian to accommodate groups of classical symmetries inherent in the
objective function. In particular, our exploration builds upon our groundwork
laid out in TSA , where we detailed the construction of mixer Hamiltonians,
along with their corresponding ground states, designed for cases where the
group of classical symmetries includes the symmetric group $S_{n}$,
encompassing permutations of string elements. While we presented compelling
arguments advocating for the adoption of such mixer Hamiltonians over
classical counterpart, practical validation was hindered by the challenge of
implementing the suggested matrices as concrete quantum circuits. Our current
focus is on cases where the group of classical symmetries involves a different
symmetric group, $S_{d}$, acting by simultaneous permutation of all factors in
$\mathbb{D}^{n}$:

$\sigma(d_{1},d_{2},\ldots,d_{n}):=(\sigma(d_{1}),\sigma(d_{2}),\ldots,\sigma(d_{n})).$

Considering such cases offers two significant advantages:

  * •

Many optimization problems exhibit these symmetries (e.g., several versions of
graph coloring and partitioning).

  * •

We can construct a mixer Hamiltonian that commutes with the action of $S_{d}$
on $W$, which can be easily implemented as a composition of basic quantum
gates.

The paper is structured as follows for clear and systematic exposition.
Section $2$ offers an overview of the main results to orient the reader. In
Section $3$, a concise review of Quantum Approximate Optimization Algorithm
fundamentals relevant to this study is provided.

Section $4$ presents formulations of the main results and delineates
properties concerning the newly proposed Hamiltonian. The subsequent sections,
$5$ and $6$, respectively, explore the classical optimization problems under
consideration and provide simulation results for three QAOA versions: one
utilizing the classical mixer and the others employing the newly proposed
mixers.

In Section $8$, the impossibility of tailoring a mixer Hamiltonian that
satisfies the Perron-Frobenius theorem within the context of warm-start QAOA
is discussed. Finally, the Appendix offers a conceptual overview of the
construction process and provides rigorous verification of the claims made
throughout the paper.

##  II Main results

We present a systematic approach to constructing a mixer Hamiltonian for QAOA
that aligns with the symmetries inherent in the objective function of the
classical optimization problem being addressed. Specifically, our approach
focuses on identifying an operator that commutes with the action of the group
of symmetries on the Hilbert space for QAOA. Additionally, this operator
fulfills the necessary technical requirements to function effectively as a
mixer Hamiltonian.

In this work, we provide a method for constructing such an operator tailored
to the aforementioned group $S_{d}$. This group naturally emerges as a set of
symmetries in numerous combinatorial optimization problems. We rigorously
validate the required properties for the proposed mixer Hamiltonian, $H_{M}$,
offering both a concrete formula and a corresponding quantum circuit for its
implementation. In addition, we show that the classical mixer $B$ commutes
only with a subgroup of $S_{d}$ of order $2^{\ell}\cdot\ell!$ (in case
$d=2^{\ell}$ is a power of two), which is significantly smaller than $d!$, the
order of $S_{d}$.

Furthermore, we explore the cyclic subgroup $\mathbb{Z}_{d}$ within $S_{d}$,
generated by the element $g:=(23\ldots n1)$. This generator cyclically shifts
$1$ to $2$, $2$ to $3$, and $n$ to $1$. Subsequently, we construct an operator
$H_{\chi}$ whose action on $W$ commutes with $\mathbb{Z}_{d}$, and has the
state $|\psi\rangle:=|\underbrace{-+\ldots+}_{n\ell}\rangle$ as its unique
ground state. Notably, the Hilbert space
$W=\underset{j=0}{\overset{d-1}{\bigoplus}}W_{j}$ decomposes into a direct sum
of equidimensional vector spaces decomposes into a direct sum of
equidimensional vector spaces with respect to the $\mathbb{Z}_{d}$-action,
with $|\psi\rangle$ situated in the subspace $W_{d/2}$. Moreover, the images
of $|\psi\rangle$ during the execution of the QAOA with $H_{\chi}$ in place of
the mixer Hamiltonian remain within this subspace until the final projection
(see Appendix $A$ for precise results). To the best of our knowledge, this is
the first example of a QAOA algorithm realized entirely (with the exception of
the final measurement) within a nontrivial representation of a symmetry group
of the objective function.

We proceed by evaluating the effectiveness of simulations of three QAOA
variants employing distinct mixer Hamiltonians: the conventional $B=\sum
X_{i}$ and the newly proposed $H_{M}$ and $H_{\chi}$, applied to the edge
coloring and graph partitioning problems across a range of graphs. Both
algorithms are configured iteratively with a depth parameter of $p=9$ for edge
coloring and $p=7$ for graph partitioning, respectively. Through $50$ or more
independent trials for each scenario, we observe statistically significant
differences in mean values at the $1.5\%$ significance level, with the new
variant consistently demonstrating lower means. Moreover, we note considerably
lower median and minimal values in the experiments utilizing the newly
introduced mixer Hamiltonians compared to the classical one (see Section $6$
for details).

Finally, we address an intriguing observation regarding the subpar performance
of warm-start QAOA variants—a phenomenon recently documented in the
literature. Warm-start strategies involve initiating QAOA from a promising
classical solution generated by a classical algorithm, with the aim of further
refining it through quantum optimization. While this approach has garnered a
lot of attention in recent studies sridhar2023adapt ; egger2021warm ;
okada2024systematic , our investigation sheds light on its fundamental
limitations.

In a recent study by CFGRT , extensive numerical experiments across a range of
problem sizes and depths uncovered a significant finding. Notably, when QAOA
initializes from a single warm-start string, it demonstrates minimal progress.
We provide a conceptual elucidation for this observation. Specifically, we
identify the absence of an operator satisfying the assumptions of the Perron-
Frobenius theorem while also possessing a superposition of classical states
with identical objective function value as its ground states. This absence
undermines the convergence guarantee of any warm-start QAOA variant to an
optimal solution, even in the limit as the depth parameter approaches infinity
($p\to\infty$).

Consequently, the convergence of warm-start QAOA variants to an optimal
solution hinges entirely on the classical optimizer’s ability to avoid being
trapped in parameter sets, leading to local extrema of the objective function
and raising a major question to a variety of warm-start heuristics that claim
observing quantum advantage, namely, "is the advantage indeed quantum?"

##  III Overview of QAOA

Let $\mathbb{D}^{n}:=\\{0,1,\ldots,d-1\\}^{n}$ be the set of $n$-element
strings and $\mathcal{S}$ the group of permutations of these $d^{n}$ elements.
A classical optimization problem can be formulated as follows: given a
function $F:\mathbb{D}^{n}\rightarrow\mathbb{R}$, find the elements in
$\mathbb{D}^{n}$ on which it attains min (max) values. If a permutation
$g\in\mathcal{S}$ is undetectable by $F$, i.e. $F(g(x))=F(x)$ for any
$x\in\mathbb{D}^{n}$, then $g$ is symmetry of $F$. Such elements form a
subgroup $G\subset\mathcal{S}$ and $F$ is invariant with respect to this
subgroup.

One of the widely employed algorithms for tackling the quantum version of the
optimization problem is the Quantum Approximate Optimization Algorithm,
introduced in QAOA . In the QAOA framework, the Hamiltonian $H_{F}$ is
commonly referred to as the problem Hamiltonian and is denoted by $H_{P}$ (as
per Farhi’s et al. paper QAOA ). We will adopt this notation consistently.

Central to QAOA is the mixer Hamiltonian $H_{M}$, characterized by a distinct
lowest energy state $|\xi\rangle\in W$ and adherence to the requirements of
the Perron-Frobenius theorem (refer to Theorem III.1). The core idea behind
the QAOA algorithm lies in iteratively transforming the mixer Hamiltonian
$H_{M}$ into the problem Hamiltonian. This process ensures that the image of
the lowest-energy vector from the preceding step becomes the lowest-energy
vector in the subsequent one.

The algorithm initiates by preparing the state $|\xi\rangle$, the ground state
for the mixer Hamiltonian $H_{M}$, and then proceeds with multiple alternating
applications of (certain exponents of) the problem and mixer Hamiltonians. The
number of iterations is conventionally denoted by $p$ (also known as QAOA
depth), and we use $\mathfrak{Q}_{p}$ to express the entire composition of
operators

$\mathfrak{Q}_{p}:=e^{-i\beta_{1}H_{M}}e^{-i\gamma_{1}H_{P}}\ldots
e^{-i\beta_{p}H_{M}}e^{-i\gamma_{p}H_{P}}.$ (2)

The final step of QAOA involves performing a measurement of the state obtained
after applying $\mathfrak{Q}_{p}$ in the standard basis. For an in-depth
description of the algorithm, we direct the reader to Section $2$ and the
references therein.

While the Hamiltonian $H_{P}$, representing the objective function, is
uniquely determined by the classical problem, there is some flexibility in
choosing the pair of mixer Hamiltonian and initial state. The convergence of
QAOA to a classical state representing an element on which $F$ attains a
minimum value is guaranteed by the adiabatic theorem, provided the mixer
Hamiltonian satisfies the conditions of the Perron-Frobenius theorem (see
below and Theorem $8.4.4$ in HJ ) and the initial state is the ground state
for it.

######  Theorem III.1.

(Perron-Frobenius). Let $M=(m_{ij})\in\mbox{Mat}_{n}(\mathbb{R})$ be an
irreducible matrix with $m_{ij}\geq 0$.

  * •

Then there is a positive real number $r$, such that $r$ is an eigenvalue of
$M$ and any other eigenvalue $\lambda$ (possibly complex) has
$\operatorname{Re}(\lambda)<r$.

  * •

Moreover, there exists a unique real vector $v=(v_{1},v_{2},\ldots,v_{n})$
such that $M(v)=rv$ and $v_{1}+v_{2}+\ldots+v_{n}=1$. This vector is positive,
i.e. all $v_{i}$ are strictly greater than $0$.

The standard and most common choice of mixer Hamiltonian involves Pauli
$X$-gates and is given by $B=\sum\limits_{0\leq j\leq\ell-1}X_{j}$, where
$\ell$ is the number of qubits needed for the (re)formulation of the original
problem. The corresponding ground state is $|\xi\rangle=|+\rangle^{\otimes
l}$. While this choice offers certain advantages, it does not consider any
specific attributes of a given problem, in particular, the group of symmetries
$G$.

##  IV Symmetries of the Mixers

In this section, we offer a broad, high-level overview of our approach to
selecting the mixer Hamiltonian based on symmetries inherent in the objective
function of the optimization problem being addressed. A more comprehensive and
conceptual discussion is deferred to the appendix.

When determining the symmetries, it is natural to start by considering the
group $\mathcal{S}$ consisting of all permutations of the elements within the
set of all $d$-element strings $\mathbb{D}^{n}$. This action naturally extends
to an action on classical states, and by linearity, to the vector space $W$
associated with $\mathbb{D}^{n}$. The group of classical symmetries for an
optimization problem forms a subgroup $G$ comprising elements
$g\in\mathcal{S}$ that remain ’undetectable’ by $F$, meaning that
$F(g(x))=F(x)$ for any $x\in\mathbb{D}^{n}$. It is straightforward to observe
that elements in this subgroup commute with the action of the problem
Hamiltonian (representing $F$) on $W$. It is natural to seek a mixer
Hamiltonian that satisfies the necessary technical requirements of the Perron-
Frobenius theorem (see Theorem III.1), ensuring convergence as
$p\rightarrow\infty$ and commuting with the largest subgroup of $G$, ideally
encompassing the entire group $G$. Given that the latter condition implies
that the corresponding unitary operator $\mathfrak{Q}_{p}$, which is the
product of $p$ alternating applications of mixer and problem Hamiltonian
operators, commutes with $G$, it is natural to refer to the corresponding QAOA
as $G$-equivariant.

Within $\mathcal{S}$, there exists a subgroup
$S_{d}=\text{{Perm}}(\mathbb{D})$, comprising permutations of elements within
a single copy of the symbol set $\mathbb{D}$. This subgroup acts by
simultaneously permuting elements of $\mathbb{D}^{n}$ in the same manner
across all copies:

$g(d_{1},d_{2},\ldots,d_{n}):=(g\cdot d_{1},g\cdot d_{2},\ldots,g\cdot
d_{n}).$

In many optimization problems (as discussed in the following sections), the
objective function contains $S_{d}$ as a subgroup of its classical symmetries,
i.e., $S_{d}\subseteq G$.

For simplicity of exposition and to facilitate future practical
implementations, we will assume that the number of elements, denoted by $d$,
is a power of two, i.e., $d=2^{\ell}$. In this case, two subgroups of $S_{d}$
will play a fundamental role in our discussion. To describe them, it is
convenient to consider the set $\mathbb{D}$ as a union of $\ell$ bits.

The group
$K_{\ell}:=\underbrace{\mathbb{Z}_{2}\times\ldots\times\mathbb{Z}_{2}}_{\ell}$,
which is a subgroup of $\mathcal{S}$, represents the bit flips for each of
these bits. Meanwhile, $S_{\ell}\subset S_{d}$ is the subgroup responsible for
permuting the bits.

In the appendix, we elaborate on the construction (and the reasoning behind
it) of a mixer Hamiltonian $H_{M}$, whose action on $W$ (the vector space
corresponding to $\mathbb{D}^{n}$) commutes with the action of the entire
group $S_{d}$. Importantly, $H_{M}$ satisfies the assumptions of the Perron-
Frobenius theorem.

Similar to the classical mixer Hamiltonian $B$, the operator $H_{M}$ has a
uniform superposition of all classical states

$|\xi\rangle=\frac{1}{2^{n\ell}}H^{\otimes{n\ell}}(|\underbrace{00\ldots
0}_{n\ell}\rangle)=|\underbrace{++\ldots+}_{n\ell}\rangle$

as its unique ground state. However, we also highlight a significant
difference between the two operators, $B$ and $H_{M}$. Specifically, the
action of the classical mixer Hamiltonian $B$ only commutes with a smaller
subgroup, which is the semidirect product of the groups $K_{\ell}$ and
$S_{\ell}$, and has an order of $2^{\ell}\cdot\ell!$. This is notably less
than the order of $S_{d}$, which is $d!=2^{\ell}!$, as demonstrated in
Proposition VIII.4 and the subsequent Corollary VIII.6.

We proceed by examining the cyclic subgroup $\mathbb{Z}_{d}$ within $S_{d}$,
generated by the element $g:=(23\ldots n1)$, which cyclically shifts the
elements from $1$ to $2$, $2$ to $3$, and $n$ to $1$. We then construct an
operator $H_{\chi}$ whose action on $W$ commutes with $\mathbb{Z}_{d}$ and has
the state $|\psi\rangle:=\frac{1}{2^{n\ell}}H^{\otimes
n\ell}(|\underbrace{10\ldots
0}_{n\ell}\rangle)=|\underbrace{-+\ldots+}_{n\ell}\rangle$ as its unique
ground state.

######  Remark IV.1.

The ambient Hilbert space $W$ admits a decomposition into a direct sum of
subspaces:

$W=\underset{j=0}{\overset{d-1}{\bigoplus}}W_{j}$

according to the $\mathbb{Z}_{d}$-action. It is interesting to note that the
state vector $|\xi\rangle$ resides in $W_{0}$, while $|\psi\rangle$ is located
in $W_{d/2}$. Moreover, the images of these vectors during the execution of
their respective QAOAs remain within these subspaces prior to the final
projection (see Remark VIII.3 for a precise statement).

Let us reiterate that we defer the verification of the existence of the
operators $H_{M}$ and $H_{\chi}$ satisfying the aforementioned properties to
the appendix. Instead, our focus in the subsequent sections will be on
demonstrating its practical advantages over the classical mixer.

##  V Outline of the Two Problems

In this section, we elucidate two significant classical optimization problems
and their reformulations within the framework of QAOA. These problems find
numerous applications across various domains bulucc2016recent ;
jensen2011graph .

###  V.1 Problem 1: Edge Coloring

One class of optimization problems with objective function having the
aforementioned group of symmetries, $S_{d}$, is coloring of the vertices or
edges of a graph in $d$ colors.

######  Definition V.1.

A vertex coloring of a graph $\Gamma=(V,E)$ is a map
$\widetilde{C}:E\rightarrow\mathfrak{C}$, where $\mathfrak{C}$ is a set of
colors with $|\mathfrak{C}|=d$. A coloring $\widetilde{C}$ is called proper if
$\widetilde{C}(v_{1})\neq\widetilde{C}(v_{2})$ for any two adjacent vertices
$v_{1},v_{2}\in V$.

Similarly, an edge coloring of a graph $\Gamma=(V,E)$ is a map
$C:E\rightarrow\mathfrak{C}$. A coloring $C$ is called proper if $C(e)\neq
C(f)$ for any two adjacent edges $e,f\in E$.

To represent $k$ colors, we employ $\ell=\ell og_{2}(d)$ bits through the
following encoding:

$\displaystyle color_{0}\longleftrightarrow 0\ldots 00$ $\displaystyle
color_{1}\longleftrightarrow 0\ldots 01$ $\displaystyle\ldots$

In this section we focus on the edge coloring. Each edge $e\in E$ is assigned
$\ell$ bits $e_{0},e_{1},\ldots,e_{\ell-1}$ whose values uniquely determine
the color of the edge. The characteristic function of a color
$C\in\mathfrak{C}$ is defined as follows:

$\chi_{c}(c^{\prime}):=\begin{cases}1,&\text{if }c^{\prime}_{i}\equiv
c_{i}\text{ for all }i\in\\{1,\ldots,\ell\\}\\\
0,&\text{otherwise}\end{cases}$

This function, denoted as $\chi_{c}(C(e))$, is explicitly given by

$\chi_{c}(C(e))=\prod\limits_{i=1}^{\ell}((1-c_{i})e_{i}+c_{i}(1-e_{i}))$

This defining property ensures that the characteristic function equals $1$ on
the specific color $C$ and $0$ on all other colors. We define the objective
function

$F_{\Gamma}(C):=\sum\limits_{e\bullet
f}\sum\limits_{c\in\mathfrak{C}}\chi_{c}(C(e))\chi_{c}(C(f)),$

where the notation $e\bullet f$ represents adjacent edges. This function
calculates the number of adjacent edges with the same color.

######  Remark V.2.

A coloring $C$ is proper if and only if $F_{\Gamma}(C)=0$.

It is evident that the action of the group $S_{d}$, permuting the colors,
preserves the values of the objective function:

$F_{\Gamma}(\sigma^{-1}(C))=F_{\Gamma}(C)\quad\forall\sigma\in
S_{d},C\in\mathfrak{C}.$

######  Definition V.3.

The chromatic index $\chi_{\Gamma}$ of a graph $\Gamma$ is the minimum number
of colors needed for a proper coloring of $\Gamma$.

The following result was proved in VIZ .

######  Theorem V.4.

Let $\Gamma$ be a simple undirected graph with maximum degree
$\triangle(\Gamma)$. Then
$\triangle(\Gamma)\leq\chi(G)\leq\triangle(\Gamma)+1$.

######  Definition V.5.

Graphs that can be colored with $\triangle(\Gamma)$ are called class one
graphs. Graphs that require at least $\triangle(\Gamma)+1$ colors are called
class two graphs.

In order to resolve the dichotomy in Theorem V.4, whether the minimal proper
coloring of edges involves $k$ or $k+1$ colors, it suffices to find out if a
proper $k$ coloring exists.

The operator representing the characteristic function $\chi_{c}$ is given by

$\widetilde{\chi}_{c}(e):=\begin{cases}e,&e_{i}\equiv c_{i}~{}\forall
i\in\\{1,\ldots,\ell\\}\\\ 0,&\text{otherwise}\end{cases}$

and is expressed as

$\widetilde{\chi}_{c}(e)=\frac{1}{2^{\ell}}\bigotimes\limits_{i=1}^{\ell}(\mathds{1}+(-1)^{c_{i}}Z_{e,i}),$

In the case $\ell=2$, this expression simplifies to

$Z_{e,0}Z_{f,0}Z_{e,1}Z_{f,1}+Z_{e,0}Z_{f,0}+Z_{e,1}Z_{f,1}+\lambda\mathds{1}.$

Meanwhile, the problem Hamiltonian representing $F_{\Gamma}$ is

$H_{P}=\sum\limits_{e\bullet
f}\sum\limits_{c\in\mathfrak{C}}\widetilde{\chi}_{c}(e)\widetilde{\chi}_{c}(f).$

The building blocks for the quantum circuit representing the exponent of the
latter operator,

$e^{-i\beta H_{P}}=\prod\limits_{e\bullet
f}e^{-i\beta(Z_{e,0}Z_{f,0}Z_{e,1}Z_{f,1}+Z_{e,0}Z_{f,0}+Z_{e,1}Z_{f,1})}=\prod\limits_{e\bullet
f}(e^{-i\beta Z_{e,0}Z_{f,0}Z_{e,1}Z_{f,1}}e^{-i\beta
Z_{e,0}Z_{f,0}}e^{-i\beta Z_{e,1}Z_{f,1}})$

are presented in Figure 1 below.

e_0 & 1 1

f_0 R_Z(2β)

e_0 & 1 1

f_0 1 1

e_1 1 1

f_1 R_Z(2β)

Figure 1: Quantum circuits for $e^{-i\beta Z_{e,0}Z_{f,0}}$ and $e^{-i\beta
Z_{e,0}Z_{f,0}Z_{e,1}Z_{f,1}}$

###  V.2 Problem 2: graph partitioning

The second optimization problem explored in this paper is the balanced graph
partitioning problem. This problem appears in numerous applications
bulucc2016recent  and has been a subject of several investigations in QAOA and
other frameworks ushijima2021multilevel ; shaydulin2019multistart. Given a
graph $\Gamma$ and a fixed integer $k$ that divides the number of vertices in
$\Gamma$, the objective is to find a partition of the vertices: $V=V_{0}\sqcup
V_{1}\sqcup\ldots\sqcup V_{k-1}$ into $k$ disjoint subsets of equal
cardinality that minimizes the total number of cut edges. A cut edge is
defined as an edge with endpoints in different subsets. The requirement of
exact equality of sizes of $V_{i}$’s for all $i$ is often referred to as
perfectly balanced graph partitioning.

This problem bears some resemblance to the vertex coloring problem for $k$
colors. Specifically, we can refer to vertices in subset $V_{i}$ as colored
with the $i$-th color. However, unlike the coloring problem where we aim to
minimize the number of adjacent vertices with the same color, here we seek to
maximize this number. Additionally, we must account for the restriction on the
cardinalities of the $V_{i}$’s.

We will examine examples with $k=4$ and the number of vertices in the graph
being a multiple of $4$. As before, we encode the $4$ colors using $2$ bits.
We define the objective function $F(C)$ as follows:

$F(C)=-\sum\limits_{v-v^{\prime}}\sum\limits_{c\in\mathfrak{C}}\chi_{c}(C(v))\chi_{c}(C(v^{\prime}))+\left(2E\sum\limits_{v\in
V}(v_{0}-0.5)\right)^{2}+\left(2E\sum\limits_{v\in
V}(1-v_{0})(v_{1}-0.5)\right)^{2}+\left(2E\sum\limits_{v\in
V}v_{0}(v_{1}-0.5)\right)^{2},$

where the notation $v-v^{\prime}$ is used for adjacent vertices. The first sum
evaluates the number of pairs of adjacent vertices belonging to different
subsets of the partition, while the remaining three ensure that
$|V_{0}|=|V_{1}|=|V_{2}|=|V_{3}|=\frac{|V|}{4}$. Specifically,
$\left(\sum\limits_{v\in V}(v_{0}-0.5)\right)^{2}$ equals zero if and only if
the numbers of vertices with the first color bit equal to $0$ and $1$
coincide; otherwise, it is positive. Similarly, $\left(\sum\limits_{v\in
V}(1-v_{0})(v_{1}-0.5)\right)^{2}$ and $\left(\sum\limits_{v\in
V}v_{0}(v_{1}-0.5)\right)^{2}$ equal zero if and only if the numbers of
vertices with the second color bit equal to $0$ and $1$ coincide,
respectively, for the first color bit being fixed at $0$ and $1$.

The corresponding problem Hamiltonian is given by:

$H_{P}=-\sum\limits_{v-v^{\prime}}\sum\limits_{c\in\mathfrak{C}}\widetilde{\chi}_{v}(c)\widetilde{\chi}_{v^{\prime}}(c)+E\left(\sum\limits_{v\in
V}Z_{v,0}\right)^{2}+E\left(\sum\limits_{v\in
V}(1-Z_{v,0})Z_{v,1}\right)^{2}+E\left(\sum\limits_{v\in
V}(1-Z_{v,0})Z_{v,1}\right)^{2}$

and is equivalent to

$-\sum\limits_{v-v^{\prime}}\sum\limits_{c\in\mathfrak{C}}\widetilde{\chi}_{v}(c)\widetilde{\chi}_{v^{\prime}}(c)+2E\sum\limits_{v,v^{\prime}\in
V}(Z_{v,0}Z_{v^{\prime},0}+Z_{v,1}Z_{v^{\prime},1})+2E\sum\limits_{v,v^{\prime}\in
V}Z_{v,0}Z_{v^{\prime},0}Z_{v,1}Z_{v^{\prime},1}.$

##  VI The Duel: equivariant $H_{M},H_{\chi}$ Vs classical $B$

In this section, we contrast the performance of QAOA algorithms using
different mixer Hamiltonians: the classical one, $B=\sum X_{i}$, and the newly
introduced equivariant $H_{M}$ and $H_{\chi}$. We analyze their effectiveness
on the problems discussed in the preceding section, primarily comparing
$H_{M}$ and $H_{\chi}$ with $H_{B}$. We implement the algorithms iteratively.
The algorithms begin by establishing the initial state:

$|\xi\rangle=\frac{1}{2^{n\ell}}H^{\otimes{n\ell}}(|\underbrace{00\ldots
0}_{n\ell}\rangle)=|\underbrace{++\ldots+}_{n\ell}\rangle$

for $H_{M}$ and $H_{B}$, or

$|\psi\rangle=\frac{1}{2^{n\ell}}H^{\otimes n\ell}(|\underbrace{10\ldots
0}_{n\ell}\rangle)=|\underbrace{-+\ldots+}_{n\ell}\rangle$

for $H_{\chi}$. The initial pair of parameters $(\beta_{1},\gamma_{1})$ is
randomly selected from the uniform distribution on the set
$[0,0.25\pi]\times[0,2\pi]$. Subsequently, the algorithm iterates through
runs: after completing the $p=1$ run, optimal values
$(\beta^{*}_{1},\gamma^{*}_{1})$ are determined with the aid of a classical
optimizer. The subsequent QAOA run is then executed with starting parameters
$(\beta^{*}_{1},\gamma^{*}_{1},0,0)$ for $p=2$, and this process continues
iteratively. The objective of the classical optimizer is to minimize the
energy, which is defined as the average value of the objective function on the
states output by the algorithm over multiple runs:

$\mathcal{E}_{p}:=\dfrac{\sum\limits_{i=1}^{m}F_{\Gamma}(\mathfrak{Q}_{p}(|s_{i}\rangle))}{m}.$
(3)

######  Remark VI.1.

In case of the edge coloring problem, if the energy $\mathcal{E}_{p}<1$, it
implies that at least one of the obtained values
$F_{\Gamma}(\mathfrak{Q}_{p}(|s_{i}\rangle))$ is zero. Consequently, the
corresponding coloring is proper, indicating that $\Gamma$ is a class one
graph.

On each successive step, the starting parameters consist of the values
converged by the classical optimizer on the preceding step, complemented by
two zeros for the additional angles that did not appear in the previous step.
This deliberate choice ensures that the energy values
$\mathcal{E}_{1},\mathcal{E}_{2},\ldots$ obtained in subsequent steps are
nonincreasing, as outlined in QAOA . The algorithm’s depth for the edge
coloring problem was set at $p=9$ and for the graph partitioning problem at
$p=7$. We conducted multiple independent simulations, ranging from $50$ to
$56$, for various graphs (see Figures 2 and 3) using the qiskit codes
available at this link. The main characteristics of the outcomes are
summarized in Table 1, while the histograms displaying the average
$\mathcal{E}_{p}$-values across sample runs of the equivariant algorithms, as
compared to the classical one for each graph, are depicted in Figures 4 and 5.

Based on Table 3, which presents the Student’s $t$-test values for testing the
hypothesis that the means of energy values for the two algorithms are equal,
we reject this hypothesis at a significance level of $\alpha=1.5\%$ for all
graphs analyzed (with the exception of graph $\Gamma_{2}$ for the mixer
$H_{\chi}$). This indicates a statistically significant difference in the
energy values between the algorithms across all examined graphs. Furthermore,
we consistently observe lower median and minimal energy values (columns $3$
and $4$) for the newly proposed mixers.

$0$$1$$2$$3$$4$$\Gamma_{1}=$

$0$$1$$2$$3$$4$$5$$6$$\Gamma_{2}=$

$0$$1$$2$$3$$4$$5$$\Gamma_{3}=$

$0$$1$$2$$3$$4$$5$$\Gamma_{4}=$

$1$$2$$3$$0$$4$$5$$6$$\Gamma_{5}=$

$1$$2$$3$$4$$5$$6$$7$$8$$0$$\Gamma_{6}=$

Figure 2: Graphs $\Gamma_{1},\Gamma_{2},\Gamma_{3},\Gamma_{4},\Gamma_{5}$ and
$\Gamma_{6}$ considered for edge coloring problem
$0$$1$$2$$3$$\mathfrak{G}_{1}$ Figure 3: Graph $\mathfrak{G}$ considered for
graph partitioning problem

Graph | Mean | Median | Min | $\mathcal{E}_{9}<1$
---|---|---|---|---
$\Gamma_{1},B$ | 0.726 | 0.7056 | 0.3584 | 41/50
$\Gamma_{1},H_{M}$ | 0.5692 | 0.4673 | 0.1923 | 47/50
$\Gamma_{1},H_{\chi}$ | 0.5726 | 0.5142 | 0.1621 | 47/50
$\Gamma_{2},B$ | 0.9696 | 0.9316 | 0.4814 | 33/56
$\Gamma_{2},H_{M}$ | 0.7437 | 0.7388 | 0.3691 | 51/56
$\Gamma_{2},H_{\chi}$ | 0.8688 | 0.7148 | 0.3964 | 47/56
$\Gamma_{3},B$ | 1.2495 | 1.2417 | 0.6533 | 11/56
$\Gamma_{3},H_{M}$ | 0.9344 | 0.8857 | 0.3691 | 35/56
$\Gamma_{3},H_{\chi}$ | 0.7334 | 0.6763 | 0.2598 | 50/56
$\Gamma_{4},B$ | 1.4857 | 1.5313 | 0.7382 | 6/56
$\Gamma_{4},H_{M}$ | 1.1959 | 1.1074 | 0.5117 | 21/56
$\Gamma_{4},H_{\chi}$ | 1.2415 | 1.1489 | 0.4395 | 20/56
$\Gamma_{5},B$ | 1.3469 | 1.3066 | 0.6162 | 14/50
$\Gamma_{5},H_{M}$ | 0.9149 | 0.9507 | 0.3516 | 30/50
$\Gamma_{5},H_{\chi}$ | 0.94123 | 0.9375 | 0.2939 | 27/50
$\Gamma_{6},B$ | 0.8726 | 0.8569 | 0.502 | 23/28
$\Gamma_{6},H_{M}$ | 0.5227 | 0.5073 | 0.17 | 28/28

Table 1: QAOA performance comparison for edge coloring problem

Graph | Mean | Median | Min
---|---|---|---
$\mathfrak{G},B$ | 10.08135 | 10.34229 | 6.24414
$\mathfrak{G},H_{M}$ | 8.05236 | 8.11035 | 4.47656
$\mathfrak{G},H_{\chi}$ | 9.039 | 8.888 | 4.94434

Table 2: QAOA performance comparison for graph partitioning problem

Graph/Mixer | $H_{M}$ | $H_{\chi}$
---|---|---
$\Gamma_{1}$ | $0.01252$ | $0.007$
$\Gamma_{2}$ | $3.054\cdot 10^{-7}$ | $0.237$
$\Gamma_{3}$ | $1.9807\cdot 10^{-6}$ | $4.0636\cdot 10^{-15}$
$\Gamma_{4}$ | $0.0033$ | $0.0169$
$\Gamma_{5}$ | $8.1731\cdot 10^{-7}$ | $5.9511\cdot 10^{-5}$
$\Gamma_{6}$ | $1.2231\cdot 10^{-8}$ |
$\mathfrak{G}$ | $9.125\cdot 10^{-7}$ | $0.0145$

Table 3: Table of $p$-values for Student’s $t$-test

$\Gamma_{1}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\Gamma_{2}$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$$1.8$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$EnergyFrequency

$\Gamma_{3}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$24$EnergyFrequency

$\Gamma_{4}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\Gamma_{5}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\Gamma_{6}$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$EnergyFrequency

$\mathfrak{G}$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$0$$2$$4$$6$$8$$10$$12$$14$EnergyFrequency

Figure 4: Histograms illustrating the frequency distributions of
$\mathcal{E}p$-values for algorithms utilizing mixers $H_{M}$ and $H_{M}$

$\Gamma_{1}$$0$$0.2$$0.4$$0.6$$0.8$$1$$1.2$$1.4$$1.6$$1.8$$2$$2.2$$2.4$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\Gamma_{2}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$0$$5$$10$$15$$20$$25$EnergyFrequency

$\Gamma_{3}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$$22$$24$EnergyFrequency

$\Gamma_{4}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\Gamma_{5}$$0$$0.5$$1$$1.5$$2$$2.5$$3$$3.5$$4$$0$$2$$4$$6$$8$$10$$12$$14$$16$$18$$20$EnergyFrequency

$\mathfrak{G}$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$0$$2$$4$$6$$8$$10$$12$$14$EnergyFrequency

Figure 5: Histograms illustrating the frequency distributions of
$\mathcal{E}p$-values for algorithms utilizing mixers $H_{M}$ and $H_{\chi}$

##  VII Mixer Hamiltonians for Warm-Start QAOA

The standard QAOA typically begins in the uniform superposition of all
classical bit strings. Its primary objective is to enhance the objective
function’s value beyond the expected value in this initial state. A natural
extension involves running a classical algorithm to generate a promising
string (i.e., a good solution for certain practical goals, e.g., optimizing
time/quality trade-off), then initializing the QAOA in the corresponding
computational basis state to seek further improvement. This approach, known as
warm-start QAOA, has been explored in various studies.

In a recent paper CFGRT , extensive numerical experiments involving both small
and large instances at varying depths revealed a notable observation.
Specifically, when the QAOA commences from a single warm-start string (or
superposition of strings with equal energy level), it exhibits negligible
progress. The authors also highlight that these findings hold true even when
the QAOA initializes with a single classical string, and the unitary operators
constituting the QAOA do not explicitly rely on the initial string.

We aim to further explore this topic by offering additional insights into the
limitations of warm-start QAOA. We start by observing that any mixer
Hamiltonian with a nontrivial spectral gap possesses a one-dimensional
eigenspace corresponding to the smallest eigenvalue $\lambda$. Let $|s\rangle$
denote a state spanning this subspace. It follows that $|s\rangle$ cannot be
an eigenvector for the problem Hamiltonian $H_{P}$. If it were, both
Hamiltonians would merely scale $|s\rangle$, and executing the corresponding
QAOA starting with the state $|s\rangle$ would result in the identical state
(up to a phase). Subsequently, measuring in the standard basis would yield a
standard state with energy $\lambda$.

In addition, as emphasized in the second assertion of Theorem III.1, every
irreducible matrix with nonnegative values ensures that the vector
corresponding to the highest eigenvalue has coordinates that are all nonzero
(positive) in the standard basis.

This crucially implies that the ground state for a mixer Hamiltonian,
satisfying the assumptions of the Perron-Frobenius theorem, _must be_ a
superposition of all classical states with nonzero amplitudes. Consequently,
the standard argument for guaranteeing the convergence of QAOA as
$p\rightarrow\infty$ to an optimal classical solution is inapplicable unless
the initial state is a superposition of all classical states with nonzero
amplitudes.

##  VIII Appendix

In this section, we introduce and detail the construction, matrix
representation, and quantum circuit for the newly introduced mixer Hamiltonian
$H_{M}$, which is employed throughout the paper. We demonstrate that $H_{M}$
satisfies the Perron-Frobenius theorem, ensuring the convergence of the
corresponding Quantum Approximate Optimization Algorithm as the number of
iterations, $p$, tends to infinity. Additionally, we revisit essential
definitions and provide a concrete representation of the result concerning
subgroups of $\mathcal{S}$ that commute with the actions of the operators
$H_{M}$ and $B$ on $W$.

###  VIII.1 New Mixers: $H_{M}$ and $H_{\chi}$

The symmetric group $S_{d}$ discussed in previous sections is also known as
$W(U_{d})$, the Weyl subgroup of the unitary group acting collectively on all
qudits. A mixer Hamiltonian $H_{M}$, which commutes with this group’s action,
can be constructed as follows.

Consider the sum of all transpositions, $\zeta=\sum\limits_{1\leq i<j\leq
n}(ij)\in\mathbb{C}[S_{d}]$, where $\mathbb{C}[S_{d}]$ denotes the group
algebra of $S_{d}$. The group algebra is a vector space with a basis indexed
by group elements, where multiplication is defined by the group operation of
the underlying group. This element $\zeta$ commutes with all permutations and,
therefore, resides in the center of the group algebra. The matrix
representation of $\zeta$ in the standard basis of a vector space representing
a single qudit is given by $\widehat{H}_{M_{ij}}=1$ for $i\neq j$, and
$\widehat{H}_{M_{ii}}={d-1\choose 2}$. A notable practical observation is
that, in the Hadamard basis, this matrix becomes diagonal:

$H^{\otimes\ell}\widehat{H}_{M}H^{\otimes\ell}=\text{diag}\left(\frac{d(d-1)}{2},\frac{(d-1)(d-2)}{2}-1,\ldots,\frac{(d-1)(d-2)}{2}-1\right),$

or, ignoring the addition of a scalar
$\left(\frac{(d-1)(d-2)}{2}-1\right)\cdot\text{Id}$ operator:

$H^{\otimes\ell}\widehat{H}_{M}H^{\otimes\ell}=\text{diag}(d,0,\ldots,0),$

resulting in $e^{-\beta
H^{\otimes\ell}\widehat{H}_{M}H^{\otimes\ell}}=\text{diag}(e^{-d\beta},1,\ldots,1)$.

######  Example VIII.1.

The quantum circuits for $e^{-\beta
H^{\otimes\ell}\widehat{H}_{M}H^{\otimes\ell}}$ with $d=4$ and $d=8$ are
illustrated on Figure 6.

e_0 & H 1 H
e_1 H P_-4β H
abc
e_0 & H 2 H
e_1 H 1 H
e_2 H P_-8β H

Figure 6: Quantum circuit for $e^{-\beta
H^{\otimes\ell}\widehat{H}_{M}H^{\otimes\ell}}$ with $d=4$ and $d=8$

We define the mixer Hamiltonian $H_{M}$ as the sum of individual terms
$\widehat{H}^{i}_{M}$, where $\widehat{H}^{i}_{M}:=Id\otimes\ldots\otimes
Id\otimes\widehat{H}_{M}\otimes Id\ldots Id$ represents the action of $H_{M}$
on the $i^{th}$ copy of the vector space $V$ corresponding to the $i^{th}$
copy of the set $\mathbb{D}$. We would like to remind the reader that
$W=V\otimes\ldots\otimes V$ is the $n$-fold tensor product of such vector
spaces.

It is straightforward to verify that the operator $H_{M}$ defined in this
manner satisfies the assumptions of the Perron-Frobenius theorem (see III.1),
thereby qualifying as a mixer Hamiltonian. Notably, its ground state
$|\xi\rangle$ coincides with that of the classical mixer $B$.

This time, we start with the element $\eta=\sum_{1\leq i<j\leq
n}(-1)^{i+j}(ij)\in\mathbb{C}[S_{d}]$. We then examine the cyclic subgroup
$\mathbb{Z}_{d}\subset S_{d}$, generated by the element $g=(23\ldots n1)$,
which cyclically permutes the elements from $1$ to $n$.

######  Lemma VIII.2.

The element $\eta$ commutes with the group $\mathbb{Z}_{d}$.

###### Proof.

To demonstrate this, we calculate $g\eta g^{-1}=\sum\limits_{1\leq i<j\leq
n}(-1)^{i+j}(g(i)g(j))=\sum\limits_{1\leq i<j\leq n}(-1)^{i+j}((i+1)\mod
d)((j+1)\mod d)=\sum\limits_{1\leq i<j\leq n}(-1)^{i+j}(ij)=\eta$, where
$i+j+2\equiv i+j\pmod{2}$. Hence, $g\eta g^{-1}=\eta$ implies $g\eta=\eta g$,
indicating that $\eta$ and $g$ commute. ∎

The matrix representation of $\eta$ in the standard basis of a vector space
representing a single qudit is given by $\widehat{H}_{\chi_{ij}}=(-1)^{i+j}$
for $i\neq j$, and $\widehat{H}_{\chi_{ii}}={d-1\choose 2}$. Furthermore, in
the Hadamard basis, this matrix becomes diagonal:

$H^{\otimes\ell}\widehat{H}_{\chi}H^{\otimes\ell}=\text{diag}\left(\frac{(d-1)(d-2)}{2}-1,\ldots,\frac{(d-1)(d-2)}{2}-1,\frac{d(d-1)}{2},\frac{(d-1)(d-2)}{2}-1,\ldots,\frac{(d-1)(d-2)}{2}-1\right),$

or, ignoring the addition of a scalar
$\left(\frac{(d-1)(d-2)}{2}-1\right)\cdot\text{Id}$ operator:

$H^{\otimes\ell}\widehat{H}_{\chi}H^{\otimes\ell}=\text{diag}(0,\ldots,0,d,0,\ldots,0),$

acting with multiplication by $d$ on the one-dimensional vector space spanned
by the vector $|-\underbrace{+\ldots++}_{\ell-1}\rangle$,

resulting in $e^{-\beta
H^{\otimes\ell}\widehat{H}_{\chi}H^{\otimes\ell}}=\text{diag}(1,\ldots,1,e^{-d\beta},1,\ldots,1)$.

We define the mixer Hamiltonian $H_{\chi}$ as the sum
$\widehat{H}_{\chi}\otimes Id\ldots\otimes
Id+\sum\limits_{i=2}^{n}\widehat{H}^{i}_{M}$.

The operator $H_{\chi}$, defined in this manner, does not meet the assumptions
of the Perron-Frobenius theorem (see III.1). Nevertheless, it is
straightforward to verify that it possesses a one-dimensional eigenspace with
the minimal eigenvalue, and therefore, a nonzero spectral gap. This eigenspace
is spanned by the state
$|\psi\rangle:=|-\underbrace{+\ldots++}_{n\ell-1}\rangle$.

Let $\zeta:=e^{\frac{2\pi i}{d}}$ be the primitive $d$th root of unity. Under
the action of the cyclic group $\mathbb{Z}_{d}$, the Hilbert space $W$
decomposes into a direct sum of vector spaces: $W=\bigoplus_{j=0}^{d-1}W_{j}$,
where each $W_{j}$ has dimension $d^{n-1}$. The action of $\mathbb{Z}_{d}$ on
$W_{j}$ is given by the equation $g\cdot w_{j}=\zeta^{j}w_{j}$, for all
$w_{j}\in W_{j}$.

It is worth noting that $\zeta^{d/2}=e^{\pi i}=-1$, and the vector
$|\psi\rangle$ resides in $W_{d/2}$.

######  Remark VIII.3.

Since the actions of both operators $H_{P}$ and $H_{\chi}$ on $W$ commute with
that of the group $\mathbb{Z}_{d}$, it follows that the operator
$\mathfrak{Q}_{p}$ preserves each subspace $W_{j}$, meaning
$\mathfrak{Q}_{p}(W_{j})\subseteq W_{j}$. Specifically, this implies
$\mathfrak{Q}_{p}(|\xi\rangle)\subseteq W_{0}$ and
$\mathfrak{Q}_{p}(|\psi\rangle)\subseteq W_{j}$.

###  VIII.2 Group actions and mixers

Recall that the symmetric group $\mathcal{S}$ acts on the set of all states
$\mathbb{D}^{n}$ by permutations. This action can be uniquely extended to a
linear action on the state vector space $W$. Said differently, there is a
homomorphism $\varphi:\mathcal{S}\rightarrow GL(W)$.

We elucidate key properties concerning the interaction of $S_{d}$, $K_{\ell}$,
and $S_{\ell}$ (see Section $3$ for the definitions of these groups) with the
objective function $F$ and the Hamiltonians $H_{P}$, $B$, and $H_{M}$.

Suppose $A:V\rightarrow V$ is a linear operator. We denote by $Z_{S_{d}}(A)$
the subgroup of elements in $S_{d}$ whose action on $V$ commutes with that of
$A$.

######  Proposition VIII.4.

Suppose the objective function $F:\mathbb{D}^{n}\rightarrow\mathbb{R}$ is
invariant with respect to the action of symmetric group $S_{d}$.

  1. $(a)$

$Z_{S_{d}}(H_{P})=S_{d}$

  2. $(b)$

$Z_{S_{d}}(H_{M})=S_{d}$

  3. $(c)$

$Z_{S_{d}}(B)=K_{\ell}\rtimes S_{\ell}$, where $K_{\ell}\triangleleft
Z_{S_{2^{\ell}}}(B)$ is normal.

###### Proof.

The statement in $(a)$ is an immediate consequence of the initial assumption.
The assertion in $(b)$ follows from the fact that the element
$\zeta=\sum\limits_{1\leq i<j\leq n}(ij)$ is in the center of the group
algebra $\mathbb{C}[S_{d}]$. The justification for $(c)$ arises from the
observation that for $\varphi(h)$ with $h\in S_{d}$ to commute with
$B=\sum\limits_{g\in K_{\ell}}\varphi(g)$, it must satisfy the condition
$\sum\limits_{g\in K_{\ell}}\varphi(hgh^{-1})=\sum\limits_{g\in
K_{\ell}}\varphi(g)$. In essence, this implies that $h$ possesses the
capability to rearrange or flip the bits. ∎

######  Remark VIII.5.

It is interesting to point out that $K_{\ell}\rtimes S_{\ell}$ is
$W(B_{\ell})$, the Weyl group for root system of type $B_{\ell}$.

######  Corollary VIII.6.

The subgroup of symmetries of the mixer $H_{M}$ surpasses that of $B$. For
instance, when $\ell=2$, $W(B_{2})$ equals the dihedral group of order
$|D_{4}|=8$, while $|S_{4}|=24$. For $\ell=3$, $|W(B_{3})|=48$, and
$|S_{8}|=8!=40320$. As $\ell$ increases, the disparity in orders becomes more
pronounced: $|W(B_{\ell})|=2^{\ell}\cdot\ell!$ and $|S_{d}|=2^{\ell}!$.

## References

  * (1) Z. Wang, N. Rubin, J. Dominy, and E. Rieffel, "XY-mixers: Analytical and numerical results for the quantum alternating operator ansatz," Physical Review A, vol. 101, p. 012320, 2020.
  * (2) Z. He, R. Shaydulin, S. Chakrabarti, D. Herman, C. Li, Y. Sun, and M. Pistoia, "Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Portfolio Optimization," arXiv:2305.03857, 2023.
  * (3) M. E. S. Morales, J. Biamonte, and Z. Zimbor’as, "On the universality of the quantum approximate optimization algorithm," Quantum Inf. Process., 2020.
  * (4) J. K. Golden, A. Bärtschi, D. O’Malley, and S. Eidenbenz, "Numerical Evidence for Exponential Speed-Up of QAOA over Unstructured Search for Approximate Constrained Optimization," in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 496-505, 2022.
  * (5) Y. Zhang, R. Zhang, and A. Potter, "QED driven QAOA for network-flow optimization," Quantum, vol. 5, p. 510, 2020.
  * (6) E. Bourreau, G. Fleury, and P. Lacomme, "Mixer Hamiltonian with QAOA for Max $k$-coloring: numerical evaluations," arXiv:2207.11520, 2022.
  * (7) M. Cain, E. Farhi, S. Gutmann, D. Ranard, and E. Tang, "The QAOA gets stuck starting from a good classical string," arXiv:2207.05089, 2022.
  * (8) E. Farhi, J. Goldstone, and S. Gutmann, "A quantum approximate optimization algorithm," arXiv:1411.4028, 2014.
  * (9) J. Golden, A. Bärtschi, D. O’Malley, and S. Eidenbenz, "Numerical Evidence for Exponential Speed-up of QAOA over Unstructured Search for Approximate Constrained Optimization," arXiv:2202.00648, 2022.
  * (10) L. C. G. Govia, C. Poole, M. Saffman, and H. K. Krovi, "Freedom of the mixer rotation axis improves performance in the quantum approximate optimization algorithm," Phys. Rev. A, vol. 104, no. 6, 2021.
  * (11) S. Hadfield, Z. Wang, B. O’Gorman, E. G. Rieffel, D. Venturelli, and R. Biswas, "From the quantum approximate optimization algorithm to a quantum alternating operator ansatz," Algorithms, vol. 12, no. 34, 2019.
  * (12) R. Horn and C. Johnson, Matrix analysis, 2nd ed. Cambridge University Press, Cambridge, 2013.
  * (13) X. Liu, R. Shaydulin, and I. Safro, "Quantum approximate optimization algorithm with sparsified phase operator," in 2022 IEEE International Conference on Quantum Computing and Engineering (QCE), pp. 133–141, 2022.
  * (14) T. R. Jensen and B. Toft, Graph coloring problems, John Wiley & Sons, 2011.
  * (15) V. Sridhar, Y. Chen, B. Gard, E. Barnes, and S. Economou, "ADAPT-QAOA with a classically inspired initial state," arXiv preprint arXiv:2310.09694, 2023.
  * (16) H. Ushijima-Mwesigwa, R. Shaydulin, C. Negre, S. Mniszewski, Y. Alexeev, and I. Safro, "Multilevel combinatorial optimization across quantum architectures," ACM Transactions on Quantum Computing, vol. 2, no. 1, pp. 1–29, 2021.
  * (17) K. Okada, H. Nishi, T. Kosugi, and Y. Matsushita, "Systematic study on the dependence of the warm-start quantum approximate optimization algorithm on approximate solutions," Scientific Reports, vol. 14, no. 1, p. 1167, 2024.
  * (18) D. Egger, J. Mareček, and S. Woerner, "Warm-starting quantum optimization," Quantum, vol. 5, p. 479, 2021.
  * (19) A. Buluç, H. Meyerhenke, I. Safro, P. Sanders, and C. Schulz, "Recent advances in graph partitioning," in Algorithm Engineering: Selected Results and Surveys, LNCS 9220, Springer-Verlag, pp. 117–158, 2016.
  * (20) B. Tsvelikhovskiy, I. Safro, and Y. Alexeev, "Symmetries and Dimension Reduction in Quantum Approximate Optimization Algorithm," arXiv:2309.13787v2, 2023.
  * (21) R. Shaydulin and S. Wild, "Exploiting symmetry reduces the cost of training QAOA," IEEE Transactions on Quantum Engineering, vol. 2, pp. 1-9, 2021.
  * (22) D. Herman, C. Googin, X. Liu, Y. Sun, A. Galda, I. Safro, M. Pistoia, and Y. Alexeev, "Quantum computing for finance," Nature Reviews Physics, vol. 5, no. 8, pp. 450-465, 2023.
  * (23) V. G. Vizing, "On an estimate of the chromatic class of a $p$-graph," Diskret. Analiz, no. 3, pp. 25-30, 1964.
  * (24) L. Zhu, H. Lun Tang, F. A. Calderon-Vargas, N. Mayhall, E. Barnes, and S. Economou, "Adaptive quantum approximate optimization algorithm for solving combinatorial problems on a quantum computer," Phys. Rev. Research, vol. 4, no. 3, 2022.