Improved quantum query algorithms for triangle finding and associativity testing

DOI10.1137/1.9781611973105.107MaRDI QIDQ5741816zbMATH OpenOpenAlexFDO

Authors Troy Lee, Frédéric Magniez, Miklos Santha

Publication date 15 May 2019

Published in Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1014

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Quantum algorithms and complexity in the theory of computing (68Q12)

Abstract: 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:SimesSightarrowS$ 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.

Recommendations

• Improved quantum query algorithms for triangle detection and associativity testing
• Extended learning graphs for triangle finding
• Extended Learning Graphs for Triangle Finding
• Quantum Algorithms for the Triangle Problem
• Quantum algorithms for the triangle problem

Cited in

(14)

• Fooling views: a new lower bound technique for distributed computations under congestion
• Extended learning graphs for triangle finding
• Quantum algorithms for learning symmetric juntas via the adversary bound
• Three-state quantum walk on the Cayley graph of the dihedral group
• Quantum query complexity of constant-sized subgraph containment
• Quantum algorithms for the triangle problem
• On the power of non-adaptive learning graphs
• Improved quantum query algorithms for triangle detection and associativity testing
• Quantum Algorithms for the Triangle Problem
• Learning graph based quantum query algorithms for finding constant-size subgraphs
• Symmetries, graph properties, and quantum speedups
• Derandomization of quantum algorithm for triangle finding
• Parameterized quantum query algorithms for graph problems
• Quantum algorithms for finding constant-sized sub-hypergraphs

This page was built for publication: Improved quantum query algorithms for triangle finding and associativity testing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5741816)