Towards Practical Quantum Multi-Objective Optimisation

by Zakaria Abdelmoiz Dahi (University of Lille, Inria, CNRS), Gabriel Luque and Francisco Chicano (Univerisity of Malaga)

Quantum computing has the potential to revolutionise optimisation, yet most existing approaches focus on problems with a single objective. Our work bridges this gap by developing scalable quantum algorithms capable of tackling realistic optimisation problems involving multiple conflicting objectives. 

Optimisation is widely regarded as one of the application domains where quantum computing could have the greatest impact. This field, grounded in mathematics and engineering, aims to find solutions that maximise (or minimise) a given quality metric, known as an objective function, which indicates the quality of a solution (e.g. determining where to place electric vehicle charging stations to satisfy as much of the city’s demand as possible). Single-objective problems involve one objective at a time. However, many practical problems involve several, often conflicting, objectives that must be optimised simultaneously. This category of problems, known as multi-objective problems, is quite complex and widespread (e.g. deciding where to build parking facilities to maximise city coverage while minimising construction costs). Rather than seeking a single optimum, multi-objective optimisation aims to identify a set of trade-off solutions, known as the Pareto front.

Many optimisation problems can naturally be formulated using binary decision variables  (e.g. deciding whether to place or not an electric charging station in a candidate spot). Such problems, known as pseudo-Boolean problems, have received considerable attention in quantum single-objective optimisation. In contrast, quantum multi-objective pseudo-Boolean optimisation has received comparatively little attention. As a result, the applicability of quantum optimisation remains limited for many real-world problems involving multiple conflicting objectives. Devising multi-objective quantum algorithms poses several challenges from both the algorithmic and hardware perspectives. From an algorithmic perspective, integrating search mechanisms that capture the objectives’ conflicting relationship, as well as solving problems with complex features is particularly challenging (even in the classical realm). From a hardware point of view, today’s quantum machines remain limited in terms of qubit counts, gate fidelity, and robustness to errors.

The limitations of current quantum hardware, together with the complexity of pseudo-Boolean multi-objective optimisation problems, raise challenging research questions on how to design optimisers that (i) can efficiently tackle complex problems, (ii) scale despite the limitations of current quantum hardware, (iii) are resilient to quantum errors, and (iv) are practically implementable (see Figure 1). Thus, our efforts have focused on four axes: efficiency, scalability, feasibility, and applicability.

To address the scalability challenge, we first proposed a distributed optimisation framework [1]. The approach exploits high-performance computing to execute multiple quantum optimisation processes in parallel, each exploring different regions of the objective space through eigensolver-based quantum optimisers. This distributed strategy enables the approximation of multiple trade-off solutions while overcoming the limited computational capacity of individual quantum processors. Building upon this framework, we further improved the proposal's optimisation capabilities in [1,2]. The initial scalarisation-based approach was extended with a reference-based formulation (known as Tchebycheff scalarisation), which guides the search towards different regions of the objective space and allows the optimiser to approximate much more complex Pareto fronts than conventional weighted-sum techniques.

Beyond scalability and efficiency, we also focused on improving the feasibility and practical applicability of quantum multi-objective optimisation. In [2], we exploited algorithmic properties to generate more compact quantum circuits, reducing the number of quantum operations and therefore the exposure to noise sources such as relaxation and dephasing. Finally, in [3], we proposed a machine learning-assisted distributed eigensolver that significantly reduces the amount of quantum-classical interaction required by NISQ algorithms (see Figure 2). This decreases communication overhead, execution costs, and error accumulation, while making the overall optimisation process more practical for current quantum hardware. Together, these contributions form a scalable quantum optimisation framework that combines distributed execution, improved Pareto front exploration, hardware-aware circuit design, and machine learning-assisted optimisation, enabling a broad class of pseudo-Boolean multi-objective problems to be tackled on current NISQ platforms. 

Our research on quantum pseudo-Boolean multi-objective optimisation combines theoretical advances with extensive experimental validation. Our proposals [1-3] have been validated using the largest collection of quantum hardware platforms and benchmark instances reported so far, including the largest IBM gate-based quantum computers and D-Wave quantum annealers, benchmark instances with up to one thousand variables, and problems of varying sizes and complexities. This is worth highlighting because our research pursues two complementary goals: advancing the theoretical foundations of quantum multi-objective optimisation while demonstrating its practical applicability. We believe both are essential stepping stones towards future advances in quantum multi-objective or general optimisation. As quantum hardware continues to evolve, these techniques are expected to scale to increasingly larger and more complex optimisation problems. We hope that this work contributes to bringing quantum multi-objective optimisation closer to real-world scientific and industrial applications. 

References: 
[1] Z.A. Dahi, et al, “Scalable Quantum Approximate Optimiser for Pseudo-Boolean Multi-objective Optimisation”, in: Proc. of the 18th Int. Conf. on Parallel Problem Solving from Nature (PPSN’24),  Springer LNCS vol 15151, 2024. https://doi.org/10.1007/978-3-031-70085-9_17
[2] Z.A Dahi, et al, “Scalable quantum Trotterised-vs-continuous annealing for pseudo-Boolean multi-objective optimisation”, Future Generation Computer Systems 183 2026, 108568. https://doi.org/10.1016/j.future.2026.108568
[3] Z.A. DAHI, F. Chicano, and G. Luque, “Tightening the Calculation Gap in Quantum Multi-Objective Pseudo-Boolean Optimisation”, in Proc. of the 19th Int. Conf. on Parallel Problem Solving From Nature (PPSN’26), Springer. https://doi.org/10.1007/978-3-032-36226-1_21

Please contact: 
Zakaria Abdelmoiz Dahi 
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, France
This email address is being protected from spambots. You need JavaScript enabled to view it.

Gabriel Luque and Francisco Chicano
ITIS Software, University of Malaga, Spain
This email address is being protected from spambots. You need JavaScript enabled to view it., This email address is being protected from spambots. You need JavaScript enabled to view it.