{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreid4rdw5yngfklpkkcyczazumhrle2spav3dq4rqwaz6u3op7o4h4m",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mj4qjwguvr22"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2604.08223v1",
  "publishedAt": "2026-04-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Reed Phillips"
  ],
  "textContent": "**Authors:** Reed Phillips\n\nTarski'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.",
  "title": "The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid"
}