Abstract The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts
ZZ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains
<1\%, yet LC-QAOA with
XpXm dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.
Feasibility-preserving mixer Hamiltonians offer an attractive alternative to penalty encodings for constrained quantum optimization, yet how enforcing constraints alters the state space reachable by the Quantum Approximate Optimization Algorithm (QAOA) remains largely unexplored. We address this question within the context of the Maximum Independent Set (MIS) problem. Alongside the standard controlled bit-flip mixer, we analyze the alternative
Flip-or-Stay mixer, whose restriction to the feasible subspace
WF corresponds precisely to the shifted negative Laplacian of the independent-set reconfiguration graph. Although both mixers induce identical transitions between independent sets, the diagonal modification changes the spectral structure and can substantially enlarge the set of reachable quantum states.
For every connected input graph with at least two vertices, we prove that independently parameterized local controls associated with either mixer generate the full unitary Lie algebra on the feasible subspace. Standard QAOA exhibits a more nuanced algebraic structure. We prove that the dynamical Lie algebra associated with MIS-QAOA employing the conventional mixer embeds into its Flip-or-Stay counterpart. Furthermore, we construct an infinite family of graphs for which the corresponding vacuum-state dynamical group orbits exhibit strictly distinct dimensions, establishing a qualitative expressivity separation between the two architectures. For either mixer, we show that standard QAOA initialized in the empty set can prepare a state supported entirely on maximum independent sets at finite depth. For the free architectures, we also derive an exact loss-variance formula in the unitary-design limit, expressed through the number of feasible independent sets and the variance of their cardinalities.
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
ℓ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 Quantum Approximate Optimization Algorithm (QAOA) is a promising framework for combinatorial optimization, but constrained problems are commonly handled using energetic penalty terms that require calibration and allow infeasible configurations to remain dynamically accessible. We develop a constraint-preserving QAOA framework for personnel rostering in which hard scheduling constraints are embedded directly into the mixer Hamiltonian. Using a binary rostering model with daily coverage and no-consecutive-duty constraints, we formulate the dynamics from a transition-graph perspective and introduce a guarded-XY mixer that confines the evolution to the fully feasible scheduling manifold. We further distinguish feasibility preservation from feasible-transition design and propose a tight-pattern extension that introduces collective feasible exchanges in saturated workload segments where local guarded exchanges alone are insufficient. Exact statevector simulations demonstrate that, compared with Penalty-X and Coverage-XY formulations under both expectation-value and Conditional Value-at-Risk optimization, the proposed approach eliminates hard-constraint penalty calibration, guarantees feasible evolution by construction, and consistently yields higher-quality output distributions with stronger concentration on optimal feasible schedules. To the best of our knowledge, this is the first constraint-preserving QAOA formulation for personnel rostering, and the transition-graph framework is readily applicable to a broad class of constrained quantum optimization problems.
We study the feasibility limitations of generic QAOA for permutation-constrained optimization, where valid configurations occupy an exponentially small fraction of the Boolean hypercube. Using random edge-cost TSP/ATSP ensembles, we establish high-probability bounds showing that optimized generic QAOA retains exponentially small feasible probability over specified parameter domains. At depth one, the bound holds uniformly over all mixer angles and a cost-angle grid that may be exponentially large in n^2. The analysis combines Walsh-Fourier/Krawtchouk estimates, which suppress low- and high-degree contributions, with transition-feature collision bounds controlling objective-dependent interference. Complementary cost-angle averaging, fourth-moment estimates, and light-cone analysis characterize energy-fibre coherence, typical-angle concentration, and constraint-correlation geometry. We compare generic QAOA with a constraint-enhanced kernel (CE-QAOA) initialized in a product one-hot subspace and evolved with a block-local XY mixer. For N = n^2 binary variables, CE-QAOA attains feasible probability at least n!/n^n at every depth, yielding an exp[Omega(n^2)] advantage over optimized generic QAOA at depth one with high probability. For linked cost-angle schedules with independently optimized mixer angles, the generic feasibility obstruction and exponential CE-QAOA separation extend throughout linear-depth windows p <= alpha*n, for fixed alpha > 0. These parameter-uniform bounds also imply exponential raw-sample requirements for adaptive feasible sampling within the prescribed domains.
Characterizing the trainability of the Quantum Approximate Optimization Algorithm (QAOA) requires understanding how its gradient landscape changes across circuit parameters and problem size. Yet these gradients are usually described in terms of the native QAOA angles, making it difficult to distinguish parameter specific features from broader changes in the underlying circuit dynamics. Here we introduce a dynamical representation of the QAOA parameter space based on a norm-weighted layer strength and a cost--mixer imbalance, separating the overall scale of the evolution from the relative contribution of the two generators.
Using exact-state simulations of MaxCut, we find that the gradient landscape exhibits a coarse organization in these dynamical variables that persists across changes in circuit depth and schedule structure, while the finer interference pattern remains schedule dependent. Near-optimal solutions do not simply coincide with the largest local gradients, but instead occupy a distinct intermediate dynamical regime. Uniform schedules recover the broad location of this regime, whereas nonuniform schedules mainly reorganize its fine structure. Across the system sizes studied, near-optimal solution regions remain extended in the dynamical representation while their preimages in the native QAOA angles become substantially compressed at larger sizes. These results separate the persistence of useful QAOA dynamics from their accessibility in the native parameterization, and provide a dynamical framework for interpreting QAOA trainability across circuit and problem scales.