{
  "annotation_id": "84733e5c-17ca-49b3-bc1c-64fbd4807528",
  "date_created": "2026-03-02T18:02:03.645000Z",
  "date_modified": "2026-03-02T18:02:03.645000Z",
  "file_hash": "990bab06cba871e4f14dde48671f5f95b6f314dc9cfde88360979520ad3f11d2",
  "private": false,
  "record": {
    "abstract": "The polynomial method and the Ambainis\u0027s lower bound (or \\emph{Alb}, for\nshort) method are two main quantum lower bound techniques. While recently\nAmbainis showed that the polynomial method is not tight, the present paper aims\nat studying the power and limitation of \\emph{Alb}\u0027s. We first use known\n\\emph{Alb}\u0027s to derive $\\Omega(n^{1.5})$ lower bounds for\n\\textsc{Bipartiteness}, \\textsc{Bipartiteness Matching} and \\textsc{Graph\nMatching}, in which the lower bound for \\textsc{Bipartiteness} improves the\nprevious $\\Omega(n)$ one. We then show that all the three known Ambainis\u0027s\nlower bounds have a limitation $\\sqrt{N\\cdot \\min\\{C_0(f), C_1(f)\\}}$, where\n$C_0(f)$ and $C_1(f)$ are the 0- and 1-certificate complexity, respectively.\nThis implies that for some problems such as \\textsc{Triangle},\n$k$-\\textsc{Clique}, and \\textsc{Bipartite/Graph Matching} which draw wide\ninterest and whose quantum query complexities are still open, the best known\nlower bounds cannot be further improved by using Ambainis\u0027s techniques. Another\nconsequence is that all the Ambainis\u0027s lower bounds are not tight. For total\nfunctions, this upper bound for \\emph{Alb}\u0027s can be further improved to $\\min\n\\{\\sqrt{C_0(f)C_1(f)}, \\sqrt{N\\cdot CI(f)}\\}$, where $CI(f)$ is the size of max\nintersection of a 0-and a 1-certificate set. Again this implies that $Alb$\u0027s\ncannot improve the best known lower bound for some specific problems such as\n\\textsc{And-Or Tree}, whose precise quantum query complexity is still open.\nFinally, we generalize the three known \\emph{Alb}\u0027s and give a new \\emph{Alb}\nstyle lower bound method, which may be easier to use for some problems.",
    "arxiv_id": "quant-ph/0311060",
    "authors": [
      "Shengyu Zhang"
    ],
    "categories": [
      "quant-ph"
    ],
    "title": "On the power of Ambainis\u0027s lower bounds",
    "url": "https://arxiv.org/abs/quant-ph/0311060"
  },
  "schema_id": "dorsal/arxiv",
  "source": {
    "execution_id": "58e37b27-4191-49ab-acde-fc9d3c11423a",
    "id": "arXiv Dataset IDs",
    "type": "Model",
    "variant": "snapshot-2026-03-01",
    "version": "0.1.0"
  },
  "user_id": 1000002
}