{"id":"arxiv/2610.16209","url":"https://arxiv.org/abs/2610.16209","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points","domain":"quant-ph","source":"arxiv","authors":["Tongyang Li","Weiran Ma","Ziyi Yang","Xingyu Zhao"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}