Delphi.science

Tight Quantum Query Bounds for Collision Finding over Arbitrary Bounded Types

Source: arxiv.org/abs/2611.17804

Tianci Peng, Shiqi Hou, Xiaoyang Dong

arXivarxiv/2611.17804Nov 13, 2026quant-phscore 0

We determine the bounded-error quantum query complexity of finding one $r$-collision in an $N$-input function of prescribed type, which specifies all equality-class sizes. For every fixed maximum class size and collision order, we give a tight bound as the maximum of scales determined by the numbers of classes of size at least $2,\ldots,r$. The lower bound holds for a uniformly random function of that type, and a matching algorithm succeeds on every such function. No intermediate class size is required to occur, and every feasible output alphabet is allowed. The characterization connects the…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.17804
curl -X POST /api/v1/records/arxiv/2611.17804/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.17804/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'