Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.16209

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

Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao

quant-phcs.CCcs.DSSubmitted Oct 12, 2026• Announced Oct 13, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

AI Summary

The paper studies the classical and quantum query complexity of finding a fixed point of a monotone map $f:[n]^k\to[n]^k$, focusing on how hardness scales jointly with dimension $k$ and width $n$. It establishes two bootstrapping results for nonnegative adversary lower bounds on families with unique fixed points forming an antichain. Multiplying dimension by $t$ preserves width and amplifies the bound by at least $t/(5+2\sqrt2)$. Multiplying width by $m$ and doubling dimension amplifies it by $\operatorname{SA}(\mathrm{OS}_m)/2=\Omega(\log m)$. A separate dimension-doubling transformation enforces the antichain condition with a factor-two loss. Consequences include an $\Omega(k\log^2 n)$ quantum lower bound for $k\ge4$; $\Omega(\log^3 n)$ for $k\ge8$, matching classical and quantum upper bounds in dimensions $8,9,10$; and, for every fixed $\alpha>0$, an $\Omega(kn^{\delta(\alpha)})$ bound when $k\ge n^\alpha$. Explicitly, $\Omega(kn^{0.0072})$ holds for $k\ge n^{2/203}$. For $n=2^{\Theta(k)}$, the bound is $(k/\log k)^{\Omega(\log k)}$, excluding generic polynomial-query black-box Tarski solvers as a route to efficient simple stochastic game or ARRIVAL algorithms, without excluding structure-specific algorithms. The constructions chain hard instances sequentially, or hide a sign at a fixed point, compose with ordered search, and embed the composition into a staircase lattice. Explicit spectral adversary matrices establish quantum hardness, hence classical hardness too. The stated limitation is that logarithmic bootstrapping loses the antichain invariant: restoring it makes dimension grow fourfold per logarithmic factor, leaving a gap with upper bounds whose corresponding dimension growth is approximately twofold.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
29 pages, 4 figures

Related papers

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

Tongyang Li, Weiran Ma, Ziyi Yang +1 more

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.

quant-pharXiv:2609.03802•Sep 4, 2026•3 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.

arXiv:2502.16679•Leibniz international proceedings in informatics•Jan 1, 2025•6 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.

arXiv:2604.08223•Apr 9, 2026•4 citations

Quantum Lower and Upper Bounds for 2D-Grid and Dyck Language

Andris Ambainis, Kaspars Balodis, Jānis Iraids +6 more

We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most $k$. We call this the $Dyck_{k,n}$ problem. We prove a lower bound of $Ω(c^k \sqrt{n})$, showing that the complexity of this problem increases exponentially in $k$. Here $n$ is the length of the word. When $k$ is a constant, this is interesting as a representative example of star-free languages for which a surprising $\tilde{O}(\sqrt{n})$ query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When $k$ is not a constant, $Dyck_{k,n}$ is not context-free. We give an algorithm with $O\left(\sqrt{n}(\log{n})^{0.5k}\right)$ quantum queries for $Dyck_{k,n}$ for all $k$. This is better than the trival upper bound $n$ for $k=o\left(\frac{\log(n)}{\log\log n}\right)$. Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of $Ω(n^{1.5-ε})$ for the directed 2D grid and $Ω(n^{2-ε})$ for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.

arXiv:2007.03402•Leibniz international proceedings in informatics•Jan 1, 2020•26 citations

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

arXiv:2610.21785•Oct 15, 2026•0 citations

Lower Bounds for Local Search by Quantum Arguments

Scott Aaronson

The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube $\left\{0,1\right\}^n$, we show a lower bound of $\Omega\left(2^{n/4}/n\right)$ on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of $\Omega\left(2^{n/2}/n^2\right)$ on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension $d\geq3$.

arXiv:quant-ph/0307149•SIAM Journal on Computing•Jun 13, 2004•127 citations
The Tarski fixed-point problem asks for a fixed point of a monotone map on a kkk-dimensional grid lattice of width nnn 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)Ω(t)Ω(t) when the dimension is multiplied by ttt and the width remains unchanged, and (ii) a factor of Ω(log⁡m)Ω(\log m)Ω(logm) when the width is multiplied by mmm and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an Ω(klog⁡2n)Ω(k\log^2 n)Ω(klog2n) lower bound for k≥4k\geq 4k≥4, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant α>0α>0α>0, there exists a constant δ(α)>0δ(α)>0δ(α)>0 such that Qε(Tarski(n,k))=Ω(knδ(α))Q_ε(\text{Tarski}(n,k))=Ω(kn^{δ(α)})Qε​(Tarski(n,k))=Ω(knδ(α)) whenever k>nαk>n^αk>nα, and in particular, an Ω(kn0.0072)Ω(kn^{0.0072})Ω(kn0.0072) lower bound for k>n2/203k>n^{2/203}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/log⁡k)Ω(log⁡k)(k/\log k)^{Ω(\log k)}(k/logk)Ω(logk) for exponentially wide grids, where n=2Θ(k)n=2^{Θ(k)}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 paper studies the classical and quantum query complexity of finding a fixed point of a monotone map f:[n]k→[n]kf:[n]^k\to[n]^kf:[n]k→[n]k, focusing on how hardness scales jointly with dimension kkk and width nnn.
It establishes two bootstrapping results for nonnegative adversary lower bounds on families with unique fixed points forming an antichain. Multiplying dimension by ttt preserves width and amplifies the bound by at least t/(5+22)t/(5+2\sqrt2)t/(5+22​). Multiplying width by mmm and doubling dimension amplifies it by SA⁡(OSm)/2=Ω(log⁡m)\operatorname{SA}(\mathrm{OS}_m)/2=\Omega(\log m)SA(OSm​)/2=Ω(logm). A separate dimension-doubling transformation enforces the antichain condition with a factor-two loss.
Consequences include an Ω(klog⁡2n)\Omega(k\log^2 n)Ω(klog2n) quantum lower bound for k≥4k\ge4k≥4; Ω(log⁡3n)\Omega(\log^3 n)Ω(log3n) for k≥8k\ge8k≥8, matching classical and quantum upper bounds in dimensions 8,9,108,9,108,9,10; and, for every fixed α>0\alpha>0α>0, an Ω(knδ(α))\Omega(kn^{\delta(\alpha)})Ω(knδ(α)) bound when k≥nαk\ge n^\alphak≥nα. Explicitly, Ω(kn0.0072)\Omega(kn^{0.0072})Ω(kn0.0072) holds for k≥n2/203k\ge n^{2/203}k≥n2/203. For n=2Θ(k)n=2^{\Theta(k)}n=2Θ(k), the bound is (k/log⁡k)Ω(log⁡k)(k/\log k)^{\Omega(\log k)}(k/logk)Ω(logk), excluding generic polynomial-query black-box Tarski solvers as a route to efficient simple stochastic game or ARRIVAL algorithms, without excluding structure-specific algorithms.
The constructions chain hard instances sequentially, or hide a sign at a fixed point, compose with ordered search, and embed the composition into a staircase lattice. Explicit spectral adversary matrices establish quantum hardness, hence classical hardness too. The stated limitation is that logarithmic bootstrapping loses the antichain invariant: restoring it makes dimension grow fourfold per logarithmic factor, leaving a gap with upper bounds whose corresponding dimension growth is approximately twofold.
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)Ω(k\log n)Ω(klogn) quantum query lower bound for finding a fixed point of a monotone function on [n]k[n]^k[n]k, using the nonnegative spectral adversary method. In the two extremal regimes n=2n = 2n=2 and k=1k = 1k=1, our quantum lower bound matches the previous classical lower bounds Ω(k)Ω(k)Ω(k) and Ω(log⁡n)Ω(\log n)Ω(logn), respectively. For n,k≥2n, k\geq 2n,k≥2, our bound improves the best previous classical lower bound when n<kn < kn<k and is within a factor of log⁡n/log⁡k\log n / \log klogn/logk compared to the known classical lower bound when n≥kn \geq kn≥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 kkk-dimensional grid of side length nnn under the ≤\leq≤ relation. In this setting, there is an unknown monotone function f:{0,1,…,n−1}k→{0,1,…,n−1}kf: \{0,1,\ldots, n-1\}^k \to \{0,1,\ldots, n-1\}^kf:{0,1,…,n−1}k→{0,1,…,n−1}k and an algorithm must query a vertex vvv to learn f(v)f(v)f(v). The goal is to find a fixed point of fff using as few oracle queries as possible. We show that the randomized query complexity of this problem is Ω(k⋅log⁡2nlog⁡k)Ω\left( \frac{k \cdot \log^2{n}}{\log{k}} \right)Ω(logkk⋅log2n​) for all n,k≥2n,k \geq 2n,k≥2. This unifies and improves upon two prior results: a lower bound of Ω(log⁡2n)Ω(\log^2{n})Ω(log2n) from [EPRY 2019] and a lower bound of Ω(k⋅log⁡nlog⁡k)Ω\left( \frac{k \cdot \log{n}}{\log{k}}\right)Ω(logkk⋅logn​) from [BPR 2024], respectively.
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\mathcal{L}^2_nLn2​ on points {1,…,n}2\{1, \ldots, n\}^2{1,…,n}2 and where (x1,y1)≤(x2,y2)(x_1, y_1) \leq (x_2, y_2)(x1​,y1​)≤(x2​,y2​) if x1≤x2x_1 \leq x_2x1​≤x2​ and y1≤y2y_1 \leq y_2y1​≤y2​. We show that the quantum query complexity of finding a fixed point given query access to a monotone function on Ln2\mathcal{L}^2_nLn2​ is Ω((log⁡n)2)Ω((\log n)^2)Ω((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.
We study the quantum query complexity of two problems. First, we consider the problem of determining if a sequence of parentheses is a properly balanced one (a Dyck word), with a depth of at most kkk. We call this the Dyckk,nDyck_{k,n}Dyckk,n​ problem. We prove a lower bound of Ω(ckn)Ω(c^k \sqrt{n})Ω(ckn​), showing that the complexity of this problem increases exponentially in kkk. Here nnn is the length of the word. When kkk is a constant, this is interesting as a representative example of star-free languages for which a surprising O~(n)\tilde{O}(\sqrt{n})O~(n​) query quantum algorithm was recently constructed by Aaronson et al. Their proof does not give rise to a general algorithm. When kkk is not a constant, Dyckk,nDyck_{k,n}Dyckk,n​ is not context-free. We give an algorithm with O(n(log⁡n)0.5k)O\left(\sqrt{n}(\log{n})^{0.5k}\right)O(n​(logn)0.5k) quantum queries for Dyckk,nDyck_{k,n}Dyckk,n​ for all kkk. This is better than the trival upper bound nnn for k=o(log⁡(n)log⁡log⁡n)k=o\left(\frac{\log(n)}{\log\log n}\right)k=o(loglognlog(n)​). Second, we consider connectivity problems on grid graphs in 2 dimensions, if some of the edges of the grid may be missing. By embedding the "balanced parentheses" problem into the grid, we show a lower bound of Ω(n1.5−ε)Ω(n^{1.5-ε})Ω(n1.5−ε) for the directed 2D grid and Ω(n2−ε)Ω(n^{2-ε})Ω(n2−ε) for the undirected 2D grid. The directed problem is interesting as a black-box model for a class of classical dynamic programming strategies including the one that is usually used for the well-known edit distance problem. We also show a generalization of this result to more than 2 dimensions.
The Six-Dimensional Tarski Problem is Ω(log⁡3n)Ω(\log^3 n)Ω(log3n)-Hard
We study the deterministic query complexity of finding a fixed point of a monotone function f:[n]d→[n]df:[n]^d\to[n]^df:[n]d→[n]d, where querying xxx returns f(x)f(x)f(x). For fixed d≥2d\ge2d≥2, earlier work established a lower bound of Ω((log⁡n)2)Ω((\log n)^2)Ω((logn)2) and an upper bound of Od((log⁡n)⌈(d+2)/3⌉)O_d((\log n)^{\lceil(d+2)/3\rceil})Od​((logn)⌈(d+2)/3⌉) 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 Tarski(n,d)=Ωd((log⁡n)2+⌊log⁡3(d/2)⌋)\text{Tarski}(n,d)=Ω_d((\log n)^{2+\lfloor\log_3(d/2)\rfloor})Tarski(n,d)=Ωd​((logn)2+⌊log3​(d/2)⌋). In particular, we obtain the optimal Θ((log⁡n)3)Θ((\log n)^3)Θ((logn)3) deterministic query complexity in six dimensions.
The problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. For functions on the Boolean hypercube {0,1}n\left\{0,1\right\}^n{0,1}n, we show a lower bound of Ω(2n/4/n)\Omega\left(2^{n/4}/n\right)Ω(2n/4/n) on the number of queries needed by a quantum computer to solve this problem. More surprisingly, our approach, based on Ambainis's quantum adversary method, also yields a lower bound of Ω(2n/2/n2)\Omega\left(2^{n/2}/n^2\right)Ω(2n/2/n2) on the problem's classical randomized query complexity. This improves and simplifies a 1983 result of Aldous. Finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension d≥3d\geq3d≥3.