Breaking the quantum barriers for Graph Collision

Abstract: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 $\Omega(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 size $q$, contrasting a known $\Omega(n^{2/3})$ lower bound for such problems with large alphabet sizes. We complement these algorithms with an $\Omega(\sqrt{n\log n})$ quantum query lower bound for graph collision, exceeding the $O(\sqrt n)$ certificate complexity barrier for the positive adversary method.

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

arXiv:2611.05356 [quant-ph]

(or arXiv:2611.05356v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2611.05356 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.