Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

Abstract

In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity $\tilde{O}(n^{5/4})$, where $n$ denotes the number of vertices in the graph. This improves the previous upper bound $O(n^{9/7})=O(n^{\mathrm{1.285...}})$ recently obtained by Lee, Magniez and Santha. Our result shows, for the first time, that in the quantum query complexity setting unweighted triangle finding is easier than its edge-weighted version, since for finding an edge-weighted triangle Belovs and Rosmanis proved that any quantum algorithm requires $\Omega (n^{9/7}/\sqrt{\log n})$ queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous $O(n^{9/7})$ upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires $\Omega (n^{9/7}/\sqrt{\log n})$ queries as well. To bypass the obstacles characterized by these lower bounds, our quantum algorithm uses combinatorial ideas exploiting the graph-theoretic properties of triangle finding, which cannot be used when considering edge-weighted graphs or the non-adaptive learning graph approach.

17 pages, to appear in FOCS'14; v2: minor corrections

References in corpus (1)

• On the Quantum Query Complexity of Detecting Triangles in Graphs

Cited by in corpus (14)

• Quantum algorithms: an overview
• Quantum Computing: Lecture Notes
• A Tool For Debugging Quantum Circuits
• The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
• Tight Distributed Listing of Cliques
• Finding Small and Large k-Clique Instances on a Quantum Computer
• Quantum Algorithm for Triangle Finding in Sparse Graphs
• Circuit Design for Clique Problem and Its Implementation on Quantum Computer
• Efficient quantum walk on the grid with multiple marked elements
• Exponential speedups for quantum walks in random hierarchical graphs
• Derandomization of quantum algorithm for triangle finding
• Near-Optimal Quantum Algorithms for String Problems
• Quantum Data Structure for Range Minimum Query
• Quantum Approximate Counting for Markov Chains and Application to Collision Counting