Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1210.1014 · Algorithmica

Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing

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

Published Oct 26, 2015• 29 citations
arXivHTMLPDF
DOI
10.1007/s00453-015-0084-9

Related papers

Quantum Associative Memory with Improved Distributed Queries

J.-P. Tchapet Njafa, S. G. Nana Engo, P. Woafo

arXiv:1204.6657•International Journal of Theoretical Physics•Jun 29, 2012•11 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.

ACM-SIAM Symposium on Discrete Algorithms (SODA)•Jan 6, 2013•37 citations

Quantum Algorithm for Triangle Finding in Sparse Graphs

François Le Gall, Shogo Nakajima

Lecture notes in computer science•Jan 1, 2015•3 citations

Quantum Algorithm for Triangle Finding in Sparse Graphs

François Le Gall, Shogo Nakajima

arXiv:1507.06878•Algorithmica•Jan 5, 2017•14 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}})$.

arXiv:quant-ph/0310107•Oct 16, 2003•27 citations

Quantum Algorithm for Triangle Finding in Sparse Graphs

フランソワ ルガル, 章吾 中島

IEICE technical report. Speech•Sep 25, 2015•0 citations
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 in the quantum query model the complexity of detecting a triangle in an undirected graph on nnn nodes can be done using O(n1+37log⁡2n)O(n^{1+{3\over 7}}\log^{2}n)O(n1+73​log2n) quantum queries. The same complexity bound applies for outputting the triangle if there is any. This improves upon the earlier bound of O(n1+12)O(n^{1+{1\over 2}})O(n1+21​).