The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911578534707200 |
|---|---|
| author | Phillips, Reed |
| author_facet | Phillips, Reed |
| contents | Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We specifically consider the two-dimensional lattice $\mathcal{L}^2_n$ on points $\{1, \ldots, n\}^2$ and where $(x_1, y_1) \leq (x_2, y_2)$ if $x_1 \leq x_2$ and $y_1 \leq y_2$. We show that the quantum query complexity of finding a fixed point given query access to a monotone function on $\mathcal{L}^2_n$ is $Ω((\log n)^2)$, matching the classical deterministic upper bound. The proof consists of two main parts: a lower bound on the quantum query complexity of a composition of a class of functions including ordered search, and an extremely close relationship between finding Tarski fixed points and nested ordered search. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_08223 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid Phillips, Reed Computational Complexity 68Q12 F.2.2 Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We specifically consider the two-dimensional lattice $\mathcal{L}^2_n$ on points $\{1, \ldots, n\}^2$ and where $(x_1, y_1) \leq (x_2, y_2)$ if $x_1 \leq x_2$ and $y_1 \leq y_2$. We show that the quantum query complexity of finding a fixed point given query access to a monotone function on $\mathcal{L}^2_n$ is $Ω((\log n)^2)$, matching the classical deterministic upper bound. The proof consists of two main parts: a lower bound on the quantum query complexity of a composition of a class of functions including ordered search, and an extremely close relationship between finding Tarski fixed points and nested ordered search. |
| title | The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid |
| topic | Computational Complexity 68Q12 F.2.2 |
| url | https://arxiv.org/abs/2604.08223 |