Quantum Approximate Optimization Algorithm Faces Limitations on Constrained Problems, yet Constraint Embedding Enables Exponential Enhancement

Constrained optimisation problems, where solutions must satisfy specific criteria, present a significant challenge for quantum algorithms, and researchers are actively seeking ways to overcome these hurdles. Chinonso Onah from Volkswagen AG and RWTH Aachen, along with Kristel Michielsen from RWTH Aachen and Forschungszentrum Jülich, investigate fundamental limitations of the Quantum Approximate Optimisation Algorithm (QAOA) when applied to these complex problems. Their work demonstrates that standard QAOA circuits struggle to effectively identify valid solutions within a vast search space, even with optimised parameters and increasing circuit depth. However, the team also introduces a novel constraint-enhanced kernel that dramatically improves performance, achieving an exponential increase in the probability of finding feasible solutions for permutation-constrained problems, and extending the potential for solving a wide range of computationally difficult optimisation challenges.

They present a provable method to exponentially improve performance through a technique called constraint embedding. Focusing on problems involving permutations, the team demonstrates that standard QAOA performance is fundamentally limited by the geometry of the constrained solution space, requiring an exponentially increasing number of computational layers to achieve even approximate solutions. This limitation arises because QAOA struggles to efficiently explore solution spaces where valid solutions are sparsely distributed, and the algorithm’s natural search process is hindered by the complex topology of the constraint space.

To overcome this, the researchers introduce a novel constraint embedding technique that maps the original constrained problem onto an unconstrained one in a higher-dimensional space, effectively smoothing the solution landscape and enabling efficient exploration by QAOA. They prove that this embedding leads to an exponential reduction in the number of layers required to achieve a given approximation ratio, demonstrating a significant enhancement in the algorithm’s performance. Furthermore, analytical results and numerical simulations validate the effectiveness of their approach and highlight its potential for solving a wide range of constrained optimization problems. The research demonstrates that standard QAOA circuits, employing a transverse-field mixer and diagonal cost function, encounter an inherent feasibility limitation.

Even after optimising circuit parameters, circuits with a limited depth cannot significantly increase the probability of finding solutions within the feasible space beyond a baseline level, allowing only for polynomial improvement. To address this, the team introduces a minimal constraint-enhanced kernel (CE-QAOA) which operates directly within a restricted solution space and utilises a block-local mixing Hamiltonian. Their work demonstrates that standard QAOA approaches struggle to efficiently find solutions within complex solution spaces, even with increasing computational depth. The team introduced a modified approach, termed constraint-enhanced QAOA, which incorporates a specialized kernel designed to operate directly within the feasible solution space. This constraint-enhanced kernel, combined with a tailored mixing Hamiltonian, demonstrably improves performance, achieving an exponential increase in the probability of finding valid solutions compared to standard QAOA at equivalent computational depths. The improvement holds for problems where the number of valid solutions grows polynomially, and the researchers rigorously established both upper and lower bounds on the performance of each approach using advanced mathematical techniques, including harmonic analysis and angle averaging.