{"id":"arxiv/2611.05356","url":"https://arxiv.org/abs/2611.05356","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Breaking the quantum barriers for Graph Collision","domain":"quant-ph","source":"arxiv","authors":["Arjan Cornelissen","Amin Shiraz Gilani","Shiva Kintali","François Le Gall","Subhasree Patro","Xingyu Zhou"],"reviews":0,"subject":"quant-ph","summary":"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 $\\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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-11-03","reactions":{}}