Scalable Quantum Approximate Optimiser for Pseudo-Boolean Multi-objective Optimisation

Quantum computation uses quantum mechanical principles to reach beyond-classical computational power. This has endless applications, especially in optimisation-problems’ solving. Most of today’s quantum optimisers, more specifically, Quantum Approximate Optimisation Algorithm (QAOA), were originally designed to solve single-objective problems, although real-life scenarios include generally dealing with multiple objectives. Very preliminary literature with design/implementation limitations has been done in this sense. This makes dealing with such limitations and expanding the QAOA applicability to multi-objective optimisation an important step towards advancing quantum computation. To do so, this work presents a decomposition-based Multi-Objective QAOA (MO-QAOA) able to solve multi-objective problems. The proposal’s design explores QAOA’s features considering the error-prone and limited nature of today’s quantum computers as well as the costly quantum simulation. This work’s contributions stand in designing both, (I) sequential and parallel MO-QAOA, based on (II) weighted-sum and Tchebycheff scalarisation, by (III) exploring the QAOA’s parameters’ transference. The validation has been done using 2, 3 and 4-objectives problems of several sizes/complexities/types, using up to 2000 slaves/jobs running quantum computer simulators, as well as three real IBM 127-qubits’ quantum computers. The results show up to 89% execution-time decrease, which supports the applicability/reliability of the proposal in today’s time-constrained and error-prone quantum computers.