NobleBlocks

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

Free to read at the publisher

You can read the abstract here, or the full text at the publisher.

Read 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$.

Discussion

Topics

More

Suggest a correction or report