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 metadatas

https://hal-cnrs.archives-ouvertes.fr/hal-02349981
Contributor : Frédéric Magniez <>
Submitted on : Tuesday, November 5, 2019 - 8:41:36 PM
Last modification on : Friday, November 8, 2019 - 10:33:02 AM

Links full text

Identifiers

Citation

Titouan Carette, Mathieu Laurière, Frédéric Magniez. Extended Learning Graphs for Triangle Finding. Algorithmica, Springer Verlag, In press, ⟨10.1007/s00453-019-00627-z⟩. ⟨hal-02349981⟩

Share

Metrics

Record views

16