TY - GEN

T1 - Quantum Optimized Crossover for the Travelling Salesman and Minimization of Makespan with Setup Times

AU - Eremeev, Anton

AU - Zakharova, Yulia

N1 - Anton Eremeev and Yulia Zakharova. 2026. Quantum Optimized Crossover for the Travelling Salesman and Minimization of Makespan with Setup Times. In Genetic and Evolutionary Computation Conference (GECCO Companion ’26), July 13–17, 2026, San Jose, Costa Rica. ACM, New York, NY, USA, 4 pages. https://doi.org/10.1145/3795101.3814656 The work is supported by the Mathematical Center in Akademgorodok under the agreement № 075-15-2025-349 with the Ministry of Science and Higher Education of the Russian Federation.

PY - 2026/8/13

Y1 - 2026/8/13

N2 - This paper proposes quantum-accelerated optimal recombination operators (optimized crossovers) to be used in genetic algorithms for the traveling salesman problem (TSP) and makespan 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 degree 4 and a set of forced edges. Applying the quantum speedup result of Moylett, Linden, and Montanaro (2017), we obtain a bounded-error quantum crossover algorithm. In the case of asymmetric TSP (ATSP) with adjacency-based encoding, the ORP reduces to the ATSP on qubic graphs, so a modification of the quantum algorithm from Moylett, Linden, and Montanaro (2017) yields a bounded-error optimized crossover. Both quantum crossovers for the TSP and ATSP have time complexity bounds, smaller by exponential factors (in the number of vertices), compared to previously known optimized crossovers for these problems. For makespan 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 ⌊k/2⌋ binary variables and, for almost all problem instances, only O(log k) binary variables, where k is the number of jobs.

AB - This paper proposes quantum-accelerated optimal recombination operators (optimized crossovers) to be used in genetic algorithms for the traveling salesman problem (TSP) and makespan 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 degree 4 and a set of forced edges. Applying the quantum speedup result of Moylett, Linden, and Montanaro (2017), we obtain a bounded-error quantum crossover algorithm. In the case of asymmetric TSP (ATSP) with adjacency-based encoding, the ORP reduces to the ATSP on qubic graphs, so a modification of the quantum algorithm from Moylett, Linden, and Montanaro (2017) yields a bounded-error optimized crossover. Both quantum crossovers for the TSP and ATSP have time complexity bounds, smaller by exponential factors (in the number of vertices), compared to previously known optimized crossovers for these problems. For makespan 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 ⌊k/2⌋ binary variables and, for almost all problem instances, only O(log k) binary variables, where k is the number of jobs.

KW - Genetic algorithm

KW - QUBO

KW - makespan minimization

KW - optimal recombination

KW - quantum annealing

KW - quantum speedup

KW - traveling salesman problem

UR - https://www.scopus.com/pages/publications/105048974430

UR - https://www.mendeley.com/catalogue/4effe0f9-680f-360a-8131-ef3af3ba6060/

U2 - 10.1145/3795101.3814656

DO - 10.1145/3795101.3814656

M3 - Conference contribution

SN - 9798400724886

SP - 1546

EP - 1549

BT - GECCO 2026 Companion - Proceedings of the 2026 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery

T2 - The 2026 Genetic and Evolutionary Computation Conference Companion

Y2 - 13 July 2026 through 17 July 2026

ER -