Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
Abstract
The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and its algorithmic variants have found broad applications in areas such as economics, game theory, and programming languages. While the query complexity of finding a Tarski fixed point has been extensively studied in classical models, comparatively little is known in the quantum setting. We prove an Ω(klog n) quantum query lower bound for finding a fixed point of a monotone function on [n]k, using the nonnegative spectral adversary method. In the two extremal regimes n = 2 and k = 1, our quantum lower bound matches the previous classical lower bounds Ω(k) and Ω(log n), respectively. For n, k≥ 2, our bound improves the best previous classical lower bound when n < k and is within a factor of log n / log k compared to the known classical lower bound when n ≥ k. To construct the adversary matrix, we develop the Tree--Filtration Adversary Method. Besides yielding our lower bound, the method offers a more transparent combinatorial interpretation of the nonnegative spectral adversary method. When the hard instances of a problem admit a tree-like organization and suggest an intuition analogous to classical decision-tree lower bounds, our method provide a promising approach to establishing quantum complexity lower bounds.
Related
- Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Quantum Query Complexity Beyond the Worst Case
- Quantum Query Complexity of Tournament Solutions
- Optimal query complexity for fractional quantum evolution
BibTeX
@misc{li2026quantum,
title = {{Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid}},
author = {Tongyang Li and Weiran Ma and Ziyi Yang and Xingyu Zhao},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03802},
eprint = {2609.03802},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03802},
}
RIS
TY - UNPB
TI - Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
AU - Tongyang Li
AU - Weiran Ma
AU - Ziyi Yang
AU - Xingyu Zhao
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03802
UR - https://arxiv.org/abs/2609.03802
AB - The Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point. Beyond its fundamental role in order theory, the theorem and its algorithmic variants have found broad applications in areas such as economics, game theory, and programming languages. While the query complexity of finding a Tarski fixed point has been extensively studied in classical models, comparatively little is known in the quantum setting. We prove an Ω(klog n) quantum query lower bound for finding a fixed point of a monotone function on [n]^k, using the nonnegative spectral adversary method. In the two extremal regimes n = 2 and k = 1, our quantum lower bound matches the previous classical lower bounds Ω(k) and Ω(log n), respectively. For n, k≥ 2, our bound improves the best previous classical lower bound when n < k and is within a factor of log n / log k compared to the known classical lower bound when n ≥ k. To construct the adversary matrix, we develop the Tree--Filtration Adversary Method. Besides yielding our lower bound, the method offers a more transparent combinatorial interpretation of the nonnegative spectral adversary method. When the hard instances of a problem admit a tree-like organization and suggest an intuition analogous to classical decision-tree lower bounds, our method provide a promising approach to establishing quantum complexity lower bounds.
ER -