Exponential Lie-algebra gaps for QAOA-MaxCut
on asymmetric graphs

Abstract

The shared parameters of the quantum approximate optimization algorithm (QAOA) for MaxCut constrain its standard dynamical Lie algebra to the subalgebra of the multi-angle algebra fixed by graph automorphisms. We show that this symmetry bound can overestimate the standard dimension by an exponential factor. For every $k\geq 7$ , we construct a connected asymmetric graph on $7k$ vertices with maximum degree five for which the symmetry bound is at least $(2048/1985)^{k}-o(1)$ times the standard dimension. This disproves the universal constant-factor conjecture of Mao, Yuan, Allcock, and Zhang (arXiv 2025). The construction starts from the seven-qubit hidden-symmetry example of Gargiulo, Menta, Giovannetti, and Zeier (arXiv 2026). We express its invariant sector by a product of singlet projectors that leaves one qubit unrestricted. Coupling copies through that qubit preserves an independent projector for each copy, while a rigid tree eliminates graph automorphisms. A general amplification theorem converts these projectors into the exponential dimension gap. The largest irreducible component occupies at most a $(63/64)^{k}$ fraction of the $2^{7k-1}$ -dimensional $+1$ eigenspace of global bit flip. This exponential additive deficit contradicts the universal polynomial-gap formulation of Kazi et al. (PRX Quantum 2025).

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

For MaxCut, the standard quantum approximate optimization algorithm (QAOA) applies the same rotation angle to every vertex and the same interaction angle to every edge. Its dynamical Lie algebra is therefore generated by two sums, whereas the multi-angle ansatz controls each term separately. Comparing these algebras asks how much freedom is lost through parameter sharing, independently of circuit depth [1, 2]. Graph automorphisms give a necessary restriction: the shared sums are unchanged by every permutation preserving the graph. On an asymmetric graph this restriction disappears. It does not follow that the standard algebra is as large as the multi-angle one.

The reason is that a symmetry of the Hamiltonians need not permute vertices. A projector may commute with a sum because contributions from different terms cancel, although it fails to commute with individual terms. Singlet states provide the local example used here: $X_{a}+X_{b}$ annihilates $(|01\rangle-|10\rangle)/\sqrt{2}$ , while $X_{a}$ alone moves it out of its one-dimensional span. A graph can have no nontrivial automorphisms and still support such cancellations across its shared mixer and cost Hamiltonians. The resulting invariant subspaces restrict standard QAOA even when the multi-angle controls can mix them.

Finite examples of this phenomenon leave a quantitative question open. Kazi et al. analyze hidden symmetries and invariant components [2]; Gargiulo et al. give a seven-qubit example with a $2\oplus 126$ invariant decomposition [4]. Such a splitting alone need only remove a small fraction of the available operators. Indeed, small-graph calculations led Mao, Yuan, Allcock, and Zhang to conjecture that the automorphism-fixed multi-angle algebra always estimates the standard dimension within a universal constant [3, Conjecture 38]. We construct connected asymmetric graphs for which this ratio grows exponentially with the number of vertices.

Simply taking disjoint copies of a hidden-symmetry example is insufficient: the graph would be disconnected and its identical copies could be permuted. Adding edges to remove those defects can also destroy the local invariant subspaces. Our construction separates these two requirements. For the seven-qubit example, the rank-two projector factors into three singlet projectors and acts as the identity on the remaining qubit. Edges joining these unrestricted qubits preserve the projector in every copy. We can therefore choose the connection pattern solely to enforce graph rigidity. A tree with three unequal arms does so with maximum degree five in the assembled graph.

The dimension calculation explains why a small local splitting suffices. For $k$ copies, the full Hilbert-space dimension is $128^{k}$ , whereas the sum of squared dimensions of the invariant blocks is

(2^{2}+126^{2})^{k}=15880^{k}<128^{2k}.

A block of dimension $d$ supports at most $d^{2}$ independent skew-Hermitian operators. The strict loss in this sum therefore multiplies across copies, even though each individual projector has rank only two. Global bit-flip parity divides both dimension estimates by two and leaves the exponential ratio intact. No classification of the standard algebra inside the blocks is required.

Let $G=(V,E)$ be a finite simple unweighted graph on $N\geq 1$ vertices, with Hilbert space $\mathcal{H}_{G}=(\mathbb{C}^{2})^{\otimes N}$ . Write $X_{v}$ and $Z_{v}$ for the Pauli operators on qubit $v$ , extended by the identity on all other factors. We use the traceless Hamiltonians

H_{X}(G)=\sum_{v\in V}X_{v},\qquad H_{ZZ}(G)=\sum_{\{u,v\}\in E}Z_{u}Z_{v}.

(1)

The usual MaxCut cost operator differs from $H_{ZZ}(G)$ by a nonzero scalar factor and an additive scalar operator; we omit the latter, which contributes only a global phase. Define

	$\displaystyle\mathfrak{g}_{\mathrm{std},G}$	$\displaystyle=\Lie\{iH_{X}(G),iH_{ZZ}(G)\},$		(2)
	$\displaystyle\mathfrak{g}_{\mathrm{ma},G}$	$\displaystyle=\Lie\bigl(\{iX_{v}:v\in V\}\cup\{iZ_{u}Z_{v}:\{u,v\}\in E\}\bigr).$		(3)

Here $\Lie$ denotes generation as a real Lie algebra. Throughout, Lie-algebra dimensions are real and Hilbert-space dimensions are complex.

An automorphism $\pi\in\Aut(G)$ acts by a unitary $U_{\pi}$ permuting the tensor factors. Following the natural-algebra terminology of Kazi et al. [2, Sec. VI], put

\mathfrak{g}_{\mathrm{nat},G}=(\mathfrak{g}_{\mathrm{ma},G})^{\Aut(G)}=\{A\in\mathfrak{g}_{\mathrm{ma},G}:U_{\pi}AU_{\pi}^{*}=A\text{ for every }\pi\in\Aut(G)\}.

(4)

This fixed-point space is a Lie subalgebra containing both standard generators, and hence

\mathfrak{g}_{\mathrm{std},G}\subseteq\mathfrak{g}_{\mathrm{nat},G}\subseteq\mathfrak{g}_{\mathrm{ma},G}.

(5)

Thus $\dim\mathfrak{g}_{\mathrm{nat},G}$ is the upper bound obtained after imposing graph automorphisms. Earlier exponential comparisons on complete graphs [2, Sec. VII.C] use the unrestricted multi-angle algebra and retain the loss caused by those automorphisms. The conjecture at issue here instead asks for a universal $C>1$ satisfying

\dim\mathfrak{g}_{\mathrm{nat},G}\leq C\dim\mathfrak{g}_{\mathrm{std},G}

(6)

for connected graphs [3, Conjecture 38, Sec. 4.7]. The following result disproves it even when the automorphism restriction is vacuous.

Theorem 1 (Exponential symmetry gap).

For every integer $k\geq 7$ , there is a connected simple unweighted graph $G_{k}$ with $7k$ vertices, $9k-1$ edges, and maximum degree $5$ , such that

\Aut(G_{k})=\{1\},\qquad\dim\mathfrak{g}_{\mathrm{std},G_{k}}\leq\frac{15880^{k}}{2}-1,\qquad\dim\mathfrak{g}_{\mathrm{nat},G_{k}}=2^{14k-1}-2.

(7)

In particular,

\frac{\dim\mathfrak{g}_{\mathrm{nat},G_{k}}}{\dim\mathfrak{g}_{\mathrm{std},G_{k}}}\geq\left(\frac{2048}{1985}\right)^{k}-\frac{4}{15880^{k}}\longrightarrow\infty.

(8)

Since $N=7k$ , the lower bound is exponential in the graph size, with a linear number of edges and uniformly bounded degree. The standard algebra need not fill the invariant blocks, so its exact dimension may be smaller than the upper bound in (7).

The blocks also control irreducible invariant subspaces. The global bit flip

F_{G}=X^{\otimes N}

commutes with all generators in (3). Let $m(G)$ be the largest dimension of an irreducible constituent of the representation of $\mathfrak{g}_{\mathrm{std},G}$ on

\mathcal{H}_{+}(G)=\ker(F_{G}-\mathbb{I}).

This sector has dimension $2^{N-1}$ . For connected asymmetric graphs, Kazi et al. consider the gap

\Delta(G)=2^{N-1}-m(G)

(9)

and formulate a polynomial upper bound in [2, Eq. (41) and Conjecture 1, Sec. IX].

Corollary 2 (Invariant-component gap).

For the graphs of Theorem 1,

m(G_{k})\leq\frac{126^{k}}{2},\qquad\Delta(G_{k})\geq\frac{128^{k}-126^{k}}{2}=2^{7k-1}\left[1-\left(\frac{63}{64}\right)^{k}\right].

(10)

Consequently $\Delta(G_{k})/2^{7k-1}\to 1$ .

Thus the gap approaches the entire parity-sector dimension. This rules out the universal polynomial bound displayed in [2, Conjecture 1]. Its surrounding discussion also considers typical graphs, and the present family does not contradict that possibility. In fact, for $G\sim G(N,1/2)$ , Mao et al. prove $\mathfrak{g}_{\mathrm{std},G}=\mathfrak{g}_{\mathrm{ma},G}$ with probability at least $1-\exp(-\Omega(N))$ [3, Theorem 3]; then (5) makes the dimension ratio one. The distinction is between a uniform claim over graphs and an assertion about most graphs.

The seven-vertex graph, its asymmetry, the pairing $(1,3),(2,7),(4,6)$ , and its computational $2\oplus 126$ decomposition are due to Gargiulo, Menta, Giovannetti, and Zeier [4, Result 1 and Figs. 1–2]. Our proof makes the local projector explicit and shows how to retain independent copies in a connected asymmetric graph. Section 2 verifies the local cancellation and the rigidity of the assembly. Section 3 counts the resulting blocks for a general projector and proves both dimension statements. The appendix records a missing term in the polynomial certificate printed in [4]; the construction uses the factorized projector and does not depend on that certificate.

2 A graph family with persistent local symmetries

2.1 The local projector and its coupling port

Let $H$ be the graph on $\{1,\ldots,7\}$ with edge set

E(H)=\{12,23,34,45,56,67,26,36\},

(11)

where $a b$ abbreviates $\{a,b\}$ . We designate vertex $5$ as the port: all edges connecting different copies of $H$ will meet their ports.

Figure 1: The seven-vertex graph from [4], with vertex

5

designated as the port. The projector uses the singlet pairs

(1,3)

(2,7)

, and

(4,6)

For two qubits $a, b$ , let $\SWAP_{ab}$ exchange their tensor factors. The singlet and its projector are

|s\rangle_{ab}=\frac{|01\rangle-|10\rangle}{\sqrt{2}},\qquad q_{ab}=|s\rangle\langle s|_{ab}=\frac{\mathbb{I}-\SWAP_{ab}}{2},

Define the local projector

P=q_{13}q_{27}q_{46}.

(12)

The three factors have disjoint supports. Their common range consists of three fixed singlets and an arbitrary state on qubit $5$ . That last factor is what allows this invariant sector to survive coupling to other copies; commutation with the isolated gadget Hamiltonians alone would not be enough.

Lemma 3 (Invariant projector at the port).

The operator $P$ is an orthogonal projector of rank $2$ . It satisfies

[P,H_{X}(H)]=0,\qquad H_{ZZ}(H)P=PH_{ZZ}(H)=0,

(13)

and, under the tensor factorization separating qubit $5$ , $P=\mathbb{I}_{5}\otimes P_{0}$ . Hence $P$ commutes with every coupling $Z_{5}Z_{w}$ to an external qubit $w$ . It also commutes with the global field $H_{Z}(H)=\sum_{v=1}^{7}Z_{v}$ .

Proof.

Each $q_{ab}$ has rank one. Their disjoint supports imply that their product is an orthogonal projector of rank $1\cdot 1\cdot 1\cdot 2=2$ . For $A\in\{X,Z\}$ , the singlet satisfies

(A_{a}+A_{b})|s\rangle_{ab}=0,\qquad(A_{a}+A_{b})q_{ab}=q_{ab}(A_{a}+A_{b})=0.

(14)

Decomposing the mixer as

H_{X}(H)=(X_{1}+X_{3})+(X_{2}+X_{7})+(X_{4}+X_{6})+X_{5}

gives $H_{X}(H)P=X_{5}P=PH_{X}(H)$ . Replacing $X$ by $Z$ gives the corresponding identity for $H_{Z}(H)$ . For the cost Hamiltonian,

	$\displaystyle H_{ZZ}(H)$	$\displaystyle=Z_{1}Z_{2}+Z_{2}Z_{3}+Z_{3}Z_{4}+Z_{4}Z_{5}+Z_{5}Z_{6}+Z_{6}Z_{7}+Z_{2}Z_{6}+Z_{3}Z_{6}$
		$\displaystyle=Z_{2}(Z_{1}+Z_{3})+(Z_{3}+Z_{5})(Z_{4}+Z_{6})+Z_{6}(Z_{2}+Z_{7}).$		(15)

In each summand, the collective $Z$ on one singlet pair annihilates the corresponding factor of $P$ by (14). Thus $H_{ZZ}(H)P=0$ ; taking adjoints gives $PH_{ZZ}(H)=0$ . Finally, (12) gives $P=\mathbb{I}_{5}\otimes P_{0}$ , which commutes with every external port coupling. ∎

This proves an invariant $2\oplus 126$ decomposition, including for the additional global $Z$ control considered in [4]; no irreducibility assertion about the $126$ -dimensional complement is needed. The projector is preserved by the shared sums but not by their individual terms. Indeed, for a non-port vertex $v$ , the operator $X_{v}$ sends its singlet to an orthogonal state, so $[P,X_{v}]\neq 0$ . No edge of $H$ joins the two qubits in a singlet pair. An internal edge operator $Z_{u}Z_{v}$ therefore takes either one or two singlets to orthogonal states, according as the edge meets the port or two different pairs. Hence $[P,Z_{u}Z_{v}]\neq 0$ for every $\{u,v\}\in E(H)$ . These local invariant sectors are therefore not preserved by the multi-angle dynamics.

2.2 Assembly along a rigid tree

The projector survives any choice of edges between ports. We now choose those edges so that the assembled graph has no automorphisms. The connection pattern must itself be rigid, and the copies must remain recognizable from the graph after attachment. The latter point prevents an automorphism from confusing a port with an internal vertex.

For $k\geq 7$ , let $T_{k}$ be the tree obtained by attaching three paths of lengths

1,\qquad 2,\qquad k-4

to a common endpoint, called the center. Lengths count edges, so $T_{k}$ has $1+1+2+(k-4)=k$ vertices and $k-1$ edges. Its center is the unique vertex of degree three. After deleting the center, the three components have distinct orders $1,2,k-4$ . An automorphism must therefore preserve each arm; since it fixes the endpoint at the center, it fixes each vertex along that arm. Thus $\Aut(T_{k})=\{1\}$ . The condition $k\geq 7$ ensures that all three arm lengths are distinct.

For every $v\in V(T_{k})$ , take a disjoint copy $H_{v}$ of $H$ with vertices $(v,1),\ldots,(v,7)$ and port $p_{v}=(v,5)$ . Retain the internal edges of each copy and add $\{p_{v},p_{w}\}$ for every $\{v,w\}\in E(T_{k})$ . Call the resulting graph $G_{k}$ . Distinguishing its ports by vertex degree alone would not suffice: most ports have degree three or four, as do some internal vertices. Instead, the edges lying on cycles recover the individual copies intrinsically.

Lemma 4 (Graph properties).

The graph $G_{k}$ is connected, simple, unweighted, non-bipartite, and asymmetric. It has $7k$ vertices, $9k-1$ edges, and maximum degree $5$ , and is not a cycle.

Proof.

Connectedness follows from that of $H$ and $T_{k}$ ; simplicity and unit edge weights are preserved by the construction. The vertex and edge counts are $7k$ and $8k+(k-1)=9k-1$ . Every non-port vertex has degree at most four, and

\deg_{G_{k}}(p_{v})=2+\deg_{T_{k}}(v)\leq 5,

with equality at the center port. The triangle on vertices $(v,2),(v,3),(v,6)$ shows that $G_{k}$ is non-bipartite. The degree-five vertex excludes a cycle.

To prove asymmetry, first observe that every inter-port edge is a bridge. Deleting the corresponding edge of $T_{k}$ partitions its vertices into two sets, and the same partition of the gadget copies leaves precisely that inter-port edge crossing between them. The internal edges $12$ and $67$ in each copy are also bridges, since they meet leaves. All other internal edges lie on the triangle $2\text{-}3\text{-}6\text{-}2$ or the cycle $3\text{-}4\text{-}5\text{-}6\text{-}3$ .

It follows that the subgraph consisting of all edges lying on a cycle, after discarding isolated vertices, has exactly $k$ connected components

C_{v}=G_{k}[\{(v,2),(v,3),(v,4),(v,5),(v,6)\}],\qquad v\in V(T_{k}).

Any automorphism of $G_{k}$ permutes these components. Form an auxiliary graph whose vertices are the $C_{v}$ , with an edge between two components when an edge of $G_{k}$ joins them. This graph is exactly $T_{k}$ . Since $T_{k}$ is rigid, every $C_{v}$ is fixed setwise. Within $C_{v}$ , the port $p_{v}$ is the unique vertex adjacent to a vertex of another component $C_{w}$ . Every vertex of $T_{k}$ has a neighbor, so this characterization fixes every port. The two leaves attached to $C_{v}$ must remain attached to that same component; thus each whole copy $H_{v}$ is fixed setwise.

It remains to check the rooted graph $(H,5)$ . Its two neighbors of $5$ , namely $4$ and $6$ , have degrees two and four in $H$ , so both are fixed. Vertex $3$ is the other neighbor of $4$ and is therefore fixed. Among the remaining neighbors of $6$ , vertices $2$ and $7$ have degrees three and one, respectively, so they are fixed as well. Vertex $1$ is fixed last. Hence every vertex of every copy is fixed, proving $\Aut(G_{k})=\{1\}$ . ∎

3 Amplification of invariant sectors

The graph construction has preserved one independent binary projector per copy. We now convert those projectors into the two bounds. The Lie-algebra estimate sums squared block dimensions; the irreducible-component estimate uses the largest block dimension. Both calculations can be made for any local splitting of ranks $r$ and $d-r$ , provided its projector is the identity on the port. A trace calculation then shows that global parity splits every block equally.

For the multi-angle algebra we use the classification of Kazi et al. [2, Theorem B4]: for a connected non-bipartite $N$ -vertex graph $G$ that is not a cycle,

\mathfrak{g}_{\mathrm{ma},G}\cong\mathfrak{su}(2^{N-1})\oplus\mathfrak{su}(2^{N-1}),\qquad\dim\mathfrak{g}_{\mathrm{ma},G}=2^{2N-1}-2.

(16)

The same case is contained in the independent classification of Kökcü et al. [5, Theorem I.1], after conjugating each qubit by the Hadamard gate. Graphs satisfying these hypotheses have a vertex of degree greater than two, as required there.

Proposition 5 (Ported-projector amplification).

Let $(K,p)$ be a finite simple graph with $h$ vertices and a designated port, and put $d=2^{h}$ . Suppose that an orthogonal projector $P=\mathbb{I}_{p}\otimes P_{0}$ has rank $0<r<d$ and satisfies

[P,H_{X}(K)]=[P,H_{ZZ}(K)]=0.

Let $\Gamma$ be formed from $k\geq 1$ disjoint copies of $(K,p)$ by adding edges only between their ports. Set

A=r^{2}+(d-r)^{2},\qquad D=\max\{r,d-r\}.

Then

\dim\mathfrak{g}_{\mathrm{std},\Gamma}\leq\frac{A^{k}}{2}-1,\qquad m(\Gamma)\leq\frac{D^{k}}{2}.

(17)

If, in addition, $\Gamma$ is connected, non-bipartite, asymmetric, and not a cycle, then

\dim\mathfrak{g}_{\mathrm{nat},\Gamma}=\frac{d^{2k}}{2}-2,\qquad\frac{\dim\mathfrak{g}_{\mathrm{nat},\Gamma}}{\dim\mathfrak{g}_{\mathrm{std},\Gamma}}\geq\left(\frac{d^{2}}{A}\right)^{k}-\frac{4}{A^{k}}.

(18)

For a fixed gadget and projector, the latter lower bound tends to infinity along any such family with $k\to\infty$ .

Proof.

Index the copies by $v\in\{1,\ldots,k\}$ . Let $P_{v}$ be the local copy of $P$ , let $Q_{v}=\mathbb{I}-P_{v}$ , and denote their full-space embeddings by $\widehat{P}_{v}$ and $\widehat{Q}_{v}=\mathbb{I}-\widehat{P}_{v}$ . If $E_{B}$ is the set of pairs indexing the added port edges, the standard Hamiltonians are

H_{X}(\Gamma)=\sum_{v}H_{X}(K_{v}),\qquad H_{ZZ}(\Gamma)=\sum_{v}H_{ZZ}(K_{v})+\sum_{\{v,w\}\in E_{B}}Z_{p_{v}}Z_{p_{w}}.

(19)

Each $\widehat{P}_{v}$ commutes with both Hamiltonians: the internal terms commute by assumption or disjoint support, and the added terms commute because $P_{v}$ acts as the identity on its port. It therefore commutes with every element of $\mathfrak{g}_{\mathrm{std},\Gamma}$ .

The projectors $\widehat{P}_{v}$ commute with one another. For $S\subseteq\{1,\ldots,k\}$ , define

R_{S}=\prod_{v\in S}\widehat{P}_{v}\prod_{v\notin S}\widehat{Q}_{v}.

They are pairwise orthogonal projectors summing to the identity: if two index sets differ at $v$ , their product contains $\widehat{P}_{v}\widehat{Q}_{v}=0$ , and their sum is the expansion of $\prod_{v}(\widehat{P}_{v}+\widehat{Q}_{v})=\mathbb{I}$ . Their ranks are

d_{S}=\rank R_{S}=r^{|S|}(d-r)^{k-|S|}.

(20)

We next refine these blocks by global parity. On a single copy,

F_{v}=X^{\otimes h}=i^{h}\exp\!\left(-\frac{i\pi}{2}H_{X}(K_{v})\right).

(21)

Indeed, the single-qubit $X$ operators commute and $\exp(-i\pi X/2)=-iX$ . The hypothesis on $P_{v}$ implies $[P_{v},F_{v}]=0$ . The tensor factorization at the port gives

\tr(F_{v}P_{v})=\tr(X_{p_{v}})\,\tr\!\left(X^{\otimes(h-1)}P_{0}\right)=0.

(22)

Since $\tr F_{v}=0$ , also $\tr(F_{v}Q_{v})=0$ . The global parity $F_{\Gamma}=\bigotimes_{v}F_{v}$ commutes with $R_{S}$ and with the standard generators. Moreover,

\tr(F_{\Gamma}R_{S})=\prod_{v\in S}\tr(F_{v}P_{v})\prod_{v\notin S}\tr(F_{v}Q_{v})=0.

(23)

The restriction of $F_{\Gamma}$ to $\ran R_{S}$ is a Hermitian involution of trace zero. Its two eigenspaces

\mathcal{H}_{S,\pm}=\ran R_{S}\cap\ker(F_{\Gamma}\mp\mathbb{I})

therefore both have dimension $d_{S}/2$ .

Every element of $\mathfrak{g}_{\mathrm{std},\Gamma}$ preserves these spaces and is skew-Hermitian and traceless. Hence

\mathfrak{g}_{\mathrm{std},\Gamma}\subseteq\left(\bigoplus_{S\subseteq\{1,\ldots,k\}}\bigl[\mathfrak{u}(\mathcal{H}_{S,+})\oplus\mathfrak{u}(\mathcal{H}_{S,-})\bigr]\right)\cap\mathfrak{su}(d^{k}).

(24)

Here $\mathfrak{u}(\mathcal{W})$ denotes the real Lie algebra of all skew-Hermitian operators on $\mathcal{W}$ , of dimension $(\dim\mathcal{W})^{2}$ . Global tracelessness imposes one nonzero real linear condition on the direct sum in (24). Consequently,

	$\displaystyle\dim\mathfrak{g}_{\mathrm{std},\Gamma}$	$\displaystyle\leq\frac{1}{2}\sum_{S\subseteq\{1,\ldots,k\}}d_{S}^{2}-1$
		$\displaystyle=\frac{1}{2}\sum_{s=0}^{k}\binom{k}{s}r^{2s}(d-r)^{2(k-s)}-1=\frac{A^{k}}{2}-1.$		(25)

The bound uses only the commuting projectors. It does not require the standard generators to generate the full algebra inside any block.

The positive-parity sector decomposes as

\mathcal{H}_{+}(\Gamma)=\bigoplus_{S}\mathcal{H}_{S,+}.

An irreducible subspace need not coincide with one displayed block; the following projection argument still bounds its dimension. Let $W$ be any nonzero irreducible invariant subspace. At least one orthogonal projection $\pi_{S}$ onto $\mathcal{H}_{S,+}$ is nonzero on $W$ . This projection commutes with the representation, so $\ker(\pi_{S}|_{W})$ is invariant. Irreducibility makes that kernel zero. Thus $\pi_{S}|_{W}$ is injective, and

\dim W\leq\dim\mathcal{H}_{S,+}\leq\frac{1}{2}\max_{S}r^{|S|}(d-r)^{k-|S|}=\frac{D^{k}}{2}.

The representation is completely reducible: if a subspace is invariant under skew-Hermitian operators, its orthogonal complement is invariant as well. Thus this bound applies to every irreducible constituent and proves the estimate for $m(\Gamma)$ .

Under the additional graph hypotheses, (16) applies with $N=hk$ . Asymmetry gives $\mathfrak{g}_{\mathrm{nat},\Gamma}=\mathfrak{g}_{\mathrm{ma},\Gamma}$ , proving its dimension in (18). Since $H_{X}(\Gamma)\neq 0$ , the standard algebra has positive dimension. Using the weaker upper bound $A^{k}/2$ for the denominator gives

\frac{\dim\mathfrak{g}_{\mathrm{nat},\Gamma}}{\dim\mathfrak{g}_{\mathrm{std},\Gamma}}\geq\frac{d^{2k}/2-2}{A^{k}/2}=\left(\frac{d^{2}}{A}\right)^{k}-\frac{4}{A^{k}}.

Finally,

A=d^{2}-2r(d-r)<d^{2}

because $0<r<d$ , which proves the divergence assertion. ∎

Only one global parity is used in this argument. An inter-port term $Z_{p_{v}}Z_{p_{w}}$ commutes with $F_{\Gamma}$ but anticommutes with the bit flip $F_{v}$ on just one endpoint copy. In particular, the proof gives a factor $1/2$ in (25), not a factor $2^{-k}$ .

Proof of Theorem 1 and Corollary 2.

Use the graph $G_{k}$ of Section 2 and the projector from Lemma 3. Their parameters are

h=7,\qquad d=128,\qquad r=2,\qquad A=2^{2}+126^{2}=15880,\qquad D=126.

Lemma 4 verifies all graph hypotheses of Proposition 5, as well as the required counts and maximum degree. The proposition yields (7), and

\frac{d^{2}}{A}=\frac{16384}{15880}=\frac{2048}{1985}

gives (8). Its bound on $m(G_{k})$ gives (10) upon substituting $N=7k$ into (9). Finally,

1-\left(\frac{63}{64}\right)^{k}\leq\frac{\Delta(G_{k})}{2^{7k-1}}\leq 1,

which proves the stated limit. ∎

The invariant splitting also identifies a subspace containing the usual initial state. Writing $|+\rangle=(|0\rangle+|1\rangle)/\sqrt{2}$ , we have $q_{ab}|++\rangle=0$ . Therefore

|+\rangle^{\otimes 7k}\in\mathcal{H}_{\varnothing,+},\qquad\dim\mathcal{H}_{\varnothing,+}=\frac{126^{k}}{2},

and standard QAOA evolution remains in this space at every depth. This invariant space is smaller than the full parity sector by the factor $(63/64)^{k}$ , but remains exponentially large. Its dimension is only an upper bound on the smallest invariant subspace containing the initial state. Determining that subspace, or the standard algebra acting on it, would be needed to draw conclusions about classical simulation or QAOA optimization from this construction.

Appendix A The polynomial symmetry certificate

For the graph (11), the expression printed in [4, Result 1 and the paragraph following it] uses

a=\Pi_{13},\qquad b=\Pi_{27},\qquad c=\Pi_{46},\qquad\Pi_{ij}=2\SWAP_{ij}-\mathbb{I},

and reads

S_{\mathrm{pr}}=-(a+b+c)+a(b+c)-abc.

(26)

Under these conventions, the polynomial is missing the term $b c$ . Indeed, the three operators commute, and $q_{13}=(\mathbb{I}-a)/4$ , with the analogous identities for the other two pairs. Thus

64P=(\mathbb{I}-a)(\mathbb{I}-b)(\mathbb{I}-c)=\mathbb{I}+S_{\mathrm{pr}}+bc.

(27)

Lemma 3 implies that $S_{\mathrm{pr}}+bc=64P-\mathbb{I}$ commutes with the mixer, the cost, and the global $Z$ field.

The missing term changes the commutator. To see this directly, use the computational basis ordered by vertices $1,\ldots,7$ and put

x=|0100000\rangle,\qquad y=|0000001\rangle.

Both $a$ and $c$ act as the identity on $\operatorname{span}\{x,y\}$ , whereas $bx=2y-x$ . On that span (26) reduces to $-\mathbb{I}-b$ , so $S_{\mathrm{pr}}x=-2y$ . A bit string with a single $1$ at a vertex of degree $t$ has $H_{ZZ}(H)$ -eigenvalue $8-2t$ : precisely the $t$ incident edges contribute $-1$ rather than $+1$ . Vertices $2$ and $7$ have degrees three and one, respectively; hence

H_{ZZ}(H)x=2x,\qquad H_{ZZ}(H)y=6y,

and therefore

[S_{\mathrm{pr}},H_{ZZ}(H)]x=-4y-(-12y)=8y\neq 0.

The correction concerns the displayed certificate in the cited version. The factorized projector (12) provides an independent analytic proof of the invariant splitting used here; no numerical decomposition or external certificate is required.

References

[1] J. Allcock, M. Santha, P. Yuan, and S. Zhang, On the dynamical Lie algebras of quantum approximate optimization algorithms, Quantum 10, 2119 (2026). https://doi.org/10.22331/q-2026-05-29-2119.
[2] S. Kazi, M. Larocca, M. Farinati, P. J. Coles, M. Cerezo, and R. Zeier, Analyzing the Quantum Approximate Optimization Algorithm: Ansätze, Symmetries, and Lie Algebras, PRX Quantum 6, 040345 (2025). https://doi.org/10.1103/yfwq-yqmk.
[3] R. Mao, P. Yuan, J. Allcock, and S. Zhang, QAOA-MaxCut has barren plateaus for almost all graphs, arXiv:2512.24577v1 [quant-ph] (2025). https://arxiv.org/abs/2512.24577v1.
[4] R. Gargiulo, R. Menta, V. Giovannetti, and R. Zeier, Obstructions to universality in globally controlled qubit graphs, arXiv:2604.18699v1 [quant-ph] (2026). https://arxiv.org/abs/2604.18699v1.
[5] E. Kökcü, R. Wiersema, A. F. Kemper, and B. N. Bakalov, Classification of dynamical Lie algebras generated by spin interactions on undirected graphs, J. Math. Phys. 67, 052205 (2026). https://doi.org/10.1063/5.0283277.

Exponential Lie-algebra gaps for QAOA-MaxCut on asymmetric graphs

Abstract

1 Introduction

Theorem 1 (Exponential symmetry gap).

Corollary 2 (Invariant-component gap).

2 A graph family with persistent local symmetries

2.1 The local projector and its coupling port

Lemma 3 (Invariant projector at the port).

Proof.

2.2 Assembly along a rigid tree

Lemma 4 (Graph properties).

Proof.

3 Amplification of invariant sectors

Proposition 5 (Ported-projector amplification).

Proof.

Proof of Theorem 1 and Corollary 2.

Appendix A The polynomial symmetry certificate

References

Exponential Lie-algebra gaps for QAOA-MaxCut
on asymmetric graphs