Source-linked AI summary
Quantum Approximate Multi-Objective Optimization in Routing Problems
Eduardo Willwock Lussi, Alisson dos Passos Fumaco, Marcos Vinicius Reballo, José Carlos Libois Neto, Fernando Augusto Caletti de Barros, Eduardo Inacio Duzzioni
TL;DR
Routing decisions must balance conflicting objectives, and QAOA parameter transfer had mainly been demonstrated on hardware-tailored MAX-CUT problems. This paper formulates TSP and VRP as QUBO and MAX-CUT problems and evaluates parameter transfer in simulations and on IBM hardware. It remains effective overall, with consistently stronger performance for TSP than for the more constrained VRP.
Problem
Parameter transfer for QAOA had been demonstrated on hardware-tailored MAX-CUT instances, leaving its applicability to realistic, more constrained routing problems uncertain.
Source: §6 · p. 19Method
The study formulates TSP and VRP as QUBO models, reduces them to MAX-CUT, and evaluates transferred QAOA parameters through simulations and IBM hardware experiments.
Source: §4.3 · p. 11, §6 · p. 19Results
Transferred parameters consistently reached the highest hypervolume for TSP, while VRP results were more variable and some configurations missed the best hypervolume.
Source: §5 · pp. 16, 18Takeaways & Limitations
Parameter transfer can extend beyond MAX-CUT to multi-objective routing, but its effectiveness varies with problem structure and is less consistent for VRP.
Source: §5 · pp. 16, 18, §6 · p. 19Further experimental benchmarking across a broader range of problems, especially highly constrained formulations and single-objective settings, remains necessary.
Source: §6 · p. 19
Abstract
from arXiv · showhide
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. A recently proposed Quantum Approximate Optimization Algorithm (QAOA) parameter-transfer strategy solves multi-objective MAX-CUT problems by reusing parameters trained on smaller instances, avoiding costly reoptimization for each scalarized problem. However, its effectiveness has only been demonstrated on proof-of-concept instances tailored to quantum hardware connectivity. In this work, we evaluate the applicability of this strategy to realistic routing problems. We formulate the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) as Quadratic Unconstrained Binary Optimization (QUBO) models, reduce them to MAX-CUT, and assess the parameter-transfer framework under conditions matching the original study. Validation is performed through classical simulations and experiments on IBM quantum hardware. The resulting Pareto fronts are compared with those obtained using an adapted classical {\epsilon}-constraint method, using hypervolume as the primary quality metric. Results indicate that parameter transfer remains effective, frequently achieving higher hypervolume and often finding competitive solutions earlier. However, performance depends on problem structure. The approach is consistently effective for TSP instances but less stable for the more constrained VRP, suggesting that QAOA parameter transferability decreases as the optimization landscape becomes more complex. These results provide the first comprehensive evaluation of QAOA parameter transfer on realistic multi-objective routing problems and demonstrate its potential beyond proof-of-concept MAX-CUT benchmarks.
1 Introduction
Logistics routing requires trade-offs among objectives such as distance, time, and risk, while parameter transfer for quantum multi-objective optimization had previously been tested mainly on hardware-tailored MAX-CUT instances. This work evaluates the strategy on TSP and VRP, reporting strong but problem-dependent results against an adapted classical method.
1 Introduction
- Multi-objective optimization seeks Pareto-optimal solutions, where improving one objective requires degrading at least one other.Classical weighted-sum methods can be computationally efficient but miss non-supported solutions in non-convex Pareto-front regions.Source: §1 · p. 2
- Routing problems such as TSP and VRP involve competing objectives, so a best route may represent a trade-off among distance, time, risk, or cost.The VRP differs from the TSP by allowing multiple vehicles.Source: §1 · p. 2
- Earlier quantum multi-objective approaches reoptimized QAOA parameters for each scalarized problem, while parameter transfer reuses parameters trained on smaller instances.The earlier demonstration focused on MAX-CUT graphs matching target-device connectivity, leaving applicability to more complex routing Hamiltonians open.Source: §1 · pp. 2–3
- The study tests whether parameter transfer can generate diverse routing solutions with trade-offs among distance, delivery time, and route-related risk.Validation uses noise-free simulations and experiments on IBM quantum hardware.Source: §1 · p. 3
- Parameter transfer remains effective beyond MAX-CUT: it often yields better Pareto-front coverage and reaches competitive solutions earlier, with more stable results for TSP than VRP.The authors relate VRP variability to its additional constraints and interactions, which make transferable parameter regions less consistent.Source: §1 · p. 3
2 Multi-Objective Optimization
Multi-objective optimization seeks a set of Pareto-optimal trade-offs when objectives conflict. The Pareto front represents these solutions in objective space, and hypervolume measures the region it dominates relative to a reference point.
2 Multi-Objective Optimization
- Conflicting objectives generally prevent one solution from maximizing every objective, so the goal is a set of non-dominated trade-offs.A solution is non-dominated when no other feasible solution dominates it.Source: §2 · p. 4
- The Pareto-optimal set contains all Pareto-optimal decision-space solutions, while its objective-space image is the Pareto front.Each front point represents a different trade-off among objectives.Source: §2 · p. 4
- Hypervolume measures the region dominated by a Pareto-front approximation relative to a reference point; larger values usually indicate better convergence and spread.Figure 1 depicts the dominated region as shading.Source: §2 · p. 4, Figure 1 · p. 5
- Weighted-sum scalarization can obtain supported Pareto-optimal solutions on the convex hull, but not non-supported solutions in non-convex regions.The figure marks a Pareto-optimal interior point that is non-supported.Source: §2 · p. 4, Figure 1 · p. 5
3 QUBO Formulations
The section formulates TSP and VRP as QUBO models, then reduces them to weighted MAX-CUT instances for the QAOA parameter-transfer framework. Penalty terms encode route-feasibility constraints within the unconstrained binary objectives.
3 QUBO Formulations
- QUBO represents a quadratic objective over binary variables, with the matrix encoding both the objective and constraints through penalty terms.The paper uses QUBO formulations for TSP and VRP before transforming them into MAX-CUT instances for QAOA.Source: §3 · p. 5
3.1 QUBO formulation of TSP
- The TSP model uses binary x_i,t variables to mark a city at each tour position and minimizes travel cost between consecutive cities, including the return to the first city.The modulo position index closes the route into a Hamiltonian cycle.Source: §3.1 · pp. 5–6
- TSP feasibility requires exactly one city at each position and each city exactly once; quadratic penalties with sufficiently large coefficients encode these constraints in the QUBO.Penalty coefficients are scaled according to the instance's maximum edge cost.Source: §3.1 · p. 6
3.2 QUBO formulation of VRP
- The VRP extends the time-indexed TSP model with a vehicle index, depot, and auxiliary route-ending node; its travel objective sums transition costs across vehicles.The auxiliary node permits routes to end before the maximum route length, and vehicles are not required to return to the depot.Source: §3.2 · p. 6
- VRP penalties enforce one node per vehicle and route position, one visit per customer, depot-start rules, contiguous route endings, and at least one customer per vehicle.The six penalty coefficients are scaled against the maximum edge cost to balance objective and constraint terms.Source: §3.2 · p. 7
3.3 Reduction from QUBO to MAX-CUT
- The QUBO-to-MAX-CUT reduction symmetrizes the QUBO matrix without changing its objective, then normalizes coefficients to [-1, 1] for comparable, better-conditioned instances.The reduction's graph has one vertex per binary variable plus an additional vertex.Source: §3.3 · p. 8
- The reduction creates a fully connected weighted graph whose MAX-CUT solution is equivalent to optimizing the original QUBO, enabling the QAOA method to apply.Pairwise variable interactions become graph edges in the weighted adjacency representation.Source: §3.3 · pp. 8–9
4 Quantum Approximate Multi-Objective Optimization
The framework maps multi-objective routing QUBOs to MAX-CUT and approximates the Pareto front by solving scalarized problems with QAOA. It reuses parameters trained on a representative instance across those problems.
4 Quantum Approximate Multi-Objective Optimization
- The routing framework reduces multi-objective QUBOs to MAX-CUT and samples convex combinations of objectives to approximate the Pareto front.The scalarized MAX-CUT problems are solved using the framework proposed by.Source: §4 · p. 9
4.1 Quantum Approximate Opimization Algorithm
- QAOA alternates cost and mixer Hamiltonians for p layers, then uses classical optimization and quantum measurements to produce candidate solutions.Lower-energy states are sampled with higher probability; increasing depth can improve expressiveness while increasing circuit complexity and parameter count.Source: §4.1 · p. 9
4.2 Multi-objective optimization with QAOA
- QAOA measurements can yield multiple candidates per scalarization, including high-quality non-supported Pareto-optimal solutions that exact weighted-sum optimization may miss.Sampling more weight vectors explores additional trade-offs, while more circuit shots increase the likelihood of sampling non-supported solutions.Source: §4.2 · p. 11
4.3 Parameter transfer
- Parameters trained offline on a representative MAX-CUT instance are fixed and reused across scalarized targets, eliminating repeated classical optimization.The training graph has the same topology as the target graph, and the framework is proposed by.Source: §4.3 · pp. 11–12
5 Results and Discussion
Across the tested routing problems, transferred QAOA parameters performed consistently for TSP but less consistently for the more constrained VRP. IBM hardware runs produced no feasible solutions, with circuit execution times exceeding the processor’s coherence window.
5 Results and Discussion
- Experiments covered TSP instances with 4–6 customers and VRP instances with 3–5 customers and 1–2 vehicles, using three seeds per size and objectives for distance, time, and risk.The largest instances feasible with the available computational resources were selected; the comparison used a 2,500-second budget, equivalent to 25 million QAOA measurement shots.Source: §5 · pp. 12, 16
- For TSP-6, p = 1 and p = 4 reached maximum hypervolume, with p = 1 first in all three seeds; for VRP-5-1, only p = 5 and p = 6 reached it and produced feasible solutions.All tested depths produced feasible TSP-6 solutions, whereas the shallower VRP-5-1 circuits violated constraints.Source: §5 · p. 13, Figure 2 · p. 14
- The VRP converged more slowly and varied more across QAOA depths, which the authors attribute to its additional variables and feasibility constraints creating a more structured, constrained optimization landscape.They interpret the TSP Hamiltonian as having parameter regions that generalize across graph sizes, while transfer is less consistent for the more complex VRP landscape.Source: §5 · pp. 15, 18
- For TSP-4, every tested depth and transfer configuration attained maximum hypervolume; as instance size increased, fewer depths did so and the time to reach it increased.Training graphs closer in size tended to perform better, but VRP results also included cases where smaller training graphs outperformed closer-sized ones.Source: §5 · pp. 15–16
- The approximated Pareto fronts contained 1–16 non-dominated solutions, and the reported TSP-6 and VRP-5-1 fronts showed trade-offs among distance, travel time, and risk.Across three seeds, TSP-6 yielded 16, 4, and 5 non-dominated solutions; VRP-5-1 yielded 5, 4, and 4.Source: §5 · pp. 13, 16
- For TSP, transferred QAOA parameters consistently reached the highest hypervolume and often did so faster than the adapted ϵ-constraint method; VRP performance was more variable and sometimes failed to attain the best hypervolume.For TSP-6, QAOA reached the reference hypervolume several hundred seconds before the classical method whenever both succeeded; for VRP-4-1, the adapted method consistently achieved higher hypervolume within the same budget.Source: §5 · p. 16, Table 4 · p. 17, Figure 4 · p. 17
5.1 Hardware Validation
- On IBM hardware, neither the TSP nor VRP experiment produced a feasible solution; the authors attribute this to circuit execution times exceeding typical qubit coherence times.The reported execution times were 599 µs for TSP and 1,550 µs for VRP, versus coherence times around 200 µs; the authors identify improved coherence and gate fidelities or more efficient compilation and error mitigation as requirements for deployment.Source: §5.1 · p. 18
6 Conclusion and Future Works
The paper benchmarks QAOA parameter transfer on TSP and VRP against the idealized MAX-CUT setting, using the original study’s experimental conditions and IBM hardware. Simulations show useful but problem-dependent performance, while the conclusion identifies hardware feasibility and broader evaluation as open challenges.
6 Conclusion and Future Works
- The evaluation extended the parameter-transfer strategy proposed by from MAX-CUT to TSP and VRP, testing under the original study’s conditions and validating on IBM hardware.The routing problems were formulated as QUBOs and reduced to MAX-CUT.Source: §6 · pp. 18–19
- In simulations, parameter transfer often achieved higher hypervolume with less computational time than the adapted ϵ-constraint method, but IBM hardware produced no feasible TSP or VRP solutions.The hardware circuits’ transpiled depths were 6,328 for TSP and 16,357 for VRP, far exceeding device coherence times.Source: §6 · p. 19
- Transfer performance varied with problem size, training-instance size, and sometimes random seed, and was considerably more stable for TSP than VRP.The authors suggest that more complex, highly constrained Hamiltonians have less concentrated optimal QAOA parameters, making transfer more challenging.Source: §6 · p. 19
- Broader experimental benchmarks across optimization problems, from simple to highly constrained and especially in single-objective settings, remain a future research need.The authors note that extensive experimental evaluation of QAOA parameter transfer is still required.Source: §6 · p. 19