1 Introduction↩︎

Combinatorial optimization problems (COPs) with global constraints pose a specific challenge for shallow variational quantum circuits. Feasible solutions occupy a vanishing fraction of the full Hilbert space, so any method that explores the entire hypercube pays an intrinsic feasibility penalty. This paper isolates that bottleneck for the Quantum Approximate Optimization Algorithm (QAOA)[1] and develops a transparent way to assess the state prepared by the algorithm for arbitrary shallow schedules of length \(p = O(n)\). QAOA is arguably one of the most studied Quantum algorithms in recent years and numerous variants have emerged. In this paper, we shall refer to the original construction in Ref. [1] as the generic QAOA ansatz in order to facilitate a clear comparison with a minimal constraint-aware variant that bakes constraint structure and symmetries into its quantum dynamics. The distinction is made explicit in Subsection 1.2.

Instead of monitoring only expectation values and approximation ratios, we study the full probability profile of depth-\(p\) QAOA states through four lines of analyses. First, a Walsh–Fourier calculation on the Boolean cube reveals that the one-hot constraints behind permutation encodings have exponentially small low-degree Fourier mass. At \(p=1\) the \(X\)-mixer acts by pure phases in this Walsh/Fourier basis, so the generic ansatz cannot significantly lift feasible mass above the uniform baseline, up to polynomial slack, and this holds uniformly over angles. Second, a gentle cost-angle averaging argument, applicable after a simple rescaling that holds for standard integer or rational instances, pins the feasible baseline at \(|\Pi|/2^N\). Third, a hypercontractive (\(l_4\)) bound on the output amplitudes then show that most angles concentrate around this baseline, which is useful for understanding shallow-depth training without assuming anything about gradients. Finally, locality enters through light-cone growth. With commuting, \(r\)-local diagonal costs, information propagates at most one neighborhood per layer. A dependency–graph argument turns this into a bound on the joint probability that all row and column constraints hold, and the same limitation persists beyond one layer in any depth window where the overlap-corrected light-cone exponent remains larger than the encoded-manifold baseline cost \(n\ln n\). In particular, for the one-dimensional nearest-row geometry this includes \(p=o\!\left(\frac{n}{\ln n}\right).\) The resulting picture is that the generic ansatz faces a structural ceiling that does not disappear at depth one and continues to matter at larger but still shallow depths.

Against this envelope, we place the recently introduced variant of QAOA called the Constraint-Enhanced Quantum Approximate Optimization algorithm (CE–QAOA)[2]. This is a constraint-enhanced kernel that works directly on the one-hot manifold with explicit symmetry enhancements derived from problem structure. The ingredients include an ancilla-free \(W\)-state initialization, a normalized block–\(XY\) mixer that preserves the encoded space and penalty derived co-design symmetry. This framework provides an existence result needed to benchmark the probability profile of generic QAOA. Thus, we take the bounds derived for CE–QAOA kernel from prior work [2] as a minimal exemplar of problem–algorithm co-design as a route to provable exponential enhancement. For any permutation constrained problem of size \(n\), its one-hot encoding requires \(N=n^2\) qubits (Def 1). The resulting enhancement is quantified in terms of \(\exp(\Theta(n^2))\) separation between the constraint enhanced variant and the generic QAOA in Eq. ?? and proved later in Theorem 2 for \(p=1\) and extended in Theorem 3 to overlap-controlled sublinear depths respectively. It is worth noting that we have only used the minimal, most conservative guarantee from Ref. [2]. Our aim is to place the minimal guarantee from the constraint-enhanced kernel against a sharp upper envelope for the generic ansatz and to show how even a modest in-subspace design changes the feasibility profile at shallow depth.

The rest of the paper proceeds as follows. Section 1.1 places our work in context of recent research works in fundamental limitations of shallow Variational Quantum Algorithms (VQA). Section 1.2 reviews the generic ansatz, recalls the definition of the CE–QAOA kernel and records their symmetry, mixing properties and the core existence result. In Section  2 we collect our main results. In Section 3 we discuss the materials and methods necessary to establish the angle-averaging, fourth-moment, and harmonic-analysis bounds that define the generic envelope. Section 3.7 develops light-cone barriers for the generic QAOA ansatz at \(p=1\) and Section 3.8 extends the light-cone barrier analyses to constant/sublinear depths. Section 4 concludes our findings.

1.1 Related Work↩︎

Variational quantum algorithms (VQAs), and QAOA in particular, have been studied along three complementary axes: (i) trainability and landscape structure, (ii) locality/light-cone limitations at shallow depth, and (iii) architecture- or problem-aware ansätze that encode constraints or symmetries from the outset. On the landscape side, early work identified barren plateaus as a key obstruction to gradient-based training in large systems [3], [4]. More recent analyses quantify landscape information content, revealing how much task-relevant signal survives in variational loss surfaces [5], and study the energy landscape structure of small-depth QAOA instances [6]. The QAOA design space has also broadened beyond the original transverse-field mixer to alternating operator ansätze tailored to problem structure [7], while symmetry constraints can both obstruct and guide expressivity [8]. Mitigation strategies such as classical shadows for gradient estimation [9] and warm starts [10] aim to stabilize training or inject structure into initial states.

A second line of work formalizes locality as the principal barrier at small depths since shallow circuits can only build correlations within a light cone whose radius grows at most linearly with depth. These are essentially Lieb–Robinson-type locality bounds [11], and they underlie modern limitations for low-depth QAOA on sparse graphs. For bounded-degree graph families, Farhi, Gamarnik, and Gutmann proved that small-\(p\) QAOA “needs to see the whole graph,” producing typical- and worst-case examples where performance is capped by local neighborhoods [12]. At constant levels \(p=O(1)\), quantitative barriers have been established on sparse hypergraphs and spin-glass models [13], while in a broader framework of local quantum algorithms, limitations propagate up to \(p<\varepsilon\log n\) for certain CSPs with the (coupled) overlap-gap property [14], [15]. Orthogonally, results on concentration for shallow circuits show output observables of low-depth evolutions are tightly concentrated, limiting global coordination at small \(p\) [16]. Collectively, these works support the heuristic that constant or slowly growing depth cannot generate the long-range correlations required by global constraints.

A third, complementary, line of work focuses on architecture- and problem-aware ansätze that encode constraints, symmetries, or known structure directly at the circuit level. In the QAOA setting, the alternating-operator framework extends the original transverse-field mixer by replacing it with constraint-preserving unitaries tailored to specific combinatorial structure [7], [17]. Constrained mixers and symmetry-projected variational families have been designed to restrict the evolution to feasible manifolds or fixed symmetry sectors, thereby reducing the effective search space and sometimes alleviating barren-plateau effects  [8], [18], [19]. Domain-specific encodings and mixers for routing and scheduling problems further illustrate how problem-aware design can unlock strong empirical performance on structured instances [20], [21].

The current paper connects these three perspectives under a single quantitative lens by focusing on the feasible probability mass generated by shallow generic versus problem-aware variational circuits under global combinatorial constraints. Rather than bounding approximation ratios instance by instance, we derive angle-uniform upper bounds on the total probability that a shallow, generic QAOA state satisfies all permutation-style one-hot constraints, for depths \(p\) up to a sublinear fraction of \(n\) on interaction hypergraphs whose incidence growth is polynomial in \(n\). Against this envelope, we place a minimal constraint-enhanced kernel (CE–QAOA) that encodes the instance in a constrained one-hot manifold and mixes within it, thereby achieving a depth-matched, angle-robust exponential separation in feasible mass, cf.Eq. ?? , in a way that complements and connects prior landscape, locality, and architecture-aware analyses. By construction, the explicit problem–algorithm co-design in the kernel definition allows these results to apply to a broad class of constrained problems satisfying Definition 1.

1.2 Background↩︎

1.2.1 Generic QAOA↩︎

The generic QAOA [1] prepares the state \(\ket{\psi_p(\vec{\gamma},\vec{\beta})} =\bigl[\prod_{\ell=1}^{p}e^{-i\beta_\ell \sum_j X_j}\,e^{-i\gamma_\ell H_C}\bigr]\ket{+}^{\otimes N},\) i.e., a depth–\(p\) alternation of a transverse–field \(X\) mixer and a diagonal cost unitary on the computational basis. Parameters \((\vec{\gamma},\vec{\beta})\) are optimized (classically) to maximize an empirical objective. For the algorithm to be performant, typical schedules need to be short (\(p=O(1)\) or \(p\ll N\)) without going to the adiabatic limit[22]. Common ideas to improve algorithmic performance include linear/adiabatic ramps[23], parameter transfer across sizes/instances to reduce training cost while keeping the same mixer/cost structures [24], recursive elimination to iteratively fix variables based on low–depth runs, shrinking the instance before a final classical solve [8], [25], warmstarting QAOA to help landscapes and convergence [10], [26].

1.2.2 Constraint–Enhanced QAOA↩︎

The alternating–operator (“QAOA+”) paradigm augments the generic X–mixer by feasibility–preserving mixers that act invariantly on constraint projectors, thereby confining evolution to structured subspaces [17], [19]. The Constraint–Enhanced QAOA (CE–QAOA) introduced in Ref. [2] follows this direction but makes the problem–algorithm co–design explicit. As can be seen in Definition 1, the kernel specifies (i) the valid problem classes with the admissible penalty structure and symmetries, the mixer and initial state.

Evidently, the identifiable problem classes is broad and far from trivial. They include: Travelling Salesman (TSP/ATSP) [27], [28], Quadratic Assignment Problem (QAP) [29], the shared transportation problems[30], Generalized Assignment / Multiple–Knapsack [31], \(k\)D Matching (NP-complete for \(k\ge3\)) [32], etc. Some base cases are polynomial-time solvable but our interest is in the NP-hard variants (e.g. TSP/GAP/CVRP, etc.) for which the same one-hot encoding and symmetries apply.

2 Results↩︎

2.1 Fundamental Limitations↩︎

Our point of departure is the following question. By how much can a shallow variational quantum circuit concentrate probability mass on the feasible manifold of a globally constrained problem? We answer this for the canonical case of a permutation constrained problem of size \(n\) one-hot encoded into \(N=n^2\) qubits (e.g., assignment/TSP) by proving that generic QAOA initialized on \(|+\rangle^{\otimes N}\) with a \(X\) mixer and a diagonal cost cannot raise the feasible mass above the uniform baseline \(|\Pi|/2^{N}\) by more than polynomial factors at any fixed constant depth, and under standard locality, not even at sublinear depth \(p=\alpha n\). Where \(|\Pi|=n!\) and \(\alpha < 1.\)

Recall that the problem Hamiltonian is diagonal in computational basis and is denoted as \(H_C\). For any \(r\)–local diagonal \(H_C\) and all angles \((\beta,\gamma)\), we show that single layer \(p=1\) generic QAOA circuits cannot generate the long–range correlations required by the feasible solution space by more than polynomial slack: \[\label{eq:probs} P_{\Pi}^{\mathrm{(gen)}}(\beta,\gamma)\;\le\;\frac{|\Pi|}{2^{N}}\cdot \mathrm{poly}(n).\tag{1}\] The reason is twofold. Structurally, the \(p{=}1\) light cone confines each block one–hot projector to a finite neighborhood, so the \(O(n)\) constraints interact only through short dependencies. This caps any joint boost to at most polynomial over uniform. Spectrally, the indicator \(1_\Pi\) is overwhelmingly high-degree in Walsh/Krawtchouk space, while a single \(X\)-mixer layer only adds phases. Consequently, average over \(\gamma\) pins the baseline exactly and fourth-moment bounds show typical angles concentrate near it.

In contrast, a constraint-enhanced variant (CE-QAOA) that operates inside a block one-hot subspace and mixes with an all-to-all \(XY\) block mixer achieves an \(\exp[\Theta(n^2)]\) improvement over generic QAOA at the same depth. We arrive at the conclusion by establishing an upper envelope for generic QAOA and a lower envelope for CE–QAOA. To derive the upper envelopes, we employ harmonic analysis, angle-averaging, hyperconstrative fourth-moment, and light-cone analyses. Detailed proofs are presented in Methods and Materials ( Section 3). We now summarize the main conclusions.

2.1.0.1 Setup

We refer to a COP of size \(n\) as permutation constrained if the valid solutions can be identified as a \(n \times n\) permutation matrix. For such problems, the one-hot encoding requires \(N=n^2\) qubits. Let \(N\) be the number of qubits and \(\Pi=n!\) the size of the feasible permutation sector (row/column one–hot constrained). Consider the Boolean cube \(\{0,1\}^N\) and write any function \(f:\{0,1\}^N\!\to\!\mathbb{C}\) in the Walsh/Krawtchouk basis \(f(x)=\sum_{S\subseteq[N]}\widehat f(S)\,\chi_S(x)\) with characters \(\chi_S(x)=(-1)^{\langle S,x\rangle}\) and degree \(|S|\). This is a complete and unique Fourier expansion for any function \(f(x)\) with unique coefficients \(\widehat f(S)\)[33].

To connect this formalism the probability amplitudes in generic QAOA, we write \[H_C=\sum_{y\in\{0,1\}^N} C(y)\,|y\rangle\!\langle y| \quad\Rightarrow\quad U_C(\gamma)=e^{-i\gamma H_C} =\sum_{y} e^{-i\gamma C(y)}\,|y\rangle\!\langle y|.\] With the phase field \(\phi_\gamma(y):=e^{-i\gamma C(y)}\) and any basis vector \(|x\rangle\) we obtain the probability profile \[a_{\beta,\gamma}(x) =\langle x|U_X(\beta)U_C(\gamma)|+\rangle^{\otimes N} =2^{-N/2}\sum_{y} \underbrace{\langle x|U_X(\beta)|y\rangle}_{K_\beta(x,y)}\,\phi_\gamma(y).\] Because \(U_X(\beta)=\prod_{i=1}^N e^{-i\beta X_i}\), its \(Z\)-basis kernel factors as \[K_\beta(x,y) \;=\; \prod_{i=1}^N \langle x_i|e^{-i\beta X}|y_i\rangle \;=\; (\cos\beta)^{\,N-d(x,y)}(-i\sin\beta)^{\,d(x,y)} \;=\; (\cos\beta)^{N}\,(-i\tan\beta)^{\,d(x,y)},\]

where \(d(x,y)=|\;x\oplus y\;|\) is the Hamming distance.

Thus, we obtain a generic representation of the probability of obtaining a feasible permutation from generic QAOA as \[\label{eq:generic-probability} a_{\beta,\gamma}(x) \;=\; 2^{-N/2}\sum_{y\in\{0,1\}^N} K_\beta(x,y)\,\phi_\gamma(y).\tag{2}\]

For the indicator \(1_\Pi\) on the permutation submanifold, we show (Materials and Methods Sections 3.2 and 3.3 ) that the total probability mass is tiny up to logarithmic degree. To derive this we define the low-degree mass up to level \(d\) as \[\|f\|^2_{\le d}\;:=\;\sum_{|S|\le d}\!|\widehat f(S)|^2, \qquad \text{and high-degree mass } \|f\|^2_{> d}= \|f\|_2^2-\|f\|^2_{\le d}.\]

We introduce Krawtchouk analysis to calculate the low–degree weight in the one-hot sector (Lemma 4), and, after tensorizing rows/columns and convolving to obtain the weight of indicator \(1_\Pi\) on the permutation submanifold (Section 3.4). Our calculations show that both low–degree and high-degree mass remain exponentially suppressed. We denote the total output pmf as \(p(x)=|a_{\beta,\gamma}(x)|^2\). To compute the total feasible mass, we choose a degree truncation \(d=T=\Theta(\log n)\) and split \(p(x)\) as low and high degree parts follows \(p=p^{\le 2T}+p^{>2T}\). The low degree part accounts for all the contributions to the Fourier mass from degrees below the \(T\) threshold and the high degree split captures all degree contributions above \(T\). For the low–degree part we have (Lemma 8), \[\frac{1}{2^N}\langle \mathbf{1}_\Pi, p^{\le 2T}\rangle \le \frac{C_T n^{O(T)}}{2^{N}}.\]

For the high–degree tail is equally suppressed (Lemma 9). We have \[\frac{1}{2^N}\big|\langle \mathbf{1}_\Pi, p^{>2T}\rangle\big| \le \frac{\sqrt{|\Pi|}}{2^N}.\] Consequently, \(p=p^{\le 2T}+p^{>2T}\) yields the harmonic bound in Theorem 6: \[P_\Pi(\beta,\gamma)\;\le\;\frac{|\Pi|}{2^N}.\]

The angle averaging version of the result follows from an averaging over the phase field \(\phi_\gamma(y)\) if the spectrum of \(H_C\) is rescaled to lie on a lattice (after standard rescaling). This arises because then \(\mathbb{E}_\gamma[\phi_\gamma(y)\overline{\phi_\gamma(y')}]=\mathbf{1}_{\{C(y)=C(y')\}}\) leading cross–terms to cancel and \[\mathbb{E}_\gamma\big[P_\Pi(\beta,\gamma)\big]=\frac{|\Pi|}{2^N}.\]

The third bound is derived the fourth–moment (hyperconractivity) analysis of the probability profile. As outlined in Sec. 3.6, let \(a(x)=a_{\beta,\gamma}(x)\) and recall \(P_\Pi=\sum_{x\in\Pi}|a(x)|^2\). By Cauchy–Schwarz, \[\sum_{x\in\Pi} |a_x|^2 \;\le\; \sqrt{|\Pi|}\,\Bigl(\sum_{x}|a_x|^4\Bigr)^{1/2}. \label{eq:CS-L4m}\tag{3}\] Thus, any bound on \(\sum_x |a_x|^4\) yields an upper bound on \(P_{\Pi}\).

Averaging over \(\gamma\) (phase field), the one-bit calculation tensorizes to \[\mathbb{E}_\gamma\!\Big[\sum_x |a(x)|^4\Big] \;\le\;\Big(\tfrac12+\tfrac14\sin^2(2\beta)\Big)^{\!N} \;\le\;\Big(\tfrac34\Big)^{\!N},\] since \(\max_{\beta}\big(\tfrac12+\tfrac14\sin^2 2\beta\big)=\tfrac34\) (achieved at \(\beta=\pi/4\)). Thus, for typical angles we have, \[P_\Pi(\beta,\gamma) \;\lesssim\; \sqrt{|\Pi|}\,\Big(\tfrac34\Big)^{N/2} \;=\; \frac{|\Pi|}{2^N}\cdot \underbrace{2^N\,|\Pi|^{-1/2}\,\Big(\tfrac34\Big)^{N/2}}_{\text{exponentially small in }N},\] i.e.exponentially close to the uniform baseline.

The light-cone analysis provides some structural intuition for the above analysis. With \(U=U_X(\beta)U_C(\gamma)\) and \(H_C=\sum_j H_j\) diagonal, \(r\)–local, conjugation preserves diagonality and expands support by at most one \(r\)–local hyperedge. Each block projector \(P_B\) depends only on its radius-1 neighborhood in the interaction hypergraph; the \(2n\) one-hot constraints therefore form a bounded-dependency family. Standard cluster/dependency bounds then cap any feasible-mass boost to a polynomial over the uniform product baseline—fully consistent with the harmonic and moment bounds above.

Synthesis. All four routes—harmonic truncation with explicit low–degree suppression (Lemma  7 + Lemmas 8,9), angle averaging via the phase field \(\phi_\gamma\), fourth-moment with CS and the \((3/4)^N\) cap, and the light-cone locality barrier agree with Eq. 1 with typical angles exponentially close to \(|\Pi|/2^N\). This is precisely the \(p{=}1\) envelope used to compare against CE–QAOA, which evades the large \(\frac{1}{2^N}\) suppression at any depth.

2.2 The Path to Exponential Enhancements↩︎

The constraint-enhanced QAOA (CE-QAOA) operates inside a product one-hot subspace and mixes with an all-to-all \(XY\) block mixer. Our main conclusion is that it achieves an \(\exp[\Theta(n^2)]\) improvement over generic QAOA at the same depth. i.e. \[\frac{P^{\mathrm{(CE)}}_{p}}{P^{\mathrm{(generic)}}_{p}}.\] In order to make statements regarding the ratio \(\frac{P^{\mathrm{(CE)}}_{p}}{P^{\mathrm{(generic)}}_{p}}\), we need some robust lower envelope for CE–QAOA which we can compare to the upper envelope for generic QAOA outlined in Sec 2.1. The necessary lower envelope comes from a basic symmetry of the product one-hot construction in Sec. 1.2.2. For an instance in the kernel with \(m\) blocks of local dimension \(n\), a depth–\(p\) CE–QAOA layer stack is given as \[\ket{\psi_p(\vec{\gamma},\vec{\beta})} \;=\; \Bigl(\prod_{\ell=1}^{p} U_M(\beta_\ell)\,e^{-i\gamma_\ell H_C}\Bigr)\ket{s_0}, \qquad \vec{\gamma}=(\gamma_1,\dots,\gamma_p),\; \vec{\beta}=(\beta_1,\dots,\beta_p).\] Because \(U_M\) preserves the one–hot sector and \(H_C\) is diagonal, each layer maps the encoded manifold \(\mathcal{H}_{\mathrm{OH}}=(\mathcal{H}_1)^{\otimes m}\) to itself. The kernel’s pattern symmetry (block permutations \(S_m\) and global symbol relabelings \(S_n\)) permits a block–permutation twirl. Averaging any fixed circuit \(U\) over such relabelings yields a robust lower bound on the probability profile of the prepared state. For \(p=1\), let \(\ket{x^\star}\in \mathcal{H}_{\mathrm{OH}}\) be any fixed product basis vector and \(D=n^n\) be the size of the product one-hot manifold explored by CE-QAOA, we recall the following lower bounds from Ref. [2]:

From the foregoing, we can therefore conclude that for every target basis state \(x^{\star}\in\mathcal{H}_{\mathrm{OH}}\), and in particular for every feasible optimal label, the blockwise relabeling symmetry guarantees the existence of a blockwise permutation \(\mathsf P^\star\) such that, for the fixed grid angles \((\gamma,\boldsymbol{\beta})\) under consideration, \[\bigl|\langle x^{\star}\!\mid \mathsf P^{\star\dagger} U_{M}(\boldsymbol{\beta}) U_{C}(\gamma) \psi_{0}\rangle \bigr|^{2} \;\ge\; \frac{1}{n^{m}}. \label{eq:lb}\tag{4}\] For permutation-constrained problems with \(m=n\), this gives the lower envelope \[P_{1}^{\mathrm{(CE)}} \;\ge\; n^{-n}.\]

This lower bound is enough to prove exponential enhancements advertised in Eq ?? . We organise the results in the following Theorem.

This supports the heuristic that to go beyond the near–uniform baseline on permutation–constrained problems one must build the constraints into the ansatz (e.g., mixers that act within the target manifold). This is precisely the role of the mixer and pattern symmetry in the CE–QAOA Kernel which uses the problem’s constraint structure as a resource and consequently yields a feasible–mass that sharply separates it from the generic ansatz.

2.3 Exponential Separation Beyond the Single layer↩︎

The light-cone analysis can be extended to QAOA circuits beyond the single layer in overlap-controlled sublinear-depth regimes. In the one-dimensional nearest-row geometry, the clean asymptotic condition is \(p=o(n/\ln n)\), with constant-fraction \(n/\ln n\) windows depending on the prefactors in the corrected exponent. For commuting, \(r\)-local diagonal costs, the Heisenberg light cone at depth \(p\) is confined to the radius-\(p\) neighborhood in the interaction hypergraph. Projectors enforcing one-hot per row therefore depend on only \(O(p)\) (or \(O(\Delta^{p})\)) degrees of freedom. Where \(\Delta^{p}\) upper-bounds the size of the radius-\(p\) neighborhood of a vertex in a degree-\(\Delta\) interaction hypergraph induced by the light-cone growth after \(p\) layers. Using a special case of Finner/Hölder inequality on dependency graphs[35] developed in Sec. 3.8, we obtain the following theorem.

To prove this Theorem we shall need the following Lemma.

2.3.1 Proof of Theorem 3↩︎

2.3.1.1 Setup.

Recall that the baseline uses the transverse–field mixer \(U_X(\beta)=\prod_i e^{-i\beta X_i}\) and a diagonal cost \(U_C(\gamma)=e^{-i\gamma H_C}\); thus light–cone growth is caused only by \(U_C(\gamma)\). Let \(\Pi\) be the set of feasible bitstrings. For a fixed row (block) of length \(n\), denote by \(E_i\) the event “row \(i\) is one–hot.” By the locality–parametrized light–cone lemma proved in the appendix (Lemma 13), in the 1D intra–row chain with nearest–row coupling one has \[\Pr[\text{row valid}] \;\le\; (2p{+}1)\,2^{-(n-1)}.\] More generally, for bounded intra–row degree \(\Delta_{\rm row}\), Lemma 13 gives \(\Pr[\text{row valid}] \le C\,\Delta_{\rm row}^{\,p}\,2^{-(n-1)}\) for a constant \(C\) depending only on the degree bounds.

Our light–cone lemmas are defined for the row–induced interaction graph, counting only count intra–row couplings which is usually slightly less than the full maximum degree. Informally, the Heisenberg support of a row one–hot projector after depth \(p\) is confined to the radius–\(p\) neighborhood in the interaction hypergraph; the number of admissible completions inside this window scales as \(W_{\mathrm{row}}(p)\le 2p{+}1\) in 1D and \(W_{\mathrm{row}}(p)=O(\Delta_{\rm row}^{\,p})\) in general, yielding the stated per–row probabilities which we now use in our proof.

2.4 Discussion↩︎

Note that full permutation feasibility implies row feasibility. Hence in the light-cone argument, one upper bounds \(P_\Pi^{(\mathrm{gen})}\) by the probability that all row one-hot events occur: \[P_\Pi^{(\mathrm{gen})} \le \Pr\!\left[\bigcap_{i=1}^n E_i\right].\] The column constraints are not treated as independent additional events; omitting them only weakens the upper bound. The Finner/Hölder overlap number \(\chi_p\) reduces the effective number of row constraints from \(n\) to \(n/\chi_p\).

2.4.0.1 Relation to known constant-depth limitations and OGP barriers.

The above locality mechanism is consistent with several independent limitations: (i) constant-depth circuits exhibit a bounded correlation radius/light-cone [11] and hence cannot see the whole instance structure at level \(p{=}1\) in the sense formalized for QAOA [12], [16]; (ii) for random sparse graphs and related ensembles, the solution space exhibits the Overlap Gap Property (OGP), which obstructs variational optimization at fixed depth [8], [12], [14], [15]. Formally, prior work shows (a) constant-level QAOA cannot surpass certain approximation thresholds on large sparse graphs [8], [13], and (b) under OGP/NLTS-type structure, low-depth circuits fail to reach near-optimal solutions with nonnegligible probability [14], [15].

2.4.0.2 Row–level degree versus global degree.

It will be important to distinguish the global hypergraph degree \(\Delta\) of the \(N\)-qubit interaction graph from the row–level degree \(\Delta_{\rm row}\). By definition, \(\Delta_{\rm row}\) is the maximum number of cost terms \(H_a\) whose support intersects a fixed row block \[\mathrm{Row}_i \;=\; \{(i,1),\dots,(i,n)\},\] i.e., the maximum degree of the interaction graph induced on a single block of \(n\) qubits. In particular, \(\Delta_{\rm row}\) depends only on the pattern of intra–row couplings and is independent of the total number of rows. In our light–cone analysis, the Heisenberg evolution of a row one–hot projector is confined to a neighborhood whose size grows at most like \(O(\Delta_{\rm row}^{\,p})\), so the number of admissible completions and hence the per–row validity probability are controlled solely by \(\Delta_{\rm row}\) (as made precise in Lemma 13), rather than by any global degree parameter of the full \(N\)-qubit constraint graph. This row–level degree is therefore the relevant locality parameter that ultimately bounds the joint feasibility probability.

2.4.0.3 Non–asymptotic degree dependence in Eq. 5 .

Let \(\Delta_{\rm row}(n)\) denote the maximum intra–row degree of the interaction hypergraph induced by \[H_C=\sum_a H_a(Z),\] where each \(H_a\) is diagonal, commuting, and \(r\)-local. The row-validity lemma gives \[\mathbb{E}[E_i] \le C\,\Delta_{\rm row}(n)^p\,2^{-(n-1)}.\] The dependency–graph Finner/Hölder bound with row light-cone overlap number \[\chi_p := \max_{v\in[N]} \left|\{\,i\in[n]:v\in S_i(p)\,\}\right|\] therefore yields \[P_p^{(\mathrm{gen})} \le \left[ C\,\Delta_{\rm row}(n)^p\,2^{-(n-1)} \right]^{n/\chi_p}.\] Equivalently, \[\log P_p^{(\mathrm{gen})} \le -\frac{n}{\chi_p} \left[ (n-1)\ln 2 - \ln C - p\ln \Delta_{\rm row}(n) \right].\] Combining this with the one-layer CE–QAOA lower envelope \[P_1^{(\mathrm{CE})} = \Omega(n^{-n}) = \exp[-O(n\ln n)]\] gives \[\log \frac{P_1^{(\mathrm{CE})}}{P_p^{(\mathrm{gen})}} \ge \frac{n}{\chi_p} \left[ (n-1)\ln 2 - \ln C - p\ln \Delta_{\rm row}(n) \right] - O(n\ln n).\] Thus the CE–vs–generic ratio grows exponentially whenever the overlap-corrected generic exponent dominates \(n\ln n\). In the one-dimensional nearest-row case, where \[\chi_p\le 2p+1, \qquad W_{\rm row}(p)=O(2p+1),\] this includes \[p=o\!\left(\frac{n}{\ln n}\right).\]

2.4.0.4 Generic feasibility suppression.

The fully parametrized suppression is given as:

\[P_p^{(\mathrm{gen})} \;\lesssim\; \exp\!\left[ -\frac{n}{\chi_p} \Bigl((n-1)\ln 2-\ln\!\bigl(CW_{\rm row}(p)\bigr)\Bigr) \right].\] Ignoring lower-order \(W_{\rm row}(p)\) terms, the suppression scale is \[P_p^{(\mathrm{gen})} \;\lesssim\; \exp\!\left[ -\Theta\!\left(\frac{n^2}{\chi_p}\right) \right].\] Consequently, \[\chi_p=O(1) \quad\Longrightarrow\quad P_p^{(\mathrm{gen})} \le \exp[-\Theta(n^2)],\] \[\chi_p=o(n) \quad\Longrightarrow\quad P_p^{(\mathrm{gen})} \le \exp[-\omega(n)],\] and \[\chi_p=\Theta(n) \quad\Longrightarrow\quad P_p^{(\mathrm{gen})} \le \exp[-\Theta(n)].\] Thus the generic feasibility suppression is governed by the effective exponent \(n^2/\chi_p\). The obstruction is quadratic-scale when \(\chi_p=O(1)\), remains superlinear whenever \(\chi_p=o(n)\), and collapses to only \(\exp[-\Theta(n)]\) once the light-cone overlap saturates at \(\chi_p=\Theta(n)\). For the CE–vs–generic comparison, the one-layer CE–QAOA lower envelope is \[P_1^{(\mathrm{CE})} \ge n^{-n} = \exp[-n\ln n].\] Therefore the overlap-corrected generic exponent must dominate the encoded-manifold baseline cost: \[\frac{n^2}{\chi_p} \gg n\ln n.\]

3 Materials and Methods↩︎

3.1 Walsh–Fourier/Krawtchouk Analysis↩︎

We seek to develop a Walsh–Fourier/Krawtchouk analysis that upper bounds the feasible mass of one–layer generic QAOA. Throughout, \(N=n^2\), \(\Pi\subset\{0,1\}^N\) is the feasible set of \(n\times n\) permutation–matrix decoded from the sampled bitstrings, hence \(|\Pi|=n!\) and \[\ket{\psi_1^{\mathrm{(gen)}}(\beta,\gamma)} \;=\; U_X(\beta)\,U_C(\gamma)\,\ket{+}^{\otimes N}, \quad U_X(\beta) = e^{-i\beta\sum_{i=1}^N X_i},\quad U_C(\gamma)=e^{-i\gamma H_C}.\] With \(H_C\) diagonal in the computational basis, we can write \[H_C=\sum_{y\in\{0,1\}^N} C(y)\,|y\rangle\!\langle y| \quad\Rightarrow\quad U_C(\gamma)=e^{-i\gamma H_C} =\sum_{y} e^{-i\gamma C(y)}\,|y\rangle\!\langle y|.\] Acting on the uniform superposition gives \[U_C(\gamma)|+\rangle^{\otimes N} =2^{-N/2}\sum_{y} e^{-i\gamma C(y)} |y\rangle.\] With the phase field \(\phi_\gamma(y):=e^{-i\gamma C(y)}\) and any basis vector \(|x\rangle\) we obtain \[a_{\beta,\gamma}(x) =\langle x|U_X(\beta)U_C(\gamma)|+\rangle^{\otimes N} =2^{-N/2}\sum_{y} \underbrace{\langle x|U_X(\beta)|y\rangle}_{K_\beta(x,y)}\,\phi_\gamma(y).\] Because \(U_X(\beta)=\prod_{i=1}^N e^{-i\beta X_i}\), its \(Z\)-basis kernel factors as \[\label{eq:kb} K_\beta(x,y) \;=\; \prod_{i=1}^N \langle x_i|e^{-i\beta X}|y_i\rangle \;=\; (\cos\beta)^{\,N-d(x,y)}(-i\sin\beta)^{\,d(x,y)} \;=\; (\cos\beta)^{N}\,(-i\tan\beta)^{\,d(x,y)},\tag{6}\]

where \(d(x,y)=|\;x\oplus y\;|\) is the Hamming distance. Thus the output amplitudes are \[\label{eq:prob95def} a_{\beta,\gamma}(x) \;=\; 2^{-N/2}\sum_{y\in\{0,1\}^N} K_\beta(x,y)\,\phi_\gamma(y).\tag{7}\]

For normalization, note that \(K_\beta\) are matrix elements of the unitary \(U_X(\beta)\), and compute \[\begin{align} \sum_{x\in\{0,1\}^N} |a_{\beta,\gamma}(x)|^2 &= 2^{-N}\sum_{x}\left|\sum_{y} K_\beta(x,y)\,\phi_\gamma(y)\right|^2 \;=\; 2^{-N}\,\|\,U_X(\beta)\,\phi_\gamma\,\|_2^2 \\ &= 2^{-N}\,\|\,\phi_\gamma\,\|_2^2 \;=\; 2^{-N}\sum_{y} |\phi_\gamma(y)|^2 \;=\; 2^{-N}\cdot 2^N \;=\; 1, \end{align}\] because \(|\phi_\gamma(y)|\equiv 1\). Thus the amplitudes \(a_{\beta,\gamma}(x)\) are correctly normalized.

3.2 Walsh–Fourier primer↩︎

We write \([N]=\{1,2,\dots,N\}\). For a subset \(S\subseteq[N]\), let \(s\in\{0,1\}^N\) be its indicator vector, \(s_i=\mathbf{1}_{\{i\in S\}}\), and we freely identify \(S\) with \(s\). The Walsh characters on the Boolean cube are [33] \[\chi_S(x)\;:=\;(-1)^{S\cdot x},\qquad S\subseteq[N].\] For \(x\in\{0,1\}^N\), define the mod-2 (parity) dot product \[S\cdot x \;\mathrel{\vcenter{:}}=\; \Bigl(\sum_{i=1}^N s_i x_i\Bigr)\bmod 2 \;\in\; \{0,1\}.\]

For \(S,T\subseteq[N]\), write \(S\oplus T\) for the symmetric difference (bitwise XOR of indicators). Therefore: \[S\oplus T \;\mathrel{\vcenter{:}}=\; (S\setminus T)\cup(T\setminus S),\] and \[\begin{align} (S\oplus T)\cdot x &\equiv (S\cdot x) + (T\cdot x) \pmod 2 \\ &\equiv (S\cdot x)\oplus (T\cdot x). \end{align}\]

So if \(t\) is the indicator of \(T\), then \(S\oplus T\) corresponds to \(s\oplus t\). The group law \(\chi_S(x)\chi_T(x)=\chi_{S\oplus T}(x)\) will be used repeatedly.

We use the (normalized) Walsh–Fourier transform is given as \[\begin{align} \widehat{f}(S)\;:=\;2^{-N}\!\sum_{x\in\{0,1\}^N} f(x)\,\chi_S(x), \qquad f(x)\;=\;\sum_{S\subseteq[N]} \widehat{f}(S)\,\chi_S(x). \label{eq:ft} \end{align}\tag{8}\] With this normalization, the hat \(\widehat{\phantom{f}}\) denotes the Walsh–Fourier transform on the Boolean cube with characters \(\chi_S(x):=(-1)^{S\cdot x}\) for \(S\subseteq[N]\). Parseval/Plancherel reads [33] \[\sum_{x}|f(x)|^2\;=\;2^{N}\sum_{S}|\widehat{f}(S)|^2, \qquad 2^{-N}\!\sum_{x}\overline{f(x)}\,g(x)\;=\;\sum_{S}\overline{\widehat{f}(S)}\,\widehat{g}(S).\]

For functions \(f:\{0,1\}^N\to\mathbb{C}\) we use the counting inner product \(\langle f,g\rangle:=\sum_{x\in\{0,1\}^N}\overline{f(x)}\,g(x)\) (and the normalized version \(\langle\!\langle f,g\rangle\!\rangle:=2^{-N}\langle f,g\rangle\) when convenient).

One could view \(K_\beta\) from Eq. 6 as a convolution on \(\mathbb{Z}_2^N\): \[(K_\beta f)(x)\;:=\;\sum_{y} K_\beta(x,y)\,f(y) \;=\;\sum_{z} k_\beta(z)\,f(x\oplus z),\] with the one-bit kernel \(k_\beta(0)=\cos\beta\) and \(k_\beta(1)=-i\sin\beta\) and \(k_\beta(z)=\prod_{i=1}^N k_\beta(z_i)\).

3.2.0.1 Permutation–feasibility indicator.

We write \(\mathbf{1}_A:\{0,1\}^N\to\{0,1\}\) for the indicator of a set \(A\), i.e. \[\mathbf{1}_A(x)= \begin{cases} 1,& x\in A,\\ 0,& x\notin A. \end{cases}\] In the permutation encoding (e.g. for TSP) we fix \(N=n^2\) and identify each bitstring \(x\in\{0,1\}^N\) with an \(n\times n\) binary matrix \[X(x)\;=\;\bigl(x_{i,j}\bigr)_{1\le i,j\le n},\] where \(x_{i,j}\in\{0,1\}\) records whether city \(j\) is placed at tour position \(i\). We say that \(x\) is permutation–feasible if and only if \(X(x)\) is a permutation matrix, i.e. \[\sum_{j=1}^n x_{i,j} \;=\; 1\quad\text{for all rows }i\in[n], \qquad \sum_{i=1}^n x_{i,j} \;=\; 1\quad\text{for all columns }j\in[n].\] Let \(\Pi\subset\{0,1\}^N\) denote the set of all such bitstrings, so \(|\Pi|=n!\). The permutation–feasibility indicator is \[\mathbf{1}_\Pi(x) \;=\; \begin{cases} 1, & \text{if }x\in\Pi\text{ (i.e.\;X(x) is a permutation matrix)},\\[2pt] 0, & \text{otherwise.} \end{cases}\] Equivalently, if we write \[R(x)\;:=\;\prod_{i=1}^n \mathbf{1}\Bigl[\sum_{j=1}^n x_{i,j}=1\Bigr], \qquad C(x)\;:=\;\prod_{j=1}^n \mathbf{1}\Bigl[\sum_{i=1}^n x_{i,j}=1\Bigr],\] for the row– and column–one–hot indicators, then \[\mathbf{1}_\Pi(x) \;=\; R(x)\,C(x), \qquad \|\mathbf{1}_\Pi\|_2^2 \;=\; \sum_{x}\mathbf{1}_\Pi(x) \;=\; |\Pi| \;=\; n!.\] With this notation, the feasible probability mass can be written as the Walsh correlation \[P_\Pi(\beta,\gamma) \;=\; 2^{-N}\sum_{x}\mathbf{1}_\Pi(x)\,|g(x)|^2.\]

Then \[P_\Pi(\beta,\gamma) \;=\;2^{-N}\sum_{x}\mathbf{1}_\Pi(x)\,|g(x)|^2 \;=\;\sum_{S\subseteq[N]} \widehat{\mathbf{1}_\Pi}(S)\,\widehat{|g|^2}(S).\] where \(g=K_\beta\phi_\gamma\) and \(\widehat{\mathbf{1}_\Pi}\) is the Walsh transform of the permutation–feasibility indicator. Writing \(b:=\widehat{\phi_\gamma}\) and using Lemma 2, \[\widehat{|g|^2}(S) \;=\;\sum_{T\subseteq[N]}\lambda_\beta(|T|)\,\overline{\lambda_\beta(|T\oplus S|)}\; b(T)\,\overline{b(T\oplus S)}, \qquad \sum_{T}|b(T)|^2\;=\;1,\] so \(P_\Pi\) is controlled by the Walsh autocorrelations of the phase field and the Fourier profile of the feasible indicator.

3.3 Krawtchouk Polynomials on the Hamming sphere↩︎

Let \(g_n\) be the “exactly–one” (one–hot) indicator on \(n\) bits, and let \(\Pi\) be the intersection of \(2n\) block one–hot constraints plus the row–column bijection (permutation) constraint. The Walsh spectrum of \(g_n\) is explicit via Krawtchouk polynomials [33], [36]. In particular,it allows us to show via explicit computation that low degrees carry exponentially small mass. To see this, we work on the Boolean cube \(\{0,1\}^n\) with Walsh characters \(\chi_S(x)=(-1)^{S\cdot x}\) for \(S\subseteq[n]\) and the normalization \[\widehat f(S)\;:=\;2^{-n}\sum_{x\in\{0,1\}^n} f(x)\,\chi_S(x), \qquad f(x)\;=\;\sum_{S\subseteq[n]} \widehat f(S)\,\chi_S(x)\] as in Eq. 8 .

Let \(g_w:\{0,1\}^n\to\{0,1\}\) denote the Hamming–sphere indicator \(g_w(x)=\mathbf{1}_{\{|x|=w\}}\). In particular, the one–hot indicator is \(g_1\) (support \(\{x:|x|=1\}\)). For \(0\le w\le n\), the (unnormalized) binary Krawtchouk polynomials are \[K_w^{(n)}(r)\;:=\;\sum_{j=0}^{w}(-1)^j \binom{r}{j}\binom{n-r}{\,w-j\,}, \qquad r=0,1,\dots,n. \label{eq:Kraw-def}\tag{9}\] They satisfy the following generating function and orthogonality identities respectively [36] \[\begin{align} \sum_{w=0}^{n} K_w^{(n)}(r)\, z^w \;&=\;(1+z)^{\,n-r}(1-z)^{\,r}, \tag{10}\\ \sum_{r=0}^{n} \binom{n}{r}\, K_w^{(n)}(r)\,K_{w'}^{(n)}(r) \;&=\;2^{n}\binom{n}{w}\,\delta_{w,w'}. \tag{11} \end{align}\]

\[K_{1}^{(n)}(r)\;=\;\binom{r}{0}\binom{n-r}{1}-\binom{r}{1}\binom{n-r}{0} \;=\;(n-r)-r\;=\;n-2r.\] Thus, for \(g_1\) (the “exactly one” indicator), \[\widehat{g_1}(S)\;=\;2^{-n}\bigl(n-2|S|\bigr), \qquad S\subseteq[n], \label{eq:onehot-transform}\tag{13}\] which matches the direct computation \(\widehat{g_1}(S)=2^{-n}\sum_{i=1}^{n}(-1)^{\mathbf{1}_{\{i\in S\}}}=2^{-n}(n-2|S|)\).

Normalization/Parseval sanity check using 12 and 11 gives, \[\sum_{x}|g_w(x)|^2 = \binom{n}{w} \;=\;2^{n}\sum_{S}|\widehat{g_w}(S)|^2 \;=\;2^{n}\sum_{r=0}^{n}\binom{n}{r}\,\bigl(2^{-n}K_w^{(n)}(r)\bigr)^2,\] which is exactly 11 with \(w'=w\). We also have \(\|g_1\|_2^2=\binom{n}{1}=n\).

The Krawtchouk identity \(\widehat{g_w}(S)=2^{-n}K_w^{(n)}(|S|)\) shows that the Walsh spectrum of any Hamming–sphere indicator is a radial (shell–dependent) polynomial of \(|S|\). For the one–hot layer (\(w=1\)), \(\widehat{g_1}(S)\) is exactly linear in \(|S|\), and its low–degree weight decays exponentially in \(n\) after summation over shells, as quantified in Lemma 4. Tensorizing across \(m=2n\) blocks and incorporating the bijection constraint yields an additional sparse factor that does not increase low–degree mass beyond a polynomial.

3.4 Route 1: Harmonic Analysis of the probability profile↩︎

To go beyond \(n-\)bit rows and make the Fourier weight decay on the permutation feasible subspace explicit, we shall use the following technical lemmas. Lemma 5 is an adaptation from Alon and Spencer (Lemma 2, p. 64, [37]) while Lemma 6 is a technical tool to control the resulting inequality.

The \(2^{-n}\) per block across \(n\) rows and \(n\) columns is the source of the \(2^{-\Theta(n^2)}\) decay. To bound the total probability profile, write the low/high–degree split of the contributuions to toal probability as \(p=p^{\le 2T}+p^{>2T}\), where \(p^{\le2T}\) denotes the Walsh truncation to degrees \(\le 2T\) and effectively identify \(d=2T\). We use Lemma 5 to replace \(n^{2n}\) by \((n!)^2 R_n\), exposing the \((n!)^2\) factor explicitly. \(R_n\) remains suppressed by \(2^{-c n^2}\). Additional suppression will come from the normalization terms as we shall see in the next Lemmas.

Adding column one-hot (turning “row-one-hot” into permutation matrices) multiplies by a sparse indicator that enforces n extra constraints. In Fourier space that becomes a convolution that can at worst blow up the low-degree mass by a polynomial factor in n and d (Cauchy–Schwarz on the convolution over the degree simplex).

3.5 Route II: Parameter–Averaging (Exact Expectation and a Typical–Angles Bound)↩︎

In this section, we show that averaging over the cost angle pins the baseline feasible mass to the uniform value \(|\Pi|/2^{N}\), independently of the mixer angle, provided the cost spectrum lies on a lattice (which holds after rescaling for the usual integer/rational Ising/TSP costs). This insight comes simple Fourier-averaging.

Recall that averaging over a wide distribution of the cost angle \(\gamma\) makes the oscillatory phases \(e^{-i\gamma\,\Delta}\) cancel out for every fixed nonzero frequency \(\Delta\). When we expand \(\mathbb{E}_\gamma\!\left[|a_x(\beta,\gamma)|^2\right]\), the cross terms carry factors \(e^{-i\gamma\,[C(y)-C(z)]}\). A wide average over \(\gamma\) drives these cross terms to \(0\) whenever \(C(y)\neq C(z)\), leaving only the diagonal (unitarity) terms. Thus the averaged mass returns to the uniform baseline. Exact degeneracies \(C(y)=C(z)\) cannot be averaged away (their phase is identically \(1\)), but they only add nonnegative contributions, so uniform baseline is recovered for nondegenerate spectra (or after tiny tie-breaking), and baseline-or-higher otherwise. The main lattice averaging result is the following Lemma.

Lemma 10 yields an expectation baseline \(|\Pi|/2^N\). To assert that most angles are near this baseline, we use a one–liner.

3.6 Route III: A Fourth–Moment (Hypercontractive–Style) Bound↩︎

The third route upper bounds \(P_{\Pi}\) for most \((\beta,\gamma)\) using the \(\ell^4\)–norm  [33] of the output amplitude vector. Recall from Eq. 7 \(a(x)=a_{\beta,\gamma}(x)=2^{-N/2}g(x)\) with \(g=K_\beta\phi_\gamma\). By Cauchy–Schwarz, \[\sum_{x\in\Pi} |a_x|^2 \;\le\; \sqrt{|\Pi|}\,\Bigl(\sum_{x}|a_x|^4\Bigr)^{1/2}. \label{eq:CS-L4}\tag{17}\] Thus, any bound on \(\sum_x |a_x|^4\) yields an upper bound on \(P_{\Pi}\). The following holds.

Note that \(\tfrac12+\cos^2\beta\,\sin^2\beta \in [\tfrac12,\tfrac34]\), with the maximum \(\tfrac34\) at \(\beta=\tfrac\pi4\). Thus the averaged fourth moment decays as \(\exp(-\Omega(N))\) for any fixed \(\beta\in(0,\tfrac\pi2)\). At \(\beta=\pi/4\) the base equals \(3/4\), giving exponential decay in \(N\).

3.7 Route IV: Local–Light–Cone Barrier (generic QAOA at single layer)↩︎

We now analyze the light cone correlation limit of single layer QAOA circuit under the following conditions:

1. Diagonal, commuting, \(r\)-local \(H_C\). The cost Hamiltonian decomposes as \(H_C=\sum_{j}H_j\) where each \(H_j\) is diagonal, acts on at most \(r=O(1)\) qubits, and all \(H_j\) commute.

2. Incidence growth is polynomial . Let \(G\) be the interaction hypergraph on \([N]\) with a hyperedge \(\mathrm{supp}(H_j)\) for each term \(H_j\). Define the one–step neighborhood \(N_1(S)\) of a set \(S\subseteq[N]\) as the union of supports of all \(H_j\) that intersect \(S\). We assume a polynomial growth bound \(|N_1(S)|\;\le\; \Delta_N\,|S|\) where \(\Delta_N=\mathrm{poly}(n)\) may scale with \(n\) (e.g.\(\Delta_N=\Theta(n)\) for permutation/TSP encodings).

3. Diagonal feasibility projectors. Feasibility is specified by commuting diagonal projectors \(P_B\) (e.g., one–hot per block and bijection constraints). Let \(\Pi=\prod_{B}P_B\) project onto the feasible subspace \(\mathcal{F}\) with \(|\Pi|=|\mathcal{F}|\).

4. Initial state. The input state is the product state \(\ket{+}^{\otimes N}\).

3.7.0.1 Light-cone support bound at \(p=1\).

Let \(O\) be any observable supported on \(S\subseteq[N]\). With (A1), \[U_C^\dagger(\gamma)\,O\,U_C(\gamma) \quad\text{is supported on}\quad N_1(S),\] because conjugation by any diagonal \(H_j\) either leaves \(O\) unchanged (if \(\mathrm{supp}(H_j)\cap S=\emptyset\)) or mixes only within \(\mathrm{supp}(H_j)\) (if it overlaps), and commuting terms do not propagate support further. Conjugation by \(U_X(\beta)\) is 1-local and does not expand support. Hence, for any diagonal projector \(P_B\), \[U^\dagger P_B\,U \;\text{acts nontrivially only on}\;N_1(\mathrm{supp}(P_B)). \label{eq:star}\tag{25}\]

3.7.0.2 Dependency graph between constraints.

Write \(\Pi=\prod_{B=1}^{M}P_B\) (with \(M\) block/constraint projectors). Let \(Q_B:=U^\dagger P_B U\). From 25 , each \(Q_B\) is supported on \(S_B:=N_1(\mathrm{supp}(P_B))\). Introduce the constraint dependency graph \(\mathcal{G}\) with vertices \([M]\) and an edge between \(B,B'\) iff \(S_B\cap S_{B'}\neq\emptyset\). By (A2), the maximum degree of \(\mathcal{G}\) is at most polynomial in \(n\): \[\Delta(\mathcal{G}) \;\le\; \max_B\;\frac{|S_B|}{\min_{B'} |\mathrm{supp}(P_{B'})|} \;\lesssim\; \mathrm{poly}(n),\] since each \(S_B\) grows by at most a factor \(\Delta_N=\mathrm{poly}(n)\) over \(\mathrm{supp}(P_B)\). The feasible mass after one QAOA layer is \[p_{\mathrm{feas}}(\beta,\gamma) \;=\; \bra{\psi_0} \prod_{B=1}^{M} Q_B \ket{\psi_0}.\] Because \(\ket{\psi_0}\) is a product state and each \(Q_B\) is localized on \(S_B\), the cumulants associated with collections of \(Q_B\)’s vanish unless the corresponding vertices form a connected cluster in \(\mathcal{G}\). A standard cluster expansion then yields \[p_{\mathrm{feas}}(\beta,\gamma) \;=\; \prod_{B=1}^{M}\!\bra{\psi_0}Q_B\ket{\psi_0} \;\times\; \Bigl(1 + \sum_{\substack{\mathcal{C}\subseteq[M]\\ \text{connected},\,|\mathcal{C}|\ge2}} \kappa(\mathcal{C})\Bigr),\] where each connected-cluster correction \(\kappa(\mathcal{C})\) depends only on the degrees and sizes of \(S_B\) in that cluster. Counting connected clusters in a graph of maximum degree \(\Delta(\mathcal{G})=\mathrm{poly}(n)\) gives \(\sum_{\text{connected }\mathcal{C}} |\kappa(\mathcal{C})|\le \mathrm{poly}(n)\) for fixed \(p=1\) and \(r=O(1)\). Moreover, for the uniform superposition \(\ket{+}^{\otimes N}\), \(\prod_B\bra{\psi_0}Q_B\ket{\psi_0} = \bra{+}^{\otimes N}U^\dagger \Pi U\ket{+}^{\otimes N} \le \tfrac{|\Pi|}{2^N}\), with equality at \(\beta=\gamma=0\). Altogether we obtain the baseline upper bound \[p_{\mathrm{feas}}^{(p=1)}(\beta,\gamma) \;\lesssim\; \frac{|\Pi|}{2^N}\cdot \mathrm{poly}(n), \label{eq:baseline-bound}\tag{26}\] where the polynomial slack depends on \(r\) and \(\Delta_N\) (hence on encoding), but not on any global degree of the problem graph.

In TSP/permutation-style encodings with one–hot rows and columns, each binary variable participates in \(O(n)\) pairwise terms within its row and \(O(n)\) within its column (from expanding squared penalties). Hence \(\Delta_N=\Theta(n)\), and \(\Delta(\mathcal{G})=\mathrm{poly}(n)\). The bound 26 therefore yields at most a polynomial improvement over the uniform baseline \(|\Pi|/2^N\) at \(p=1\). Intuitively, the single-layer light cone can correlate only a polynomial number of blocks; it cannot sustain the long-range correlations needed to inflate feasible mass by superpolynomial factors.

3.8 Light Cone Barriers at Arbitrary Depths↩︎

Write \(H_C=\sum_a H_a(Z)\) where each \(H_a\) acts on at most \(r\) qubits and the interaction hypergraph has maximum vertex degree \(\Delta = O(n)\). We arrange the qubits in an \(n\times n\) grid of rows; “row \(i\)” refers to the \(n\) qubits \(\{(i,1),\dots,(i,n)\}\). Let \(\Delta_{\rm row}\) bound the intra–row degree and \(\Delta_{\rm inter}\) bound inter–row couplings; in all cases \(\Delta_{\rm row},\Delta_{\rm inter}\le \Delta=O(n)\).¹ The \(X\) mixer does not expand supports; each layer of \(U_C\) grows supports by at most one shell in the interaction hypergraph. After \(p\) alternating layers, any local observable’s Heisenberg support lies inside the radius–\(p\) neighborhood in this hypergraph [11].

We will use the following standard inequality (a special case of Finner/Hölder on dependency graphs[35]): if nonnegative random variables \(\{A_j\}_{j\in J}\) are each measurable with respect to a set of underlying coordinates forming a dependency graph of maximum overlap number \(\chi\) (i.e., every coordinate influences at most \(\chi\) of the \(A_j\)), then \[\label{eq:finner} \mathbb{E}\!\Bigl[\prod_{j\in J} A_j\Bigr] \;\le\; \prod_{j\in J} \bigl(\,\mathbb{E}[A_j^{\chi}]\,\bigr)^{1/\chi}.\tag{27}\]

Proof of 27 .↩︎

Let \(V\) be the set of underlying coordinates (qubits) and write the product probability space \((\Omega,\mu)=\bigotimes_{v\in V}(\Omega_v,\mu_v)\) for the independent single–site \(Z\)–basis outcomes. For each \(j\in J\), let \(S_j\subseteq V\) be the coordinate set on which \(A_j:\Omega\to[0,1]\) depends (in our application \(A_j=E_i\) is the indicator that row \(i\) is one–hot after depth \(p\), so \(S_j\) is the radius–\(p\) neighborhood of that row). Let \(\chi:=\max_{v\in V}\#\{j\in J:\;v\in S_j\}\) be the overlap number. Order the coordinates arbitrarily as \(v_1,\dots,v_{|V|}\). Starting from \(\mathbb{E}_\mu[\prod_{j}A_j]=\int \prod_{j}A_j\,d\mu\), integrate iteratively over \(v_1,\dots,v_{|V|}\). At step \(t\), split the factors into those that depend on \(v_t\) (index set \(J_t=\{j:\;v_t\in S_j\}\)) and those that do not. Applying Hölder on the one–dimensional space \((\Omega_{v_t},\mu_{v_t})\) with equal exponents \(p_j=\chi\) for \(j\in J_t\) (valid because \(\sum_{j\in J_t}1/p_j=\#J_t/\chi\le 1\) by definition of \(\chi\)) yields \[\int_{\Omega_{v_t}}\prod_{j\in J_t} A_j\,d\mu_{v_t} \;\le\;\prod_{j\in J_t}\Bigl(\int_{\Omega_{v_t}} A_j^{\chi}\,d\mu_{v_t}\Bigr)^{1/\chi},\] while the factors \(j\notin J_t\) pass through as constants. Iterating this bound for \(t=1,\dots,|V|\) and using Fubini (Lemma 14) repeatedly, each \(A_j\) accrues a factor \(\prod_{v\in S_j}\bigl(\int_{\Omega_v}(\cdot)^{\chi}d\mu_v\bigr)^{1/\chi}\), which composes to \(\bigl(\int_{\Omega_{S_j}} A_j^{\chi}\,d\mu_{S_j}\bigr)^{1/\chi}\) and (trivially) to \(\bigl(\int_{\Omega} A_j^{\chi}\,d\mu\bigr)^{1/\chi}\). Thus \[\mathbb{E}_\mu\Bigl[\prod_{j\in J}A_j\Bigr] \;\le\;\prod_{j\in J}\bigl(\,\mathbb{E}_\mu[A_j^{\chi}]\,\bigr)^{1/\chi},\] which is 27 . In particular, for indicators \(A_j\in[0,1]\) one has \(A_j^{\chi}=A_j\), giving \(\mathbb{E}[\prod_j A_j]\le \prod_j \mathbb{E}[A_j]^{1/\chi}\). 0◻

3.8.0.1 Overlap number (intuition).

In the dependency–graph Hölder bound, the overlap number \(\chi\) measures how strongly the row events can “see” the same underlying qubits. Formally, each event \(A_j\) depends only on a coordinate set \(S_j\subseteq V\) (its Heisenberg light cone), and \[\chi \;:=\; \max_{v\in V}\#\{j:\;v\in S_j\}\] is the maximum number of events whose supports pass through a single coordinate \(v\). When \(\chi=1\) the \(A_j\) live on disjoint qubit sets and behave as if they were independent; as \(\chi\) grows, more events overlap on the same coordinates and can become correlated. Inequality 27 shows that this overlap directly suppresses the joint success probability: even in the worst case, the product \(\prod_j A_j\) is bounded by the product of the individual expectations, but with an exponent penalty \(1/\chi\), which is exactly where our light–cone geometry enters the global bound on \(P_p^{\mathrm{(gen)}}\). For indicators \(A_j\in[0,1]\) this simplifies to \(\mathbb{E}[\prod_j A_j]\le \prod_j \bigl(\mathbb{E}[A_j]\bigr)^{1/\chi}\).

3.8.0.2 From local to global via overlap.

Having obtained a per–row light–cone bound from Lemma 13, the remaining task is to convert this into a bound on the joint feasibility of all rows. The difficulty is that the row–validity events \(E_i\) are not independent: their Heisenberg light cones can intersect in the underlying interaction graph. To quantify this, we work on the \(Z\)–basis product space and view each \(E_i\) as a random variable depending only on a coordinate set \(S_i\subseteq V\). The overlap number \(\chi=\max_{v\in V}\#\{i:\;v\in S_i\}\) measures how many row events can simultaneously “touch” the same qubit. The dependency–graph Hölder/Finner inequality 27 then implies that, even in this correlated setting, the joint success probability \(\mathbb{E}[\prod_i E_i]\) is controlled by the product of the individual expectations, but with an exponent penalty \(1/\chi\). Thus the geometry of the light cones (through \(\chi\)) feeds directly into the global upper bound on \(P_p^{\mathrm{(gen)}}\) that we derive next. Before applying the derived dependency–graph Hölder inequality, we record the following standard Fubini–Tonelli fact about iterated integration on product spaces, which we will use to justify exchanging the order of integration in the proof below.

4 Conclusion and Outlook↩︎

This work reframes the computational power of shallow variational quantum algorithms through the lens of feasibility concentration. For permutation encodings on \(n^2\) qubits we prove that the generic QAOA cannot lift feasible mass much beyond the uniform baseline. The ceiling persists at constant depth and, under bounded degree, up to linear depth. In the same regime a minimal constraint–enhanced surrogate, CE–QAOA, achieves a depth-matched and angle-robust exponential gain in feasible mass. The separation follows from three transparent controls on the output distribution—angle averaging with low order moments, Boolean harmonic analysis, and light-cone locality.

The CE–QAOA kernel is not engineered here. We use it merely as a clean illustration of problem–algorithm co-design as a route to exponential enhancements. As we have demonstrated, even the minimal symmetry based bound we explored here was enough to achieve exponential enhancement. These results suggest that a simple design rule for globally constrained problems is to build feasibility into the ansatz and make the mixer operate within the constraint manifold. This converts a global coordination task that shallow generic circuits cannot sustain into a local exploration inside the encoded space, where light-cones grow at the block level and the baseline is information-theoretically favorable. Typical-angle and fourth-moment controls also serve as diagnostics when a generic shallow circuit appears to “fail to train.” The bounds here show that the obstacle is structural, not an artifact of optimizer choice, sampling noise, or unlucky initialization.

Our assumptions are mild but explicit. We work with diagonal commuting costs of arbitrary degree and the standard \(X\) mixer. We analyze permutation encodings because they capture a broad family of assignment and routing objectives and make the obstruction sharp. CE-QAOA–style kernels offer one principled path in this broader space, but other constraint-preserving designs are possible and worth exploring. We conclude that while feasibility concentration is the bottleneck for generic shallow VQA on global constraints, algorithms that respect those constraints in part or in full convert that bottleneck into a computational resource and unlock exponential gains. A natural next step is to build the same harmonic and Boolean–cube toolkit inside the CE–QAOA manifold to track how the block–\(XY\) mixer reshapes Fourier weight, and identify which degrees are actually reachable at fixed depth. This would give matching upper bounds for CE–QAOA and expose its ultimate limitations rather than only its advantages.

Data Availability Statement↩︎

All data in this paper and the Python implementation in Qiskit are made available here https://doi.org/10.5281/zenodo.17701648.

Conflict of Interests↩︎

All authors declare no competing interests.

Author contributions↩︎

C.O. wrote the main paper and prepared all the figures, K.M. provided guidance during the project. All the authors reviewed the paper.

Funding↩︎

This research received no external funding.

References↩︎

---

1. In standard one–hot/bijection penalties each qubit couples via pairwise \(ZZ\) to \(O(n)\) peers in its row/column, and objectives used in COPs add at most polynomially many terms, so the per-qubit participation number—and hence the hypergraph degree—is \(O(n)\).↩︎