Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem

arXiv:2610.33188v1 Announce Type: new Abstract: Comb inequalities are essential cutting planes for the travelling salesman problem, yet their separation remains computationally challenging. We propose a quantum heuristic separation algorithm for this family of inequalities. The algorithm uses a procedure that prepares a uniform superposition of all combs with a fixed number of teeth using polynomially many gates and qubits. As part of this procedure, we present a circuit that coherently encodes the Hamming weight of a data register in one-hot form in an auxiliary register. The separation algorithm then searches for violated inequalities using the Grover-Mixer Quantum Alternating Operator Ansatz.