Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem
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. Its running time is polynomial under prescribed polynomial budgets for the number of QAOA rounds, parameter optimization steps and samples gathered, although we provide no evidence that such budgets suffice to find a violated comb with constant probability when one exists. We provide an explicit circuit construction for the mixer unitary, the full problem Hamiltonian and a resource analysis.
Related
- Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
- Travelling Dark State Polariton as a Viable Quantum Memory in a Solid-State Medium
- Quantum iterative approach to the Traveling Salesman Problem
- Heuristic Quantum Amplitude Amplification: A Traffic QUBO Case Study
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
BibTeX
@misc{finet2026quantum,
title = {{Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem}},
author = {Yohan Finet and Victor Drouin-Touchette},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.33188},
eprint = {2610.33188},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.33188},
}
RIS
TY - UNPB
TI - Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem
AU - Yohan Finet
AU - Victor Drouin-Touchette
PY - 2026
DA - 2026/10/23
PB - arXiv
DO - 10.48550/arxiv.2610.33188
UR - https://arxiv.org/abs/2610.33188
AB - 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. Its running time is polynomial under prescribed polynomial budgets for the number of QAOA rounds, parameter optimization steps and samples gathered, although we provide no evidence that such budgets suffice to find a violated comb with constant probability when one exists. We provide an explicit circuit construction for the mixer unitary, the full problem Hamiltonian and a resource analysis.
ER -