Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem

Fabrizio Fagiolo, Nicolò Vescera · 2025

Read Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem by Fabrizio Fagiolo, Nicolò Vescera (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-21730.txt.

Introduction

Fabrizio Fagiolo and Nicolò Vescera wrote a computing paper in two thousand twenty-five on the traveling salesman problem. The task is to find the shortest tour through a set of cities. Their method uses a quantum circuit whose shape can be reused on new cases.

First, the circuit shape is tuned on one training case with a search method. Then that shape is frozen, and only its settings are tuned again for each new case. Tests on small random cases with four to seven cities worked well up to six cities. With seven cities, success fell sharply, which shows a clear limit on size.

Catalog record

CREATORFabrizio Fagiolo, Nicolò Vescera
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE31 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-21730

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Freeze and Conquer: Reusable Ansatz for Solving the Traveling Salesman Problem Fabrizio Fagiolo, Nicolò Vescera Abstract 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 40 randomly generated symmetric instances that span 4 − 7 4-7 cities, the resulting Ansatz achieves an average optimal trip sampling probability of 100 % 100\% for 4 city cases, 90 % 90\% for 5 city cases and 80 % 80\% for 6 city cases. With 7 cities the success rate drops markedly to an average of ∼ 20 % \sim 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. 1 Introduction Solving combinatorial optimization problems is among the most prominent applications of quantum computing. Two main paradigms have emerged to tackle such problems: quantum annealers, which are specialized hardware devices designed to minimize a cost Hamiltonian, and gate-based quantum processors, which implement Variational Quantum Algorithms (VQAs) such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA). However, when dealing with NP-hard combinatorial problems such as the Traveling Salesman Problem (TSP), two recurring bottlenecks emerge in quantum technology: (i) the use of \mathcal{O}(n^{2}) qubits in standard QUBO/HUBO encodings, which require heavy penalty terms to enforce feasibility, and (ii) deep, fixed circuit layouts that are ill-suited to the constraints of NISQ devices. In this work, we use the Variational Quantum Eigensolver (VQE), where one prepares a parameterized Ansatz \mathcal{A} , |\psi(\boldsymbol{\theta})\rangle , and adjusts the parameter vector \boldsymbol{\theta} so as to minimize E(\boldsymbol{\theta})\;=\;\langle\psi(\boldsymbol{\theta})\,|\,\hat{H}\,|\,\psi(\boldsymbol{\theta})\rangle, thereby obtaining an approximation of the ground–state energy E_{\min} of \hat{H} [ 1 , 2 ] . The shallow depth and flexibility of the circuit make VQE particularly suitable for NISQ hardware [ 4 , 5 ] . Another approach to solving the combinatorial optimization problem is the Quantum Approximate Optimization Algorithm (QAOA) that alternates p layers of two unitaries, \begin{aligned} U_{C}(\gamma_{k})&=e^{-i\gamma_{k}\hat{H}_{C}},\\ U_{B}(\beta_{k})&=e^{-i\beta_{k}\hat{H}_{B}},\end{aligned}\qquad k=1,\dots,p,\qquad\hat{H}_{B}=\sum_{j=1}^{n}X_{j}, to construct the variational state. |\psi_{p}(\boldsymbol{\gamma},\boldsymbol{\beta})\rangle=\Bigl(\prod_{k=1}^{p}U_{B}(\beta_{k})\,U_{C}(\gamma_{k})\Bigr)\,|+\rangle^{\otimes n}, where \boldsymbol{\gamma}=(\gamma_{1},\ldots,\gamma_{p}) and \boldsymbol{\beta}=(\beta_{1},\ldots,\beta_{p}) are optimized to minimize \langle\hat{H}_{C}\rangle [ 6 , 7 ] . Because the circuit explicitly mirrors \hat{H}_{C} , the exploration of the Hilbert space is biased toward states that are relevant to the target optimization problem. The Traveling Salesman Problem serves as our case study in this work. Let V=\{v_{1},\dots,v_{n}\} be a set of n cities and let c:V\times V\to\mathbb{R}_{\geq 0} be a non‑negative cost function with c_{ij}=c(v_{i},v_{j}) . A tour is a permutation \pi\in S_{n} of \{1,\dots,n\} that induces the closed walk \,v_{\pi(1)}\to v_{\pi(2)}\to\cdots\to v_{\pi(n)}\to v_{\pi(1)}\, with total cost C(\pi)\;=\;\sum_{k=1}^{n}c_{\pi(k),\,\pi(k+1)},\qquad\text{with the convention }\pi(n+1)=\pi(1). The optimization task is to find \pi^{\ast}\in S_{n} by minimizing C(\pi) over all n! permutations. Computing \pi^{\ast} is NP-hard and exact methods quickly become impractical as n grows. In the VQE/QAOA formulations of the TSP, one of the first fundamental design choices concerns the encoding of permutations in qubits. Instead of QUBO/HUBO encodings, we adopt compact representations such as Lehmer encoding or permutation encoding [ 8 ] that reduce the number of qubits needed to \mathcal{O}(n\log n) . From this encoding, we develop a two-step workflow inspired by Machine Learning (ML) methods. During the training phase, a Simulated Annealing (SA) procedure jointly explores and learns the circuit topology and its parameters. In the subsequent test phase, the learned topology is frozen and the parameters are only slightly re-optimized, allowing a direct evaluation of the generalization ability. Rather than deriving a Hamiltonian of the TSP in closed form, we estimate the objective value by sampling: at each measurement, we translate the outcome into a tour, compute its classical cost, and use the average cost as an estimate of the expected energy; instead, the solution is the minimum cost tour among those generated by the circuit. This allows us to perform variational optimization without explicitly writing the Hamiltonian. The remainder of the paper is organized as follows. Section 2 describes the related work. Section 3 introduces the scheme of the proposed approach. Section 4 describes and comments on the experimental results. Section 5 ends the paper by providing some concluding remarks as well as possible future research lines. 2 Related work In the Variational Quantum Algorithm (VQA), \mathcal{A} defines the set of states reachable by the circuit, effectively delimiting the space of explorable solutions. In the chemical-quantum domain, for example, it has already been shown that the choice of \mathcal{A} from the hardware efficient circuits of Kandala et al. [ 2 ] decisively affects the trade-off between circuit depth and accuracy of results. The same is true for combinatorial problems such as TSP. Venkat et al. [ 13 ] show that both the architecture (annealer versus gate-based) and the shape of \mathcal{A} decisively affect solution quality and computation time. Murhaf et al. [ 14 ] , exploiting D-Wave’s Pegasus topology and a QUBO reformulation that eliminates the initial node, achieve better tours than D-Wave’s “standard” TSP solver and arrive at 20 cities with fewer qubits. In contrast, the unoptimized approach of Jain et al. [ 15 ] stops at 8 cities without showing competitive performance. Despite the limited number of qubits, gate-based computers can still hold their own against annealers through targeted encoding and \mathcal{A} . Ruan et al. [ 16 ] integrate TSP constraints into the QAOA mixer, halve the qubits needed and double the probability of finding the optimal tour. Qian et al. [ 17 ] test three alternative mixers, improved edge-based coding and layered learning, achieving the best trade-off between depth and quality even in the presence of realistic noise. Finally, Meng Shi et al. [ 18 ] propose APIs that automatically transform any problem on graphs (including TSP) into circuits solved by VQA, achieving with not too many qubits solutions equal to or better than those of specialized algorithms. The most recent literature points out that, in VQA, it is not only the shape of \mathcal{A} that determines performance, but also how parameters are initialized and updated. Egger et al. [ 25 ] introduce the warm-starting quantum optimization paradigm, showing that the choice of initial parameters obtained from a classical relaxation accelerates convergence without compromising quality guarantees. In a complementary study, Montañez-Barrera et al. [ 26 ] show that parameters optimized on small instances of QAOA can be successfully transferred to larger instances, and even to other combinatorial problems, while maintaining high accuracy of the solutions. Similarly, with Meta-VQE, Cervera-Lierta et al. [ 27 ] train a one time set of parameters that quickly adapts to different Hamiltonian configurations, reducing optimization time by orders of magnitude.

Read the complete text