Quantum query complexity of Graph Collision
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\).