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

• URL: http://arxiv.org/abs/2609.03802v1
• Date: Thu, 03 Sep 2026 13:06:12 GMT
• Title: Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid
• Abstract summary: Knaster-Tarski fixed-point theorem states that every monotone function over a complete lattice has a fixed point.<n>We prove an $(klog n)$ quantum query lower bound for finding a fixed point of a monotone function on $[n]k$, using the nonnegative spectral adversary method.
• Score: 31.45779401617503
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Optimal Lower Bounds for Hamiltonian Simulation [42.227880669333835]
  For Hamiltonian $H = sum_j h_j$, we proveally tight lower bounds on the gate and query complexities of simulating time evolution on a quantum computer.<n>Our hold for arbitrary term norms $|h_j|$, time $t$, and trace-distance error $$.
  arXiv  Detail & Related papers  (2026-07-22T07:41:32Z)
• Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy [4.843542453440025]
  We study one-way quantum communication lower bounds for search problems.<n>For collision finding, we prove a tight $(N1/4)$ one-way quantum communication lower bound.<n>For triangle finding, we prove a one-pass quantum streaming space lower bound of $left(sqrt_Vright)$ for graphs with $m$ edges, $(m)$ triangles, and constant $_E$.
  arXiv  Detail & Related papers  (2026-07-09T14:11:09Z)
• Tight Quantum Lower Bound for k-Distinctness [52.10197476419622]
  We introduce a new quantum query lower bound framework.<n>We show how this framework behaves on the problem of finding equal elements in the input string.<n>In particular, we demonstrate its power by proving a first tight quantum query lower bound for the k-Distinctness problem.
  arXiv  Detail & Related papers  (2026-04-06T19:52:58Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• From Classical to Quantum: Explicit Classical Distributions Achieving Maximal Quantum $f$-Divergence [4.956709222278243]
  Explicit classical states achieving maximal $f$-divergence are given, allowing for a simple proof of Matsumoto's Theorem.<n>Our methodology is particularly simple as it does not require any elaborate matrix analysis machinery but only basic linear algebra.
  arXiv  Detail & Related papers  (2025-01-24T09:06:13Z)
• Better bounds on Grothendieck constants of finite orders [20.068273625719943]
  We exploit a recent Frank-Wolfe approach to provide good candidates for lower bounding some Grothendieck constants.<n>The complete proof relies on solving difficult binary quadratic optimisation problems.
  arXiv  Detail & Related papers  (2024-09-05T17:53:52Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  We study quantum Ordered Binary Decision Diagrams($OBDD$) model. We prove lower bounds and upper bounds for OBDD with arbitrary order of input variables. We extend hierarchy for read$k$-times Ordered Binary Decision Diagrams ($k$-OBDD$) of width.
  arXiv  Detail & Related papers  (2022-04-22T12:37:56Z)
• Quantum algorithms for escaping from saddle points [7.191453718557392]
  We study quantum algorithms for escaping from saddle points with provable guarantee. Our main contribution is the idea of replacing the classical perturbations in gradient descent methods. We also show how to use a quantum gradient computation algorithm due to Jordan.
  arXiv  Detail & Related papers  (2020-07-20T16:42:53Z)
• Quantum Communication Complexity of Distribution Testing [114.31181206328276]
  Two players each receive $t$ samples from one distribution over $[n]$. The goal is to decide whether their two distributions are equal, or are $epsilon$-far apart. We show that the quantum communication complexity of this problem is $tildeO$(tepsilon2))$ qubits when distributions have low $l$-norm.
  arXiv  Detail & Related papers  (2020-06-26T09:05:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.