Name
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 is based on a design concept of Ambainis [in Proceedings of the $45$th IEEE Symposium on Foundations of Computer Science, 2004, pp. 22-31] that incorporates the benefits of quantum walks into Grover Search [L. Grover, in Proceedings of the Twenty-Eighth ACM Symposium on Theory of Computing, 1996, pp. 212-219]. 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 [H. Buhrman et al., SIAM J. Comput., 34 (2005), pp. 1324-1330], where an algorithm with $O(n+\sqrt{nm})$ query complexity was presented, where $m$ is the number of edges of $G$. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1137/050643684 | Symposium on Discrete Algorithms |
Keywords | Field | DocType |
quantum subroutine,quantum algorithms,grover search,combinatorial idea,computer science,siam j. comput,th ieee symposium,triangle problem,l. grover,twenty-eighth acm symposium,new quantum algorithm,quantum walk,quantum algorithm | Discrete mathematics,Graph,Binary logarithm,Quantum,Combinatorics,Theory of computing,Quantum walk,Tilde,Quantum algorithm,Qubit,Mathematics | Journal |
Volume | Issue | ISSN |
37 | 2 | 0097-5397 |
ISBN | Citations | PageRank |
0-89871-585-7 | 78 | 4.29 |
References | Authors | |
25 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Frédéric Magniez | 1 | 570 | 44.33 |
| Miklos Santha | 2 | 728 | 92.42 |
| Mario Szegedy | 3 | 3358 | 325.80 |
| MagniezFre´de´ric | 4 | 78 | 4.29 |