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 $Ω(n^{3/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\ge 7$, constructing a multiplicative $k$-spanner requires $Ω(n^{1+\frac{1}{2μ_k}})$ quantum queries, where $μ_k=k/3+O(1)$. For $k\in\{7,8\}$ the bound is $Ω(n^{5/4})$, which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large $k$ the exponent $1+\frac{3}{2k}$ exceeds the $1+\frac{4}{3k}$ implied by the provable high girth dense graphs due to Lazebnik, Ustimenko and Woldar, 1995.
AI Summary
The paper studies quantum query lower bounds for triangle listing and explicit multiplicative $k$-spanner construction in the general graph model, allowing adjacency, degree, and ordered-neighbor queries in arbitrary superposition. Both tasks require recovering combinatorial objects rather than deciding a property.
For triangle listing, it constructs $n$-vertex graphs with $\Theta(n)$ triangles on which reporting any constant fraction requires $\Omega(n^{3/2}/2^{O(\sqrt{\log n})})=\Omega(n^{3/2-o(1)})$ queries. The reduction uses Ruzsa–Szemerédi graphs partitioned into induced matchings, with each triangle identifying a marked position in an independent search block. For explicit $k$-spanners, every fixed $k\geq7$ has a lower bound $\Omega(n^{1+1/(2\mu_k)})$, where $\mu_k=\lfloor(k+1)/3\rfloor-\mathbf{1}[k\equiv2\pmod6]$. This gives $\Omega(n^{5/4})$ for $k=7,8$ and exponent $1+3/(2k)+O(1/k^2)$ asymptotically. These instances have girth four and admit $3$-spanners with $O(n)$ edges, so the obstruction is locating required edges, not output length.
The proofs establish $\Omega(B\sqrt N)$ bounds for recovering hidden values in a constant fraction of $B$ independent blocks. They extend recording-oracle analysis to coupled bidirectional queries and derive an exact operator-norm identity relating low-weight records and local accepting projectors to a classical Bernoulli lower-tail probability. Both graph reductions simulate all three query interfaces with constant overhead.
The triangle bound applies to a particular dense family with linearly many triangles; the stated best upper bound there is $\widetilde O(n^{35/18})$, leaving a gap. The spanner bounds concern explicit edge output and fixed stretch.
Little sign of AI-generated textUnclear writing
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies quantum query lower bounds for triangle listing and explicit multiplicative k-spanner construction in the general graph model, allowing adjacency, degree, and ordered-neighbor queries in arbitrary superposition. Both tasks require recovering combinatorial objects rather than deciding a property.
For triangle listing, it constructs n-vertex graphs with Θ(n) triangles on which reporting any constant fraction requires Ω(n3/2/2O(logn))=Ω(n3/2−o(1)) queries. The reduction uses Ruzsa–Szemerédi graphs partitioned into induced matchings, with each triangle identifying a marked position in an independent search block. For explicit k-spanners, every fixed k≥7 has a lower bound Ω(n1+1/(2μk)), where μk=⌊(k+1)/3⌋−1[k≡2(mod6)]. This gives Ω(n5/4) for k=7,8 and exponent 1+3/(2k)+O(1/k2) asymptotically. These instances have girth four and admit 3-spanners with O(n) edges, so the obstruction is locating required edges, not output length.
The proofs establish Ω(BN) bounds for recovering hidden values in a constant fraction of B independent blocks. They extend recording-oracle analysis to coupled bidirectional queries and derive an exact operator-norm identity relating low-weight records and local accepting projectors to a classical Bernoulli lower-tail probability. Both graph reductions simulate all three query interfaces with constant overhead.
The triangle bound applies to a particular dense family with linearly many triangles; the stated best upper bound there is O(n35/18), leaving a gap. The spanner bounds concern explicit edge output and fixed stretch.
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(N3/2) to O(N5/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 Ω(N13/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.
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 study the minimum weight cycle problem (MWC) and the minimum weight triangle problem (MWT) in the quantum query model, for n-vertex graphs with integer edge weights in [M] given by their adjacency matrix. Roditty and Vassilevska Williams showed that the two problems are classically equivalent. We show that an exact minimum weight cycle of an undirected graph can be found with O~(n19/12) queries, while Ω(n3/2) queries are necessary. The algorithm learns only the n7/6 lightest vertex pairs, uses quantum counting to locate weight thresholds above them, applies a strict form of the Moore bound to bound the optimum and the size of each weight class, and searches the classes for the few heavy edges of an optimal cycle with nested quantum walks. A simpler version gives O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5) queries and a tight O(logn)-approximation in O~(n3/2) queries. In contrast, MWT costs O(n9/7logM) queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as O~(n125/83) for the minimum weight 5-cycle, and we prove that deciding whether a graph has a k-cycle of total weight exactly zero requires Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4. Finally, non-adaptive learning graphs cannot beat n2 for cycles of about logn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1) queries.
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.
The edge list model is arguably the simplest input model for graphs, where the graph is specified by a list of its edges. In this model, we study the quantum query complexity of three variants of the triangle finding problem. The first asks whether there exists a triangle containing a target edge and raises general questions about the hiding of a problem's input among irrelevant data. The second asks whether there exists a triangle containing a target vertex and raises general questions about the shuffling of a problem's input. The third asks whether there exists a triangle; this problem bridges the 3-distinctness and 3-sum problems, which have been extensively studied by both cryptographers and complexity theorists. We provide tight or nearly tight results for these problems as well as some first answers to the general questions they raise. Furthermore, given any graph with low maximum degree, such as a typical random sparse graph, we prove that the quantum query complexity of finding a length-k cycle in its length-m edge list is m3/4−1/(2k+2−4)±o(1), which matches the best-known upper bound for the quantum query complexity of k-distinctness on length-m inputs up to an mo(1) factor. We prove the lower bound by developing new techniques within Zhandry's recording query framework [CRYPTO '19] as generalized by Hamoudi and Magniez [ToCT '23]. These techniques extend the framework to treat any non-product distribution that results from conditioning a product distribution on the absence of rare events. We prove the upper bound by adapting Belovs's learning graph algorithm for k-distinctness [FOCS '12]. Finally, assuming a plausible conjecture concerning only cycle finding, we show that the lower bound can be lifted to an essentially tight lower bound on the quantum query complexity of k-distinctness, which is a long-standing open question.
Triangles capture higher-order structures in graphs and are fundamental to applications such as clustering and network analysis. To enable efficient use of such structures at scale, we study the problem of triangle cut sparsification, which aims to reduce the graph size while approximately preserving triangle counts across every cut. We investigate quantum algorithms for this problem, using triangle listing as our main technical ingredient. In particular, we present a quantum algorithm for triangle listing that, for a graph with n vertices, m edges, and t triangles, runs in time Tq-list=O(min(n5/4t7/12+n7/6t7/9,m+m3/4t1/2,n3/2t1/2)), improving upon the best known classical bounds over a broad range of parameters. Our algorithm is based on a heavy-light vertex partition and an extension of triangle detection via quantum walks and Grover search. Leveraging this result, we design a quantum algorithm for constructing ε-triangle cut sparsifiers of size O(n/ε2) in time O(Tq-list+mn/ε). Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of Ω(n/ε2) on the size of any ε-triangle cut sparsifiers.