Quantum Algorithms Gain Efficiency Boost for Complex Problem Solving

Scientists are increasingly investigating quantum approaches to multi-objective optimisation, a crucial process for resolving conflicting objectives across numerous industrial applications. Linus Ekstrøm, Takafumi Hosogi, and Xavier Bonet-Monroig from Honda Research Institute Europe GmbH, working with Hao Wang from ⟨aQaL⟩Applied Quantum Algorithms and Universiteit Leiden, and Thomas Bäck and Sebastian Schmitt from LIACS, Universiteit Leiden, present a significant advancement in variational multi-objective optimisation (QMOO). Their research introduces a Pareto Archive and dominated solutions substitution technique, demonstrably improving hyper-volume convergence, albeit with additional classical computational cost. The team devised a method for mapping Random Multi-Knapsack landscapes, a common benchmark in classical multi-objective optimisation, to quantum systems, enabling rigorous hyperparameter tuning and performance comparison against established classical solvers such as NSGA-II/III. These findings suggest that carefully tuned QMOO algorithms possess the potential to outperform classical methods on more complex optimisation problems.

Scientists are refining variational quantum multi-objective optimisation (QMOO) , a technique designed to tackle complex problems with competing goals, by introducing a novel archiving and substitution method. This improvement demonstrably enhances hyper-volume convergence, a key metric for evaluating the quality of solutions in multi-objective optimisation, albeit with increased quantum and classical computational demands.

The research addresses a critical challenge in leveraging the potential of quantum computers for real-world applications where trade-offs between multiple objectives are commonplace, such as in industrial design, logistics, and financial modelling. By enhancing QMOO, researchers aim to unlock the possibility of finding optimal solutions in scenarios where simply minimising a single objective is insufficient.

This work establishes a standardized benchmarking approach for QMOO algorithms using RMNK-landscapes, a well-established methodology in classical multi-objective optimisation. A crucial step involved devising a method to translate these classical landscapes into a form compatible with quantum cost Hamiltonians, enabling a systematic evaluation of QMOO’s performance.

Through careful numerical tuning of QMOO’s hyperparameters, the team significantly boosted its efficiency, demonstrating that the algorithm can achieve strong results even with a limited number of measurement shots and a modest population size. This is particularly important for near-term quantum devices where resources are constrained.

The study then directly compared the enhanced QMOO against two prominent classical multi-objective solvers, NSGA-II and NSGA-III, on RMNK-landscapes of varying complexity. Initial results reveal comparable performance on smaller instances, but suggest that the carefully tuned QMOO algorithm may offer advantages when tackling more challenging optimisation problems.

This finding hints at the potential for quantum algorithms to outperform their classical counterparts in specific scenarios, paving the way for future investigations into the scalability and practical utility of QMOO for complex, real-world multi-objective optimisation tasks. The research underscores the importance of tailored optimisation strategies for quantum algorithms to fully realise their potential.

Pareto archive refinement and RMNK landscape mapping boost quantum optimisation performance

Improvements to the quantum multi-objective optimisation (QMOO) algorithm have yielded significant enhancements in hyper-volume convergence at the cost of both quantum and classical computational resources. The research introduces a Pareto Archive and dominated solutions substitution technique, demonstrably improving the algorithm’s performance.

A key achievement is the development of a generic classical-to-quantum mapping for RMNK-landscapes, enabling systematic benchmarking of QMOO, a common practice in classical multi-objective optimisation. Numerical hyperparameter tuning, facilitated by this mapping, substantially enhanced QMOO’s performance across a range of test problems.

Specifically, the tuned QMOO algorithm demonstrated strong performance even with a low number of measurement shots and modest population sizes. Comparisons against well-established classical solvers, NSGA-II and NSGA-III, revealed comparable results on small instances of the RMNK-landscapes. The study highlights that QMOO, when carefully tuned to the specific characteristics of the optimisation task, may offer advantages over its classical counterparts when tackling more complex problems.

Hypervolume calculations consistently served as the primary metric for evaluating the quality of solution sets, quantifying both convergence and coverage of the Pareto front. The work establishes a robust framework for evaluating multi-objective quantum algorithms using RMNK-landscapes, providing a valuable tool for future research in this area.

Pareto front exploration using a 72-qubit processor and RMNK-landscape cost Hamiltonians

A 72-qubit superconducting processor serves as the foundation for implementing a variational multi-objective optimisation (QMOO) algorithm, designed to identify optimal solutions across conflicting objectives. This work builds upon existing QMOO methods by introducing a Pareto Archive and a dominated solutions substitution technique, both intended to enhance hypervolume convergence, a measure of solution quality, at the cost of increased quantum and classical computational resources.

The core innovation lies in the algorithm’s ability to maintain a diverse set of non-dominated solutions, facilitating exploration of the Pareto front, which represents the best possible trade-offs between multiple objectives. To facilitate benchmarking, the research proposes utilising RMNK-landscapes, a unifying testbed commonly employed in classical multi-objective optimisation.

A crucial methodological step involves devising a generic mapping from these RMNK-landscapes to cost Hamiltonians, enabling their implementation on quantum devices. This mapping allows for a direct comparison between quantum and classical approaches, leveraging the strengths of each paradigm. Following this, a numerical hyperparameter tuning process was undertaken to optimise the performance of the improved QMOO algorithm, significantly enhancing its efficiency.

The quantum circuit employed follows an alternating-layer ansatz comprising L layers, each parametrised by angles βl and γl, evolving an initial uniform superposition state. Each layer consists of K objective blocks, one for each objective function, applying mixing and cost unitaries to manipulate the quantum state.

The resulting output state is a superposition of binary strings, with amplitudes determined by the variational parameters. Sampling from this state yields candidate solutions, from which a non-dominated subset is identified to approximate the Pareto set. The hypervolume indicator, quantifying both convergence and coverage of the Pareto front, is then used as the cost function within a classical optimiser, iteratively refining the quantum circuit’s parameters. This hybrid quantum-classical loop concentrates probability mass on Pareto-optimal solutions.

The Bigger Picture

The persistent challenge of balancing competing priorities, a hallmark of real-world optimisation problems, may have edged closer to a quantum solution. For years, the promise of quantum optimisation has been hampered by the difficulty of translating abstract algorithms into demonstrable advantage on practical problems.

The ‘No Free Lunch’ theorem reminds us that no single algorithm excels across all landscapes; success demands careful tailoring to the specific problem structure. This research addresses that head-on, proposing a standardised testbed, RMNK-landscapes, borrowed from classical optimisation, and a systematic approach to tuning the quantum algorithm for these landscapes.

The results, showing comparable performance to established classical solvers on smaller instances, are not groundbreaking in themselves. However, the real value lies in the methodology. By demonstrating a pathway to rigorous benchmarking and hyperparameter optimisation, this work establishes a foundation for more meaningful comparisons between quantum and classical approaches.

Limitations remain, notably the current scale of quantum hardware, and the question of whether these gains will persist as problem complexity increases. Future efforts will likely focus on scaling up these algorithms and exploring their application to genuinely intractable, real-world scenarios, from portfolio optimisation to complex engineering design, where the ability to navigate multiple, conflicting objectives is paramount.