Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

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 $\Omega(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $\Omega(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $\Omega(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $\alpha>0$, there exists a constant $\delta(\alpha)>0$ such that $Q_\epsilon(\text{Tarski}(n,k))=\Omega(kn^{\delta(\alpha)})$ whenever $k>n^\alpha$, and in particular, an $\Omega(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)^{\Omega(\log k)}$ for exponentially wide grids, where $n=2^{\Theta(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.

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

arXiv:2610.16209 [quant-ph]

(or arXiv:2610.16209v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2610.16209 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.