Transferable Equivariant Quantum Circuits for TSP: Generalization Bounds and Empirical Validation

Abstract

In this work, we address the challenge of generalization in quantum reinforcement learning (QRL) for combinatorial optimization, focusing on the Traveling Salesman Problem (TSP). Training quantum policies on large TSP instances is often infeasible, so existing QRL approaches are limited to small-scale problems. To mitigate this, we employed Equivariant Quantum Circuits (EQCs) that respect the permutation symmetry of the TSP graph. This symmetry-aware ansatz enabled zero-shot transfer of trained parameters from $n-$city training instances to larger m-city problems. Building on recent theory showing that equivariant architectures avoid barren plateaus and generalize well, we derived novel generalization bounds for the transfer setting. Our analysis introduces a term quantifying the structural dissimilarity between $n-$ and $m-$node TSPs, yielding an upper bound on performance loss under transfer. Empirically, we trained EQC-based policies on small $n-$city TSPs and evaluated them on larger instances, finding that they retained strong performance zero-shot and further improved with fine-tuning, consistent with classical observations of positive transfer between scales. These results demonstrate that embedding permutation symmetry into quantum models yields scalable QRL solutions for combinatorial tasks, highlighting the crucial role of equivariance in transferable quantum learning.