A team of researchers has lowered the quantum query complexity of the graph collision problem, a classic challenge in quantum computing in which, given a known graph on n vertices and query access to the bits marking the vertices, one must decide whether an edge exists with both endpoints marked. The work refutes the conjecture that any bounded-error quantum algorithm would require Ω(n²ᐟ³) queries, and instead presents an algorithm that solves the problem with Õ(n⁹²ᐟ¹³⁹) queries.

The advance is consolidated with a refined version of the method that further reduces the number of queries to Õ(n¹¹ᐟ¹⁷). In addition, the authors extend the result to all (partial) Boolean output functions with positive certificate complexity at most 2 and alphabet size q, obtaining a bound of Õ((nq)¹¹ᐟ¹⁷). This contrasts with the known Ω(n²ᐟ³) lower bound for such problems with large alphabet sizes, suggesting that the previous barrier was not achievable in the quantum regime.

The work is complemented by a new quantum lower bound of Ω(√(n log n)) queries for the graph collision problem. This limit is notable because it exceeds the positive certificate complexity barrier, O(√n), which the positive adversary method cannot surpass by construction. The lower bound therefore places the problem in an intermediate zone between what standard techniques promised and what the algorithms proposed here allow.

The results open up several lines of work. It remains to be seen whether the Õ(n¹¹ᐟ¹⁷) upper bound can be brought closer to the new lower bound, or whether there is an intrinsic barrier that prevents closing the gap. It also remains to explore to what extent the techniques developed can be applied to other query problems with small certificates, a terrain where standard quantum tools have so far found clear limits.