Quantum Approximate Multi-Objective Optimization in Routing Problems

arXiv:2610.00168 · cs.ET, quant-ph · Submitted 2026-09-15 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "Quantum Approximate Multi-Objective Optimization in Routing Problems".

Mira: Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk.

Kai: First, who's behind it and why it matters.

Title and authors: Kai: So we're starting with how they framed this whole thing in their paper, "Quantum Approximate Multi-Objective Optimization in Routing Problems," and who the folks behind it are.

Mira: The authors include Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, Jose Carlos Libois Neto, Fernando Augusto Caletti de Barros, and Eduardo Inacio Duzzioni. They're clearly a team with a strong background spanning quantum computing and logistics applications.

Lev: I'm interested in their specific research roles; it helps me gauge what kind of theoretical depth we can expect from this paper when considering how to run these kinds of algorithms on physical systems.

Kai: Willwock Lussi, for instance, is the primary author and seems to be driving the main direction of this work on the quantum MOO aspect.

Mira: Fumaco and Reballo seem heavily involved in formulating the problem reductions, which is important because they are taking TSP and VRP and converting them into those QUBO problems that QAOA needs to run on.

Lev: And I think Caletti de Barros' involvement points toward the complexity of mapping these classical optimization problems onto the quantum structure, which is usually where things get tricky for error correction concerns.

Kai: It seems like a solid mix: problem formulation, quantum algorithm application, and testing on actual hardware results.

Mira: The title itself sets the stage by immediately linking multi-objective optimization with routing problems in a quantum context, which is exactly what we wanted to see explored.

Lev: And given their background in error correction research, I'm always looking for the assumptions they make about noise and how those constraints affect the viability of this parameter transfer strategy when scaled up.

Kai: Right, so we know who's doing what and why it matters for our hardware experiments.

The paper's summary: Kai: Now, let’s talk about what the paper actually says in its summary regarding their approach to solving these multi-objective routing problems.

Mira: Essentially, the authors are tackling the problem of finding a set of solutions that represent optimal trade-offs between objectives like travel distance and delivery time, which is what Pareto optimality means in this context.

Lev: They are investigating two specific variants: the classical Traveling Salesman Problem, TSP, and a more complex custom Vehicle Routing Problem variant that accounts for multiple vehicles.

Kai: The main distinction they highlight is that VRP involves multiple vehicles, meaning the definition of the "best possible route" changes depending on how you allocate those vehicles across locations.

Mira: And to solve these routing problems quantumly, they reduce them to MAX-CUT instances because that's what QAOA is designed to operate on.

Lev: That reduction step is critical because it dictates the structure of the cost Hamiltonian they are dealing with, which directly impacts how we model things for error correction purposes.

Kai: They then define their QAOA framework using a cost Hamiltonian derived from the QUBO matrix Q, where they map the objective function into an Ising Hamiltonian through a specific transformation involving x i = one - z i two/two.

Mira: The algorithm itself alternates between applying the cost Hamiltonian, which encodes the optimization problem, and a mixer Hamiltonian that explores different search spaces using parameters beta and gamma.

Lev: And they start this process from a uniform superposition state, +, which is what we usually expect for a standard QAOA setup before the cost Hamiltonian starts pulling the state toward an answer.

Kai: So they set up the cost Hamiltonian as H C = - X i<j J ij sigma i z sigma j z - X i h i sigma i z, where J ij and h i come from the QUBO matrix.

Mira: This setup allows them to optimize the variational parameters beta and gamma to minimize the expectation value of this cost Hamiltonian, which is what we want for finding a solution.

Lev: I wonder how stable those parameters are when we introduce noise, because if the optimization isn't robust against noise, the whole thing falls apart quickly on real hardware.

The paper's improvements: Kai: Moving on to what they actually propose as an improvement in their methodology for this paper, which is the parameter transfer strategy.

Mira: The key innovation is reusing QAOA parameters across multiple scalarizations by optimizing them offline on representative small instances and then fixing those parameters before running the algorithm again for different objective weights.

Lev: That sounds like a smart way to reduce the computational overhead of re-optimizing those parameters every time we change the trade-off vector c, which is what they are doing with the Weighted Sum Method.

Kai: Exactly; instead of optimizing them from scratch for every scalarized instance, they only need to change the cost Hamiltonian H(c) = sum i c i H i and execute the circuit using those fixed parameters.

Mira: The paper demonstrated this strategy on multi-objective MAX-CUT instances using Matrix Product State simulations and experiments on IBM quantum hardware, showing it can produce Pareto fronts with better coverage than their adapted classical epsilon-constraint method.

Lev: So for real hardware implementation, the crucial part is whether those pre-optimized parameters trained on a training graph truly generalize to the more complex Hamiltonians of the actual VRP instances.

Kai: The paper did test this on TSP and VRP problems using thirty-seven and forty-three qubits respectively, showing that this transfer enabled them to reach high hypervolume values.

Mira: So, in simpler terms, they are saying that this strategy helps you explore the objective space much more efficiently by reusing quantum resources for different trade-offs.

Lev: The authors themselves noted a limitation: their study focused on MAX-CUT graphs matching the connectivity of the target quantum device, which means whether this approach remains effective for realistic combinatorial optimization problems with more complex Hamiltonians is still an open question.

Conclusion: Kai: To wrap up what we’ve discussed about this paper, the main implication is that parameter transfer offers a way to tackle the computational bottleneck of MOO in routing problems.

Mira: They found that this method helps generate a set of Pareto-optimal solutions more efficiently, achieving better coverage in the objective space than their classical adapted method under specific conditions.

Lev: For running this on real hardware, my main concern remains how well these pre-trained parameters hold up when we move to those larger VRP instances with more intricate constraints.

Kai: Ultimately, the paper shows that for the TSP instances, parameter transfer reached competitive results faster and produced higher hypervolume values compared to the adapted classical epsilon-constraint method.

Mira: This suggests that leveraging quantum resources through parameter transfer could be a valuable tool for exploring complex logistics trade-offs without needing massive amounts of classical optimization time upfront.

Lev: I think the practical impact hinges on whether we can build error-corrected hardware capable of maintaining those quantum states long enough to realize this speed advantage over classical methods for hard VRPs.

Kai: So, in summary, the paper "Quantum Approximate Multi-Objective Optimization in Routing Problems" shows that parameter transfer is a viable technique for speeding up the exploration of trade-off solutions in these problems.

Mira: It’s a neat application of QAOA to solve a very practical logistics challenge by making it more efficient computationally.

Lev: And we just need to see how scalable and error-free this approach becomes before it moves out of the simulation realm and into industrial reality.

Eldorado Research Institute · Federal University of Santa Catarina

cs.ET, quant-ph

Submitted: 2026-09-15

Updated: 2026-09-15

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 77/100

The gist: Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk.

Key concepts

QUBO Reduction
This process converts complex routing problems like TSP and VRP into a format called Quadratic Unconstrained Binary Optimization (QUBO). This transformation is necessary because the QAOA algorithm is specifically designed to work on MAX-CUT instances, allowing the quantum computer to solve the routing challenge.
QAOA Framework
QAOA is a hybrid quantum-classical algorithm that uses two Hamiltonians: a cost Hamiltonian representing the problem's objective and a mixer Hamiltonian exploring possibilities. The algorithm iteratively adjusts parameters to find solutions that minimize the cost while exploring different parts of the solution space.
Parameter Transfer Strategy
This innovation involves optimizing QAOA parameters (β, γ) once on a simpler training graph. These fixed parameters are then reused for many different objective trade-offs in real problems. This saves significant classical optimization time because the quantum circuit only needs to be re-run with new cost functions.
Pareto Front Approximation
Since the algorithm optimizes multiple weighted versions of the problem, it generates a set of candidate solutions. By comparing these solutions using dominance relations, the paper approximates the Pareto front—the set of optimal trade-offs between conflicting goals like distance and time.

Terminology

Summary

Multi-objective optimization (MOO) problems are common in logistics, where routing decisions must balance conflicting objectives such as travel distance, delivery time, and operational risk. The study investigates whether a Quantum Approximate Optimization Algorithm (QAOA) parameter transfer strategy remains effective for practical multi-objective routing problems beyond proof-of-concept MAX-CUT instances.

The gist: Parameter transfer remains effective in this more realistic setting, frequently producing Pareto fronts with a better coverage of the objective space than the adapted classical ϵ-constraint method, while often reaching competitive solutions earlier under the adopted computational assumptions.

Problem Formulation and Reduction

The paper formulates the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) problems, which are then reduced to equivalent MAX-CUT instances. This reduction is a necessary step because the QAOA framework operates on MAX-CUT instances. The TSP formulation involves introducing binary decision variables where each city is visited at a specific position in the tour, and the objective is to minimize total travel cost subject to constraints ensuring each position holds exactly one city and each city appears exactly once.

The VRP formulation extends this by incorporating multiple vehicles, using auxiliary nodes to represent route termination. The QUBO formulation for VRP involves decision variables that specify which vehicle visits which node at which position, with constraints enforcing that every customer is visited exactly once by exactly one vehicle and that every vehicle starts at the depot. These formulations are then transformed into weighted MAX-CUT problems by transforming the QUBO matrix Q into its symmetric representation and normalizing it.

Quantum Approximate Optimization Algorithm (QAOA) Framework

The QAOA framework is a hybrid quantum-classical variational algorithm designed for combinatorial optimization, utilizing two complementary Hamiltonians: a cost Hamiltonian (HC), which encodes the optimization problem, and a mixer Hamiltonian (HM), which explores the search space. The algorithm alternates the application of these two Hamiltonians for a fixed number of layers, known as the circuit depth p. The objective is to determine the parameter values β and γ that minimize the expectation value of the cost Hamiltonian, specifically minimizing min β,γ ⟨ψ(β, γ) HC ψ(β, γ)⟩.

The QUBO objective is mapped to an Ising Hamiltonian through a transformation where xi = 1 − zi2/2. The cost Hamiltonian (HC) is then defined as HC = − Xi<j Jiⱼσzi σzⱼ − Xi hiσzi, where Jij and hi are coefficients derived from the QUBO matrix. The algorithm starts from a uniform superposition state, +⟩ = 1/√2n Σ x∈0,1n x⟩, which corresponds to the ground state of the mixer Hamiltonian (HM).

Multi-Objective Optimization Strategy

The multi-objective routing problem is solved by repeatedly applying Weighted Sum Method (WSM) to generate scalarized optimization problems. For each iteration, a weight vector c = (c1,..., cm) is sampled from the unit simplex to define the scalarized objective fc(x) = Σ i ci fi(x). This scalarized objective is converted into the corresponding cost Hamiltonian H(c) = Σ i ci Hi. QAOA then optimizes its variational parameters using this specific cost Hamiltonian, producing a candidate solution for that trade-off.

To approximate the Pareto front, this procedure is repeated for multiple weight vectors. The paper notes that instead of returning only the optimal solution of each scalarized problem (which would only recover supported Pareto solutions), QAOA prepares a quantum state whose measurement produces a probability distribution over multiple candidate solutions, including high-quality solutions that are not optimal for the weighted objective. The dominance relation is then applied to identify the non-dominated solutions, forming an approximation of the Pareto front.

Parameter Transfer Mechanism

The core innovation is the parameter transfer strategy proposed by [14], which aims to reduce repeated classical optimization by reusing QAOA parameters across multiple scalarizations. The variational parameters (β, γ) are first optimized offline on a representative MAX-CUT training graph that shares the same topology as the target graph and has edge weights independently sampled according to N(0, 1/3). These trained parameters are then fixed. For each randomly sampled weight vector c, only the cost Hamiltonian changes to H(c) = Σ i ci Hi, and the QAOA circuit is executed using these transferred parameters without further classical optimization.

Experimental Validation and Findings

Experiments were conducted on real IBM quantum hardware for TSP-6 (37 qubits) and VRP-5-1 (43 qubits), transferring parameters from smaller training graphs (e.g., 17 or 27 qubits). The results show that parameter transfer consistently enables the algorithm to reach the maximum hypervolume for the considered instances, often producing higher hypervolume values than the adapted classical ϵ-constraint method while requiring less computational time for TSP instances.

Improvements for AI systems

Here are the specific improvements to AI systems derived from this scientific paper, categorized by capability:

) 1. Enhanced Multi-Objective Logistics Planning System (TSP & VRP Solver):

The improved system will be capable of generating a set of Pareto-optimal routes for complex logistics problems (like delivery scheduling or vehicle routing) simultaneously optimizing conflicting objectives such as travel distance, delivery time, and operational risk.

  1. Efficient Trade-off Exploration via Parameter Transfer:

Unlike current methods that require re-optimizing the Quantum Approximate Optimization Algorithm (QAOA) parameters from scratch for every different trade-off scenario (scalarization), the improved system will leverage a parameter transfer strategy. This allows it to quickly generate multiple high-quality Pareto fronts by reusing pre-optimized quantum parameters trained on representative, smaller problem instances.

  1. Robustness to Problem Complexity:

The system's performance will be more stable when solving the Traveling Salesman Problem (TSP) compared to the Vehicle Routing Problem (VRP). This suggests that for highly constrained logistics scenarios (like VRP), the system can better adapt its optimization strategy, potentially by utilizing deeper QAOA circuits or employing tailored parameter transfer techniques that account for increased Hamiltonian complexity.

  1. Faster Pareto Front Generation:

By avoiding the costly classical optimization of QAOA parameters for every scalarized problem, the improved system will generate solutions corresponding to different trade-offs significantly faster than traditional methods, allowing decision-makers to explore a wider range of optimal logistics options within a fixed computational budget (e.g., 2,500 seconds).

  1. Hardware-Aware Optimization:

The system can be benchmarked and deployed considering the limitations of near-term quantum hardware (like IBM Kingston). The improved framework provides insights into the necessary QAOA circuit depth and required coherence times for specific problem sizes, enabling researchers to tailor problem constraints to match current quantum hardware capabilities or plan future hardware development.

  1. Comparative Performance Benchmarking:

The system can be used as a benchmark against classical methods (like the adapted ϵ-constraint method) across various instance sizes (TSP-4 to TSP-6, VRP instances). The paper demonstrates that the parameter transfer strategy frequently reaches higher hypervolume (better solution coverage) while often achieving this in less time, providing a quantitative metric for when quantum approaches outperform classical trade-off exploration.

Related papers