Skip to Main content Skip to Navigation
Journal articles

Extended Learning Graphs for Triangle Finding

Abstract : 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].
Document type :
Journal articles
Complete list of metadata
Contributor : Frédéric Magniez Connect in order to contact the contributor
Submitted on : Tuesday, November 5, 2019 - 8:41:36 PM
Last modification on : Tuesday, September 6, 2022 - 1:27:24 PM

Links full text



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



Record views