Structural Bottlenecks in QAOA Mixer Design: Transport and Causal Reach

Abstract

The choice of mixer is a central design decision in the Quantum Approximate Optimization Algorithm (QAOA), yet different structural limitations of a mixer need not be captured by a single metric. We identify two complementary structural bottlenecks for shallow QAOA: configuration-space transport, which limits how strongly probability can concentrate on high-quality solutions, and finite-depth causal reach, which limits which parts of a problem instance can influence a local objective term. In Part I, we derive first-order mixer-dependent objective bounds in complementary small-$β$ and small-$γ$ regimes. For connected regular mixer graphs, the two leading-order expressions are exactly equivalent through a graph-Laplacian identity and reduce to the same cost-weighted Dirichlet energy. We then derive a non-perturbative upper envelope from the layer-wise $\ell_1$ spreading of the mixer unitary, yielding a cost-distribution-dependent necessary spreading condition for attaining a target approximation ratio. In Part II, we study the locality bottleneck for MaxCut by augmenting the transverse-field mixer with problem-graph-aligned two-local interactions. The resulting $k$-hop construction has causal radius at most $(k+1)p$ at depth $p$; for the $k=1$ architectures studied numerically, this gives radius $2p$. Across cycles, circular ladders, and high-girth regular bipartite graphs, $X{+}XX$ and $X{+}YY$ improve the best-found approximation ratios over the standard $X$ mixer at equal depth, while $X{+}YY$ at depth $p$ comes within about one approximation-ratio point of plain $X$ at depth $2p$ in the reach-matched cases examined. The unequal performance of the equal-reach $XX$ and $YY$ augmentations shows that satisfying a structural capability does not by itself guarantee performance. Together, the results provide complementary structural insights for mixer design.

The paper asks how mixer structure limits shallow QAOA, distinguishing configuration-space amplitude transport from the causal reach of local objective terms. It analyzes these constraints separately rather than proposing a single predictor of mixer performance. For adjacency-matrix mixers, nested-commutator expansions give objective bounds in small-$\beta$ and small-$\gamma$ parameter boxes. For connected regular mixer graphs, the resulting first-order bound coefficients coincide through the Laplacian identity $\mathcal E_M=|F|\sum_{b\ne0}(\lambda_0-\lambda_b)|C_{0b}|^2$, where $\mathcal E_M=\sum_{(x,y)\in E_M}(C(x)-C(y))^2$. Operator-norm remainder bounds control the corresponding exact objectives. Nonperturbatively, defining $S_j=\max_x\|e^{-i\beta_jH_M}|x\rangle\|_1$ and $\Lambda=\prod_jS_j^2$ gives $q(x)\le\Lambda/|F|$. Optimizing over distributions satisfying this cap bounds the objective by the average cost of the best $1/\Lambda$ fraction of configurations, yielding necessary spreading and depth conditions. For MaxCut, graph-aligned commuting $XX$ or $YY$ augmentation increases the causal-radius bound from $p$ to $(k+1)p$ for interactions spanning at most $k$ graph hops. At $k=1$, exact representative-lightcone evaluations and numerical optimization show equal-depth improvements on cycles, circular ladders, and high-girth regular bipartite graphs. On cycles at $p=1$, best-found ratios are $0.7500$, $0.7829$, and $0.8247$ for $X$, $X+XX$, and $X+YY$; reach-matched $X$ at $p=2$ gives $0.8333$. Limitations include phase-blind transport bounds, vacuity at common hypercube angles, restrictive perturbative regimes, uncertified numerical optima, and comparisons without fully matched resource budgets. Transport is not evaluated for the augmented circuits.