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 Ω(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 Ω(klog2 n) lower bound for k≥ 4, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant α>0, there exists a constant δ(α)>0 such that Qε(Tarski(n,k))=Ω(knδ(α)) whenever k>nα, and in particular, an Ω(kn0.0072) lower bound for k>n2/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.
Related
- Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
- Bootstrapping Classical Systems with Quenched Disorder
- Quantum vs Classical Erasure: Equal Bounds but Unequal Costs
- Whither quantum advantage? New classical lower bounds for Max-Cut on large-girth 3-regular graphs
- Tight bounds for hybrid quantum-classical query algorithms
BibTeX
@misc{li2026bootstrapping,
title = {{Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points}},
author = {Tongyang Li and Weiran Ma and Ziyi Yang and Xingyu Zhao},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16209},
eprint = {2610.16209},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16209},
}
RIS
TY - UNPB
TI - Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
AU - Tongyang Li
AU - Weiran Ma
AU - Ziyi Yang
AU - Xingyu Zhao
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16209
UR - https://arxiv.org/abs/2610.16209
AB - 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 Ω(klog^2 n) lower bound for k≥ 4, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant α>0, there exists a constant δ(α)>0 such that Q_ε(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.
ER -