The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
This provides a quantum lower bound for a computational geometry problem, but it is incremental as it matches existing classical bounds without a quantum speedup.
The paper tackles the problem of finding a Tarski fixed point on a 2D grid with monotone functions, showing that the quantum query complexity is Ω((log n)^2), which matches the classical deterministic upper bound.
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.