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(n^{2-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 $\widetilde O(n^{2-2/k})$.
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=maxk(k+1)(m+1)k2−2(m+1),k(d+1)(m−d+2)2k−d−3. The previous best algorithm of Magniez et al. had complexity O(n2−2/k).
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.
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.
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.
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 making O(n35/27) queries. For the problem of determining if an operation ∘: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, 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.