arXiv:quant-ph/0310134

An $O(n^{1.3})$ Quantum Algorithm for the Triangle Problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

Published Oct 21, 2003• 23 citations

Abstract

We present a new quantum algorithm that either finds a triangle (a copy of K3) in an undirected graph G on n nodes, or it outputs “reject ” if G is triangle free. The algorithm uses O(n 1.3) queries, and it is based on a new design concept of Ambainis [Amb03] that incorporates the benefits of quantum walks into Grover search [Gro96]. The algorithm both improves on, and is simpler than a recent algorithm of Szegedy [Sze03] which has Õ(n10/7) query complexity. The Triangle Problem was first treated in [BDH + 01], where an algorithm with O ( √ n|E|) query complexity was presented (here |E | is the number of edges of G). 1

Related papers

Quantum algorithms for the triangle problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

Symposium on Discrete AlgorithmsJan 23, 200583 citations

Quantum Algorithms for the Triangle Problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

SIAM Journal on ComputingJan 1, 2007311 citations

Quantum algorithms for subset finding

Andrew M. Childs, Eisenberg, J M

Nov 6, 200353 citations

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

ACM-SIAM Symposium on Discrete Algorithms (SODA)Jan 6, 201333 citations

On the Quantum Query Complexity of Detecting Triangles in Graphs

Márió Szegedy

arXiv:quant-ph/0310107Oct 16, 200322 citations

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

arXiv:1210.1014Oct 3, 20120 citations

arXiv:quant-ph/0310134

An $O(n^{1.3})$ Quantum Algorithm for the Triangle ProblemAn $O(n^{1.3})$ Quantum Algorithm for the Triangle Problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

Published Oct 21, 2003• 23 citations

arXiv HTML PDF

Abstract

Related papers

Quantum algorithms for the triangle problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

We present two new quantum algorithms that either find a triangle (a copy of K3) 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 Õ(n10/7) queries. The second algorithm uses Õ(n13/10) queries, and it is based on a design concept of Ambainis [6] that incorporates the benefits of quantum walks into Grover search [18]. 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 [12], where an algorithm with O(n + √ nm) query complexity was presented, where m is the number of edges of G.We present two new quantum algorithms that either find a triangle (a copy of K3) 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 Õ(n10/7) queries. The second algorithm uses Õ(n13/10) queries, and it is based on a design concept of Ambainis [6] that incorporates the benefits of quantum walks into Grover search [18]. 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 [12], where an algorithm with O(n + √ nm) query complexity was presented, where m is the number of edges of G.

Symposium on Discrete AlgorithmsJan 23, 200583 citations

Quantum Algorithms for the Triangle Problem

Frédéric Magniez, Miklós Sántha, Márió Szegedy

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

SIAM Journal on ComputingJan 1, 2007311 citations

Quantum algorithms for subset finding

Andrew M. Childs, Eisenberg, J M

Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.Recently, Ambainis gave an O(N^(2/3))-query quantum walk algorithm for element distinctness, and more generally, an O(N^(L/(L+1)))-query algorithm for finding L equal numbers. We point out that this algorithm actually solves a much more general problem, the problem of finding a subset of size L that satisfies any given property. We review the algorithm and give a considerably simplified analysis of its query complexity. We present several applications, including two algorithms for the problem of finding an L-clique in an N-vertex graph. One of these algorithms uses O(N^(2L/(L+1))) edge queries, and the other uses \\tilde{O}(N^((5L-2)/(2L+4))), which is an improvement for L <= 5. The latter algorithm generalizes a recent result of Magniez, Santha, and Szegedy, who considered the case L=3 (finding a triangle). We also pose two open problems regarding continuous time quantum walk and lower bounds.

Nov 6, 200353 citations

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|S|3/2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S is associative, we give an algorithm making O(|S|10/7) queries, the first improvement to the trivial O(|S|3/2) application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work [9], the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

ACM-SIAM Symposium on Discrete Algorithms (SODA)Jan 6, 201333 citations

On the Quantum Query Complexity of Detecting Triangles in Graphs

Márió Szegedy

We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on $n$ nodes can be done using $O(n^{1+{3\over 7}}\log^{2}n)$ quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of $O(n^{1+{1\over 2}})$ .We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on $n$ nodes can be done using $O(n^{1+{3\over 7}}\log^{2}n)$ quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of $O(n^{1+{1\over 2}})$.

arXiv:quant-ph/0310107Oct 16, 200322 citations

Improved Quantum Query Algorithms for Triangle Finding and Associativity Testing

Troy Lee, Frédéric Magniez, Miklós Sántha

We show that the quantum query complexity of detecting if an $n$ -vertex graph contains a triangle is $O(n^{9/7})$ . This improves the previous best algorithm of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an operation $\circ : S \times S \rightarrow S$ is associative, we give an algorithm making $O(|S|^{10/7})$ queries, the first improvement to the trivial $O(|S|^{3/2})$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.We show that the quantum query complexity of detecting if an $n$-vertex graph contains a triangle is $O(n^{9/7})$. This improves the previous best algorithm of Belovs making $O(n^{35/27})$ queries. For the problem of determining if an operation $\circ : S \times S \rightarrow S$ is associative, we give an algorithm making $O(|S|^{10/7})$ queries, the first improvement to the trivial $O(|S|^{3/2})$ application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.

arXiv:1210.1014Oct 3, 20120 citations

O(n^{1.3})

Quantum Algorithm for the Triangle Problem

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.

We show that in the quantum query model the complexity of detecting a triangle in an undirected graph on

n

nodes can be done using

O(n^{1+{3\over 7}}\log^{2}n)

quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of

O(n^{1+{1\over 2}})

We show that the quantum query complexity of detecting if an

n

-vertex graph contains a triangle is

O(n^{9/7})

. This improves the previous best algorithm of Belovs making

O(n^{35/27})

queries. For the problem of determining if an operation

\circ : S \times S \rightarrow S

is associative, we give an algorithm making

O(|S|^{10/7})

queries, the first improvement to the trivial

O(|S|^{3/2})

application of Grover search. Our algorithms are designed using the learning graph framework of Belovs. We give a family of algorithms for detecting constant-sized subgraphs, which can possibly be directed and colored. These algorithms are designed in a simple high-level language; our main theorem shows how this high-level language can be compiled as a learning graph and gives the resulting complexity. The key idea to our improvements is to allow more freedom in the parameters of the database kept by the algorithm. As in our previous work, the edge slots maintained in the database are specified by a graph whose edges are the union of regular bipartite graphs, the overall structure of which mimics that of the graph of the certificate. By allowing these bipartite graphs to be unbalanced and of variable degree we obtain better algorithms.