Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments

In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity Õ(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 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 O(n 9/7 / √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 v(n 9/7 / √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.

Authors

• François Le Gall

Keywords

• Complexity theory
• Search problems
• Upper bound
• Algorithm design and analysis
• Quantum computing
• Quantum mechanics
• Computer science
• Quantum Algorithms
• Combinatorial Arguments
• Nodes In The Graph
• Vertices
• Graph Learning
• Unweighted Graph
• High Probability
• Complex Problems
• Undirected
• Previous Paragraph
• Complex Class
• Matrix Multiplication
• Variable Costs
• Algorithm For Problem
• Binary String
• Determination Of Complexes
• Setup Cost
• Search Problem
• Boolean Function
• Triangle Edges
• Fraction Of States
• Additional Queries
• Algorithmic Techniques
• triangle finding
• query complexity