Preprint
Nov 2026
Breaking the quantum barriers for Graph Collision
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 $\Omega(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $...
A. Cornelissen, Amin Shiraz Gilani, Shiva Kintali et al.
· 0 citations