Higher-order objectives possess many exact Hamiltonian encodings, and these encodings differ in the qubits, penalties, gates, and depth that they require. Representation selection is therefore an algorithmic decision for the quantum approximate optimisation algorithm on resource-constrained hardware. This work develops a pointwise-exact family of representations in which selected higher-order interactions are replaced by shared Rosenberg auxiliaries while the remaining interactions stay native. A sharp single-step penalty condition and a closed form for cubic residuals certify exactness at every stage of such a selective reduction. Within the direct-pair class, a static feasibility theory identifies infinite families of objectives for which a mixed representation meets joint budgets that exclude both the native and the fully reduced endpoint. A separate construction extends this separation to gate and depth limits under a fixed synthesis. Compilation on 12-qubit line, ring, and grid targets finds certified mixed-only regions for 23 of 30 weighted maximum three-satisfiability instances, all 30 constructed instances, and 2 of 30 cubic spin-glass instances under the stated class and penalty rule. A separate routing experiment retains 52.9% of mixed-only budget points across five seeds within fixed candidate sets. In noiseless depth-one evaluation, the native encoding attains the best mean objective under the tested protocols, and the joint resource-and-quality test finds no mixed-only success at the primary budget. Resource feasibility is thus a sound reason to select a mixed encoding, whereas solution quality requires a separate assessment.
Higher-order objectives possess many exact Hamiltonian encodings, and these encodings differ in the qubits, penalties, gates, and depth that they require. Representation selection is therefore an algorithmic decision for the quantum approximate optimisation algorithm on resource-constrained hardware. This work develops a pointwise-exact family of representations in which selected higher-order interactions are replaced by shared Rosenberg auxiliaries while the remaining interactions stay native. A sharp single-step penalty condition and a closed form for cubic residuals certify exactness at every stage of such a selective reduction. Within the direct-pair class, a static feasibility theory identifies infinite families of objectives for which a mixed representation meets joint budgets that exclude both the native and the fully reduced endpoint. A separate construction extends this separation to gate and depth limits under a fixed synthesis. Compilation on 12-qubit line, ring, and grid targets finds certified mixed-only regions for 23 of 30 weighted maximum three-satisfiability instances, all 30 constructed instances, and 2 of 30 cubic spin-glass instances under the stated class and penalty rule. A separate routing experiment retains 52.9% of mixed-only budget points across five seeds within fixed candidate sets. In noiseless depth-one evaluation, the native encoding attains the best mean objective under the tested protocols, and the joint resource-and-quality test finds no mixed-only success at the primary budget. Resource feasibility is thus a sound reason to select a mixed encoding, whereas solution quality requires a separate assessment.
Minimum-cost orders of commuting phase terms can produce substantially different routed circuits. On the same 36-term instances, three orders with identical support cost 74 yield mean routed depths of 228.6, 233.8, and 256.7. We exploit this degeneracy under fixed placement and maintained-parity lowering: Stage 1 attains the support optimum, and Stage 2 selects minimum routed depth among 24 equal-cost orders. For distinct pair supports, we characterize orders attaining the support lower bound through Hamiltonian paths of the support line graph and count optima exactly through 20 terms. On synthetic 16-qubit assignment-Ising instances, selection reduces depth by 12.83% under a different SABRE routing seed, with lower depth in all 20 instances. The selected orders lie a median 1.57 pool standard deviations below the pool mean, consistent with ordinary best-of-24 selection; the useful feature is that candidate rankings persist across routing seeds. Depth reductions extend to 48 terms and a random-MaxCut generator, whereas evaluation with BasicSwap reverses the gain. A 40-instance IBM Heron study measures a 0.59% error reduction on the executed stabilizer-probe panel, but the primary confidence interval across instances includes zero. Plateau selection therefore improves routed depth in the tested SABRE pipeline while preserving the logical support optimum.
Abstract Purpose : Poor feasible sampling in full-space Penalty-X quantum approximate optimization algorithm (QAOA) can reflect representation-induced dilution, classical optimizer inadequacy, objective misalignment, or limited ansatz capacity. We separate these explanations on a controlled routing benchmark. Methods : Exact-statevector experiments use 140 resource-constrained shortest-path tasks and a scale-controlled Hamiltonian. Exact depth embeddings diagnose optimizer inadequacy. A frozen discovery/held-out design compares mean-energy training (O0), an exact-feasibility capacity control (O2), and conditional value at risk (CVaR)-0.10 (O3), with post-hoc depth, optimizer, tail-fraction, and finite-shot checks. Results : O2 showed that the fixed ansatz could reach feasible mass not induced by O0. On 84 held-out tasks from 15 graphs, O3 improved graph-level log-feasibility gain over O0 by +0.3547 decades and was non-inferior to O2: the O3–O2 effect was −0.0086, with lower bound −0.0360 above the frozen −0.10 margin. Certified nested failures occurred under COBYLA, Nelder–Mead, and SLSQP. Fixed-endpoint sampling was stable, whereas both finite-shot retraining intervals crossed zero. Conclusion : Optimizer inadequacy and objective misalignment are distinct under the tested diagnostics, and CVaR approaches the mechanistic O2 capacity control on held-out graphs. The classically tractable study supports no quantum-advantage or extrapolative scaling claim and does not test hardware noise.
The performance of the Quantum Approximate Optimization Algorithm (QAOA) on noisy intermediate-scale quantum (NISQ) devices is strongly limited by sparse qubit connectivity. When interactions required by QAOA Hamiltonians are not aligned to the hardware topology, transpilation introduces SWAP gates, increasing circuit depth and noise. We propose a SWAP-free QAOA framework based on modifying the cost Hamiltonian so that it can be implemented natively on the hardware. We formulate this as a mixed-integer semidefinite program (MISDP) that selects a hardware-compatible approximation of the original cost matrix and optimizes the allocation of logical variables to physical qubits. We prove that the associated decision problem is NP-complete and derive theoretical guarantees relating the MISDP objective to the loss in the original optimization problem through the Lovász number of the hardware graph. Since solving MISDPs is practical only for small instances, we introduce heuristics based on spectral properties of the problem matrix and hardware graph. Our experiments on a cardinality-constrained quadratic optimization model for index tracking show competitive performance against a baseline representing ideal QAOA under SWAP-induced noise. These results indicate that, on sparse NISQ architectures, a hardware-aware approximation of the objective may be more effective than an exact but heavily transpiled Hamiltonian implementation.
The Quantum Approximate Optimisation Algorithm (QAOA) has emerged as a leading candidate for near-term quantum advantage in combinatorial optimisation, but most evaluations remain confined to synthetic benchmarks such as random MaxCut instances. Translating QAOA to real-world problem instances -- with irregular graph structures, heterogeneous constraint types, and practical scale requirements -- introduces additional challenges including QUBO formulation overhead, hardware embedding costs, and the performance gap between QAOA on structured real instances vs. random benchmarks. This paper presents the Real-World QAOA (RW-QAOA) framework, a systematic methodology for applying QAOA to four real-world application domains: supply chain network optimisation, financial portfolio rebalancing, telecommunications frequency assignment, and traffic signal timing optimisation. RW-QAOA introduces three methodological contributions: a domain-adaptive QUBO formulator (DAQF) encoding real-world constraints as penalised QUBO terms with penalty coefficient auto-tuning; a warm-start initialisation strategy (WSIS) using classical heuristic solutions to seed QAOA parameter search; and a layered noise adaptation protocol (LNAP) adjusting circuit depth based on real-time device calibration data. RW-QAOA is evaluated on real problem instances from industry partners across all four domains on IBM Quantum Eagle (127-qubit). RW-QAOA achieves solution quality within 4.2% of classical exact solvers across all four domains, outperforming classical greedy heuristics by 12.4% (SD = 3.8%) on average. WSIS reduces QAOA parameter convergence iterations by 48.4%. LNAP improves approximation ratio by 8.4pp vs. fixed-depth QAOA under device noise variation.
Constraint-preserving mixers keep QAOA within a feasible subspace, but feasibility and global mixer connectivity do not determine which feasible configurations are available to a particular shallow circuit. We study constrained QAOA at the level of the circuit actually executed: a specified feasible initial state, finite depth, and finite schedule of mixer interactions. We define the finite-depth accessible set Rp(M,x0) and show that the computational-basis support of the ideal QAOA circuit is contained within it. This gives a parameter-independent objective ceiling fR⋆=maxx∈Rpf(x) and a normalized reachable-quality diagnostic QR, separating accessible volume from the objective quality contained within it.
We evaluate this framework using resource-matched block-local XY mixer schedules for constrained portfolio optimization and synthetic block-constrained quadratic problems. Across 207 favorable-tail CVaR QAOA configurations, QR shows the strongest association with realized shallow-QAOA performance among the structural diagnostics considered, with Pearson and Spearman correlations of 0.7003 and 0.8057; the relationship remains positive under controlled and dependence-aware analyses. The distinction persists across changes in feasible initialization, portfolio size, and objective family.
A compilation-only study further shows that, for the dense portfolio Hamiltonians considered here, phase-separator routing dominates the compiled two-qubit resource scale, while mixer schedules with comparable compiled two-qubit cost can exhibit markedly different finite-depth accessible quality. These results motivate objective-relevant finite-depth accessibility as a complementary diagnostic for resource-bounded constrained QAOA.
Variational quantum optimization provides a useful setting for examining how circuit structure, parameterization, and trainability interact in practice. Objectives: Among the most promising variational quantum algorithms, the Quantum Approximate Optimization Algorithm (QAOA) depends critically on circuit architecture, but greater circuit complexity does not necessarily lead to easier optimization or better solutions. Using the Maximum Cut (MaxCut) problem on graphs as a controlled setting, we investigate how variational behavior changes as problem-specific QAOA structure is progressively removed, with particular attention to representational capacity, optimization geometry, and finite-budget trainability. Methods: We analytically characterize a graph-agnostic product-state formulation of MaxCut and derive exact equivalences, redundancies, and local-landscape properties. These results motivate a controlled comparison among separable product ansätze, a representative graphagnostic entangling circuit, and graph-structured QAOA at several depths, including a parameter-count-matched control. The numerical benchmark comprises 95 small unweighted graph instances optimized under a common objective-evaluation budget. Results: The product-state formulation preserves the exact discrete MaxCut optimum, while its strict local maxima correspond to classical cuts that are stable under singlevertex flips. Redundant phase parameters increase optimization effort without enlarging the objective-relevant family. Under the prescribed optimization budget, the productstate ansatz attains higher average solution quality than the tested QAOA depths while requiring substantially fewer objective evaluations. The graph-agnostic entangling comparator provides no consistent advantage over the separable baseline, and a simple classical local-search method remains highly competitive. Conclusion: In the regime considered here, objective-relevant parameterization and optimization geometry can be as important as circuit richness.