arXiv:2609.03802

Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid

Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao

quant-phcs.CCcs.DSSubmitted Sep 3, 2026• Announced Sep 4, 2026• 0 citations

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 $Ω(k\log 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\geq 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 \geq 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.

Comments: 35 pages, 5 figures

Related papers

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

Tongyang Li, Weiran Ma, Ziyi Yang +1 more

quant-pharXiv:2610.16209Oct 13, 20260 citations

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid

Reed Phillips

arXiv:2604.08223Apr 9, 20260 citations

Tarski Lower Bounds from Multi-Dimensional Herringbones

Simina Brânzei, Reed Phillips, Nicholas Recker

arXiv:2502.16679Leibniz international proceedings in informaticsJan 1, 20250 citations

The Six-Dimensional Tarski Problem is $Ω(\log^3 n)$-Hard

Kristóf Zólomy

arXiv:2610.21785Oct 15, 20260 citations

THEORETICAL FOUNDATIONS OF CLASSICAL AND QUANTUM QUERY MODELS: COMPLEXITY, LOWER BOUNDS, AND POLYNOMIAL-SPECTRAL INTERPLAY

Medak Srinivas

Iterative International Publishers eBooksMay 1, 20260 citations

Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

arXiv:2203.02968Leibniz international proceedings in informaticsJan 1, 20222 citations

arXiv:2609.03802

Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid

Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao

quant-phcs.CCcs.DSSubmitted Sep 3, 2026• Announced Sep 4, 2026• 0 citations

arXiv HTML PDF

Abstract

We prove an

Ω(k\log 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\geq 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 \geq 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.

Comments: 35 pages, 5 figures

Related papers

Bootstrapping Classical and Quantum Query Lower Bounds for Finding Tarski Fixed Points

Tongyang Li, Weiran Ma, Ziyi Yang +1 more

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 $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$ , improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$ , there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$ , and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/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/\log k)^{Ω(\log k)}$ 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 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 $Ω(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $Ω(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $α>0$, there exists a constant $δ(α)>0$ such that $Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})$ whenever $k>n^α$, and in particular, an $Ω(kn^{0.0072})$ lower bound for $k>n^{2/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/\log k)^{Ω(\log k)}$ 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.

quant-pharXiv:2610.16209Oct 13, 20260 citations

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid

Reed Phillips

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.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.

arXiv:2604.08223Apr 9, 20260 citations

Tarski Lower Bounds from Multi-Dimensional Herringbones

Simina Brânzei, Reed Phillips, Nicholas Recker

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 $\leq$ relation. In this setting, there is an unknown monotone function $f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, 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 $Ω\left( \frac{k \cdot \log^2{n}}{\log{k}} \right)$ for all $n,k \geq 2$ . This unifies and improves upon two prior results: a lower bound of $Ω(\log^2{n})$ from [EPRY 2019] and a lower bound of $Ω\left( \frac{k \cdot \log{n}}{\log{k}}\right)$ from [BPR 2024], respectively.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 $\leq$ relation. In this setting, there is an unknown monotone function $f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, 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 $Ω\left( \frac{k \cdot \log^2{n}}{\log{k}} \right)$ for all $n,k \geq 2$. This unifies and improves upon two prior results: a lower bound of $Ω(\log^2{n})$ from [EPRY 2019] and a lower bound of $Ω\left( \frac{k \cdot \log{n}}{\log{k}}\right)$ from [BPR 2024], respectively.

arXiv:2502.16679Leibniz international proceedings in informaticsJan 1, 20250 citations

The Six-Dimensional Tarski Problem is $Ω(\log^3 n)$ -HardThe Six-Dimensional Tarski Problem is $Ω(\log^3 n)$-Hard

Kristóf Zólomy

We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$ , where querying $x$ returns $f(x)$ . For fixed $d\ge2$ , earlier work established a lower bound of $Ω((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})$ . In particular, we obtain the optimal $Θ((\log n)^3)$ deterministic query complexity in six dimensions.We study the deterministic query complexity of finding a fixed point of a monotone function $f:[n]^d\to[n]^d$, where querying $x$ returns $f(x)$. For fixed $d\ge2$, earlier work established a lower bound of $Ω((\log n)^2)$ and an upper bound of $O_d((\log n)^{\lceil(d+2)/3\rceil})$ for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to $\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})$. In particular, we obtain the optimal $Θ((\log n)^3)$ deterministic query complexity in six dimensions.

arXiv:2610.21785Oct 15, 20260 citations

THEORETICAL FOUNDATIONS OF CLASSICAL AND QUANTUM QUERY MODELS: COMPLEXITY, LOWER BOUNDS, AND POLYNOMIAL-SPECTRAL INTERPLAY

Medak Srinivas

Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.Query complexity provides a basic framework to quantify the inherent computational cost of functions in the model where access to the input is limited to oracle queries. In this paper, we provide a detailed discussion of classical and quantum models of inquiry, emphasizing the structural differences and the common mathematical basis. We consider deterministic, randomized and quantum query complexities and highlight key techniques to prove lower bounds such as adversarial techniques, polynomial approximations and hybrid arguments . The main theme of this paper is the polynomial-spectral relation which underlies both the classical and the quantum models. In the classical setting, the decision tree complexity is closely related to the degree of real polynomials representing Boolean functions. In the quantum setting, the relation involves the spectral properties of the operators controlling quantum query algorithms, and gives deep insights into quantum accelerations. We study tight bounds for basic problems such as search and element distinctness, proving separations between classical and quantum query complexity. The present study uses methods from approximation theory, linear algebra and spectrum analysis to build a foundation for a complete understanding of the power and limitations of query-based computation.

Iterative International Publishers eBooksMay 1, 20260 citations

Improved Quantum Query Upper Bounds Based on Classical Decision Trees

Arjan Cornelissen, Nikhil S. Mande, Subhasree Patro

Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost $O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size $s$ . Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.Given a classical query algorithm as a decision tree, when does there exist a quantum query algorithm with a speed-up over the classical one? We provide a general construction based on the structure of the underlying decision tree, and prove that this can give us an up-to-quadratic quantum speed-up. In particular, we obtain a bounded-error quantum query algorithm of cost $O(\sqrt{s})$ to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size $s$. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.

arXiv:2203.02968Leibniz international proceedings in informaticsJan 1, 20222 citations

We prove an

Ω(k\log 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\geq 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 \geq k

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

Ω(\log m)

when the width is multiplied by

m

and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an

Ω(k\log^2 n)

lower bound for

k\geq 4

, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant

α>0

, there exists a constant

δ(α)>0

such that

Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})

whenever

k>n^α

, and in particular, an

Ω(kn^{0.0072})

lower bound for

k>n^{2/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/\log k)^{Ω(\log k)}

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.

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)

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

Ω((\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.

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

\leq

relation. In this setting, there is an unknown monotone function

f: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, 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

Ω\left( \frac{k \cdot \log^2{n}}{\log{k}} \right)

for all

n,k \geq 2

. This unifies and improves upon two prior results: a lower bound of

Ω(\log^2{n})

from [EPRY 2019] and a lower bound of

Ω\left( \frac{k \cdot \log{n}}{\log{k}}\right)

from [BPR 2024], respectively.

The Six-Dimensional Tarski Problem is

Ω(\log^3 n)

-Hard

We study the deterministic query complexity of finding a fixed point of a monotone function

f:[n]^d\to[n]^d

, where querying

x

returns

f(x)

. For fixed

d\ge2

, earlier work established a lower bound of

Ω((\log n)^2)

and an upper bound of

O_d((\log n)^{\lceil(d+2)/3\rceil})

for the query complexity. Very recently, several papers obtained improved lower bounds using AI-assisted proofs. In this paper, we further improve these lower bounds to

\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})

. In particular, we obtain the optimal

Θ((\log n)^3)

deterministic query complexity in six dimensions.

O(\sqrt{s})

to compute a Boolean function (more generally, a relation) that can be computed by a classical (even randomized) decision tree of size

s

. Lin and Lin [ToC'16] and Beigi and Taghavi [Quantum'20] showed results of a similar flavor, and gave upper bounds in terms of a quantity which we call the "guessing complexity" of a decision tree. We identify that the guessing complexity of a decision tree equals its rank, a notion introduced by Ehrenfeucht and Haussler [Inf. Comp.'89] in the context of learning theory. This answers a question posed by Lin and Lin, who asked whether the guessing complexity of a decision tree is related to any complexity-theoretic measure. We also show a polynomial separation between rank and randomized rank for the complete binary AND-OR tree. Beigi and Taghavi constructed span programs and dual adversary solutions for Boolean functions given classical decision trees computing them and an assignment of non-negative weights to its edges. We explore the effect of changing these weights on the resulting span program complexity and objective value of the dual adversary bound, and capture the best possible weighting scheme by an optimization program. We exhibit a solution to this program and argue its optimality from first principles. We also exhibit decision trees for which our bounds are asymptotically stronger than those of Lin and Lin, and Beigi and Taghavi. This answers a question of Beigi and Taghavi, who asked whether different weighting schemes could yield better upper bounds.