Quantum Framework Maps Multiple QUBO Problems to Ising Hamiltonians for Optimization

The challenge of solving complex optimisation problems frequently relies on transforming them into a simplified energy landscape, often resembling an Ising-type Hamiltonian, which can then be tackled using techniques like adiabatic optimisation and the Approximate Optimisation Algorithm. Sebastian Egginger, Kristina Kirova, and colleagues at Johannes Kepler University Linz and the Software Competence Center Hagenberg now present a novel framework, termed Multi-Objective Approximations, or MOQA, that significantly expands the range of solvable problems. MOQA provides tractable mappings for finding the optimal solutions to multiple Quadratic Unconstrained Binary Optimisation problems simultaneously, effectively recasting classical binary optimisation challenges as ground state problems within a manageable Hamiltonian. This breakthrough enables the application of quantum-inspired algorithms to a wider variety of practical problems, including complex routing, partitioning, and inequality-constrained optimisation tasks, potentially unlocking solutions previously beyond reach.

Subsequently, techniques such as adiabatic optimization, quantum annealing, and the Quantum Approximate Optimization Algorithm (QAOA) can be used to find the ground state of this Hamiltonian. This work introduces a novel framework, Multi-Objective Approximations, or MOQA, that allows researchers to simultaneously optimize several distinct objective functions within a quantum computational paradigm.

Quantum Optimization via Parametrized Circuits

Scientists are developing methods to improve how complex optimization problems are prepared for solution using quantum-inspired algorithms. A central challenge lies in accurately representing these problems as finding the ground state of a Hamiltonian, an energy landscape that reflects the problem’s possible solutions. The team focuses on the Quantum Approximate Optimization Algorithm (QAOA) and related techniques, which require careful mapping of the problem’s constraints and objective function. The core of this work involves mapping the problem’s objective function to a Hamiltonian operator, where the ground state corresponds to the optimal solution. This work addresses a critical challenge in applying these algorithms, which require problems to be expressed as finding the ground state of a specific type of Hamiltonian. MOQA allows researchers to recast problems involving maximizing multiple objectives as ground state problems, opening new avenues for tackling a wider range of practical applications. The team demonstrated that MOQA can effectively handle routing and partitioning problems, as well as optimization problems with inequality constraints.

Researchers achieved this by applying a shift to ensure all objective values are non-negative, guaranteeing a positive landscape for optimization. This shift is carefully calculated using the smallest eigenvalue of a modified matrix, ensuring minimal disruption to the problem’s structure. Experiments revealed that the accuracy of this approximation can be precisely controlled, with a relative error bounded by a function of the number of objectives and the approximation level. Specifically, for up to 105 objectives, maintaining an accuracy within ±5% requires an approximation level of no more than 100.

Furthermore, the team established a threshold for the spectral gap ratio, a measure of the problem’s inherent difficulty, demonstrating that minima of the approximated and original Hamiltonians align above this threshold. To demonstrate practical implementation, scientists developed an algorithm that translates a MOQA-type Hamiltonian into a classical n-qubit Hamiltonian comprised solely of Pauli-Z and identity terms. This means the resulting Hamiltonian requires only a polynomial number of resources to implement, a significant advantage over the exponential resources needed for the exact Hamiltonian.

MOQA Transforms Optimization for Quantum Algorithms

This work presents a new framework, Multi-Objective Approximations (MOQA), which maps complex optimization problems onto a form suitable for solution using quantum-inspired algorithms. A key achievement is a prototype algorithm that converts MOQA approximations into weighted Pauli terms with polynomial runtime, and importantly, identifies a sparse structure within the necessary weight vector. Extensive numerical studies reveal that MOQA consistently finds good solutions with small relative errors, and the difficulty of approximation does not increase proportionally with problem size.

Larger problems tend to exhibit fewer constraint violations, a counterintuitive finding that warrants further investigation. While acknowledging the limitations of achieving perfect solutions, the team highlights that MOQA’s performance is influenced by factors such as problem size, sparsity, symmetries, and the required precision. Future work will focus on reducing the algorithm’s memory requirements by exploiting the identified sparsity in the weight vector and further exploring the observed relationship between problem size and solution quality.