In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) thatcombines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) anoptimize-freeze-reuse strategy: where the circuit topology (“Ansatz”) is first optimized on a train-ing instance by Simulated Annealing (SA), then “frozen” and re-used on novel instances, limitedto a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structuralresearch in testing, making the procedure immediately implementable on NISQ hardware.On a set of 40 randomly generated symmetric instances that span 4 − 7 cities, the resultingAnsatz achieves an average optimal trip sampling probability of 100% for 4 city cases, 90% for 5city cases and 80% for 6 city cases. With 7 cities the success rate drops markedly to an average of∼ 20%, revealing the onset of scalability limitations of the proposed method.The results show robust generalization ability for moderate problem sizes and indicate howfreezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality.The paper also discusses scalability limitations, the impact of “warm-start” initialization of pa-rameters, and prospects for extension to more complex problems, such as Vehicle Routing andJob-Shop Scheduling.
In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) thatcombines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) anoptimize-freeze-reuse strategy: where the circuit topology (“Ansatz”) is first optimized on a train-ing instance by Simulated Annealing (SA), then “frozen” and re-used on novel instances, limitedto a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structuralresearch in testing, making the procedure immediately implementable on NISQ hardware.On a set of 40 randomly generated symmetric instances that span 4 − 7 cities, the resultingAnsatz achieves an average optimal trip sampling probability of 100% for 4 city cases, 90% for 5city cases and 80% for 6 city cases. With 7 cities the success rate drops markedly to an average of∼ 20%, revealing the onset of scalability limitations of the proposed method.The results show robust generalization ability for moderate problem sizes and indicate howfreezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality.The paper also discusses scalability limitations, the impact of “warm-start” initialization of pa-rameters, and prospects for extension to more complex problems, such as Vehicle Routing andJob-Shop Scheduling.
In this paper we present a variational algorithm for the Traveling Salesman Problem (TSP) that combines (i) a compact encoding of permutations, which reduces the qubit requirement too, (ii) an optimize-freeze-reuse strategy: where the circuit topology (``Ansatz'') is first optimized on a training instance by Simulated Annealing (SA), then ``frozen'' and re-used on novel instances, limited to a rapid re-optimization of only the circuit parameters. This pipeline eliminates costly structural research in testing, making the procedure immediately implementable on NISQ hardware. On a set of 40 randomly generated symmetric instances that span 4−7 cities, the resulting Ansatz achieves an average optimal trip sampling probability of 100% for 4 city cases, 90% for 5 city cases and 80% for 6 city cases. With 7 cities the success rate drops markedly to an average of ∼20%, revealing the onset of scalability limitations of the proposed method. The results show robust generalization ability for moderate problem sizes and indicate how freezing the Ansatz can dramatically reduce time-to-solution without degrading solution quality. The paper also discusses scalability limitations, the impact of ``warm-start'' initialization of parameters, and prospects for extension to more complex problems, such as Vehicle Routing and Job-Shop Scheduling.
The Traveling Salesman Problem (TSP) is a prototypical combinatorial optimization problem, but its quantum implementation is limited by the O(n^2)-qubit overhead of standard one-hot encodings. Here, we propose a resource-efficient variational quantum framework based on compact binary-register encoding, a permutation-preserving problem-inspired ansatz, and a complementary divide-and-conquer execution strategy. The compact encoding reduces the data-qubit requirement to O(n log n), while the divide-and-conquer formulation lowers the number of qubits required in each local hardware execution to the size of the largest subsystem. Numerical simulations on TSP instances with 4, 5, and 6 cities achieve best average success rates of 100%, 100%, and 95.5%, respectively. A local two-qubit implementation of the divide-and-conquer approximation is further evaluated for a 5-city TSP instance on SpinQ Gemini Pro and SpinQ Triangulum II NMR quantum computers. Taken together, the results indicate how compact encoding and divide-and-conquer execution with classical post-processing can be used to study small combinatorial optimization instances on resource-constrained quantum hardware.
This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP), a clustered routing problem that naturally models variant selection and sequencing problems under discrete alternatives. We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing, as well as a hardware-executable gate-based pipeline utilizing the Quantum Approximate Optimization Algorithm (QAOA). We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model, while feasibility with respect to the full GTSP constraints is tracked explicitly during post-processing. We compare the two quantum optimization paradigms on problem instances from GTSPLIB, an established benchmark dataset, and validate against classical state-of-the-art solvers. To mitigate current quantum hardware size limitations, we further extend a preprocessing method to reduce the node count in instance clusters, constructing new NISQ-friendly instances from reduced subsets. Across all tested instances, quantum solvers often produce competitive solution quality when tested on smaller graphs, but exhibit higher runtimes and a sharp degradation in feasibility and scalability as instance size grows. Our evaluation highlights where quantum optimizers can already succeed and which algorithmic bottlenecks, like sampling rates, runtime issues, and other practical failure modes, remain as open problems.
The Travelling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimisation problem with important industrial applications. Although extensively studied, quantum solutions for instances beyond a dozen locations remain uncommon. We present a hybrid penalty-free Variational Quantum Algorithm (VQA) that significantly reduces both the qubit count and the runtime through a compact penalty-free formulation scaling as O(nlog2n) qubits compared to conventional formulations with O(n2) scaling. The VQA achieves solution qualities exceeding 90\% on Rigetti quantum hardware for instances of up to 17 locations. To the best of our knowledge, this represents the largest TSP instance solved on gate-based hardware. We systematically evaluate multiple encoding and optimisation strategies, and show that warm-start initialisation improves solution quality, while runtime is reduced by nearly two orders of magnitude through the use of gradient-free optimisation methods and cost-function caching. We additionally introduce a novel VQA inspired classical machine learning model (VQAi-CML) and benchmark the VQA against VQAi-CML, a greedy heuristic, a Monte Carlo baseline, and a strong classical optimisation baseline. Across the networks evaluated, the VQA consistently achieves superior solution quality relative to VQAi-CML, greedy heuristic, and Monte Carlo baselines, but not the classical solver
The traveling salesman problem (TSP) is one of the most often-used NP-hard problems in computer science to study the effectiveness of computing models and hardware platforms. In this regard, it is also heavily used as a vehicle to study the feasibility of the quantum computing paradigm for this class of problems. In this paper, we tackle the TSP using the quantum approximate optimization algorithm (QAOA) approach by formulating it as an optimization problem. By adopting an improved qubit encoding strategy and a layer-wise learning optimization protocol, we present numerical results obtained from the gate-based digital quantum simulator, specifically targeting TSP instances with 3, 4, and 5 cities. We focus on the evaluations of three distinctive QAOA mixer designs, considering their performances in terms of numerical accuracy and optimization cost. Notably, we find that a well-balanced QAOA mixer design exhibits more promising potential for gate-based simulators and realistic quantum devices in the long run, an observation further supported by our noise model simulations. Furthermore, we investigate the sensitivity of the simulations to the TSP graph. Overall, our simulation results show that the digital quantum simulation of problem-inspired ansatz is a successful candidate for finding optimal TSP solutions.
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–64% of instances, versus 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.