Quantum Space-Time Tradeoffs for TSP and Hypercube Path via Extremal Set Systems

Abstract

We give a quantum analogue of the extremal set-system framework introduced by Ameli, Nederlof and Wang (FOCS 2026) and Dallant and Kozma (FOCS 2026) for space-time tradeoffs in TSP and related permutation problems. Let $1<S\le 2$, and let $P_S$ denote the optimal inverse normalized chain density among set systems of normalized size at most $S$. We use quantum minimum finding over a covering family of set systems to obtain a bounded-error algorithm using $S^{n+o(n)}$ QRAM space and ${\left(S\sqrt{P_S}\right)}^{n+o(n)}$ time. Combined with the set-system constructions of Andoni, Dallant, Kozma and Yu, this gives an explicit tradeoff improving the Caroppo et al. (ESA 2026) TSP tradeoff for $1<S\le 1.657$. The same method applies to a variety of permutation problems, including the Hypercube Path query problem introduced by Ambainis et al. (SODA 2019), for which it improves the previous bound of $1.817^{n+o(n)}$ for both time and QRAM space to $1.784^{n+o(n)}$ time using $1.430^{n+o(n)}$ QRAM space.

arXiv commentImproved exposition and added results about the Hypercube Path query problem