Quantum query complexity of Graph Collision

Unsolved ID op_39721600d81c6992 Last edited 6 November 2026
Edit

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

\begin{equation} f_G(x)=\bigvee_{\{u,v\}\in E}(x_u\wedge x_v). \tag{1} \end{equation}

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

\begin{equation} Q_{\mathrm{GC}}(n)=\widetilde O(\sqrt n). \tag{2} \end{equation}

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

Cite this problem

Please also cite the primary sources listed under References. Cite this page for the statement, status, and stable identifier.

BibTeX

@incollection{qiqcop_op_39721600d81c6992,
  title = {Quantum query complexity of Graph Collision},
  booktitle = {Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo)},
  year = {2026},
  howpublished = {\url{https://qiqc-op.com/problem/op_39721600d81c6992/}},
  note = {Stable ID op_39721600d81c6992; status: Unsolved; accessed 2026-11-06}
}

Plain text

“Quantum query complexity of Graph Collision,” Quantum Information and Quantum Computation Open Problem Zoo (QIQCOP Zoo), https://qiqc-op.com/problem/op_39721600d81c6992/, ID op_39721600d81c6992, accessed 2026-11-06.

Share this problem

Permanent link

Identifiers

op_39721600d81c6992
01M6QPWWVNB3XX451C81W80JWR