Quantum Algorithm for Triangle Finding in Sparse Graphs

摘要

This paper presents a quantum algorithm for triangle finding over sparse graphs that improves over the previous best quantum algorithm for this task by Buhrman et al. [SIAM Journal on Computing, 2005]. Our algorithm is based on the recent O(n~(5/4))-query algorithm given by Le Gall [FOCS 2014] for triangle finding over dense graphs (here n denotes the number of vertices in the graph). We show in particular that triangle finding can be solved with O(n~(5/4-∈)) queries for some constant ∈ > 0 whenever the graph has at most O(n~(2-c)) edges for some constant c > 0.