Quantum algorithms for the triangle problem

By Frédéric Magniez, Miklos Santha, Mario Szegedy. ACM-SIAM Symposium on Discrete Algorithms, 2003

379 citations recorded by the source corpus.

We present two new quantum algorithms that either find a triangle (a copy of K<inf>3</inf>) 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 new 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 + √n|E|) query complexity was presented (here |E| is the number of edges of G).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/e089e3aadb28d76194927dce8b0b41364e6934f1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Universal computation by quantum walk. (2008, background): “By exploiting interference effects, quantum walks can outperform random walks at certain computational tasks: there are black-box problems for which quantum walk provides an exponential speedup over classical computation [4, 5], and many quantum walk algorithms achieve polynomial speedup over classi”
Subcubic Equivalences between Path, Matrix and Triangle Problems (2010, methodology): “The first time bound of Theorem I.5 is obtained by simply applying the best known quantum algorithm for triangle [ 23 ] to our generic matrix product to triangle detection reduction, already improving the previous best [9] output-sensitive quantum algorithm for BMM.”
Search via quantum walk (2006, methodology): “culties in the analysis of the earlier approaches, and leads to improvements in various aspects of algorithms for Element Distinctness, Matrix Product Veri.cation, Triangle Finding, and Group Commutativity.”
On the Relationship Between Continuous- and Discrete-Time Quantum Walk (2008, methodology): “This approach was later generalized [35, 50] and applied to quantum algorithms for triangle finding [36], checking matrix multiplication [10], and testing group commutativity [34].”
Quipper: a scalable quantum programming language (2013, background): “P L] 1 1 A pr 2 Keywords Quipper; Quantum Programming Languages Categories and Subject Descriptors D.3.1 [Programming Languages]: Formal Definitions and Theory”
Quantum Walk Based Search Algorithms (2008, methodology): “The frameworks of Ambainis and Szegedy were used in various contexts to ﬁnd algorithms with substantial complexity gains over simple Grover search [26,12,23,15].”
Quantum walks: a comprehensive review (2012, methodology): “Additionally, another quantum algorithm, based on Grover’s search quantum algorithm [180], is presented in [311] for solving the same triangle problem.”