Source-linked AI summary
Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
Tongyang Li, Weiran Ma, Ziyi Yang, Xingyu Zhao
TL;DR
Finding Tarski fixed points has been studied extensively in classical query models, but quantum bounds for general grid dimensions remained largely open. The paper applies a tree-based adversary framework to this problem and proves an Ω(k log n) quantum query lower bound.
Problem
Quantum query complexity for finding Tarski fixed points on general high-dimensional grids remained largely open, beyond a prior lower bound for the two-dimensional grid.
Source: §1 · p. 2Method
The paper introduces the Tree-Filtration Adversary Method, organizing hard instances in an equal-depth filtration tree.
Source: §4.1 · pp. 13–14Results
Ω(k log n) quantum queries are required; this matches tight bounds for n=2 and k=1, improves classical lower bounds when n<k, and is within a log n/log k factor when n≥k.
Source: §5 · p. 26Takeaways & Limitations
The bound captures the joint influence of n and k, with tightness in the extremal regimes n=2 and k=1.
Source: §5 · p. 26The framework assumes an equal-depth hard-instance filtration tree and strictly positive reachability probabilities for its conditional probabilities to be well defined.
Source: §4.1 · p. 14
Abstract
from arXiv · showhide
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 $\Omega(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 $\Omega(k)$ and $\Omega(\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.
1 Introduction
Classical query complexity for finding Tarski fixed points on finite grids has been extensively studied, while quantum bounds for general grid dimensions remained largely open. The paper proves a joint quantum lower bound and develops a tree-based adversary framework to establish it.
1 Introduction
- Tarski fixed points have applications in programming languages, economics, and game theory, and finding them on finite grids has an extensive classical query literature.The quantum setting had received little attention, with prior work limited to a two-dimensional lower bound.Source: §1 · pp. 1–2
1.1 Our Contributions
- The Ω(k log n) quantum lower bound matches tight classical bounds when n=2 or k=1, improves the classical bound for n<k, and is smaller by a Θ(log n/log k) factor when n≥k.Source: §1.1 · p. 3
- The Tree-Filtration Adversary Method organizes hard instances in a tree, uses a top-down random walk to construct an adversary matrix, and avoids problem-specific algebraic calculations.The paper also gives a new Ω(log n) lower-bound proof for one-dimensional binary search without Hilbert-matrix spectral analysis.Source: §1.1 · p. 3
1.2 Technical Overview
- Nested difference sets shrink as the tree reveals more information, bounding the query locations that can still distinguish instances below a node.Source: §1.2 · p. 4
- Each hard Tarski instance has a Θ(k log n)-vertex spine whose midpoint is its unique fixed point; off-spine points project toward that midpoint.Source: §1.2 · p. 5
- The hard instances form an equal-depth prefix–suffix tree whose leaves correspond bijectively to instances, with deeper nodes revealing more of the hidden instance.Source: §1.2 · pp. 4, 6
- The random walk samples a scale proportional to unused-token count times token length, then selects two distinct tokens; it is 1/2 anti-concentrated and 2/3 geometrically indistinguishable.Source: §1.2 · p. 6
1.3 Paper Organization
- The paper reviews preliminaries, presents the hard-instance construction and adversary proof, then concludes with discussion and open problems.Source: §1.3 · p. 6
2 Preliminaries
The preliminaries establish notation and lattice properties, then introduce the linear-algebra, quantum-query, and adversary frameworks used in the paper.
2.1 Notations
- Notation covers indicator functions, sequences and partial permutations, valid disjoint prefix–suffix pairs, and rooted-tree depth, subtrees, children, and ancestors.Source: §2.1 · pp. 6–7
2.2 Basic Properties of the Lattice
- The grid [n]^k is a complete lattice under coordinatewise order, and composing monotone functions preserves monotonicity.Source: §2.2 · p. 7
2.3 Linear Algebra
- The section defines spectral norm and states entrywise monotonicity and block-matrix norm bounds used in later analysis.Source: §2.3 · pp. 7–8
2.4 Computational Model
- Quantum inputs are accessed by an oracle, and bounded-error query complexity counts oracle calls needed to return the correct output with the required probability.Source: §2.4 · p. 8
2.5 Spectral Adversary Method
- The nonnegative spectral adversary framework uses nonnegative symmetric matrices and per-index distinguisher matrices to lower-bound quantum query complexity.Source: §2.5 · p. 9
3 Hard Instance
The hard instances are built from token-ordered monotone spines: grid points project onto a spine and move toward its center. The construction yields monotone functions with a unique fixed point.
Hard-instance construction
- Step lengths 1, 4, …, 4^U give Θ(log n) geometric scales along a spine, onto which every grid point is projected before moving one edge toward its center.Tokens encode coordinate directions and layer-dependent move lengths.Source: §3 · p. 10
- Balanced token permutations pair matching layers across prefixes and reversed suffixes, with each half containing k/2 tokens from every layer; these define the family F_n,k.Source: §3 · p. 11
Hard-instance properties
- The map from token permutations to functions is injective: the orbit of 0 recovers the spine, whose consecutive edge differences identify the tokens.Source: §3 · p. 11
Examples
- The visualization encodes distance to the fixed point by color intensity, while the reported counts suggest that points at successive spine depths decrease geometrically.Darker arrows indicate smaller distance; the passage describes this pattern as evidence that most points reveal little about the spine.Source: §3 · pp. 11–12
Hard-instance properties
- Every constructed function f_π is monotone and has the unique fixed point x_π,m, the central vertex of its spine.Source: §3 · p. 13
4 Tree-Filtration Adversary Method
Section 4 develops the tree-filtration adversary method and applies it to a restricted fixed-point search problem, organizing hard instances in a filtration tree. Its proof combines a nested simplified difference criterion with a distinguishing random walk whose anti-concentration and geometric indistinguishability properties establish the Ω(k log n) quantum query lower bound.
4.1 Introduction to the General Framework
- The framework organizes hard instances as leaves of an equal-depth filtration tree, with each node representing a subset of instances and a nested simplified difference criterion.The criterion contains every coordinate on which instances below a node can differ, and can only shrink toward the leaves.Source: §4.1 · pp. 13–14
- A distinguishing random walk must keep output values dispersed within each subtree while the probability that a fixed query coordinate remains distinguishing decays geometrically with depth.Under these anti-concentration and geometric-indistinguishability conditions, Theorem 4.10 derives an adversary bound from the construction.Source: §4.1 · pp. 13, 16
- The method constructs a nonnegative symmetric adversary matrix whose entries vanish for pairs with equal function outputs, then bounds its numerator and denominator to prove Theorem 4.10.The numerator and denominator are treated separately in Lemmas 4.12 and 4.15.Source: §4.1 · pp. 16, 19
4.2 Proof of the Main Theorem
- The proof restricts fixed-point search to the family Fn,k, whose functions are monotone and have unique fixed points; a lower bound for this restricted problem transfers to Tarski(n, k).The goal on each input is to compute its unique fixed point.Source: §4.2 · p. 19
- The construction organizes Fn,k using a tree of balanced prefix–suffix pairs, yielding an m-equal-depth hard-instance filtration tree whose leaves correspond bijectively to Fn,k.The correspondence identifies each leaf with the function instance represented there.Source: §4.2 · pp. 20–21
- The simplified difference criterion captures all differing inputs and is nested along the filtration tree.Source: §4.2 · p. 21
- The distinguishing walk makes the hidden fixed point uniform among each subtree’s possible points, yielding 1/2 anti-concentration at every non-leaf depth.Source: §4.2 · pp. 22–23
- The cited text states a 2/3-compression lemma for adjacent layers and separately states that A satisfies the 2/3-geometric-indistinguishability property.Source: §4.2 · pp. 23–24
- For all n,k ≥ 2, the proof establishes an Ω(k log n) quantum query lower bound for finding a Tarski fixed point.For k = 1, it reduces to ordered search, with an Ω(log n) lower bound from; n = 1 is trivial.Source: §4.2 · p. 25
- On normalized hard instances, iterating x ← f(x) reaches a fixed point within m = k(U + 1)/2 = O(k log n) steps, making the lower bound tight for this family.Source: §4.2 · p. 26
5 Conclusion
The paper proves an Ω(k log n) bounded-error quantum query lower bound for Tarski fixed points and introduces a tree-based adversary framework. It identifies possible directions for quantum algorithms and extensions of the framework.
5 Conclusion
- For Tarski(n, k), the bounded-error quantum lower bound Ω(k log n) is tight at n = 2 (Θ(k)) and k = 1 (Θ(log n)), improves prior classical lower bounds for n < k, and leaves a gap log n / log k for n ≥ k.Source: §5 · p. 26
- The Tree-Filtration Adversary Method builds a canonical nonnegative adversary matrix from a tree-organized hard-instance family and a distinguishing random walk.Its analysis reduces to anti-concentration and geometric-indistinguishability, separating hard-instance design from spectral analysis.Source: §5 · p. 26
- A coherent version of the decomposition lemma is proposed as a possible route to quantum speedup over classical algorithms in high dimensions.The conclusion contrasts this possibility with prior work on the low-dimensional regime and notes that quadratic-speedup techniques may be ineffective for the current lower bound.Source: §5 · p. 26
- The quantum query complexity of multidimensional-herringbone instances remains open; their classical lower bound is Ω(k log^2 n / log k).The paper suggests investigating whether wildcard search could yield a quadratic quantum speedup; a spine vertex with a specified ℓ1-norm can be found in O(k log n) queries.Source: §5 · p. 26
- Possible framework extensions include unequal-depth filtration trees, surjective leaf-to-instance maps, nonuniform anti-concentration, and layer- or subtree-specific geometric indistinguishability.These are presented as possible extensions to the current version of the method.Source: §5 · pp. 26–27
A Quantum Query Complexity of a Previous Hard Instance Family
The section analyzes quantum query complexity on a prior hard-instance family by reducing its fixed-point problem to wildcard search. It uses wildcard queries to recover the hidden vector through coordinatewise binary search.
A Quantum Query Complexity of a Previous Hard Instance Family
- Each coordinatewise binary-search round recovers the comparison bits b_i = 1{a_i < m_i} using wildcard queries to the hard-instance oracle.Testing whether all bits on a chosen subset are zero or one uses one oracle query per test, and a wildcard query to the comparison vector uses two such queries.Source: A Quantum Query Complexity of a… · pp. 30–31
- Quantum search with wildcards recovers the hidden comparison string with O(k log k) queries, which is then used across the coordinatewise binary-search rounds.The search subroutine's success probability is amplified to support the union bound over the rounds.Source: A Quantum Query Complexity of a… · p. 31
- O(k log k log n log log n) queries suffice for the hard-instance family when ϵ is constant.The procedure amplifies each wildcard-search subroutine O(log log n) times and performs ⌈log₂ n⌉ binary-search rounds.Source: A Quantum Query Complexity of a… · pp. 30–31
- An oracle for the restricted fixed-point family can be simulated with O(log k) wildcard queries, and its unique fixed point reveals the hidden vector without additional queries.Thus, an algorithm using T queries for that fixed-point problem would solve k-bit WildcardSearch using O(T log k) queries.Source: A Quantum Query Complexity of a… · pp. 32–33
B Alternate Proof of Lower Bound for Binary Search
The appendix applies the tree-filtration framework to binary search, organizing thresholds by binary prefixes and bounding the adversary using a top-down random walk. This recovers the asymptotic lower bound without Hilbert-matrix spectral analysis.
B Alternate Proof of Lower Bound for Binary Search
- The binary trie organizes threshold instances by prefixes, and the associated difference criterion identifies query coordinates that can distinguish instances below a node.The criterion's sets shrink as prefixes are extended.Source: B Alternate Proof of Lower Bound for… · p. 34
- A top-down walk choosing each child with probability 1/2 satisfies the stated anti-concentration property at each depth.Conditioned on a node at depth t, the walk is uniform over its descendant leaves.Source: B Alternate Proof of Lower Bound for… · p. 34
- The walk also satisfies 1/2-geometric-indistinguishability, yielding the framework's required upper bound with r = 1/2.For a query coordinate in the criterion set, membership at a descendant is determined by matching the intervening random bits.Source: B Alternate Proof of Lower Bound for… · pp. 34–35
- The tree-filtration framework recovers the optimal asymptotic binary-search lower bound without spectral analysis of the Hilbert matrix.The section applies the framework with r = 1/2 and the walk's depth-dependent anti-concentration parameter.Source: B Alternate Proof of Lower Bound for… · pp. 34–35