We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether a n-vertex graph contains a triangle, clique or star of some size. For a general subgraph H with k vertices, we show that H containment can be solved with quantum query complexity [Formula: see text], with g(H) a strictly positive function of H. This is better than Õ(n 2-2/k ) by Magniez et al. This result is obtained in the learning graph model of Belovs.
We study the quantum query complexity of constant-sized subgraph containment. Such problems include determining whether a n-vertex graph contains a triangle, clique or star of some size. For a general subgraph H with k vertices, we show that H containment can be solved with quantum query complexity [Formula: see text], with g(H) a strictly positive function of H. This is better than Õ(n 2-2/k ) by Magniez et al. This result is obtained in the learning graph model of Belovs.
Subgraph detection asks whether an n-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph H. We prove the first unconditional superlinear lower bounds on the bounded-error quantum query complexity of this problem, answering a longstanding open question. A copy of H is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds.
For every fixed r≥4, detecting the clique Kr requires nλr−o(1) queries, where λ4=19/18, the exponents λr increase strictly with r, and λr≥2−42/r+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph H with chromatic number c≥4. These bounds approach quadratic as c grows: for sufficiently large c, detection requires n2−O(loglogc/c)−o(1) queries. Chromatic number alone does not characterize the quantum query complexity of subgraph detection: we show that detecting the complete bipartite graph Kr,r requires nβr−o(1) queries, where β10=181/180 and βr≥2−O(1/r).
Our main technical result is a lower bound for finding an all-ones certificate from a known family when the input bits are sampled independently. Its proof combines Zhandry's compressed oracle [CRYPTO 2019] with conditioning on a randomly planted certificate, adapting an argument of Belovs [FOCS 2026]. Our hard instances are built from graphs containing many copies of the desired subgraph with limited overlap. For cliques, we use a construction of Gowers and Janzer [CPC 2021]; for complete bipartite graphs, we use a random construction.
Let H be a fixed k-vertex graph with m edges and minimum degree d>0. We use the learning graph framework of Belovs to show that the bounded-error quantum query complexity of determining if an n-vertex graph contains H as a subgraph is O(n2−2/k−t), where $ t = \max{\frac{k^2- 2(m+1)}{k(k+1)(m+1)}, \frac{2k - d - 3}{k(d+1)(m-d+2)}}$. The previous best algorithm of Magniez et al. had complexity O(n2−2/k).
The quantum query complexity of subgraph-containment problems, which ask whether a given subgraph H is present in an input graph G, has been the subject of considerable study. However, even for relatively simple subgraphs, such as paths and cycles, a complete understanding of their query complexities remains elusive. In this work, we consider several variants of path- and cycle-containment problems in the adjacency matrix model, where we search for paths or cycles of constant length k. We compare the settings where the graphs are directed or undirected, where the goal is to detect or find the existence of a path/cycle, and where the path/cycle we are looking for has length exactly k, or at most k. We also consider several promise versions of these problems, where we suppose that the input graph has a certain structure. We characterize the relative difficulty of these variants of the path/cycle-containment problems, by relating them to one another using randomized reductions, and grouping them into equivalence classes.
When we restrict our attention to path-containment problems, we get a dichotomy result. Some of the path-containment problems can be solved using a linear number of queries, and all the others are equivalent to one another (and additionally to several cycle-containment problems) under randomized reductions, up to constant overhead. For the latter equivalence class, we prove a novel quantum-walk-based algorithm that achieves query complexity O(n3/2−αk), where αk∈Θ(c−k) and c=3+17/2≈1.33, beating the previous best upper bound O(n3/2) on its query complexity. We also provide a conditional lower bound based on the graph-collision problem, which implies that this equivalence class does not admit linear-query quantum algorithms unless graph collision admits an O(n) query algorithm.
We show that the quantum query complexity of detecting if an n-vertex graph contains a triangle is O(n9/7). This improves the previous best algorithm of Belovs [2] making O(n35/27) queries. For the problem of determining if an operation o : S × S → S 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 [9], 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.
We study the quantum query complexity of several basic graph problems. 1) We prove a tight Θ(n3/2) bound for finding a maximum-out-degree vertex in an n-vertex tournament, resolving a conjecture of Mande, Paraashar, and Saurabh [FSTTCS'23]. 2) Using the same proof idea, we give a direct proof that finding a maximum-degree vertex in an n-vertex undirected graph requires Θ(n3/2) quantum queries, a bound implicit in the work of Apers and Lee [CCC'21]. Both lower bounds above hold even for computing only the maximum degree or maximum out-degree. 3) We also study Maximum (k,n−k)-Cut, which asks for the largest cut with one side of size k. For every constant k≥1, we give an O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)-Cut involving k-Graph Collision, which asks whether the marked vertices of a known graph contain a k-clique. For k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for k-Graph Collision, the reduction yields a lower bound matching our upper bound above.
In this paper, we consider the parameterized quantum query complexity for graph problems. We design parameterized quantum query algorithms for k-vertex cover and k-matching problems, and present lower bounds on the parameterized quantum query complexity. Then, we show that our quantum query algorithms are optimal up to a constant factor when the parameters are small. Our main results are as follows. Parameterized quantum query complexity of vertex cover. In the k-vertex cover problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a vertex cover of size at most k. We show that the quantum query complexity of the k-vertex cover problem is O(√kn + k^{3/2}√n) in the adjacency matrix model. For the design of the quantum query algorithm, we use the method of kernelization, a well-known tool for the design of parameterized classical algorithms, combined with Grover’s search. Parameterized quantum query complexity of matching. In the k-matching problem, we are given an undirected graph G with n vertices and an integer k, and the objective is to determine whether G has a matching of size at least k. We show that the quantum query complexity of the k-matching problem is O(√kn + k²) in the adjacency matrix model. We obtain this upper bound by using Grover’s search carefully and analyzing the number of Grover’s searches by making use of potential functions. We also show that the quantum query complexity of the maximum matching problem is O(√pn + p²) where p is the size of the maximum matching. For small p, it improves known bounds Õ(n^{3/2}) for bipartite graphs [Blikstad-v.d.Brand-Efron-Mukhopadhyay-Nanongkai, FOCS 2022] and O(n^{7/4}) for general graphs [Kimmel-Witter, WADS 2021]. Lower bounds on parameterized quantum query complexity. We also present lower bounds on the quantum query complexities of the k-vertex cover and k-matching problems. The lower bounds prove the optimality of the above parameterized quantum query algorithms up to a constant factor when k is small. Indeed, the quantum query complexities of the k-vertex cover and k-matching problems are both Θ(√k n) when k = O(√n) and k = O(n^{2/3}), respectively.