Breaking the quantum barriers for Graph Collision

Abstract

In the graph collision problem, the task is to decide whether a known graph on n vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured Ω(n^2/3) query lower bound with a bounded error quantum algorithm using Õ(n^92/139) queries. We then refine this approach to obtain a Õ(n^11/17) query algorithm. We also obtain a Õ((nq)^11/17) query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size q, contrasting a known Ω(n^2/3) lower bound for such problems with large alphabet sizes. We complement these algorithms with an Ω(√(nlog n)) quantum query lower bound for graph collision, exceeding the O(√n) certificate complexity barrier for the positive adversary method.

Measuring the entanglement-breaking index of a qubit collision channel on a quantum processor: protocol and worked example
Eran Kopel
arXiv26 Sep 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Graph-theory measures capture weak ergodicity breaking on large quantum systems
Heiko Georg Menzler, Rafał Świętek, Mari Carmen Bañuls +1
arXiv30 Oct 2026PreprintarXiv licenceFull textCondensed matter Quantum physics & quantum informationarXiv
Graph-theoretic framework for semi-Markov networks: transient and stationary occupation probabilities, hitting times and weak ergodicity breaking
Julian Voits
arXiv9 Oct 2026PreprintCC BY 4.0Full textProbability Statistical & nonlinear physicsarXiv
Gate-Based Quantum Simulation of Finite-Temperature Open-System Dynamics: A Post-Processing Reconstruction Approach for Collision Models
Kazunari Hashimoto, Chikako Uchiyama
arXiv2 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Rotation Collision based Quantum Lattice Boltzmann Methods
Kangyang Zeng, Changshen Huang, Xi Liu +2
arXiv15 Sep 2026PreprintCC BY 4.0Full textFluid dynamics Quantum physics & quantum informationarXiv

Cite

BibTeX RIS

BibTeX

@misc{cornelissen2026breaking,
  title = {{Breaking the quantum barriers for Graph Collision}},
  author = {Arjan Cornelissen and Amin Shiraz Gilani and Shiva Kintali and François Le Gall and Subhasree Patro and Xingyu Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05356},
  eprint = {2611.05356},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05356},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Breaking the quantum barriers for Graph Collision
AU  - Arjan Cornelissen
AU  - Amin Shiraz Gilani
AU  - Shiva Kintali
AU  - François Le Gall
AU  - Subhasree Patro
AU  - Xingyu Zhou
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05356
UR  - https://arxiv.org/abs/2611.05356
AB  - In the graph collision problem, the task is to decide whether a known graph on n vertices contains an edge with both endpoints marked, given query access to the input bits specifying the marked vertices. We first refute the conjectured Ω(n^2/3) query lower bound with a bounded error quantum algorithm using Õ(n^92/139) queries. We then refine this approach to obtain a Õ(n^11/17) query algorithm. We also obtain a Õ((nq)^11/17) query bound for all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size q, contrasting a known Ω(n^2/3) lower bound for such problems with large alphabet sizes. We complement these algorithms with an Ω(√(nlog n)) quantum query lower bound for graph collision, exceeding the O(√n) certificate complexity barrier for the positive adversary method.
ER  -

Abstract

Related

Cite