Quantum query complexity of Graph Collision
- Field
- Topic
Problem
Does Graph Collision on every known \(n\)-vertex graph admit a bounded-error quantum algorithm using \(\widetilde O(\sqrt n)\) queries to the marked-vertex bits? Let \(G=([n],E)\) be a simple undirected graph given in full, and let \(x\in\{0,1\}^n\) be accessible through the quantum oracle \(O_x|v,b\rangle=|v,b\oplus x_v\rangle\). The task is to compute
Only calls to \(O_x\) are counted. All computation involving the known graph is free, and the algorithm must return the value in (1) with probability at least \(2/3\) for every \(x\).
Let \(Q_2(f_G)\) be the minimum worst-case query count under this guarantee, and let \(Q_{\mathrm{GC}}(n)=\max_{G:\,|V(G)|=n}Q_2(f_G)\). The question is whether
In (2), \(\widetilde O\) hides only factors polynomial in \(\log n\) as \(n\to\infty\).
Source
Gavinsky and Ito explicitly ask for a \(\widetilde O(\sqrt n)\) query algorithm for all graphs in Section 6 of [GI12]. Their Definition 1 fixes the known-graph, marked-vertex oracle model.
Progress
Reports do not certify correctness or automatically change the problem's status. Progress policy.
Gavinsky and Ito give an \(O(\sqrt n+\sqrt{\alpha^*(G)})\) query algorithm, where \(\alpha^*(G)\) is the maximum sum of vertex degrees over an independent set (Theorem 1) [GI12]. Their Corollary 2 gives \(O(\sqrt{n\log n})\) queries with high probability over a random graph with independently sampled edges, for any choice of edge probability. This result for typical graphs does not give the target bound for every graph.
Cornelissen, Gilani, Kintali, Le Gall, Patro, and Zhou report an algorithm using \(\widetilde O(n^{11/17})\) queries for arbitrary graphs and a lower bound of \(\Omega(\sqrt{n\log n})\) for a family of graphs (Theorems 1.1 and 6.1, preprint version 1) [CGKLPZ26]. Both bounds concern queries to marked-vertex bits, with the graph known for free. The lower bound excludes \(O(\sqrt n)\) queries in general, but is compatible with the polylogarithmic factors allowed in (2).
Comment
The remaining question is whether the upper bound can be reduced to \(\widetilde O(\sqrt n)\), or whether some graph family requires more than \(\sqrt n\) times every fixed power of \(\log n\) queries. Graph Collision here is a query problem with a known graph. It is distinct from triangle finding with oracle access to unknown edges, and its query bound does not assert a matching running time.
References
- [GI12]
- Dmitry Gavinsky and Tsuyoshi Ito, “A quantum query algorithm for the graph collision problem,” preprint (2012).arXiv
- [CGKLPZ26]
- Arjan Cornelissen, Amin Shiraz Gilani, Shiva Kintali, François Le Gall, Subhasree Patro, and Xingyu Zhou, “Breaking the quantum barriers for Graph Collision,” preprint (2026).arXiv