arXiv:2610.14062
Grover Search for a Threshold-Fraction Variant of the Travelling Salesman Problem: A Circuit-Level Construction
Aayra Dhindsa Sawkmie
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/\sqrt{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.
AI Summary
The paper considers a promise variant of threshold TSP: given $N$ cities, a length threshold $K$, and $p\in(0,1]$, distinguish instances where at least $pN!$ tour permutations have length at most $K$ from those where none do. Intermediate cases are excluded. The question concerns the abundance of feasible tours, not finding an optimal tour or robustness to uncertain edge lengths. The construction applies amplitude amplification to a uniform superposition of valid permutations, prepared by a reversible Fisher–Yates shuffle. Its feasibility oracle loads edge lengths through controlled table lookups, sums them with ripple-carry adders, compares the total with $K$, and uncomputes the workspace. Randomising the Grover iteration count handles the unknown feasible fraction. Combined with a classical random-tour check, each run succeeds with probability at least $1/4$ on yes-instances, using $O(p^{-1/2})$ queries. Repetition reduces failure probability to $\delta$ with an additional $O(\log(1/\delta))$ factor; verification prevents false acceptance. For $w$-bit edge lengths, the stated gate cost is $O(N^3(\log N+w)p^{-1/2}\log(1/\delta))$, with $O(N(\log N+w))$ qubits. Classical sampling needs $O(p^{-1})$ checks, so fixed $p$ also makes the classical problem polynomial-time. With the explicit lookup circuit, quantum running time beats this sampling baseline only roughly when $p<N^{-4}$, where the query count is no longer constant. Further limitations include the demanding promise, potentially stronger classical heuristics, and the absence of simulation or hardware validation.
Error found: The abstract's polynomial-in-N runtime claim omits a bound on edge-weight bit width w, although the circuit cost is O(N³(log N + w)) per iteration.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 12 pages, 2 figures