Improved Quantum Algorithm for Triangle Finding via Combinatorial Arguments
arXiv:1407.0085 · doi:10.1109/FOCS.2014.31
Abstract
In this paper we present a quantum algorithm solving the triangle finding problem in unweighted graphs with query complexity , where denotes the number of vertices in the graph. This improves the previous upper bound 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 queries. Our result also illustrates some limitations of the non-adaptive learning graph approach used to obtain the previous upper bound since, even over unweighted graphs, any quantum algorithm for triangle finding obtained using this approach requires 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.
arXiv comment17 pages, to appear in FOCS'14; v2: minor corrections
References in corpus (9)
- Quantum Amplitude Amplification and Estimation
- Search via Quantum Walk
- Quantum Counting
- Negative weights make adversaries stronger
- Quantum Search on Bounded-Error Inputs
- Quantum Algorithms for Element Distinctness
- Span programs and quantum query complexity: The general adversary bound is nearly tight for every boolean function
- Nested Quantum Walks with Quantum Data Structures
- On the Quantum Query Complexity of Detecting Triangles in Graphs
Cited by in corpus (15)
- 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
- Circuit Design for Clique Problem and Its Implementation on Quantum Computer
- Quantum Algorithm for Triangle Finding in Sparse Graphs
- 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
- Quantum Algorithms for Finding Constant-sized Sub-hypergraphs
- 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