2026-07-22T18:58:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7013 2024-03-06T10:39:10Z ddc:004 open_access

Extended Learning Graphs for Triangle Finding Carette, Titouan Laurière, Mathieu Magniez, Frédéric Quantum query complexity learning graphs triangle finding 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(n^(5/4)) without any of the extra logarithmic factors present in the previous algorithm of Le Gall [FOCS'14]. For sparse graphs with m >= n^(5/4) edges, we get a query complexity of O(n^(11/12) m^(1/6) sqrt(log n)), which is better than the one obtained by Le Gall and Nakajima [ISAAC'15] when m >= n^(3/2). We also obtain an algorithm with query complexity O(n^(5/6) (m log n)^(1/6) + d_2 sqrt(n)) where d_2 is the variance 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 based on the MNRS quantum walk framework [SICOMP'11]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Titouan Carette and Mathieu Laurière and Frédéric Magniez 2017 Is Part Of LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2017.20 urn:nbn:de:0030-drops-70132 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.20 eng https://creativecommons.org/licenses/by/3.0/legalcode