Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.37091

Quantum Query Lower Bounds for Triangle-Listing and Spanners

Yu Chen, Ananta Mukherjee, Mingyang Yang

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

A Quantum Lower Bound for Triangle Finding

Arjan Cornelissen, Amin Shiraz Gilani, Xingyu Zhou

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.

arXiv:2611.06751•Nov 4, 2026•0 citations

Quantum Query Complexity of Maximum Degree and its Generalizations

Amin Shiraz Gilani, Nikhil S. Mande, Subhasree Patro +1 more

We study the quantum query complexity of several basic graph problems. 1) We prove a tight $Θ(n^{3/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 $Θ(n^{3/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\geq 1$, we give an $O(n^{2-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\geq 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.

quant-pharXiv:2610.13906•Oct 12, 2026•2 citations

Quantum Query Complexity of Minimum Weight Cycles

Naman Goyal

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 $\tilde{O}(n^{19/12})$ queries, while $\Omega(n^{3/2})$ queries are necessary. The algorithm learns only the $n^{7/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 $\tilde{O}(n^{5/3})$ queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in $\tilde{O}(n^{8/5})$ queries and a tight $O(\log n)$-approximation in $\tilde{O}(n^{3/2})$ queries. In contrast, MWT costs $O(n^{9/7}\log M)$ queries, so the classical equivalence becomes a polynomial separation. For cycles of constant length we give explicit exponents, such as $\tilde{O}(n^{125/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 $\Omega(n^{2-2/(\lfloor k/2\rfloor+1)})$ queries for every constant $k\ge 4$. Finally, non-adaptive learning graphs cannot beat $n^2$ for cycles of about $\log n$ edges, and we conjecture that exact MWC on directed graphs requires $n^{2-o(1)}$ queries.

•Oct 2, 2026•0 citations

Superlinear Quantum Query Lower Bounds for Subgraph Detection

Amin Shiraz Gilani, Xingyu Zhou

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\ge 4$, detecting the clique $K_r$ requires $n^{λ_r-o(1)}$ queries, where $λ_4=19/18$, the exponents $λ_r$ increase strictly with $r$, and $λ_r\ge 2-4\sqrt{2/r}+O(1/r)$. More generally, we prove superlinear lower bounds for detecting every fixed connected graph $H$ with chromatic number $c\ge 4$. These bounds approach quadratic as $c$ grows: for sufficiently large $c$, detection requires $n^{2-O(\sqrt{\log\log c/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 $K_{r,r}$ requires $n^{β_r-o(1)}$ queries, where $β_{10}=181/180$ and $β_r\ge 2-O(1/\sqrt{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.

quant-pharXiv:2609.40263•Oct 1, 2026•2 citations

Quantum Algorithms on Edge Lists: Hiding, Shuffling, and Cycle Finding

Amin Shiraz Gilani, Daochen Wang, Wu, Pei +1 more

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 $m^{3/4-1/(2^{k+2}-4)\pm o(1)}$, which matches the best-known upper bound for the quantum query complexity of $k$-distinctness on length-$m$ inputs up to an $m^{o(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.

arXiv:2412.17786•Leibniz international proceedings in informatics•Dec 23, 2024•4 citations

Quantum Algorithms for Triangle Cut Sparsification

Shan Jiang, Pan Peng

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 $T_{\mathrm{q\text{-}list}} =$ $\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},$ $n^{3/2}t^{1/2})\bigr)$, 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 $\varepsilon$-triangle cut sparsifiers of size $\widetilde{O}(n/\varepsilon^2)$ in time $\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)$. Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of $Ω(n/\varepsilon^2)$ on the size of any $\varepsilon$-triangle cut sparsifiers.

quant-pharXiv:2606.06287•Jun 5, 2026•1 citation
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 nnn-vertex graphs with Θ(n)Θ(n)Θ(n) triangles on which listing any constant fraction of the triangles requires Ω(n3/2−o(1))Ω(n^{3/2-o(1)})Ω(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≥7k\ge 7k≥7, constructing a multiplicative kkk-spanner requires Ω(n1+12μk)Ω(n^{1+\frac{1}{2μ_k}})Ω(n1+2μk​1​) quantum queries, where μk=k/3+O(1)μ_k=k/3+O(1)μk​=k/3+O(1). For k∈{7,8}k\in\{7,8\}k∈{7,8} the bound is Ω(n5/4)Ω(n^{5/4})Ω(n5/4), which matches what would be implied by an unproven instance of the Erdős girth conjecture, and for large kkk the exponent 1+32k1+\frac{3}{2k}1+2k3​ exceeds the 1+43k1+\frac{4}{3k}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 kkk-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 nnn-vertex graphs with Θ(n)\Theta(n)Θ(n) triangles on which reporting any constant fraction requires Ω(n3/2/2O(log⁡n))=Ω(n3/2−o(1))\Omega(n^{3/2}/2^{O(\sqrt{\log n})})=\Omega(n^{3/2-o(1)})Ω(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 kkk-spanners, every fixed k≥7k\geq7k≥7 has a lower bound Ω(n1+1/(2μk))\Omega(n^{1+1/(2\mu_k)})Ω(n1+1/(2μk​)), where μk=⌊(k+1)/3⌋−1[k≡2(mod6)]\mu_k=\lfloor(k+1)/3\rfloor-\mathbf{1}[k\equiv2\pmod6]μk​=⌊(k+1)/3⌋−1[k≡2(mod6)]. This gives Ω(n5/4)\Omega(n^{5/4})Ω(n5/4) for k=7,8k=7,8k=7,8 and exponent 1+3/(2k)+O(1/k2)1+3/(2k)+O(1/k^2)1+3/(2k)+O(1/k2) asymptotically. These instances have girth four and admit 333-spanners with O(n)O(n)O(n) edges, so the obstruction is locating required edges, not output length.
The proofs establish Ω(BN)\Omega(B\sqrt N)Ω(BN​) bounds for recovering hidden values in a constant fraction of BBB 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)\widetilde O(n^{35/18})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 NNN-vertex graphs given by their adjacency matrices, a long line of work has improved the quantum query upper bound from O(N3/2)O(N^{3/2})O(N3/2) to O(N5/4)O(N^{5/4})O(N5/4). However, the best known lower bound has remained the elementary Ω(N)Ω(N)Ω(N) bound obtained from unstructured search. We prove the first superlinear quantum query lower bound for triangle finding, showing that Ω(N13/12)Ω(N^{13/12})Ω(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)Θ(n^{3/2})Θ(n3/2) bound for finding a maximum-out-degree vertex in an nnn-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 nnn-vertex undirected graph requires Θ(n3/2)Θ(n^{3/2})Θ(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)(k,n-k)(k,n−k)-Cut, which asks for the largest cut with one side of size kkk. For every constant k≥1k\geq 1k≥1, we give an O(n2−1/(k+1))O(n^{2-1/(k+1)})O(n2−1/(k+1))-query quantum algorithm. 4) We establish a reduction to Maximum (k,n−k)(k,n-k)(k,n−k)-Cut involving kkk-Graph Collision, which asks whether the marked vertices of a known graph contain a kkk-clique. For k≥3k\geq 3k≥3, this yields unconditional lower bounds with exponents strictly larger than 3/23/23/2, showing that this problem is strictly harder than computing maximum degree. Additionally, under a conjecture we propose for kkk-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)\tilde{O}(n^{19/12})O~(n19/12) queries, while Ω(n3/2)\Omega(n^{3/2})Ω(n3/2) queries are necessary. The algorithm learns only the n7/6n^{7/6}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)\tilde{O}(n^{5/3})O~(n5/3) queries, and searching for fewer heavy edges trades queries for approximation, with a 2-approximation in O~(n8/5)\tilde{O}(n^{8/5})O~(n8/5) queries and a tight O(log⁡n)O(\log n)O(logn)-approximation in O~(n3/2)\tilde{O}(n^{3/2})O~(n3/2) queries. In contrast, MWT costs O(n9/7log⁡M)O(n^{9/7}\log M)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)\tilde{O}(n^{125/83})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))\Omega(n^{2-2/(\lfloor k/2\rfloor+1)})Ω(n2−2/(⌊k/2⌋+1)) queries for every constant k≥4k\ge 4k≥4. Finally, non-adaptive learning graphs cannot beat n2n^2n2 for cycles of about log⁡n\log nlogn edges, and we conjecture that exact MWC on directed graphs requires n2−o(1)n^{2-o(1)}n2−o(1) queries.
Subgraph detection asks whether an nnn-vertex graph, accessed through queries to its adjacency matrix, contains a copy of a fixed graph HHH. 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 HHH is a certificate of constant size, so the adversary method with nonnegative weights cannot prove superlinear lower bounds. For every fixed r≥4r\ge 4r≥4, detecting the clique KrK_rKr​ requires nλr−o(1)n^{λ_r-o(1)}nλr​−o(1) queries, where λ4=19/18λ_4=19/18λ4​=19/18, the exponents λrλ_rλr​ increase strictly with rrr, and λr≥2−42/r+O(1/r)λ_r\ge 2-4\sqrt{2/r}+O(1/r)λr​≥2−42/r​+O(1/r). More generally, we prove superlinear lower bounds for detecting every fixed connected graph HHH with chromatic number c≥4c\ge 4c≥4. These bounds approach quadratic as ccc grows: for sufficiently large ccc, detection requires n2−O(log⁡log⁡c/c)−o(1)n^{2-O(\sqrt{\log\log c/c})-o(1)}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,rK_{r,r}Kr,r​ requires nβr−o(1)n^{β_r-o(1)}nβr​−o(1) queries, where β10=181/180β_{10}=181/180β10​=181/180 and βr≥2−O(1/r)β_r\ge 2-O(1/\sqrt{r})β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 333-distinctness and 333-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-kkk cycle in its length-mmm edge list is m3/4−1/(2k+2−4)±o(1)m^{3/4-1/(2^{k+2}-4)\pm o(1)}m3/4−1/(2k+2−4)±o(1), which matches the best-known upper bound for the quantum query complexity of kkk-distinctness on length-mmm inputs up to an mo(1)m^{o(1)}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 kkk-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 kkk-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 nnn vertices, mmm edges, and ttt triangles, runs in time Tq-list=T_{\mathrm{q\text{-}list}} =Tq-list​= O~(min⁡(n5/4t7/12+n7/6t7/9,m+m3/4t1/2,\widetilde{O}\bigl(\min(n^{5/4}t^{7/12} + n^{7/6}t^{7/9}, m + m^{3/4}t^{1/2},O(min(n5/4t7/12+n7/6t7/9,m+m3/4t1/2, n3/2t1/2))n^{3/2}t^{1/2})\bigr)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 ε\varepsilonε-triangle cut sparsifiers of size O~(n/ε2)\widetilde{O}(n/\varepsilon^2)O(n/ε2) in time O~(Tq-list+mn/ε)\widetilde{O}(T_{\mathrm{q\text{-}list}} + \sqrt{mn}/\varepsilon)O(Tq-list​+mn​/ε). Finally, we demonstrate applications to clustering algorithms based on triangle-related measures and prove a lower bound of Ω(n/ε2)Ω(n/\varepsilon^2)Ω(n/ε2) on the size of any ε\varepsilonε-triangle cut sparsifiers.