by Carette, Titouan, Laurière, Mathieu and Magniez, Frédéric
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(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$\backslash$ge n\^\5/4\$}{\$ edges, we get a query complexity of $}{\$O(n\^\11/12\m\^\1/6\$\backslash$sqrt\$\backslash$log n\)$}{\$, which is better than the one obtained by Le Gall and Nakajima $[$ISAAC’15$]$ when $}{\$m $\backslash$ge n\^\3/2\$}{\$. We also obtain an algorithm with query complexity $}{\$\O\(n\^\5/6\(m$\backslash$log n)\^\1/6\+d_2$\backslash$sqrt\n\)$}{\$ where $}{\$d_2$}{\$ 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$]$.
Reference:
Extended Learning Graphs for Triangle Finding (Carette, Titouan, Laurière, Mathieu and Magniez, Frédéric), In Algorithmica, volume 82, 2020.
Bibtex Entry:
@article{Carette:2020bf,
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(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{$\backslash$}ge n\^{}{\{}5/4{\}}{\$}{\$} edges, we get a query complexity of {\$}{\$}O(n\^{}{\{}11/12{\}}m\^{}{\{}1/6{\}}{$\backslash$}sqrt{\{}{$\backslash$}log n{\}}){\$}{\$}, which is better than the one obtained by Le Gall and Nakajima {$[$}ISAAC’15{$]$} when {\$}{\$}m {$\backslash$}ge n\^{}{\{}3/2{\}}{\$}{\$}. We also obtain an algorithm with query complexity {\$}{\$}{\{}O{\}}(n\^{}{\{}5/6{\}}(m{$\backslash$}log n)\^{}{\{}1/6{\}}+d{\_}2{$\backslash$}sqrt{\{}n{\}}){\$}{\$} where {\$}{\$}d{\_}2{\$}{\$} 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{$]$}.},
author = {Carette, Titouan and Laurière, Mathieu and Magniez, Frédéric},
da = {2020/04/01},
date-added = {2021-03-05 17:30:11 +0100},
date-modified = {2021-03-05 17:30:11 +0100},
doi = {10.1007/s00453-019-00627-z},
id = {Carette2020},
isbn = {1432-0541},
journal = {Algorithmica},
number = {4},
pages = {980--1005},
title = {Extended Learning Graphs for Triangle Finding},
ty = {JOUR},
url = {https://doi.org/10.1007/s00453-019-00627-z},
volume = {82},
year = {2020},
bdsk-url-1 = {https://doi.org/10.1007/s00453-019-00627-z}}