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

Reed Phillips

arxiv: 2604.08223 · v1 · submitted 2026-04-09 · 💻 cs.CC

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

Reed Phillips This is my paper

Pith reviewed 2026-05-10 17:20 UTC · model grok-4.3

classification 💻 cs.CC

keywords quantum query complexityTarski fixed pointmonotone function2D latticeordered searchlower boundquery complexity

0 comments

The pith

Finding a Tarski fixed point on the 2D grid requires Omega((log n)^2) quantum queries.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that the quantum query complexity of finding a fixed point of a monotone function on the two-dimensional lattice L_n^2 is Omega((log n)^2). This lower bound is proven by first establishing a general lower bound for quantum query complexity of compositions of functions that include ordered search, and then using the tight correspondence between Tarski fixed point finding and nested ordered search to transfer the bound. A sympathetic reader would care because this matches the known upper bound from classical deterministic algorithms, suggesting that quantum methods do not yield an asymptotic improvement for this problem. The result bridges concepts from order theory and quantum computing by exploiting the lattice structure.

Core claim

Tarski's theorem guarantees a fixed point for any monotone function on a complete lattice. On the specific lattice L_n^2 consisting of pairs (x,y) with 1 ≤ x,y ≤ n ordered componentwise, the quantum query complexity of finding such a fixed point, when given query access to the function, is Omega((log n)^2). This bound is obtained via a lower bound on the quantum query complexity of a composition of a class of functions including ordered search and the extremely close relationship between finding Tarski fixed points and nested ordered search.

What carries the argument

The composition of ordered search functions and its quantum query complexity lower bound, transferred via the equivalence to nested ordered search for Tarski fixed points.

If this is right

Quantum algorithms offer no asymptotic speedup over classical deterministic ones for finding Tarski fixed points on 2D grids.
Any quantum algorithm for this problem must make at least Omega((log n)^2) queries in the worst case.
The lower bound technique applies directly due to the structural similarity with nested search problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same approach could yield quantum lower bounds for Tarski fixed points on higher-dimensional grids if similar nested structures exist.
This equivalence might help in analyzing other lattice problems in the quantum query model.
Practical implementations for small n could test the tightness of the bound against quantum simulators.

Load-bearing premise

The task of finding a Tarski fixed point is equivalent in query complexity to performing nested ordered search, allowing the lower bound to carry over without additional factors.

What would settle it

A quantum algorithm that finds any fixed point of a monotone function on L_n^2 using o((log n)^2) queries would falsify the lower bound.

Figures

Figures reproduced from arXiv: 2604.08223 by Reed Phillips.

**Figure 1.** Figure 1: An example herringbone function for T ARSKI(5, 2). The blue nodes are the spine, which runs through the red fixed point. Blue arrows flow along the spine while black arrows flow diagonally towards the spine. There is a natural O((log n) 2 ) algorithm for finding the fixed point of a herringbone function: run binary search on the spine, where each spine vertex is found by running binary search perpendicular… view at source ↗

**Figure 2.** Figure 2: Using the notation of Definition 14, an example sketch of a chunked spine for n = 3. The three chunks are the bold black rectangles, each subdivided into five square regions. The spine is in red. It uses C = (1, 2, 1, 3). And let the elements of Bc be indexed Bc 1 , Bc 2 , . . ., ordered by increasing x-coordinate. For any two c ≤ d ∈ [2n ′ ], let R(c, d) denote the set: R(c, d) = {w ∈ [n ′ ] 2 | ∃u ∈ B c… view at source ↗

read the original abstract

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 $\Omega((\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper claims a tight Omega((log n)^2) quantum lower bound for Tarski fixed-point search on the 2D grid by reducing it to nested ordered search.

read the letter

The main point is that the quantum query complexity of finding a Tarski fixed point on the 2D lattice L_n^2 is Omega((log n)^2), matching the known classical deterministic upper bound. The proof splits into a general lower bound for compositions of ordered-search-type functions and a direct reduction showing the fixed-point task is essentially nested ordered search on the grid. If both pieces hold, the result is clean and tight for a natural problem with ties to game theory and optimization. The paper does well by making that reduction explicit and by targeting a bound that lines up exactly with the classical side, which is not trivial. The high-level structure avoids obvious circularity and the abstract cites no prior work with this exact combination, so the specific application looks new. The math sits in standard quantum query complexity territory, probably using adversary methods on the composition, and the citations follow the usual pattern for the area. The soft spot is that the abstract gives no equations or proof steps, so the strength of the composition lower bound and the exact tightness of the nested-search relationship cannot be checked here. If the full paper shows the reduction preserves the quadratic log factor without hidden looseness or extra assumptions, it is fine; otherwise the bound could slip. No load-bearing fitting or internal contradiction is visible from the given structure. This is for readers who already know quantum query lower bounds and Tarski's theorem. Someone working on query complexity or fixed-point problems in lattices will get value from the connection. It deserves a serious referee because the claim is precise, the approach is structured, and the target bound is interesting even if revisions are needed for the details of the reduction.

Referee Report

2 major / 1 minor

Summary. The paper claims that the quantum query complexity of finding a Tarski fixed point of a monotone function on the 2D grid lattice L_n^2 is Omega((log n)^2), matching the classical deterministic upper bound. The proof consists of a quantum lower bound for compositions of functions including ordered search, together with a direct transfer of this bound via an extremely close relationship between the Tarski fixed-point problem and nested ordered search.

Significance. If the claimed lower bound holds, the result is significant: it establishes a tight quantum query bound for a natural fixed-point problem on a lattice, showing that quantum algorithms obtain no asymptotic improvement over classical deterministic search for this task. The explicit matching of the known O((log n)^2) classical upper bound is a strength, as is the use of composition lower bounds to obtain the result.

major comments (2)

[Abstract] Abstract: the stated Omega((log n)^2) lower bound is presented at a high level with no equations, no explicit composition function, and no verification steps for the transfer from nested ordered search; without these details the central claim cannot be checked for correctness.
[Proof structure] Proof structure: the manuscript asserts an 'extremely close relationship' between Tarski fixed-point search and nested ordered search that permits direct transfer of the lower bound. The precise reduction (including how query access to the monotone function is simulated by the nested-search oracle and whether any query overhead is incurred) must be stated explicitly with a formal lemma.

minor comments (1)

[Notation] Notation: the lattice is written as both L_n^2 and mathcal{L}^2_n; adopt a single consistent symbol throughout.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and constructive suggestions. We agree that the abstract and proof structure would benefit from greater explicitness to facilitate verification of the central claims. We will revise the manuscript to incorporate the requested details while preserving the overall structure and results.

read point-by-point responses

Referee: [Abstract] Abstract: the stated Omega((log n)^2) lower bound is presented at a high level with no equations, no explicit composition function, and no verification steps for the transfer from nested ordered search; without these details the central claim cannot be checked for correctness.

Authors: We acknowledge that the abstract is written at a high level for brevity. In the revised version, we will expand the abstract to explicitly name the composition function (a suitable composition of ordered search instances), include the key equation for the Omega((log n)^2) bound, and briefly outline the verification steps for transferring the lower bound from nested ordered search to the Tarski problem. This will make the central claim directly checkable without altering the stated result. revision: yes
Referee: [Proof structure] Proof structure: the manuscript asserts an 'extremely close relationship' between Tarski fixed-point search and nested ordered search that permits direct transfer of the lower bound. The precise reduction (including how query access to the monotone function is simulated by the nested-search oracle and whether any query overhead is incurred) must be stated explicitly with a formal lemma.

Authors: We agree that the relationship should be formalized. The revised manuscript will add a dedicated lemma (Lemma X) that precisely defines the reduction: it will show how each query to the monotone function on L_n^2 is simulated by a constant number of queries to the nested ordered search oracle, with no asymptotic overhead. The lemma will include the explicit mapping between fixed-point instances and nested-search instances, confirming that the query complexity transfers directly. This addresses the request for a formal statement. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained

full rationale

The paper structures its proof explicitly as two independent components: (1) a quantum lower bound for the query complexity of composing functions that include ordered search, and (2) a direct reduction showing an extremely close relationship between Tarski fixed-point search on the 2D grid and nested ordered search. Neither component is described as being derived from the other or from fitted parameters within the Tarski problem itself. No equations, self-citations, or ansatzes are presented that reduce the central Omega((log n)^2) claim back to its own inputs by construction. The matching to the known classical O((log n)^2) upper bound is a conventional lower-bound objective and introduces no circularity. The derivation chain therefore remains non-circular and externally grounded.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on Tarski's theorem (standard background) and the reduction to ordered search; no free parameters, invented entities, or ad-hoc axioms are visible in the abstract.

axioms (1)

standard math Tarski's theorem that every monotone function from a complete lattice to itself has a fixed point
Invoked to guarantee existence of the object being searched for.

pith-pipeline@v0.9.0 · 5446 in / 1175 out tokens · 72222 ms · 2026-05-10T17:20:31.007481+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 2 (composition lower bound for SA(h) ≥ SA(f)·min SA(g_i) when g_i are generalized search functions)
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Lemma 13 (SA(TARSKI(n(n²+n-1),2)) ≥ (1/7) SA(NOS_{n+1,n}))

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

Tarski lower bounds from multi-dimensional herringbones

[BPR25a] Simina Brˆ anzei, Reed Phillips, and Nicholas Recker. Tarski lower bounds from multi-dimensional herringbones. InApprox- imation, Randomization, and Combinatorial Optimization: Algo- rithms and Techniques (APPROX/RANDOM 2025), volume 353, pages 52:1–52:12. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Infor- matik,

work page 2025
[2]

Reichardt

[Rei09] Ben W. Reichardt. Span programs and quantum query complex- ity: The general adversary bound is nearly tight for every boolean function. InProceedings of the 2009 50th annual IEEE Syposium on Foundations of Computer Science, pages 544–551. IEEE,

work page 2009

[1] [1]

Tarski lower bounds from multi-dimensional herringbones

[BPR25a] Simina Brˆ anzei, Reed Phillips, and Nicholas Recker. Tarski lower bounds from multi-dimensional herringbones. InApprox- imation, Randomization, and Combinatorial Optimization: Algo- rithms and Techniques (APPROX/RANDOM 2025), volume 353, pages 52:1–52:12. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Infor- matik,

work page 2025

[2] [2]

Reichardt

[Rei09] Ben W. Reichardt. Span programs and quantum query complex- ity: The general adversary bound is nearly tight for every boolean function. InProceedings of the 2009 50th annual IEEE Syposium on Foundations of Computer Science, pages 544–551. IEEE,

work page 2009