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
Ln2 on points
{1,…,n}2 and where
(x1,y1)≤(x2,y2) if
x1≤x2 and
y1≤y2. We show that the quantum query complexity of finding a fixed point given query access to a monotone function on
Ln2 is
Ω((logn)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.
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
Ω(logm) when the width is multiplied by
m and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an
Ω(klog2n) 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/logk)Ω(logk) 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.
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
Ω(klogn) 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
Ω(logn), respectively. For
n,k≥2, our bound improves the best previous classical lower bound when
n<k and is within a factor of
logn/logk 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.
Tarski's theorem states that every monotone function from a complete lattice to itself has a fixed point. We analyze the query complexity of finding such a fixed point on the
k-dimensional grid of side length
n under the
≤ relation. In this setting, there is an unknown monotone function
f:{0,1,…,n−1}k→{0,1,…,n−1}k and an algorithm must query a vertex
v to learn
f(v). The goal is to find a fixed point of
f using as few oracle queries as possible. We show that the randomized query complexity of this problem is
Ω(logkk⋅log2n) for all
n,k≥2. This unifies and improves upon two prior results: a lower bound of
Ω(log2n) from [EPRY 2019] and a lower bound of
Ω(logkk⋅logn) from [BPR 2024], respectively.
In 1983, Aldous proved that randomization can speedup local search. For example, it reduces the query complexity of local search over grid \left[ {1:n} \right]^d from \Theta (n^{d - 1} ) to {\rm O}(d^{1/2} n^{d/2} ). It remains open whether randomization helps fixed-point computation. Inspired by the recent advances on the complexity of equilibrium computation, we solve this open problem by giving an asymptotically tight bound of (\Omega (n))^{d - 1} on the randomized query complexity for computing a fixed point of a discrete Brouwer function over grid \left[ {1:n} \right]^d Our result can be extended to the black-box query model for Sperner's Lemma in any dimension. It also yields a tight bound for the computation of d-dimensional approximate Brouwer fixed points as defined by Scarf and by Hirsch, Papadimitriou, and Vavasis. Since the randomized query complexity of global optimization over \left[ {1:n} \right]^d is \Theta (n^d ), the randomized query model over \left[ {1:n} \right]^d strictly separates these three important search problems: Global optimization is harder than fixed-point computation, and fixed-point computation is harder than local search. Our result indeed demonstrates that randomization does not help much in fixed-point computation in the black-box query model. Our randomized lower bound matches the deterministic complexity of this problem, which is \Theta (n^{d - 1} ).
The quantum query complexity of searching for local optima has been a subject of much interest in the recent literature. For the d-dimensional grid graphs, the complexity has been determined asymptotically for all fixed d ges 5, but the lower dimensional cases present special difficulties, and considerable gaps exist in our knowledge. In the present paper we present near-optimal lower bounds, showing that the quantum query complexity for the 2-dimensional grid [n]2is Omega(nfrac12 - delta), and that for the 3-dimensional grid [n]3is Omega(n1 - delta), for any fixed delta > 0. A general lower bound approach for this problem, initiated by Aaronson (2004) (based on Ambainis' adversary method (2003) for quantum lower bounds), uses random walks with low collision probabilities. This approach encounters obstacles in deriving tight lower bounds in low dimensions due to the lack of degrees of freedom in such spaces. We solve this problem by the novel construction and analysis of random walks with non-uniform step lengths. The proof employs in a nontrivial way sophisticated results of Sarkozy and Szemeridi (1965), Bose and Chowla (1962-63), and Halasz (1977) from combinatorial number theory, as well as less familiar probability tools like Esseen's inequality