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.