Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 46 min ago
PreprintCC BY 4.0arXiv

Elementary proofs of quantum lower bounds for element distinctness and k-sum

  • Andris Ambainis
  • Martins Kokainis
Open at sourcePDFDOICite

Abstract

We give elementary proofs of the Ω(n2/3) quantum query lower bound for element distinctness and the Ω(nk/(k+1)) lower bound for the k-sum problem, for fixed k and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.

Related

  1. Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
    Frédéric Magniez, Sebastian Zur
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  2. Natural proofs for quantum state preparation lower bounds
    Christine Li, Natalie Parham
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
  3. Algebraic Proofs of Quantum Period--TBA Relations
    Min-xin Huang
    arXivPreprintCC BY 4.0Full textHigh-energy & particle physicsarXiv
  4. Zero Knowledge Proofs in Quantum Networks
    Tuhin Paul, Srijani Das, Manasi Patra +1
    arXivPreprintCC BY-SA 4.0Full textMathematical physicsQuantum physics & quantum informationarXiv
  5. On Removing Interaction from Quantum Proofs
    Nicholas Spooner, Max Tromanhauser
    arXivPreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv

Cite

BibTeXRIS
BibTeX
@misc{ambainis2026elementary,
  title = {{Elementary proofs of quantum lower bounds for element distinctness and k-sum}},
  author = {Andris Ambainis and Martins Kokainis},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.32693},
  eprint = {2610.32693},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.32693},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Elementary proofs of quantum lower bounds for element distinctness and k-sum
AU  - Andris Ambainis
AU  - Martins Kokainis
PY  - 2026
DA  - 2026/10/23
PB  - arXiv
DO  - 10.48550/arxiv.2610.32693
UR  - https://arxiv.org/abs/2610.32693
AB  - We give elementary proofs of the Ω(n^2/3) quantum query lower bound for element distinctness and the Ω(n^k/(k+1)) lower bound for the k-sum problem, for fixed k and sufficiently large groups. The proofs use only basic properties of quantum states and linear algebra, analyzing the differences of algorithm states on different inputs.
ER  -