Quantum Algorithms for the Triangle Problem

Details Quantum Algorithms for the Triangle Problem Quantum Algorithms for the Triangle Problem

2003-10-21

arxiv.org/abs/quant-ph/0310134v3

Physics

Quantum Physics

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

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Quantum Algorithms for the Triangle Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Quantum Algorithms for the Triangle Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Quantum Algorithms for the Triangle Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-510298