Extended Learning Graphs for Triangle Finding - Archive ouverte HAL Access content directly
Journal Articles Algorithmica Year : 2020

Extended Learning Graphs for Triangle Finding

(1) , (2) , (3)


We present new quantum algorithms for Triangle Finding improving its best previously known quantum query complexities for both dense and sparse instances. For dense graphs on n vertices, we get a query complexity of O(n5/4) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS’14]. For sparse graphs with m≥n5/4 edges, we get a query complexity of O(n11/12m1/6logn−−−−√), which is better than the one obtained by Le Gall and Nakajima [ISAAC’15] when m≥n3/2. We also obtain an algorithm with query complexity O(n5/6(mlogn)1/6+d2n−−√) where d2 is the quadratic mean of the degree distribution. Our algorithms are designed and analyzed in a new model of learning graphs that we call extended learning graphs. In addition, we present a framework in order to easily combine and analyze them. As a consequence we get much simpler algorithms and analyses than previous algorithms of Le Gall et al. based on the MNRS quantum walk framework [SICOMP’11].

Dates and versions

hal-02349981 , version 1 (05-11-2019)



Titouan Carette, Mathieu Laurière, Frédéric Magniez. Extended Learning Graphs for Triangle Finding. Algorithmica, 2020, 82 (4), pp.980-1005. ⟨10.1007/s00453-019-00627-z⟩. ⟨hal-02349981⟩
51 View
0 Download



Gmail Facebook Twitter LinkedIn More