Quantum analysis finds stronger limits on detecting triangles in graphs

A Quantum Lower Bound for Triangle Finding

Data Structures and Algorithms

Summary

Finding triangles in networks is an important problem in computer science and can be solved faster with quantum computers than classical ones. Before, experts knew quantum algorithms could do this with about N to the 1.25 steps, and they also knew there was a simple limit of N steps below which no quantum method could go. The authors showed there is actually a higher lower limit, at about N to the 1.08 steps, meaning quantum computers need at least that many questions to detect triangles. Their work advances understanding of quantum limits and applies to finding any fixed pattern that isn't bipartite in graphs.

What this means in practice

  • For quantum algorithm designers: Set realistic expectations for the minimum number of queries needed when designing quantum algorithms for detecting triangles and similar patterns in graphs.
  • For quantum hardware engineers: Understand the fundamental limits on query efficiency that influence hardware resource allocation for graph pattern detection tasks on quantum devices.

A theory result. No direct application yet.

Authors

Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou

Abstract

Triangle finding is a fundamental problem in graph theory that has played a central role in the development of quantum algorithmic techniques. For $N$-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from $O(N^{3/2})$ to $O(N^{5/4})$. However, the best known lower bound has remained the elementary $Ω(N)$ bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that $Ω(N^{13/12})$ queries are necessary. Our result also implies the same lower bound for triangle detection and for detecting every fixed connected non-bipartite graph. The proof builds on the compressed oracle approach of Zhandry and the transfer approaches of Belovs. It compares the computation on graphs with a planted triangle to the computation on random graphs conditioned to be triangle-free, through a map on the input registers that almost commutes with every query. We average over local changes to the input while preserving its distribution, through a procedure known as conditional resampling. Our main technical contribution is a set of estimates that let us control the query error under this averaging, despite the dependence introduced by conditioning a dense graph to be triangle-free.