PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao

arXiv:2610.16209v1quant-phcs.CCcs.DS

TL;DR

Finding a fixed point of a monotone map on a grid lattice is the Tarski problem, which provides a framework for game-theory problems. The paper bootstraps quantum query lower bounds from hard instance families, obtaining stronger bounds across several dimension and width regimes.

  • Problem

    Given oracle access to a monotone map on [n]^k, the Tarski problem is to find a fixed point; it provides a common framework for several game-theory problems.

    Source: §1 · p. 3

  • Method

    The authors construct new adversary matrices in two stages: building abstract problems from known problems, then embedding them into grid lattices.

    Source: §2.4 · p. 8, §6 · p. 27

  • Results

    For k ≥ 4, Qϵ(Tarski(n, k)) = Ω(k log^2 n), and for fixed α > 0 with k > n^α, Qϵ(Tarski(n, k)) = Ω(kn^δ(α)).

    Source: §1.1 · p. 4

  • Takeaways & Limitations

    On exponentially wide grids with n = 2^Θ(k), the quantum query lower bound is superpolynomial in k.

    Source: §6 · p. 27

    Iterating logarithmic bootstrapping requires increasing dimension from k to 4k, and the log bootstrapping does not preserve the crucial antichain property.

    Source: §6 · p. 27

Abstract

from arXiv · show

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 $\Omega(t)$ when the dimension is multiplied by $t$ and the width remains unchanged, and (ii) a factor of $\Omega(\log m)$ when the width is multiplied by $m$ and the dimension is doubled. Applying these theorems, we obtain three consequences: (i) an $\Omega(k\log^2 n)$ lower bound for $k\geq 4$, improving previously best-known classical and quantum lower bounds; (ii) for every fixed constant $\alpha>0$, there exists a constant $\delta(\alpha)>0$ such that $Q_\epsilon(\text{Tarski}(n,k))=\Omega(kn^{\delta(\alpha)})$ whenever $k>n^\alpha$, and in particular, an $\Omega(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)^{\Omega(\log k)}$ for exponentially wide grids, where $n=2^{\Theta(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.

1 Introduction

The paper studies quantum query lower bounds for finding fixed points of monotone maps on grid lattices, a problem connected to game theory, economics, and computer science. It develops two lower-bound bootstrapping theorems and uses them to strengthen bounds across several dimension and width regimes.

1 Introduction

  • Tarski fixed-point computation on a grid is connected by reductions to supermodular-game equilibria, simple stochastic games, and ARRIVAL.The decision versions of simple stochastic games and ARRIVAL are in NP ∩ coNP, while their membership in P remains open.Source: §1 · p. 3

1.1 Our Contributions

  • The bootstrapping theorems amplify nonnegative-adversary lower bounds by Ω(t) with dimension multiplied by t, or by Ω(log m) when width is multiplied by m and dimension doubled.The starting families have unique fixed points forming an antichain.Source: §1.1 · pp. 4–5
  • For every k ≥ 4, Qϵ(Tarski(n, k)) = Ω(k log^2 n), strengthening the previously known quantum and classical lower bounds.The cited prior bounds are Ω(log^2 n + k log n) quantum and Ω(k + k log^2 n / log k) classical randomized [Phi26] [LMYZ26] [BPR25b] [BPR25a].Source: §1.1 · p. 4
  • For each fixed α > 0, Qϵ(Tarski(n, k)) = Ω(k n^δ(α)) when k > n^α; for α = 2/203, the bound is Ω(k n^0.0072).At exponential width n = 2^Θ(k), the paper also proves a superpolynomial lower bound (k / log k)^Ω(log k).Source: §1.1 · p. 4

1.2 Concurrent Work

  • The dimensional bootstrapping theorem is identified as new relative to concurrent works, and the lower bounds also apply to classical deterministic and bounded-error randomized query complexity.The paper reports a more compact embedding than the concurrent works and an Ω(log^3 n) quantum lower bound already at dimension 8.Source: §1.2 · p. 5

1.3 Paper Organization

  • The paper organization assigns chain construction and antichain lifting to Section 3, logarithmic bootstrapping to Section 4, and consequences to Section 5.Section 2 reviews the problems, quantum query model, adversary method, and construction techniques.Source: §1.3 · p. 5

2 Preliminaries

The preliminaries define the grid-lattice fixed-point problems and the quantum query model, then review nonnegative adversary bounds and tools for constructing new lower bounds. Those tools cover both abstract composition and transferring bounds through query reductions.

2.1 The Tarski and Tarski∗Problems

  • Tarski(n, k) asks for any fixed point of a monotone function on the coordinatewise ordered grid [n]^k; Tarski* allows a monotone sign function and accepts points satisfying one of two signed inequalities.The lower-bound arguments require only monotonicity of the function, not the coordinate-difference restriction used in some prior upper bounds.Source: §2.1 · p. 6

2.2 Quantum Query Model

  • A quantum query algorithm accesses its input through an oracle between input-independent unitaries and outputs the function value with probability at least 1 − ϵ.Qϵ denotes the minimum number of oracle queries needed for that error guarantee.Source: §2.2 · pp. 6–7

2.3 Nonnegative Adversary Method

  • The nonnegative adversary method is a standard technique for quantum query lower bounds; its spectral formulation maximizes over nonzero nonnegative adversary matrices using query-specific distinguisher matrices and the spectral norm.Source: §2.3 · p. 7

2.4 Techniques for Adversary Matrix Construction

  • The construction toolkit has two stages: build abstract problems from known problems, then embed them into grid lattices while transferring adversary lower bounds.The text cites generalized-search composition and adversary-preserving query reductions as the respective techniques.Source: §2.4 · p. 8

2.4.1 Generalized Search Composition

  • Generalized-search composition requires each inner function to have equally sized fibers and a labeling whose query-coordinate equality behavior depends only on variant labels and whether outer labels match.Phillips's composition theorem applies when every inner function is generalized search [Phi26].Source: §2.4.1 · p. 8

2.4.2 Adversary Bounds via Query Reductions

  • The adversary reduction lemma transfers a lower bound through an injective, output-preserving embedding when each new query distinction is witnessed by one of a constant number of old query positions.Relabeling the original adversary matrix yields a lower bound scaled by the reciprocal of that query-position count.Source: §2.4.2 · p. 9

3 Dimensional Hardness Bootstrapping Theorem

This section develops a dimensional bootstrapping theorem for Tarski query lower bounds, amplifying hardness by Ω(t) when dimension grows by a factor of t and width remains fixed. It constructs a chain of hard instances and uses a conjugation transformation to enforce the antichain condition while retaining a nonnegative-adversary lower bound.

3 Dimensional Hardness Bootstrapping Theorem

  • Increasing dimension by t at unchanged width amplifies the lower bound by Ω(t), assuming unique fixed points forming an antichain and a nonnegative adversary lower bound.The starting family must have a nonnegative adversary matrix yielding a spectral lower bound.Source: §3 · pp. 9–10

3.1 Constructing a Chain of Hard Instance

  • The chain constructor arranges t instances so fixed-point search solves them in sequence, producing an injective, monotone instance with a unique tuple of fixed points.Its antichain assumption supports the padding construction.Source: §3.1 · pp. 10–11

3.2 Adversary Matrix Construction and Spectral Analysis

  • The quantum lower-bound analysis constructs a nonnegative adversary matrix for the chain-lifted family, using a tensor-product construction indexed by tuples of base instances.The construction builds on the classical deterministic bootstrapping already obtained from the chain.Source: §3.2 · pp. 12–13
  • The chain-constructed family yields a nonnegative-adversary spectral lower bound tλ/(Cδ) for Tarski(n, tk).The construction applies to tuples from the antichain-constrained hard family.Source: §3.2 · p. 15

3.3 Enforcing the Antichain Condition by Conjugation Transformation

  • The conjugation-based antichain constructor doubles dimension, gives unique fixed points whose possibilities form an antichain, and retains a nonnegative-adversary lower bound λ/(2δ).It applies to a hard family for Tarski(n, k) in which every function has a unique fixed point; the antichain condition is essential to the chain construction, but existing hard families cited here do not satisfy it.Source: §3.3 · pp. 15–16

4 Logarithmic Hardness Bootstrapping Theorem

This section proves a logarithmic hardness-bootstrapping theorem that converts a hard Tarski family with unique antichain fixed points into a hard family for Tarski( nm, 2k), using ordered search and a staircase embedding to obtain a nonnegative-adversary lower bound.

4 Logarithmic Hardness Bootstrapping Theorem

  • Theorem 1.2 lifts a λ/δ lower bound for Tarski(n, k) to SA(OS_m)λ/(2δ) for Tarski(nm, 2k), assuming unique fixed points on an antichain.The lifted family also has unique fixed points, for every integer m ≥2.Source: §4 · p. 16
  • The antichain condition lets the construction hide any sign at the unique fixed point; repeated bootstrapping requires an antichain constructor after embedding.Each additional log m factor increases dimension from k to 4k and width from n to nm; the resulting dimension is below 4k + 2 in [CGL+26] and 4k + 1 in [LW26].Source: §4 · pp. 16–17

4.1 A Hidden-Sign Transformation from Tarski to Tarski∗

  • The hidden-sign transformation preserves the λ/δ spectral lower bound while encoding a chosen sign at the unique fixed point.For each sign, the transformed instance has a monotone sign function and the original unique fixed point remains the unique Tarski∗ solution.Source: §4.1 · p. 17

4.2 Composing Tarski∗with Ordered Search

  • TarskiH on the transformed family is a generalized search problem, enabling composition with ordered search OSm and a nonnegative adversary matrix.The generalized-search condition follows because oracle-answer equality depends only on the inner instances and whether their hidden signs match.Source: §4.2 · pp. 18–19

4.3 Embedding of the Composed Problem

  • The composed problem is embedded into Tarski(nm, 2k) through an order-preserving staircase construction.The abstract ordered blocks embed into [nm]^k, and the staircase embedding uses the product structure on two copies to produce a grid map in dimension 2k.Source: §4.3.1 · pp. 19–20

4.3.1 Reducing the Embedding to a Staircase

  • A monotone retraction onto a staircase in Q2 makes the embedding tractable while preserving the staircase points.The staircase is built from main blocks and bridges, and the order-preserving embedding places Q2 in [nm]^2k.Source: §4.3.1 · pp. 19–20

4.3.2 The Staircase Hard Instance Constructor

  • The staircase constructor is injective and monotone, has a unique fixed point at the hidden ordered-search position, and preserves oracle distinctions from the inner instances.Its block transitions use the inner sign functions to choose directions, with extremal padding values preserving monotonicity across blocks.Source: §4.3.2 · pp. 20–21
  • The staircase constructor is monotone, has a unique fixed point at the block indexed by the ordered-search zero, and each output uses only two oracle answers.Source: §4.3.2 · pp. 22–23

4.3.3 Putting Everything Together

  • Embedding the m-copy composed problem yields a valid hard family for Tarski(nm, 2k), with spectral lower bound SA(OSm)λ/(2δ).Each embedded query depends on only two queries to the original instance, and its fixed point determines the ordered-search answer.Source: §4.3.3 · p. 23

5 Consequences of Hardness Bootstrapping

The consequences apply to quantum query complexity and therefore also to deterministic and randomized classical algorithms. The bootstrapping scheme yields increasingly strong dimension-sensitive and width-sensitive lower bounds, including a superpolynomial bound for exponentially wide grids.

5.1 The Bootstrapping Scheme

  • For every fixed k≥2, the lower bound grows by an additional log n factor with each fourfold dimension increase; for k≥4, the bound is Ω(k log^2 n), improving or matching prior dimension-sensitive bounds.For k=8, 9, and 10, the query complexity is Θ(log^3 n).Source: §5.1 · pp. 24–25

5.2 Polynomial-in-Width Lower Bounds in High Dimensions

  • When k≥n^α for any fixed α>0, the lower bound is linear in k and polynomial in n; at α=2/203, it includes Ω(kn^0.0072).The width exponent δ(α) is positive for every fixed α>0, and Figure 4 depicts its trade-off with the dimension threshold.Source: §5.2 · pp. 25–26, Figure 4 · p. 26

5.3 Superpolynomial Lower Bounds at Exponential Width

  • For exponentially wide grids, n=2^Θ(k), the lower bound is superpolynomial and rules out generic polynomial-query black-box Tarski solvers as a route to polynomial-time algorithms for SSG and ARRIVAL.The stated boundary concerns invoking such a solver for arbitrary black-box Tarski instances in this parameter regime.Source: §5.3 · pp. 26–27

6 Conclusions

The conclusions present two hardness bootstrapping theorems for Tarski fixed-point query lower bounds, then derive stronger bounds across dimensions and widths. The approach depends on antichain structure, and its current dimension costs leave open how to match the classical upper-bound exponent more closely.

6 Conclusions

  • For Tarski(n, tk), the chain constructor amplifies the starting spectral lower bound as dimension grows, although the supplied expression is incomplete.The starting family has unique fixed points lying on an antichain, and a nonnegative adversary matrix gives spectral lower bound L.Source: §6 · p. 27
  • For Tarski(nm, 2k), composing the hidden-sign problem with ordered search yields a spectral lower bound of CL log m/2.The construction embeds the composed problem into [nm]^2k.Source: §6 · p. 27
  • Sequentially applying the bootstrapping theorems gives an Ω(k log^2 n) lower bound for k ≥ 4 and Ω(kn^δ(α)) whenever k > n^α, for each fixed α > 0.On exponentially wide grids with n = 2^Θ(k), the lower bound is superpolynomial in k.Source: §6 · p. 27
  • The approach needs dimension growth from k to 4k for each additional log m factor, while logarithmic bootstrapping does not preserve the antichain property.The authors ask whether an antichain constructor can use dimension k + 1, or logarithmic bootstrapping can work in dimension 2k + 2 while preserving the antichain.Source: §6 · p. 27
Loading 2610.16209v1…