arXiv:2610.16209
Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao
Abstract
The Tarski fixed-point problem asks for a fixed point of a monotone map on a $k$-dimensional grid lattice of width $n$ and has applications in game theory, economics, and verification. Substantial gaps remain between the known upper and lower bounds on its quantum query complexity. We prove two hardness bootstrapping theorems for quantum query lower bounds. Starting from a hard instance family whose instances have pair-wise incomparable unique fixed points, and a lower bound established by the nonnegative adversary method, we bootstrap this lower bound by (i) a factor of $Ω(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$, there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$, and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/203}$, the first lower bound with simultaneous linear dependence on the dimension and polynomial dependence on the width; and (iii) a superpolynomial lower bound of $(k/\log k)^{Ω(\log k)}$ for exponentially wide grids, where $n=2^{Θ(k)}$. The last result rules out a route to polynomial-time algorithms for simple stochastic games and ARRIVAL through generic polynomial-query black-box Tarski solvers.
AI Summary
The paper studies the classical and quantum query complexity of finding a fixed point of a monotone map $f:[n]^k\to[n]^k$, focusing on how hardness scales jointly with dimension $k$ and width $n$. It establishes two bootstrapping results for nonnegative adversary lower bounds on families with unique fixed points forming an antichain. Multiplying dimension by $t$ preserves width and amplifies the bound by at least $t/(5+2\sqrt2)$. Multiplying width by $m$ and doubling dimension amplifies it by $\operatorname{SA}(\mathrm{OS}_m)/2=\Omega(\log m)$. A separate dimension-doubling transformation enforces the antichain condition with a factor-two loss. Consequences include an $\Omega(k\log^2 n)$ quantum lower bound for $k\ge4$; $\Omega(\log^3 n)$ for $k\ge8$, matching classical and quantum upper bounds in dimensions $8,9,10$; and, for every fixed $\alpha>0$, an $\Omega(kn^{\delta(\alpha)})$ bound when $k\ge n^\alpha$. Explicitly, $\Omega(kn^{0.0072})$ holds for $k\ge n^{2/203}$. For $n=2^{\Theta(k)}$, the bound is $(k/\log k)^{\Omega(\log k)}$, excluding generic polynomial-query black-box Tarski solvers as a route to efficient simple stochastic game or ARRIVAL algorithms, without excluding structure-specific algorithms. The constructions chain hard instances sequentially, or hide a sign at a fixed point, compose with ordered search, and embed the composition into a staircase lattice. Explicit spectral adversary matrices establish quantum hardness, hence classical hardness too. The stated limitation is that logarithmic bootstrapping loses the antichain invariant: restoring it makes dimension grow fourfold per logarithmic factor, leaving a gap with upper bounds whose corresponding dimension growth is approximately twofold.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 29 pages, 4 figures