Abstract: This paper proposes quantum-accelerated optimal recombination operators (optimized crossovers) to be used in genetic algorithms for the traveling salesman problem (TSP) and make span minimization on a single machine with setup times. For the symmetric TSP with adjacency-based encoding, the Optimal Recombination Problem (ORP) reduces to a TSP on a graph with maximum vertex degree4 and a set of forced edges. Applying the quantum speedup result of Moylett, Linden, and Montanaro (2017), we obtain a bounded-errorquantum crossover algorithm. In the case of asymmetric TSP (ATSP)with adjacency-based encoding, the ORP reduces to the ATSP onqubic graphs, so a modification of the quantum algorithm from Moylett, Linden, and Montanaro (2017) yields a bounded-error op-timized crossover. Both quantum crossovers for the TSP and ATS Phave time complexity bounds, smaller by exponential factors (in the number of vertices), compared to previously known optimized crossovers for these problems. For make span minimization on a single machine with position-based encoding, the ORP reduces to a quadratic unconstrained binary optimization (QUBO) formulation, enabling solution by quantum annealers. The QUBO has at most⌊ /2⌋ binary variables and, for almost all problem instances, only (log ) binary variables, where is the number of jobs

Cite: Eremeev A. , Zakharova Y.
Quantum Optimized Crossover for the Travelling Salesman and Minimization of Makespan with Setup Times
In compilation GECCO '26 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion. – Association for Computing Machinery New York., 2026. – C.1546-1549. – ISBN 979-8-4007-2488-6. DOI: 10.1145/3795101.3814656 OpenAlex

Identifiers:

≡ OpenAlex:

W7202384906

Altmetrics: