Quantum query lower bounds advance understanding of Tarski fixed points
Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
Computational ComplexityData Structures and Algorithms
Summary
Finding fixed points of certain mathematical functions, like those described by the Tarski fixed-point problem, is important in areas like economics and game theory. The paper studies how hard it is for quantum computers to solve this problem when given limited information. The authors develop methods to scale up known hardness results, showing that finding fixed points in higher dimensions or larger grids requires significantly more queries. Their results improve previous lower bounds and highlight limits on how quickly quantum algorithms can solve these problems.
What this means in practice
- •For quantum algorithm designers: Understand fundamental limits on query efficiency for fixed-point problems to guide algorithm development.
- •For verification tool builders: Use these hardness results to assess feasibility of generic black-box solvers for monotone fixed points in verification tasks.
A theory result. No direct application yet.
Authors
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.