Quantum Algorithms for the Triangle Problem

Frederic Magniez, Miklos Santha, Mario Szegedy

We present two new quantum algorithms that either find a triangle (a copy of $K_3$) in an undirected graph $G$ on $n$ nodes, or reject if $G$ is triangle free. The first algorith…