Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
Abstract
The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold K and a promised fraction p, decide whether at least a fraction p of all tours have total length at most K, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using O(1/√p) oracle queries, independent of the number of cities N, with each query implemented by a quantum circuit of polynomial size in N. For any fixed robustness level p, the total runtime is therefore polynomial in N. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on 1/p over classical random sampling, which needs Θ(1/p) samples; because each quantum query is costly, however, it is faster in total running time only when p is very small (roughly below N−4), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.
Related
- Quantum Heuristic Separation of Comb Inequalities for the Travelling Salesman Problem
- Exact cost of the Euclidean Maximum Traveling Salesman Problem in one dimension
- Travelling Dark State Polariton as a Viable Quantum Memory in a Solid-State Medium
- Quantum iterative approach to the Traveling Salesman Problem
- Geometric admissibility conditions for travelling-wave solitons in the Kuralay–IIA equation
BibTeX
@misc{sawkmie2026grover,
title = {{Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction}},
author = {Aayra Dhindsa Sawkmie},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14062},
eprint = {2610.14062},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14062},
}
RIS
TY - UNPB
TI - Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
AU - Aayra Dhindsa Sawkmie
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.14062
UR - https://arxiv.org/abs/2610.14062
AB - The Travelling Salesman Problem (TSP) is a classic combinatorial optimisation problem which is NP-hard in optimisation form and NP-complete as a decision problem. The standard question asks for the shortest tour that visits every city exactly once and returns to the origin. This paper studies a threshold-fraction variant, which we call the robust TSP, formulated as a promise problem: given a distance threshold K and a promised fraction p, decide whether at least a fraction p of all tours have total length at most K, or whether no such tour exists. We show that Grover's quantum search algorithm decides this problem using O(1/√p) oracle queries, independent of the number of cities N, with each query implemented by a quantum circuit of polynomial size in N. For any fixed robustness level p, the total runtime is therefore polynomial in N. Measured in oracle queries, the quantum algorithm offers a quadratic improvement in the dependence on 1/p over classical random sampling, which needs Θ(1/p) samples; because each quantum query is costly, however, it is faster in total running time only when p is very small (roughly below N^−4), where the number of queries is no longer constant. We describe the problem formulation, detail the oracle construction (edge-length loading, sequential quantum addition, and threshold comparison), and analyse the query complexity to achieve the required result.
ER -