Quantum Algorithms for the Triangle Problem

Original · EN

We present two new quantum algorithms that either find a triangle (a copy of K₃) in an undirected graph G on n nodes, or reject if G is triangle free. The first algorithm uses combinatorial ideas with Grover Search and makes O(n¹⁰/⁷) queries. The second algorithm uses O(n¹³/¹⁰) queries, and it is based on a design concept of Ambainis amb04 that incorporates the benefits of quantum walks into Grover search gro96. The first algorithm uses only O(n) qubits in its quantum subroutines, whereas the second one uses O(n) qubits. The Triangle Problem was first treated in bdhhmsw01, where an algorithm with O(n+√nm) query complexity was presented, where m is the number of edges of G.