Ferrari and Colleagues Introduces Λ-Lr-QAOA for Heterogeneous Constrained Optimization

A new method improves the performance of quantum algorithms for complex optimisation problems. Francesco Ferrari of the Quantum Computing Solutions and colleagues from Leonardo Hypercomputing Continuum present extensions to the linear-ramp Quantum Approximate Optimisation Algorithm (lr-QAOA) designed for problems with multiple constraints. The research addresses the challenge of balancing feasibility and solution quality, moving away from inefficient penalty adjustments typically used in Quadratic Unconstrained Binary Optimisation formulations. By introducing both $Λ$-lr-QAOA and piecewise-ramp QAOA, and guiding optimisation with a feasibility-driven loss function, they demonstrate improved performance on Earth-observation satellite mission planning tasks, achieving high feasibility rates and highlighting a key trade-off between feasibility and optimality.

Piecewise-ramp QAOA substantially improves solution feasibility for complex optimisation problems

A feasibility rate exceeding 98 percent is now achievable using piecewise-ramp QAOA. This represents a strong improvement over the less than 80 percent attained with both lr-QAOA and Λ-lr-QAOA methods. High feasibility is key for real-world industrial applications where obtaining workable solutions is vital, something previously difficult to guarantee with traditional penalty-based approaches. The development of piecewise-ramp QAOA extended linear-ramp QAOA by assigning independent schedules to penalty terms and employing two-segment piecewise schedules to increase the algorithm’s ability to explore potential solutions. Traditionally, quantum optimisation algorithms, particularly those employing the QUBO formulation, represent constraints as ‘soft’ penalties added to the objective function. This necessitates careful tuning of penalty coefficients; a process that becomes exponentially more difficult as the number of constraints increases. Incorrectly weighted penalties can lead to either infeasible solutions that violate constraints or suboptimal solutions that satisfy constraints poorly. The lr-QAOA method attempts to address this by linearly increasing the penalty strength over the course of the quantum computation, but still requires initial parameter estimation.

The piecewise-ramp variant achieved consistently higher performance than standard methods across varying circuit depths and problem sizes. Numerical tests showed successful solutions to Earth-observation satellite mission planning tasks, formulated as budget-constrained Maximum Weight Independent Set problems. A strikingly improved ability to balance solution quality and adherence to constraints was observed, alongside an intrinsic trade-off between finding feasible solutions and optimising for the best possible outcome, managed by a single adjustable parameter within a filtered loss function. The Maximum Weight Independent Set problem, in this context, involves selecting a subset of potential satellite targets to observe, maximising the total scientific value of the observations while remaining within a limited budget of resources (e.g., power, time). The budget constraint represents a hard constraint that must be satisfied. The piecewise-ramp approach allows for a more nuanced exploration of the solution space, effectively prioritising constraint satisfaction early in the optimisation process and then refining the solution for optimality. The filtered loss function incorporates both the objective function (representing the scientific value) and a penalty term for constraint violations, allowing the algorithm to simultaneously optimise for both.

This new method eliminates the need for time-consuming adjustments to penalty coefficients, simplifying the optimisation process. Benchmarking against instances with 24 targets, a scale suitable for initial testing and validation, revealed that piecewise-ramp QAOA consistently outperformed lr-QAOA and Λ-lr-QAOA across different circuit depths and system sizes. Both Λ-lr-QAOA and piecewise-ramp QAOA achieve a high feasibility rate, valuable in industrial applications, and the algorithm’s performance stems from jointly optimising solution quality and constraint satisfaction. The circuit depth refers to the number of quantum gate layers applied in the QAOA algorithm; deeper circuits generally allow for more complex optimisation but also increase the risk of errors due to decoherence. The system size relates to the number of qubits required to represent the problem, with larger problems demanding more qubits. The consistent outperformance across these parameters demonstrates the robustness of the piecewise-ramp approach.

Quantum optimisation balances solution feasibility with performance gains

Quantum algorithms now offer a potential pathway towards automating complex scheduling and resource allocation, important for industries like satellite mission planning. Even a slightly better outcome can translate to significant gains in efficiency and data collection when scheduling complex tasks. By shifting constraint handling from a cumbersome external process to internal parameters within the quantum computation itself, a more scalable and manageable system has been created. The potential benefits extend beyond satellite mission planning to other areas such as logistics, finance, and materials discovery, where complex optimisation problems with numerous constraints are commonplace. The ability to reliably find feasible solutions is often more critical than achieving the absolute optimal solution, particularly in time-sensitive applications.

The Space Agency’s scientists have refined quantum algorithms to better manage complex tasks such as scheduling Earth-observation satellites. This development represents a shift towards internalising constraint handling within the quantum computation. Assigning independent schedules to penalty terms, the components that enforce rules within the problem, and utilising two-segment piecewise schedules enhances the algorithm’s capacity to explore potential solutions. Testing this approach on complex Earth-observation satellite mission planning, a task involving optimising schedules under budgetary constraints, demonstrated a significant improvement in both feasibility and solution quality. Earth-observation satellites collect data crucial for monitoring climate change, tracking deforestation, and responding to natural disasters. Optimising their schedules involves balancing competing priorities, such as maximising coverage of specific regions, minimising power consumption, and adhering to strict operational constraints. The lr-QAOA and its extensions offer a promising avenue for automating this complex process, potentially leading to more efficient and effective data collection. The $Λ$-lr-QAOA variant introduces a parameter, $Λ$, to control the rate at which the penalty terms are ramped up, providing an additional degree of freedom for tuning the algorithm’s performance.

Furthermore, the observed trade-off between feasibility and optimality highlights a crucial consideration for practical applications. While the piecewise-ramp QAOA excels at finding feasible solutions, achieving the absolute best possible solution may require sacrificing some degree of feasibility. The single adjustable parameter within the filtered loss function allows users to fine-tune this trade-off, prioritising either feasibility or optimality based on the specific requirements of the application. This level of control is essential for adapting the algorithm to diverse problem settings and ensuring that the resulting solutions are both practical and effective. Future research will focus on extending these methods to larger and more complex problem instances, as well as exploring the potential for hybrid quantum-classical algorithms that combine the strengths of both approaches.

The research successfully developed two improvements to linear-ramp Quantum Approximate Optimisation Algorithm (lr-QAOA) for solving complex optimisation problems with multiple constraints. These new methods, $Λ$-lr-QAOA and piecewise-ramp QAOA, optimise penalty terms internally rather than requiring manual adjustment, improving efficiency when dealing with numerous rules. Testing on Earth-observation satellite mission planning demonstrated that piecewise-ramp QAOA consistently achieved higher quality, feasible solutions. The authors intend to extend these methods to even larger and more complex problems, and explore combining them with classical algorithms.