Research indexPreprint
Quantum Algorithm for Triangle Finding in Sparse Graphs
Le Gall, Nakajima
arXiv (Cornell University)24 Jul 2015Open access
NobleIDark:/48914/w1/20260521/BB613AF9DOI10.48550/arxiv.1507.06878
Quantum Algorithm for Triangle Finding in Sparse Graphs
Le Gall, Nakajima · arXiv (Cornell University) · 2015
NobleIDark:/48914/w1/20260521/BB613AF9DOI10.48550/arxiv.1507.06878
Free to read at the publisher
You can read the abstract here, or the full text at the publisher.
Abstract
This paper presents a quantum algorithm for triangle finding over sparse graphs that improves over the previous best quantum algorithm for this task by Buhrman et al. [SIAM Journal on Computing, 2005]. Our algorithm is based on the recent $\tilde O(n^{5/4})$-query algorithm given by Le Gall [FOCS 2014] for triangle finding over dense graphs (here $n$ denotes the number of vertices in the graph). We show in particular that triangle finding can be solved with $O(n^{5/4-ε})$ queries for some constant $ε>0$ whenever the graph has at most $O(n^{2-c})$ edges for some constant $c>0$.