Quantum Algorithms for the Triangle Problem

Abstract

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 algorithm uses combinatorial ideas with Grover Search and makes $\tilde{O}(n^{10/7})$ queries. The second algorithm uses $\tilde{O}(n^{13/10})$ queries, and it is based on a design concept of Ambainis~\cite{amb04} that incorporates the benefits of quantum walks into Grover search~\cite{gro96}. The first algorithm uses only $O(\log n)$ qubits in its quantum subroutines, whereas the second one uses O(n) qubits. The Triangle Problem was first treated in~\cite{bdhhmsw01}, where an algorithm with $O(n+\sqrt{nm})$ query complexity was presented, where $m$ is the number of edges of $G$.

Several typos are fixed, and full proofs are included. Full version of the paper accepted to SODA'05

References in corpus (3)

• Hidden Subgroup States are Almost Orthogonal
• Bounds for Small-Error and Zero-Error Quantum Algorithms
• On the Quantum Query Complexity of Detecting Triangles in Graphs

Cited by in corpus (9)

• Efficient Distributed Quantum Computing
• Quipper: A Scalable Quantum Programming Language
• An Introduction to Quantum Programming in Quipper
• Quantum search algorithms
• Coins Make Quantum Walks Faster
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
• Robust Quantum Circuit for Clique Problem with Intermediate Qudits
• Quantum search with variable times