Quantum Algorithms for the Triangle Problem
| dc.creator | Magniez, Frederic | |
| dc.creator | Santha, Miklos | |
| dc.creator | Szegedy, Mario | |
| dc.date | 2003-10-21 | |
| dc.date | 2005-12-14 | |
| dc.date.accessioned | 2026-07-07T06:36:28Z | |
| dc.date.available | 2026-07-07T06:36:28Z | |
| dc.description | 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$. | |
| dc.description | Several typos are fixed, and full proofs are included. Full version of the paper accepted to SODA'05 | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0310134 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0310134 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/100092 | |
| dc.subject | Quantum Physics | |
| dc.title | Quantum Algorithms for the Triangle Problem | |
| dc.type | text |