Ansatz Optimization Using Simulated Annealing in Variational Quantum Algorithms for the Traveling Salesman Problem

In this paper we present a Variational Quantum Algorithm (VQA) for solving the Traveling Salesman Problem (TSP) that requires only O (n log n) qubits and an ansatz whose topology evolves via Simulated Annealing (SA). Instead of fixing the circuit in advance, the optimizer dynamically adds, removes, or rearranges rotation gates and entanglement gates to balance exploration and exploitation. On synthetic instances with 5 − 7 cities (7 − 13 qubits, 21 − 39 parameters), the algorithm identifies the optimal tour in almost all its runs within a few hundred iterations, demonstrating that co-optimization of encoding and circuit structure can efciently address combinatorial problems.