Reproduce “Breaking the quantum barriers for Graph Collision” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, Xingyu Zhou
The authors give a bounded-error quantum algorithm for graph collision, which asks whether adjacent vertices are both marked. It estimates marked-neighbor counts and reduces marked volume to test edge sets, counting only queries to hidden mark bits while treating the graph as known. For every n-vertex graph, it uses \(\widetilde O(n^{11/17})\) queries; a graph family requires \(\Omega(\sqrt{n\log n})\), ruling out \(O(\sqrt n)\) but leaving a polylogarithmic gap.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.