The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an $N$-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every $K\ge2$ and $N\ge4^{K-1}$, finds and verifies a homogeneous $K$-set using $O\!\left(2^K K\log\frac Kη\right)$ edge queries with failure probability at most $η$. At the Ramsey scale $N=2^n$, this yields a homogeneous set of order $\lfloor n/2\rfloor+1$ using $O(\sqrt N\log N\log(\log N/η))$ queries, improving on the $O(N)$ queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an $Ω(N^{1/12})$ quantum lower bound by a reduction from collision finding.
The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an $Ω(N^{1-1/\sqrt2})$ randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution $G(N,1/2)$. On that distribution a greedy quantum search uses only $\widetilde O(N^{1/4})$ queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
The constructive diagonal Ramsey problem asks, given adjacency-oracle access to an N-vertex graph, for a clique or independent set of the order guaranteed by Ramsey's theorem. We give a bounded-error quantum algorithm that, for every K≥2 and N≥4K−1, finds and verifies a homogeneous K-set using O(2KKlogηK) edge queries with failure probability at most η. At the Ramsey scale N=2n, this yields a homogeneous set of order ⌊n/2⌋+1 using O(NlogNlog(logN/η)) queries, improving on the O(N) queries of the explicit classical recursion and giving, to our knowledge, the first sublinear worst-case algorithm for the Ramsey relation. We also derive an Ω(N1/12) quantum lower bound by a reduction from collision finding.
The algorithm runs the constructive recursion over implicit candidate sets. Each set is represented by a short conjunction of adjacency constraints and sampled using capped unknown-solution quantum search, and a scale-aware concentration schedule balances estimation accuracy against the increasing cost of sampling deeper sets. We complement the upper bound with an Ω(N1−1/2) randomized lower bound, transported from the random-Painter analysis of online Ramsey numbers, which holds on the uniform distribution G(N,1/2). On that distribution a greedy quantum search uses only O(N1/4) queries, giving a provable polynomial quantum speedup for Ramsey search on random graphs. We also give an estimation-free size-biased recursion and extend it to every fixed number of edge colours.
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 are presented with a graph, G, on n vertices with m edges whose edge set is unknown. Our goal is to learn the edges of G with as few queries to an oracle as possible. When we submit a set S of vertices to the oracle, it tells us whether or not S induces at least one edge in G. This so-called OR-query model has been well studied, with Angluin and Chen giving an upper bound on the number of queries needed of O(mlogn) for a general graph G with m edges. When we allow ourselves to make *quantum* queries (we may query subsets in superposition), then we can achieve speedups over the best possible classical algorithms. In the case where G has maximum degree d and is O(1)-colorable, Montanaro and Shao presented an algorithm that learns the edges of G in at most O~(d2m3/4) quantum queries. This gives an upper bound of O~(m3/4) quantum queries when G is a matching or a Hamiltonian cycle, which is far away from the lower bound of Ω(m) queries given by Ambainis and Montanaro. We improve on the work of Montanaro and Shao in the case where G has bounded degree. In particular, we present a randomized algorithm that, with high probability, learns cycles and matchings in O~(m) quantum queries, matching the theoretical lower bound up to logarithmic factors.
The graph isomorphism problem asks whether two graphs are identical up to vertex relabeling. While the exact problem admits quasi-polynomial-time classical algorithms, many applications in molecular comparison, noisy network analysis, and pattern recognition require a flexible notion of structural similarity. We study the quantum query complexity of approximate graph isomorphism testing, where two graphs on n vertices drawn from the Erdős--Rényi distribution G(n,1/2) are considered approximately isomorphic if they can be made isomorphic by at most k edge edits.
We present a quantum algorithm based on MNRS quantum walk search over the product graph Γ(G,H) of the two input graphs. When the graphs are approximately isomorphic, the quantum walk search detects vertex pairs belonging to a dense near isomorphic matching set; candidate pairings are then reconstructed via local consistency propagation and verified via a Grover-accelerated consistency check. We prove that this approach achieves query complexity O(n3/2logn/ε), where ε parameterizes the approximation threshold. We complement this with an Ω(n2) classical lower bound for constant approximation, establishing a genuine polynomial quantum speedup in the query model.
We extend the framework to spectral similarity measures based on graph Laplacian eigenvalues, as well as weighted and attributed graphs. Small-scale simulation results on quantum simulators for graphs with up to twenty vertices demonstrate compatibility with near-term quantum devices.
Quantum algorithms for clique problems are usually analyzed in the query model, where the graph is accessed through an oracle of unit cost. When the oracle must itself be compiled into gates, published k-clique circuits have depth quadratic in the number n of vertices, and every oracle that counts edges spends at least one non-Clifford gate per edge. We first show that scheduling the commuting edge gates by a proper edge coloring yields adjacency-type oracles, including an exact k-clique oracle, whose depth and width are linear in n, within a logarithmic factor of a depth--width lower bound. Our central result is a k-clique oracle in which the graph enters only through the Clifford gate that prepares a graph state, so that its non-Clifford cost is linear in n for every graph. We analyze this oracle exactly: on a candidate vertex set it acts as a reflection whose overlap is −1 for cliques and, as we prove, at most 5/8 in modulus otherwise, a tight bound that tends to 1/2 as the candidate set grows. A two-qubit phase-estimation filter turns the reflection into a one-sided bounded-error phase oracle, and amplitude amplification then finds a k-clique with O((kn)) oracle calls, each of depth O(Δ+logn) for maximum degree Δ. The guarantee holds for two or more estimation registers; exact simulations on 312 induced subgraphs of two brain networks confirm it and show that the cheaper single-register variant performs nearly as well.
This paper gives quantum query lower bounds for two relational graph problems, triangle listing and explicit multiplicative spanner construction, in the general graph query model, where quantum adjacency, degree and neighborhood queries are all available in arbitrary superposition. Both results are obtained by reductions via intermediate multi-block search problems. We extend the quantum query recording framework by Zhandry (CRYPTO 2019) and Hamoudi and Magniez (ToCT 2023) to handle a recording architecture for bidirectional oracles and give a generic blockwise soundness framework, which for arbitrary families of local accepting projectors, gives an exact operator-norm characterization of their maximum overlap with the subspace of bounded weight records. Using the intermediate search problems, we exhibit a family of n-vertex graphs with Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1)) quantum queries. This is the first nontrivial quantum lower bound for triangle listing, a question raised by Jiang and Peng (ICML 2026). Further, we show that, for every fixed k≥7, constructing a multiplicative k-spanner requires Ω(n1+2μk1) quantum queries, where μk=k/3+O(1). For k∈{7,8} the bound is Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large k the exponent 1+2k3 exceeds the 1+3k4 implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.