Quantum Lower Bounds for Collision Problems
Abstract
We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised k-to-one Finding on an exactly k-to-one input string x∈ℤqn, for every fixed k≥2 and every feasible alphabet size q≥ n/k. The lower bounds are Ωk(n1/2−1/(2(2k−1))) for unrestricted adaptive algorithms and Ωk(n1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ωk(√(n/k)) for k-to-one Testing when q≥ n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
Related
- Quantum lower bounds for convex optimization and real matrix-vector query problems
- Quantum Communication Lower Bounds for Search Problems via Matrix Discrepancy
- Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
- Elementary proofs of quantum lower bounds for element distinctness and k-sum
- Natural proofs for quantum state preparation lower bounds
BibTeX
@misc{peng2026quantum,
title = {{Quantum Lower Bounds for Collision Problems}},
author = {Pan Peng and Jingyu Wu},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.01767},
eprint = {2611.01767},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.01767},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Lower Bounds for Collision Problems
AU - Pan Peng
AU - Jingyu Wu
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.01767
UR - https://arxiv.org/abs/2611.01767
AB - We establish tight lower bounds on the adaptive and non-adaptive quantum query complexities of Promised k-to-one Finding on an exactly k-to-one input string x∈ℤ_q^n, for every fixed k≥2 and every feasible alphabet size q≥ n/k. The lower bounds are Ω_k(n^1/2−1/(2(2^k−1))) for unrestricted adaptive algorithms and Ω_k(n^1−1/k) for one-round non-adaptive algorithms. The former matches the adaptive quantum algorithm of Liu and Zhandry [LZ19], whereas the latter matches classical birthday sampling even when the parallel queries are arbitrarily entangled. We also establish the non-adaptive lower bound Ω_k(√(n/k)) for k-to-one Testing when q≥ n, resolving an open question posed by Koiran, Landes, Portier, and Yao [KLPY10]. Our proofs generate the balanced input from a uniformly random permutation and use compressed permutation oracles to describe the information learned by the algorithm. The adaptive proof bounds the growth of partial collisions through successive queries. The one-round proof instead analyzes the state after the parallel queries directly, bounding the probability that the compressed database contains a full collision. In both proofs, a short verification step accounts for correct outputs that include unrecorded positions. For the decision problem, we also compare one-round states with independent and distinct output labels.
ER -