Quantum 2025 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
WED-ID: Industry Day
WED-ID 6: Quantum Hardware, Software & Solutions
WED-ID 6.4: Talk
Wednesday, September 10, 2025, 16:25–16:45, ZHG006
Provable Exponentially Enhanced QAOA on NISQ Hardware — •Chinonso Onah1,2 and Kristel Michielsen2,3 — 1Volkswagen Group, Germany — 2Department of Physics, RWTH Aachen, Germany — 3Forschungszentrum Jülich, Germany
Industrial routing, scheduling and matching problems consume disproportionate compute budgets, yet their feasible solutions typically lie on a low-dimensional algebraic manifold (for example, subspaces with fixed Hamming-weight patterns). Vanilla QAOA must explore the full Hilbert space, diluting amplitude on invalid states and succumbing to barren plateaus. Consequently, we introduce Constraint-Enhanced QAOA (CE-QAOA), which starts and stays inside the exponentially smaller one-hot subspace of size n. A depth-optimal, ancilla-free encoder prepares a uniform superposition of single-excitation states per block, while a block-wise XY mixer preserves feasibility and is native to several hardware platforms. Circuit overhead is minimal: CE-QAOA adds at most the depth of a single XY block beyond vanilla QAOA.
Three exponential advantages compound from:
(i) Feasibility concentration. (ii) Exponential parameter-transfer amplification. (iii) Depth-robust exponential separation.
The framework extends to the traveling-salesman problem (TSP), the capacitated vehicle-routing problem (CVRP), graph matching, flow-shop scheduling, graph colouring, and more.
Keywords: Constraint‐Enhanced QAOA; One‐Hot Subspace Encoding; Combinatorial Optimization; Parameter‐Transfer Amplification; Quantum Approximate Optimization Algorithm