Source-linked AI summary
Superlinear Quantum Query Lower Bounds for Subgraph Detection
Amin Shiraz Gilani, Xingyu Zhou
TL;DR
Subgraph detection asks whether a graph accessed through adjacency-matrix queries contains a fixed subgraph, and unconditional superlinear quantum query lower bounds had been lacking. The paper develops a lower bound for certificate search and establishes superlinear bounds for cliques, connected graphs with chromatic number at least four, and complete bipartite graphs.
Problem
The open question is whether detecting a fixed subgraph requires superlinear quantum queries, even though a copy is a short certificate.
Source: §1 · pp. 3–4Method
The paper proves a lower bound for finding an all-ones certificate from a known family of independently sampled bits, using a compressed oracle and conditioning on a randomly planted certificate.
Source: §1.1 · pp. 6–7Results
n^(λ_r-o(1)) queries are required for K_r (λ_4=19/18); connected H with c≥4 need superlinear queries, and K_{r,r} needs n^(β_r-o(1)) (β_10=181/180).
Source: §1.1 · pp. 4, 6Takeaways & Limitations
Chromatic number alone does not settle query complexity: fixed paths admit O(n) queries, while large complete bipartite graphs require superlinear bounds.
Source: §1.4 · p. 11The nonnegative-weight adversary method cannot prove superlinear lower bounds here because of the certificate-complexity barrier.
Source: §1 · p. 3
Abstract
from arXiv · showhide
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^{\lambda_r-o(1)}$ queries, where $\lambda_4=19/18$, the exponents $\lambda_r$ increase strictly with $r$, and $\lambda_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^{\beta_r-o(1)}$ queries, where $\beta_{10}=181/180$ and $\beta_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.
1 Introduction
The introduction presents superlinear quantum query lower bounds for fixed-subgraph detection, covering cliques, connected graphs of high chromatic number, and some complete bipartite graphs, alongside a certificate-search framework for proving them. It also discusses related lower-bound work and open questions on triangle detection, bipartite graphs, and improving clique exponents.
1 Introduction
- The paper gives the first unconditional superlinear quantum query lower bounds for fixed-subgraph detection, addressing a question left open while prior lower bounds remained linear.A copy of fixed H has a constant-size 1-certificate, which prevents the nonnegative adversary method from proving bounds larger than O(n).Source: §1 · pp. 3–4
1.1 Results
- For every fixed r≥4, K_r detection and search require n^{λ_r-o(1)} queries, with λ_4=19/18 and exponents strictly increasing toward 2.The K_4 exponent follows by composing a triangle-collision lower bound with OR; the clique bounds combine clique collision and a matching-number argument.Source: §1.1 · pp. 4–5
- For connected H of chromatic number c, detection requires n^{19/18-o(1)} queries at c=4, n^{13/12-o(1)} at c=5, and n^{11/10-o(1)} at c≥6.For sufficiently large c, the lower bound is n^{2-α√(log log c/c)-o(1)}; these bounds also hold for search.Source: §1.1 · p. 6
- Theorem 1.4 states that for every fixed r≥10, complete bipartite graph detection has an associated strictly increasing sequence β_r, where β_10=181/180 and every β_r is less than 2.The same bounds hold for K_{r,r} search when the input is bipartite and its bipartition is known to the algorithm.Source: §1.1 · p. 6
- The main technical result lower-bounds finding a present all-ones certificate from a known family when input bits are independently sampled and biased.Conditioning on a randomly planted certificate yields a coherent, non-diagonal progress measure in the compressed-oracle framework; it improves the bound by a polynomial factor in 1/p when d≤q−2.Source: §1.1 · pp. 6–7
The compressed oracle.
- A coherent progress measure counts a triangle's presence separately from its identification in the database, avoiding overcounting reversible record changes.Conditioning on a randomly planted certificate gives the identified triangle its true worth, p, rather than treating it as fully verified.Source: §1.1 · p. 7, The compressed oracle · p. 8
1.2 Proof overview
- A tripartite construction of Gowers and Janzer [GJ21] with n^{2-o(1)} edge-disjoint triangles yields an n^{5/9-o(1)} triangle-collision lower bound and, by OR composition, the K_4 exponent 19/18.The construction has every edge in at most one triangle; the K_4 reduction uses independent collision instances and adds 1/2 to the exponent.Source: §1.2 · p. 7, The compressed oracle · p. 9
The compressed oracle.
- For K_r,r, a matching-threshold random bipartite graph gives each h-matching polylogarithmically many extensions; connected H with a K_r minor inherits K_r hardness at constant query overhead [DVW22].The chromatic-number argument uses minors from known cases of Hadwiger’s conjecture and a coloring theorem [DP25].Source: The compressed oracle · p. 9
1.3 Related work
- Earlier triangle-certificate bounds did not apply to Boolean triangle detection; extending the graph-collision reduction [BI16] yields exponents above 1/2 for K_r collision when r≥3.The known graph-collision lower bound gives only a linear lower bound for triangle detection.Source: §1.3 · p. 10
The compressed oracle.
- Belovs’s transfer framework [Bel26] is specialized to a uniformly planted certificate, and threshold-crossing bounds yield a lower bound for arbitrary certificate families.The proof uses output orthogonality and the norm of a restricted conditioning map to bound progress below the threshold.Source: §1.3 · p. 10
1.4 Open Problems
- A superlinear triangle lower bound remains open; the matching argument does not apply, and an ω(√n) lower bound for GCK2 on a fixed graph would imply one for triangles [BI16].Every connected non-bipartite subgraph is at least as hard as the triangle, so such a result would also cover odd cycles.Source: §1.4 · p. 11
- K_r,r detection becomes superlinear at r=10, while smaller complete bipartite graphs such as K2,2 remain open.Source: §1.4 · p. 11
- Which fixed subgraphs admit O(n)-query detection remains open: connected graphs with chromatic number at least four do not, fixed paths do, and chromatic-number-three cases lack a superlinear bound [BR12].Among bipartite graphs, both linear-query and non-linear-query behavior occur.Source: §1.4 · p. 11
- The clique lower-bound exponent 2−O(1/r) remains below the learning-graph upper-bound exponent 2−Θ(1/r), and improving even K4’s 19/18 exponent is open.The framework may need a different threshold or a sharper bound on progress over successive queries; polylogarithmic extension multiplicity leaves the exponent unchanged.Source: §1.4 · p. 11
2 Preliminaries
The preliminaries fix graph and quantum-query conventions, state a query-preserving reduction framework, and introduce certificate search under independent biased inputs. A second-moment bound relates certificate overlap to the probability of finding a certificate.
2.1 Graphs and asymptotic notation
- The paper fixes graph, asymptotic, and query conventions, including that H is fixed as n grows and query bounds allow constants to depend on H.It defines copies as edge-preserving embeddings, not necessarily induced, and Q(f) as bounded-error worst-case query complexity.Source: §2.1 · p. 12, §2.2 · p. 12
2.2 Quantum queries and exact reductions
- A reduction that maps each target input bit to a constant or a source bit preserves query complexity, and search reductions must also translate valid outputs.The section also records composition of the general adversary bound with OR and the relation between fixed connected-subgraph search and decision.Source: §2.2 · pp. 12–13
2.3 Certificates and a second moment bound
- For a known certificate family, certificate search asks for a member whose coordinates are all one; subgraph detection can be restricted to the desired edges of a fixed host graph.The restricted coordinates are host-graph edges, and distinct certificate edge sets are counted once.Source: §2.3 · p. 13
- When certificates have size q and p=|F|^-1/q, the expected number present is one, and the probability that at least one is present is at least 1/(2+W).W measures contributions from overlapping distinct certificates; a search algorithm succeeding with probability at least 2/3 whenever a certificate exists has success probability at least 2/(3(2+W)) under the product distribution.Source: §2.3 · p. 14
3 A lower bound for certificate search
This section bounds quantum search for an all-ones certificate from a known family when input bits are independent and biased. It analyzes certificate transitions using compressed-oracle thresholds and combines low- and high-threshold estimates to prove the bound.
3 A lower bound for certificate search
- Theorem 3.1 bounds certificate-search success using the maximum size of low sets and the number of certificates whose threshold one coordinate can cross.Its corollary gives a query bound when |F|pq = 1 and success is sufficiently high.Source: §3 · pp. 14–15
3.1 The compressed oracle
- After t queries, the compressed-oracle database is supported on sets of size at most t.The compressed basis represents an empty database initially, and each query changes at most one entry; a database entry does not certify that its input bit is one.Source: §3.1 · pp. 15–16, The compressed states satisfy · p. 17
3.2 Planting a certificate
- Planting a uniformly chosen certificate makes the algorithm’s probability of outputting that certificate equal to σ|F|p^q on average.The algorithm is not told which certificate was planted; conditioning is implemented on the compressed database register.Source: §3.2 · pp. 18–19
3.3 Progress across a threshold
- The compressed-state progress measure tracks conditioned high-threshold components, while low components contribute according to the conditioning-map norm below threshold.A query can increase progress only through transitions crossing the threshold.Source: §3.3 · pp. 20–21
3.4 Norms at a threshold
- The threshold analysis bounds the conditioning-map norm on low databases and the average squared norm of boundary-crossing operators.Under Theorem 3.1’s hypotheses, Lemma 3.8 bounds boundary crossing; only query transitions between low and high databases contribute.Source: §3.4 · pp. 22–23
- Grouping orthogonal (j, S) outputs, counting each coefficient once, and averaging over C establishes the threshold norm bound in Equation (38).The contributions for fixed j and U combine, while distinct output labels are orthogonal.Source: §3.4 · p. 24
3.5 Proof of the certificate search bound
- Substituting the low- and high-term estimates into the recurrence proves the certificate-search bound in Equation (12).The high-term estimate starts from κ0 = 0, since the empty database lies below every threshold.Source: §3.5 · p. 25
4 Lower bounds for cliques
The clique lower bounds use two applications of the certificate-search bound: one through vertex-mark queries and clique collision, and another through edge queries with a matching-number threshold.
4 Lower bounds for cliques
- The first approach lower-bounds clique collision on vertex marks and composes it with OR to obtain a lower bound for K_r detection.It gives the stronger bounds for small r, but its exponent tends to 3/2 as r grows.Source: §4 · p. 25
- The second approach queries edges directly and thresholds the matching number of database edges within each candidate clique.This approach yields exponents tending to two.Source: §4 · p. 25
4.1 Graphs with unique clique extensions
The clique arguments use graphs with many K_r copies and limited overlap, with unique smaller-clique extensions controlling both threshold crossings and certificate overlap. A random partition yields an r-partite construction with n^ℓ−o(1) copies and no K_{r+1}.
4.1 Graphs with unique clique extensions
- Unique K_ℓ extensions ensure distinct K_r copies overlap in fewer than ℓ vertices, limiting certificate overlap and the number of threshold crossings from a query.The paper uses the resulting overlap bounds to keep certificate presence probability constant.Source: §4.1 · pp. 25–26
- For fixed r>ℓ, the Gowers–Janzer construction supplies graphs with many K_r copies while each K_ℓ lies in at most one K_r [GJ21, Theorem 1.2].Source: §4.1 · p. 25
- A random r-coloring and deletion of same-color edges preserves a constant fraction of the K_r copies and makes the graph r-partite.The resulting graph has n^ℓ−o(1) copies of K_r, with every K_ℓ in at most one K_r, and contains no K_{r+1}.Source: §4.1 · pp. 25–26
4.2 Clique collision
This section establishes a lower bound for clique collision by applying the certificate-search bound to a family of marked cliques in a fixed graph. The analysis controls certificate size, overlap, and the algorithm’s success probability.
4.2 Clique collision
- Proposition 4.4 establishes a lower bound for GCK_r, where the algorithm knows G and queries only its vertex marks.The proposition, together with Proposition 4.2, proves Theorem 1.2.Source: §4.2 · p. 26
- The same lower bound applies to search for a marked copy of K_r.Source: §4.2 · p. 26
- The certificate family contains |F| = n^(ℓ−o(1)) copies of K_r, with certificate size r and density p = |F|^−1/r.The family is downward closed, and its sets have at most ℓ−1 elements.Source: §4.2 · p. 27
- The crossing analysis uses i = ℓ−1 and δ = 1, and the success probability is at least 1/4 for sufficiently large n.This permits application of Corollary 3.2 to obtain the lower bound.Source: §4.2 · p. 27
4.3 Composition with OR
The section reduces clique detection to an OR of independent clique-collision instances by adding a vertex for each instance. The construction ensures that each larger clique corresponds to one added vertex and a marked clique in its instance.
4.3 Composition with OR
- With Θ(n) independent instances, composition with OR contributes a factor of √n to the lower bound.The reduction extends the approach of Balodis and Iraids [BI16].Source: §4.3 · p. 27
- For each instance, an added vertex is adjacent exactly to the vertices marked in that instance, and the added vertices are pairwise nonadjacent.The construction uses b = ⌊n/2⌋ marking strings and produces an n-vertex graph.Source: §4.3 · p. 27
- For K4, each added vertex connects to the vertices marked by its input, and every K4 has exactly one added vertex and one triangle in G.The figure distinguishes fixed edges from queried edges and depicts only one possible witness.Source: Figure 2 · p. 28
- Every K_(r+1) consists of one added vertex and a K_r in G marked by its instance.The original graph is r-partite, so it contains no K_(r+1), and the added vertices cannot occur together in a clique.Source: §4.3 · pp. 27–28
- Each adjacency query in the constructed graph uses at most one query to the marking strings, whose input blocks are disjoint.Thus the reduction transfers the clique-collision lower bound to detection.Source: §4.3 · p. 28
4.4 Large cliques via the matching number
For large cliques, the section uses edge queries and a certificate family defined by a matching-number threshold. Optimizing that threshold yields exponents tending to two.
4.4 Large cliques via the matching number
- The matching-number threshold method gives exponents tending to two for large cliques.The method queries edges directly and assigns each candidate clique a threshold on the matching number of its database edges.Source: §4.4 · p. 28
- Proposition 4.7 gives a clique lower bound using m, the maximum number of edges in a K_r subgraph with matching number less than h.The same lower bound holds for search.Source: §4.4 · p. 29
- The certificate coordinates are edges of G, and copies of K_r in G define the certificate family.The graph is chosen so every K_(2h) lies in at most one K_r; the certificate size is the number of edges in K_r.Source: §4.4 · p. 29
- The certificate family is downward closed because removing edges cannot increase matching number, and its sets have at most m edges.Source: §4.4 · p. 29
- For a crossing certificate, the queried edge completes an h-matching; removing it leaves an (h−1)-matching that identifies a K_(2h) lying in no other certificate.This gives the crossing condition with i = h−1 and δ = 1.Source: §4.4 · p. 29
- The success probability is at least 1/4 for sufficiently large n, allowing Corollary 3.2 to yield the bound.Because K_r is fixed and connected, decision and search have the same query complexity up to a constant factor.Source: §4.4 · p. 29
4.5 Optimizing the clique exponents
The section defines the clique exponent as the maximum of bounds from clique collision and matching number. It proves that these exponents increase strictly with clique size and balances the matching threshold to approach two.
4.5.1 Monotonicity of the bounds from clique collision
- For each fixed admissible ℓ ≥ 2, the clique-collision exponent increases strictly with r.The ℓ = 1 choice never attains the maximum, and every admissible ℓ remains admissible at r + 1.Source: §4.5.1 · p. 30
4.5.2 Monotonicity of the matching bound
- For each fixed admissible h, the matching-bound exponent increases strictly with r.The extremal matching-number formula of Erdős–Gallai [EG59, Theorem 4.1] is used to establish the required decrease in the ratios.Source: §4.5.2 · pp. 30–31
4.5 Optimizing the clique exponents
- The optimized exponents satisfy λ_(r+1) > λ_r, with λ_4 = 19/18.The exponent is the maximum over the clique-collision and matching-bound families.Source: §4.5 · p. 30, §4.5.2 · p. 31
4.5.3 Balancing the threshold on the matching number
- An exponent approaching two requires h → ∞ and h = o(r); balancing the two asymptotic terms determines the threshold choice.For h → ∞ with h = o(r), the terms are asymptotic to 2/h and 4h/r, respectively.Source: §4.5.3 · p. 31
- The balancing argument completes the proof of Theorem 1.1.Source: §4.5.3 · p. 31
5 Extensions beyond cliques
The section extends clique lower bounds to connected graphs of large chromatic number, then treats complete bipartite graphs separately. Its bounds show that chromatic number yields strong lower bounds, while a different construction gives superlinear bounds even for K_{r,r}.
5.1.1 Cores, minors, and Hadwiger’s conjecture
- The homomorphism core preserves chromatic number and connectivity; it is the smallest induced subgraph receiving a homomorphism from H.A homomorphism maps vertices to vertices and edges to edges, but need not be injective.Source: §5.1.1 · p. 32
5.1.2 Encoding a clique through a core minor
- If core(H) contains a K_r minor, detecting H requires at least the query complexity of detecting K_r, and the reduction preserves this comparison for search.The reduction encodes K_r first as the core, then encodes the core as H; each adjacency query in the constructed graphs costs at most one query to the original graph.Source: §5.1.2 · p. 33
5.1.3 Consequences of chromatic number
- For connected H, c=4, 5, and c≥6 require n^{19/18−o(1)}, n^{13/12−o(1)}, and n^{11/10−o(1)} queries, respectively; sufficiently large c gives n^{2−α√(log log c/c)−o(1)}.The bounds also hold for search.Source: §5.1.3 · pp. 33–34
- Known minor results give K_c minors for c≤6, while the coloring bound yields a minor of order Ω(c/log log c) for sufficiently large c.The latter follows from the bound c=O((r+1)log log(r+1)) for graphs without a K_r minor.Source: §5.1.1 · p. 32, §5.1.3 · p. 34
5.2.1 A bipartite graph with bounded extensions
- A bipartite graph with n vertices per part contains Θ(n^{2rh/(r+h)}) copies of K_{r,r}, with each h-matching in at most (log n)^{2r+2} copies.Retaining each edge independently with probability p=|F|^{-1/r²} leaves a K_{r,r} with probability Ω(1).Source: §5.2.1 · p. 34
5.2.2 Proof of the lower bound
- The K_{r,r} lower-bound proof uses this certificate family with a matching threshold: below threshold, edge sets contain no h-matching and have size at most r(h−1).The bounded-extension estimate controls certificates crossing the threshold, and the resulting bound applies even to search on bipartite inputs with a known bipartition.Source: §5.2.2 · pp. 36–37
- For K_{r,r}, query complexity is n^{β_r−o(1)}; β_r increases strictly and β_10=181/180, with the same lower bound for search.The theorem also applies when inputs are promised bipartite with a known bipartition.Source: §5.2 · p. 34, §5.2.2 · p. 37
- Choosing the matching threshold optimally gives β_10=181/180; approaching exponent two requires h→∞ and h=o(r), balancing losses asymptotic to 2/h and 4h/r.The leading loss is minimized at h=√(r/2)+O(1).Source: §5.2.2 · p. 37