HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 : Friday, February 4, 2022 - 3:33:14 AM

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