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 $\Omega(n^{2/3})$ query lower bound with a bounded error quantum algorithm using $\widetilde O(n^{92/139})$ queries. We then refine this approach to obtain a $\widetilde O(n^{11/17})$ query algorithm. We also obtain a $\widetilde 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 $\Omega(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $\Omega(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.