Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2504.19934 · IEEE Transactions on Intelligent Transportation Systems

Warm-Starting QAOA With XY Mixers: A Novel Approach for Traveling Salesman Problem

Rafael Simões do Carmo, Marcos Cleison Silva Santana, F. F. Fanchini, Victor Hugo C. de Albuquerque, João Paulo Papa

Published Jan 1, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.

DOI
10.1109/tits.2026.3744587

Related papers

A Warm-start QAOA based approach using a swap-based mixer for the TSP: theoretical considerations,implementation and experiments

Eric Bourreau, Gérard Fleury, Philippe Lacomme

This paper investigates quantum heuristics based on Mixer Hamiltonians, which allow the search to be restricted to a specific subspace and enable warm-start strategies for solving the Traveling Salesman Problem (TSP). Approaches involving Mixer Hamiltonians can be integrated into the Quantum Approximate Optimization Algorithm (QAOA), where the Mixer acts as a mapping function that transforms qubit strings into feasible solution sets. We first introduce a swap-based mixer tailored to the TSP, which ensures that only qubit strings representing valid TSP solutions are explored during the QAOA process. Second, we propose a warm-start technique that initializes QAOA with a solution generated by any classical heuristic, thereby promoting faster convergence. These two contributions are combined into a Warm-Start QAOA framework with a Swap-Based Mixer, leveraging both structural and initialization advantages. Experimental results on a custom TSP instance involving five customers demonstrate the effectiveness of this approach, providing, for the first time, a viable integration of warm-start and swap-based mixers for the TSP within a quantum optimization framework.

arXiv:2505.01214•May 2, 2025•1 citation

Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers

David Bucher, Maximilian Janetschek, Michael Poppel +3 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-$k$-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.

quant-pharXiv:2604.02083•New Journal of Physics•Apr 3, 2026•0 citations

Improving Feasibility in Quantum Approximate Optimization Algorithm for Vehicle Routing via Constraint-Aware Initialization and Hybrid XY-X Mixing

Yuan-Zheng Lei, Yaobang Gong, Xianfeng Terry Yang +1 more

The Quantum Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-$X$ mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-$X$ mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.

cs.ETCross-listedarXiv:2604.07218•Transportation Research Part C Emerging Technologies•Apr 9, 2026•0 citations

Warm-start adaptive-bias quantum approximate optimization algorithm

Yunlong Yu, Xiang‐Bin Wang, Nic Shannon +1 more

In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with $40$ to $180$ qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to $1000$ qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the $1000$-qubit case even in level 1 can only be matched by the GW algorithm after about $10^{5.5}$ random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.

arXiv:2503.20048•Physical Review A•Jul 14, 2025•4 citations

Comparative Analysis of Quantum Approximate Optimization Algorithms for Solving the Travelling Salesperson Problem

Siddharth Chander

The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.

IEEE International Conference on Quantum Control, Computing and Learning (qCCL)•Jun 25, 2025•1 citation

Warm-Starting PCE for Traveling Salesman Problem

Rafael Simões do Carmo, Reis, Renato Gomes dos, Silva, Samuel Fernando F +2 more

Variational quantum algorithms are promising for combinatorial optimization, but their scalability is often limited by qubit-intensive encoding schemes. To overcome this bottleneck, Pauli Correlation Encoding (PCE) has emerged as one of the most promising algorithms in this scenario. The method offers not only a polynomial reduction in qubit count and a suppression of barren plateaus but also demonstrates competitive performance with state-of-the-art methods on Maxcut. In this work, we propose a warm-start PCE, an extension that incorporates a classical bias from the Goemans-Williamson (GW) randomized rounding algorithm into the loss function to guide the optimization toward improved approximation ratios. We evaluated this method on the Traveling Salesman Problem (TSP) using a QUBO-to-MaxCut transformation for up to $5$ layers. Our results show that Warm-PCE consistently outperforms standard PCE, achieving the optimum solution in $28\text{--}64\%$ of instances, versus $4\text{--}26\%$ for PCE, and attaining higher mean approximation ratios that improve with circuit depth. These findings highlight the practical value of this warm-start strategy for enhancing PCE-based solvers on near-term hardware.

arXiv:2509.14414•Sep 17, 2025•0 citations
Quantum optimization algorithms, such as the Quantum Approximate Optimization Algorithm, are emerging as promising heuristics for solving complex combinatorial problems. To improve performance, several extensions to the standard QAOA framework have been proposed in recent years. Two notable directions include: warm-starting techniques, which incorporate classical approximate solutions to guide the quantum evolution, and custom mixer Hamiltonians, such as XY mixers, which constrain the search to feasible subspaces aligned with the structure of the problem. In this work, we propose an approach that integrates these two strategies: a warm-start initialization with an XY mixer ansatz, enabling constraint-preserving quantum evolution biased toward high-quality classical solutions. The method begins by reformulating the combinatorial problem as a MaxCut instance, solved approximately using the Goemans-Williamson algorithm. The resulting binary solution is relaxed and used to construct a biased superposition over valid one-hot quantum states, maintaining compatibility with the XY mixer's constraints. We evaluate the approach on 5-city instances of the Traveling Salesperson Problem, a canonical optimization problem frequently encountered as a subroutine in real-world Vehicle Routing Problems. Our method is benchmarked against both the standard XY-mixer QAOA and a warm-start-only variant based on MaxCut relaxation. Results show that the proposed combination consistently outperforms both baselines in terms of the percentage and rank of optimal solutions, demonstrating the effectiveness of combining structured initializations with constraint-aware quantum evolution for optimization problems.
This paper investigates quantum heuristics based on Mixer Hamiltonians, which allow the search to be restricted to a specific subspace and enable warm-start strategies for solving the Traveling Salesman Problem (TSP). Approaches involving Mixer Hamiltonians can be integrated into the Quantum Approximate Optimization Algorithm (QAOA), where the Mixer acts as a mapping function that transforms qubit strings into feasible solution sets. We first introduce a swap-based mixer tailored to the TSP, which ensures that only qubit strings representing valid TSP solutions are explored during the QAOA process. Second, we propose a warm-start technique that initializes QAOA with a solution generated by any classical heuristic, thereby promoting faster convergence. These two contributions are combined into a Warm-Start QAOA framework with a Swap-Based Mixer, leveraging both structural and initialization advantages. Experimental results on a custom TSP instance involving five customers demonstrate the effectiveness of this approach, providing, for the first time, a viable integration of warm-start and swap-based mixers for the TSP within a quantum optimization framework.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading hybrid heuristic for combinatorial optimization, but efficiently handling hard constraints remains a significant challenge. XY-mixers successfully confine quantum state evolution to a feasible subspace, such as the Hamming-weight-1 sector for one-hot constraints. On the contrary, warm-starting biases the search toward promising regions based on preliminary solutions. Combining these two techniques requires maintaining the essential alignment between the initial state and the mixer Hamiltonian to preserve convergence guarantees. Previous work demonstrated warm-starting with XY-mixers via a biased initial state, but relying only on standard mixer Hamiltonians. Consequently, the initial state is no longer a ground state of the mixer. In this work, we overcome these limitations by formulating a warm-started XY-mixer Hamiltonian for one-hot constraints and proving its ground-state properties. Furthermore, we provide a shallow circuit implementation suitable for NISQ implementations. We embed the warm-starting into a classical heuristic that iteratively updates the bias based on previous samples, called Iterative Warm-Starting (IWS). Extensive numerical simulations on Max-kkk-Cut and Traveling Salesperson Problem instances demonstrate that IWS-QAOA significantly accelerates the solution-finding process, increasing the probability of sampling optimal solutions by orders of magnitude compared to standard XY-QAOA. Finally, we validate our approach on the ibm_boston QPU using hardware-tailored 144-qubit problem instances. By coupling IWS-QAOA with a greedy steepest-descent post-processing strategy to repair infeasible measurements caused by hardware noise, we successfully identify optimal solutions on actual quantum devices.
The Quantum Approximate Optimization Algorithm (QAOA) is a leading framework for quantum combinatorial optimization. The Vehicle Routing Problem (VRP), a core problem in logistics and transportation, is a natural application target, but it poses a major feasibility challenge for standard QAOA because feasible solutions occupy only a tiny fraction of the search space, and the conventional Pauli-XXX mixer can disrupt partial solution structures that satisfy key local constraints. To address this issue, we propose a constraint-aware QAOA framework with two complementary components. First, we design a lightweight initialization strategy that encodes a selected subset of simple yet informative local one-hot constraints into the initial state, thereby reducing the initial superposition space and increasing the probability mass on states with important local structure. Second, we introduce a hybrid XY-XXX mixer that preserves the constraint structure imposed at initialization while retaining exploratory flexibility over the remaining unconstrained degrees of freedom during QAOA evolution. We evaluate the proposed framework against standard QAOA under three progressively more realistic regimes: ideal statevector simulation, finite-shot sampling, and noisy finite-shot sampling. Across all regimes, the proposed method consistently achieves lower average energy and higher feasible-solution ratios than standard QAOA, indicating more effective guidance toward structurally valid, lower-cost VRP solutions. However, the performance gap narrows in the noisy regime. Because this setting adopts a hardware-inspired error model based on near-best-reported laboratory-level qubit gate and readout fidelities, the observed attenuation suggests that the practical advantage of the more structured mixer is likely to grow as quantum hardware improves and error rates decline.
In the search for quantum advantage in real--world problems, one promising avenue is to use a quantum algorithm to improve on the solution found using an efficient classical algorithm. The quantum approximate optimization algorithm (QAOA) is particularly well adapted for such a "warm start" approach, and can be combined with the powerful classical Goemans-Williamson (GW) algorithms based on semi-definite programming. Nonetheless, the best way to leverage the power of the QAOA remains an open question. Here we propose a general model that describes a class of QAOA variants, and use it to explore routes to quantum advantages in a canonical optimization problem, MaxCut. For these algorithms we derive analytic expectation values of the cost Hamiltonian for the MaxCut problem in the level-1 case. Using these analytic results we obtain reliable averages over many instances for fairly large numbers of qubits. We find that the warm start adaptive-bias QAOA (WS-ab-QAOA) initialized by the GW algorithm outperforms previously proposed warm start variants on problems with 404040 to 180180180 qubits. To assess whether a quantum advantage exists with this algorithm, we did numerical simulations with up to 100010001000 qubits to see whether the level-1 WS-ab-QAOA can improve the GW solution for 3-regular graphs. In fact the improvement in the 100010001000-qubit case even in level 1 can only be matched by the GW algorithm after about 105.510^{5.5}105.5 random projections performed after the semi-definite program stage. This work gives evidence that the final stage of optimization after an efficient classical algorithm has produced an approximate solution may be a place where quantum advantages can be realized.
The Quantum Approximate Optimization Algorithm (QAOA) was developed to tackle combinatorial optimization problems, such as the Travelling Salesman Problem (TSP), by approximating solutions through quantum mechanics. QAOA utilizes a unitary transformation to prepare a quantum state that encodes a potential solution, with the parameters of the unitary optimized by a classical optimizer. This study evaluates QAOA's performance on the NP-hard TSP, comparing the standard version of the algorithm from Farhi \cite{qaoa} and an enhancement, Warm-Start QAOA \cite{warmstart}, to a classical solver. The TSP seeks the shortest possible route that visits a set of cities, a problem that is amenable to quantum formulation using platforms like Qiskit. Warm-Start QAOA initializes the algorithm's parameters based on a solution to a relaxed version of the problem, offering potential improvements in optimization efficiency. By comparing these quantum algorithms to a classical solver, we provide a comprehensive assessment of their performance across key metrics, including route quality, execution time, and scalability. Through this analysis, we highlight the relative strengths and weaknesses of QAOA and its warm-start variant for solving the TSP, alongside the classical approach, offering insights into their potential for route optimization and practical applications in realworld settings. We conclude that, while the classical solver significantly outperforms QAOA and warm-start QAOA at smaller-scale problem cases, warm-Start QAOA has the potential to yield advantages at a larger scale when run on NISQ-era noisy hardware.
Variational quantum algorithms are promising for combinatorial optimization, but their scalability is often limited by qubit-intensive encoding schemes. To overcome this bottleneck, Pauli Correlation Encoding (PCE) has emerged as one of the most promising algorithms in this scenario. The method offers not only a polynomial reduction in qubit count and a suppression of barren plateaus but also demonstrates competitive performance with state-of-the-art methods on Maxcut. In this work, we propose a warm-start PCE, an extension that incorporates a classical bias from the Goemans-Williamson (GW) randomized rounding algorithm into the loss function to guide the optimization toward improved approximation ratios. We evaluated this method on the Traveling Salesman Problem (TSP) using a QUBO-to-MaxCut transformation for up to 555 layers. Our results show that Warm-PCE consistently outperforms standard PCE, achieving the optimum solution in 28–64%28\text{--}64\%28–64% of instances, versus 4–26%4\text{--}26\%4–26% for PCE, and attaining higher mean approximation ratios that improve with circuit depth. These findings highlight the practical value of this warm-start strategy for enhancing PCE-based solvers on near-term hardware.