⚛️ quantum physics

Improving Quantum Multi-Objective Optimization with Archiving and Substitution

This paper proposes an enhanced Variational Quantum Multi-Objective Optimization (QMOO) algorithm that utilizes a Pareto Archive and dominated solution substitution to improve hyper-volume convergence, demonstrating through RMNK-landscape benchmarking that a carefully tuned QMOO can perform comparably to classical solvers like NSGA-II/III and potentially offer advantages on complex problems.

Original authors: Linus Ekstrøm, Takafumi Hosogi, Xavier Bonet-Monroig, Hao Wang, Thomas Bäck, Sebastian Schmitt

Published 2026-02-12

📖 3 min read🧠 Deep dive

CC BY 4.0

Original authors: Linus Ekstrøm, Takafumi Hosogi, Xavier Bonet-Monroig, Hao Wang, Thomas Bäck, Sebastian Schmitt

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to create the "perfect" dish. But there’s a catch: you have three conflicting goals. You want it to be delicious, extremely cheap to make, and super fast to cook.

If you make it incredibly delicious, it might become expensive and slow. If you make it lightning-fast, it might taste like cardboard. In the world of math and science, this is called Multi-Objective Optimization. You aren't looking for one single "best" recipe; you are looking for a "menu" of perfect trade-offs (called a Pareto Front).

This paper explores how to use Quantum Computers to find that perfect menu more efficiently.

The Problem: The "Messy Kitchen"

Current quantum algorithms for this task are a bit like a chef who has a great memory for one recipe but forgets everything else the moment they try a new ingredient. They struggle to keep track of the good recipes they’ve already found, and they often get stuck in "culinary dead ends"—parts of the kitchen where every dish tastes bad, and they can't find their way out.

The Solution: Two New Kitchen Rules

The researchers introduced two clever upgrades to the quantum "chef" (the QMOO algorithm):

1. The Recipe Archive (Pareto Archiving)
Imagine the chef now has a Master Recipe Book. Every time they stumble upon a recipe that is a great trade-off (e.g., "not too expensive and quite tasty"), they write it down in the book. Even if the next batch of cooking goes poorly, they don't lose that progress. They always have their "best hits" saved. This prevents the algorithm from "forgetting" its successes.

2. The "Try Everything" Rule (Dominated Substitution)
In the old version, if the chef cooked 20 dishes and 15 of them were terrible, they would just throw them all away and start over. This was a waste of time.
The new rule says: "Wait! Even if those 15 dishes weren't perfect, maybe one of them was slightly better than the others." Instead of throwing everything out, the chef picks the best "almost-good" dishes to keep the momentum going. It’s like a scout who doesn't just look for gold, but also keeps the silver and copper to study how to find more gold later.

The Testing Ground: The "Labyrinth" (RMNK Landscapes)

To see if this worked, they didn't just test it on easy problems. They used something called RMNK Landscapes.

Think of this as a mountain range with many peaks and valleys.

If the mountains are smooth, it's easy to find the top.
If the mountains are jagged, rocky, and full of sudden cliffs (high "epistasis"), it’s incredibly hard to navigate.

The researchers showed that while traditional "classical" computers (the ones we use every day) are great at smooth mountains, they start to struggle when the terrain gets extremely jagged and complex. The quantum chef, however, holds its own and even starts to show its strength when the "terrain" becomes a nightmare.

The Bottom Line

The researchers proved that by adding a "memory" (the Archive) and a "better way to filter results" (Substitution), quantum computers are becoming much better at solving these complex, multi-goal problems.

While they aren't quite beating the best classical computers on simple tasks yet, they are showing a "superpower" potential: as the problems get more chaotic and complex, the quantum approach might eventually become the master chef of the digital age.

Technical Summary: Improving Quantum Multi-Objective Optimization with Archiving and Substitution

1. Problem Statement

Multi-objective optimization (MOO) is critical in industrial applications where decision-makers must navigate trade-offs between conflicting objectives (e.g., cost vs. performance). The goal is to find the Pareto-optimal set—solutions where no objective can be improved without degrading another.

While Variational Quantum Multi-Objective Optimization (QMOO) has been proposed to leverage quantum advantages for these problems, existing versions lack the robust mechanisms found in classical solvers to maintain solution diversity and ensure convergence. Furthermore, there has been a lack of standardized, scalable benchmarking frameworks to compare QMOO against state-of-the-art classical algorithms like NSGA-II and NSGA-III.

2. Methodology

The authors propose an enhanced version of the QMOO algorithm and a new benchmarking framework.

A. Algorithmic Improvements:

Pareto Archiving: Inspired by classical MOO, the authors integrate an unbounded archive that retains previously discovered non-dominated solutions. This ensures that the algorithm progressively builds a better approximation of the Pareto front across iterations.
Dominated Solution Substitution: To improve early-stage convergence, the authors introduce a mechanism that draws additional candidate solutions from the quantum measurement outcomes. Instead of discarding dominated solutions immediately, the algorithm sequentially samples bitstrings until a target number of non-dominated candidates is reached, effectively expanding the evaluated solution set.

B. Benchmarking Framework (RMNK Landscapes):

The authors utilize RMNK-landscapes, a generalization of the NK-model, to create tunable, multi-modal testbeds. These landscapes allow for controlled complexity by adjusting:
- $N$ : Number of variables.
- $M$ : Number of objectives.
- $K$ : Epistatic interactions (degree of ruggedness/complexity).
- $\rho$ : Correlation between objectives.
Classical-to-Quantum Mapping: They devise a method to map these landscapes to quantum cost Hamiltonians by using a Walsh-Hadamard transform to convert local lookup tables into diagonal Pauli-Z operators.

3. Key Contributions

Enhanced QMOO Algorithm: The introduction of archiving and substitution mechanisms that optimize the trade-off between quantum circuit iterations and classical function evaluations.
Systematic Mapping: A generic mathematical framework for translating any RMNK-landscape into a cost Hamiltonian implementable on quantum devices.
Hyperparameter Tuning: A numerical study demonstrating how tuning measurement shots ( $N_{shots}$ ) and the number of selected solutions ( $N_{most\_prob}$ ) can tailor the algorithm to specific resource constraints.
Standardized Benchmarking: Establishing RMNK-landscapes as a unifying testbed for comparing quantum and classical multi-objective solvers.

4. Results

Convergence Gains: Adding a Pareto archive significantly improves the hypervolume (HV) convergence compared to the original QMOO. Substitution provides a boost in early-stage convergence.
Resource Flexibility: The substitution mechanism allows users to trade classical computational cost for fewer quantum iterations, which is vital for current NISQ-era hardware.
Comparative Performance:
- In small or simple instances, QMOO performs comparably to classical NSGA-II and NSGA-III.
- Crucially, as the landscape complexity ( $K$ ) increases, the performance of classical solvers tends to degrade more sharply than QMOO. In high-complexity scenarios, QMOO demonstrates competitive or even superior performance, suggesting it may hold a potential advantage for "harder" problems.

5. Significance

This work represents a significant step toward the practical utility of quantum algorithms in combinatorial optimization. By bridging the gap between quantum variational methods and established classical MOO techniques (like archiving), the authors have created a more robust and tunable algorithm. The ability of QMOO to remain resilient in highly rugged landscapes ( $high\ K$ ) provides a theoretical and empirical pathway for quantum advantage in complex, real-world industrial optimization tasks.