Quantum Framework Solves Inequality-Constrained, Multi-Objective Binary Optimization with Rigorous Performance Guarantees

Many practical optimisation problems involve both limitations and multiple, competing goals, yet current computational methods struggle to address these complexities simultaneously. Sebastian Egginger, Kristina Kirova, and colleagues at Johannes Kepler University Linz and the Software Competence Center Hagenberg demonstrate a novel approach to tackling these challenges by establishing a fundamental connection between inequality constraints and multi-objective optimisation. Their work reveals that incorporating these constraints is mathematically equivalent to seeking solutions that balance multiple objectives, leading to the development of the Multi-Objective Approximation (MOQA) framework. MOQA offers rigorous performance guarantees and operates directly on the underlying physics of the problem, making it compatible with a range of optimisation algorithms, and importantly, extending beyond the limitations of purely quadratic functions.

Quantum Framework for Constrained Multi-Objective Optimisation

Encoding complex optimisation problems into physically meaningful Hamiltonians forms the foundation of quantum optimisation. This research presents a rigorous quantum framework designed to solve binary optimisation problems burdened by inequality constraints and multiple objectives. The approach involves formulating a novel Hamiltonian structure that directly incorporates these complexities, allowing for a natural mapping onto quantum systems. Specifically, the team developed a method to represent inequality constraints using auxiliary variables and penalty terms within the Hamiltonian, ensuring feasible solutions. Furthermore, the framework introduces a weighted sum approach to handle multiple objectives, enabling the optimisation of trade-offs between conflicting goals. This work establishes a foundational step towards developing quantum algorithms capable of solving complex, real-world optimisation problems with inherent constraints and competing objectives.

Spectral Gap Guarantees Approximation Accuracy

This research investigates the conditions under which a polynomial approximation of a binary optimisation problem retains its essential properties, particularly the location of its minimum. The team demonstrates that if the number of iterations is sufficiently large, the approximating function will have the same minimum as the original problem, with the required iterations determined by the spectral gap ratio. Furthermore, the study proves that the spectral gap of the approximating Hamiltonian is greater than or equal to the spectral gap of the original Hamiltonian, potentially making the problem easier to solve by increasing the separation between the ground state and excited states. The proof relies on bounding the values of the approximating function and relating them to the spectral gap of the Hamiltonian.

Constraints and Objectives, A Quantum Link

Researchers have established a fundamental connection between constrained binary optimisation problems and multi-objective optimisation, revealing that incorporating inequality constraints is mathematically equivalent to seeking solutions across multiple objectives. Building on this insight, the team developed the Multi-Objective Quantum Approximation (MOQA) framework, a novel approach to tackling complex optimisation challenges. MOQA approximates optimal solutions by utilizing smaller norms, and comes with guaranteed performance bounds. The MOQA framework operates directly at the level of the Hamiltonian and is compatible with various quantum solving techniques, including adiabatic quantum optimisation and the Quantum Approximate Optimisation Algorithm. Significantly, this new method is not limited to quadratic problems, extending its potential applicability to a wider range of real-world scenarios.