{"id":"arxiv/2610.14062","url":"https://arxiv.org/abs/2610.14062","tags":["cs.DS","quant-ph"],"score":0,"title":"Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction","domain":"cs.DS","source":"arxiv","authors":["Aayra Dhindsa Sawkmie"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-07","reactions":{}}