Quantum Annealing Vastly Outperforms Classical and Quantum Methods in Multi-objective Optimization

Generating the best possible compromises between multiple, competing goals is a central challenge in many fields, and identifying the complete set of these optimal solutions, known as the Pareto front, can be incredibly demanding for even modest problems. Andrew D. King from D-Wave Quantum Inc. investigates this challenge by applying quantum annealing to multi-objective optimisation, and directly compares the results with those recently achieved using a different quantum approach on an alternative processor. The research demonstrates that quantum annealing significantly outperforms not only the gate-model quantum processor tested, but also all previously published classical and quantum methods, even improving upon the best known Pareto front for a particularly difficult problem. This work reinforces the potential of quantum annealing as a powerful tool for tackling complex optimisation challenges with multiple objectives.

Here, researchers compare these QAOA results with quantum annealing on the same two input problems, using a consistent methodology. The study reveals that quantum annealing vastly outperforms not just QAOA, but all classical and quantum methods analysed in previous work. On a particularly challenging problem, quantum annealing improves upon the best known Pareto front, reinforcing its potential in multi-objective optimization. In multi-objective optimization (MOO), one must simultaneously consider the priorities of multiple stakeholders.

Quantum Optimization via QAOA and Quantum Annealing

Generating the set of Pareto-optimal compromises, where improving one objective degrades another, can be enormously difficult even when each individual objective function is easily optimized. This makes MOO, particularly for unconstrained binary problems, an attractive target for quantum optimization. This study considers two popular quantum optimization approaches: the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). QAOA applies multiple layers of mixer and objective Hamiltonians to a quantum state, while QA guides an initial state through a quantum phase transition into a low-energy state of the classical target Hamiltonian.

Several recent studies already report promising results in applying QA to MOO. QAOA and QA are related, falling into the same general framework of quantum optimization through the application of varying Hamiltonians. However, evidence suggests that QA is a more effective means of optimization on current quantum processors. Nonetheless, QAOA, which has theoretical approximation guarantees in an ideal fault-tolerant QPU, maintains a place in gate-model orthodoxy.

Quantum Annealing Generates Superior Pareto Fronts

This work presents a significant advancement in multi-objective optimization through the application of quantum annealing, demonstrating substantial performance gains over both classical methods and a recent quantum approximate optimization algorithm (QAOA) approach. Researchers tackled the complex task of generating Pareto fronts, sets of optimal compromises between multiple conflicting objectives, using quantum annealing on D-Wave systems and compared the results to those obtained with QAOA and classical algorithms. The study focused on maximizing weighted maximum-cut problems, a task well-suited to the architecture of quantum annealers. Experiments involved generating Pareto fronts by sampling from numerous weighted combinations of objective functions, with the team drawing 1000 samples using quantum annealing for each weighting.

Utilizing the Advantage2 system, they successfully packed 96 instances of the problem onto the qubit connectivity graph, enabling parallel sampling and accelerating the process. Data from the previous-generation Advantage system, which offered higher parallelism with 114 instances but increased noise, was also collected for comparison. The team ran anneals with a duration of 1μs, noting that the overall processor time was dominated by readout. Results demonstrate that quantum annealing significantly outperformed all previously analyzed classical and quantum methods, including the QAOA approach. Both the Advantage2 system and Advantage system found the same optimal solution, constructing Pareto fronts comprised of 2067 non-dominated points. Performance was quantified using the hypervolume (HV) of non-dominated points, a figure of merit that measures the volume encompassed by the Pareto front in multi-dimensional space. These findings reinforce the promise of quantum annealing as a powerful tool for tackling complex optimization challenges.

Quantum Annealing Outperforms QAOA in Optimization

This research demonstrates a significant advancement in multi-objective optimization through the application of quantum annealing. Scientists successfully compared quantum annealing with a previous implementation of the quantum approximate optimization algorithm (QAOA) on the same complex problems, revealing substantially improved performance with quantum annealing. Specifically, the team achieved a faster approach to identifying optimal solutions, with quantum annealing proving approximately 1000times quicker than a simulated QAOA implementation when considering comparable computational effort. The study not only replicated a multi-objective quantum optimization workflow but also identified the Pareto front, the set of optimal compromise solutions, more efficiently.

In one instance, the quantum annealing method matched a Pareto front believed to be optimal, achieved with significantly fewer computational steps than previously reported methods. While acknowledging the limitations inherent in comparing different quantum approaches, the authors highlight the consistency of these findings with existing research indicating the superior performance of quantum annealing in binary optimization tasks. Future work could explore the scalability of this approach to even larger and more complex problems, potentially unlocking new capabilities in fields reliant on multi-objective optimization.