PaperlayerView exact revision on arXiv

Source-linked AI summary

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model

Chandrima Kayal, Sayantan Sen, Dániel Szabó

arXiv:2610.01752v1quant-phcs.DS

TL;DR

A central open question was whether meaningful quantum query lower bounds could be proved for fundamental property-testing problems. The paper analyzes hard instances for intermediate testing problems and refines the polynomial-method approach. It proves near-optimal quantum query lower bounds for bipartiteness and expansion testing, while leaving some parameter dependencies open.

  • Problem

    A central open question was whether nontrivial quantum query lower bounds could be proved for fundamental property-testing problems.

    Source: §1 · p. 2

  • Method

    The proof analyzes hard instances for intermediate testing problems, including signed balancedness, and adjusts graph size by subdividing edges.

    Source: §3.1 · p. 13, §4.3 · p. 25

  • Results

    Both bipartiteness and expansion testing require eΩ(N^1/3) quantum queries, settling their query complexities up to polylogarithmic factors.

    Source: §1.1.1 · p. 3

  • Takeaways & Limitations

    The quantum property-testing algorithms of [ACL11] for bipartiteness and expansion testing are essentially optimal.

    Source: §1.1.1 · p. 3

    The exact logarithmic factors remain open, as does dependence on ε when it varies with N.

    Source: §1.2 · p. 6

Abstract

from arXiv · show

In this work, we study bipartiteness and expansion testing, two canonical problems in graph property testing in the bounded-degree model through the lens of quantum query complexity. In the classical setting, it is known that $\widetilde{\Theta}(\sqrt{N})$ queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002), where $N$ denotes the number of vertices of the input graph. Due to their significance, (Ambainis, Childs, and Liu, 2011) initiated the study of these problems in the quantum setting and designed quantum algorithms for bipartiteness and expansion testing that perform $\widetilde{O}(N^{1/3})$ queries, showing a polynomial speedup. They also proved that $\widetilde{\Omega}(N^{1/4})$ queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open. Despite significant effort, there has been no improvement in these results in the last decade and a half. In this work, we prove essentially tight $\widetilde{\Omega}(N^{1/3})$ quantum query lower bounds for both bipartiteness and expansion testing, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors. While our proofs use the polynomial method similarly to Ambainis, Childs, and Liu, we use intermediate problems that we relate to the main problems via reductions, and perform a more precise analysis of the resulting polynomials, leading to the near-optimal lower bounds.

1 Introduction

In the bounded-degree graph model, the paper addresses open quantum query lower-bound questions for bipartiteness and expansion testing. It proves near-optimal lower bounds using reductions and a refined polynomial-method analysis.

1.1.1 Main results

  • Both bipartiteness and expansion testing require eΩ(N^1/3) quantum queries, settling their complexities up to polylogarithmic factors.These lower bounds make the quantum testing algorithms of [ACL11] essentially optimal.Source: §1.1.1 · p. 3, §1.1.2 · p. 6

1.1.2 Technical overview

  • Forests cancel in the acceptance gap, leaving cycle patterns with ℓ-factors; approximating the reciprocal denominator then enables a sharper polynomial degree lower bound.The authors identify the ℓ-factor count through cycle rank and use a reciprocal polynomial rather than replacing the denominator by a constant.Source: §1.1.2 · pp. 4, 6
  • The bipartiteness lower bound proceeds through signed-graph balancedness, replacing 0-label edges with length-2 paths and 1-label edges with length-3 paths.Balancedness is the property that edge labels equal the XOR of endpoint labels for some vertex assignment.Source: §1.1.2 · pp. 4–5
  • For expansion, Θ(log N′) matchings preserve expansion, while a replacement gadget yields a maximum-degree-4 graph of size Θ(N′ log N′).A simulation argument transfers the lower bound from the intermediate graph to the bounded-degree graph.Source: §1.1.2 · pp. 5–6

1.2 Open problems

  • The paper leaves open the exact power of log(N) in both query complexities and how complexity depends on ε when ε varies with N.It also identifies expansion-parameter dependence as an open question, especially across different α versus α′ gaps.Source: §1.2 · p. 6

2 Preliminaries

The preliminaries formalize bounded-degree graph query access and the testing notions used in the paper, then set up signed-graph and polynomial tools for quantum lower bounds. They also introduce the [ACL11] hard distribution and polynomial lemmas used in the analysis.

2.1.1 Classical Query Model

  • Classical query complexity counts oracle accesses to indexed input entries, and the graph model specializes this to adjacency-list queries for bounded-degree graphs.A query specifies a vertex and neighbor index; the oracle returns that neighbor or ⊥ when it does not exist.Source: §2.1.1 · p. 7

2.1.2 Quantum Query Model

  • A quantum query algorithm accesses the graph through a unitary adjacency-list oracle, with input-independent unitaries between oracle calls.The algorithm's state is represented by query, answer, and workspace registers, and its output is measured at the end.Source: §2.1.2 · p. 7

2.2 Property testing

  • An ε-tester distinguishes graphs satisfying a property from graphs ε-far from it, while expansion in this work means vertex expansion.A graph is ε-far if at least εNd edge modifications are needed; the tester must distinguish the two cases with probability at least 2/3.Source: §2.2 · p. 8

2.3 Signed graphs, balance, and frustration

  • A signed graph assigns a bit to each edge; it is balanced when vertex bits reproduce every edge sign by XOR, and frustration measures violations of this condition.Balancedness is equivalent to every cycle having an even number of edges labeled 1; the frustration index is the minimum number of edge deletions needed to make the graph balanced.Source: §2.3 · pp. 8–9

2.4 The quantum acceptance polynomial

  • A q-query quantum algorithm's acceptance probability is a real multilinear polynomial of degree at most 2q in response indicators.Consistent monomials encode graph patterns, and the coefficient estimate bounds each degree-k coefficient in absolute value by 2^k.Source: §2.4 · p. 9

2.5.1 The hard distribution from [ACL11]

  • The [ACL11] hard distribution builds an ambient graph from colored random matchings within blocks, then samples N visible vertices and takes their induced graph.The resulting graph has maximum degree at most the number of colors; conditioning on no block overflow gives the feasible distributions.Source: §2.5.1 · p. 10

2.5.2 Two important lemmas

  • Under the [ACL11] distribution, the expected acceptance probability of a q-query algorithm is rational, with denominator dividing Dq and numerator degree O(q log q).The same rational-function statement applies to linear combinations of expected acceptance probabilities.Source: §2.5.2 · p. 10
  • A translated and rescaled bivariate polynomial lemma uses boundedness and value separation to obtain degree lower bounds via Paturi's theorem.The paper states this version as following the same proof as the [ACL11] lemma.Source: §2.5.2 · p. 11

3 Quantum query lower bound for bipartiteness testing

This section establishes an 

3 Quantum query lower bound for bipartiteness testing

  • Distinguishing bipartite graphs from graphs ε-far from bipartite requires Ω(N^1/3/log N) quantum queries for constant ε and success probability at least 2/3.Source: §3 · p. 11

3.1 Description of our hard instances

  • The intermediate balancedness problem also requires Ω(N^1/3/log N) queries; at (M0, 1), no instances have frustration index at least 0.026N with probability 1−2^-Ω(N).At this parameter, the yes distribution is supported on balanced signed graphs.Source: §3 · p. 11, §3.1 · p. 13

3.2 Analyzing the acceptance probability

  • Forest patterns have equal label-assignment probabilities under the yes and no distributions, so only nonforest patterns contribute to the acceptance gap, with a factor of ℓ in its polynomial numerator.The numerator polynomial has degree O(q log q).Source: §3.1 · p. 13, §3.2 · p. 15

3.3 Bounding the sampling failure probability

  • The feasible acceptance gap ∆(M, ℓ) equals its formal version ∆form(M, ℓ) plus η(M, ℓ), where |η(M, ℓ)| ≤ 2 exp(C1q log N − c1N^(1/3)).Source: §3.3 · p. 16

3.4 Polynomial approximation of the denominator

  • A polynomial of degree at most 4d + 10 approximates the denominator reciprocal to error at most 10^-2; the constructed approximation has degree O(q log q) on the stated parameter region.The region satisfies 1 ≤ ℓ ≤ R and |M − M0| ≤ R^3/2.Source: §3.4 · pp. 16–17

3.5 Combining everything

  • Ω(N^1/3/log N) quantum queries are necessary to distinguish balanced signed graphs from graphs ε-far from balancedness.The bound holds for bounded-degree signed graphs on N vertices, for constant ε ∈ (0, 1), with success probability at least 2/3.Source: §3.5 · p. 17
  • The proof uses a degree O(q log q) polynomial with values above 0.44 and below 0.26 at two parameter points, forcing q log q = Ω(N^1/3).At (M0, 1), P(M0, 1) > 0.44; at (M0, 2), |P(M0, 2)| < 0.26.Source: §3.5 · p. 18

3.6 Reduction to bipartiteness testing

  • The reduction proves an Ω(N^1/3/log N) quantum query lower bound for testing bipartiteness in bounded-degree graphs.It preserves the number of edge deletions needed to reach bipartiteness as the signed graph’s frustration index, and each adjacency-list query is simulable with a constant number of signed-graph queries.Source: §3.6 · p. 19

4 Quantum query lower bound for expansion testing

This section proves quantum query lower bounds for bounded-degree expansion testing using hard instances and polynomial approximation arguments. The proof uses graph transformations and extends the analysis to additional vertex counts.

4.1 Description of our hard instances

  • With c = Θ(log N) matchings, the construction yields yes instances for ℓ = 1 and disconnected no instances for ℓ = 2 that are far from α′-expanders.Source: §4.1 · pp. 20–21

4.2 The replacement-product construction

  • If every U⊆V(H) satisfies |e_H(U,V(H)\U)| ≥ βc min{|U|,N−|U|}, R(H) has vertex expansion at least α depending only on β and h0, and maximum degree four.A q-query algorithm distinguishing replacement-graph distributions yields a 2q-query algorithm for the corresponding intermediate-graph distributions with the same advantage.Source: §4.2 · pp. 22–23

4.3 The rational acceptance probability with logarithmically many colors

  • For c = Θ(log N) colors, the expected acceptance probability retains a rational form with numerator degree O(q log q), and its total coefficient absolute value is exp(O(q log N)).Source: §4.3 · p. 24
  • To reach arbitrary graph sizes, the construction subdivides existing edges rather than adding isolated vertices, preserving the no-instance promise and constant expansion of yes instances when at most one quarter of edges are subdivided.Source: §4.3 · p. 25

4.4 Combining everything

  • Ω(N^1/3/(log N)^4/3) quantum queries are necessary to distinguish an α-expander from a graph ε-far from every α′-expander with probability at least 2/3.Source: §4.4 · p. 25
  • The proof constructs P from an approximation of degree O(q log q); for sufficiently large N′, P(M0, 1) > 0.46 and |P(M0, 2)| < 0.04.Theorem 4.10 gives η(M, ℓ) = o(1) uniformly under the assumed query bound, and the polynomial is bounded by one on the grid.Source: §4.4 · pp. 25–26
  • The polynomial degree bound implies q = Ω(N′^(1/3)), contradicting the assumed query bound.The argument obtains deg P = Ω(N′^(1/3)) and uses deg P = O(q log q).Source: §4.4 · p. 26
  • For vertex counts not of the form considered directly, the proof applies the earlier size-adjustment argument.The direct argument considers graphs with N′c vertices.Source: §4.4 · p. 26

A.1 Proof of Theorem 2.10

The proof bounds the coefficient mass of the canonical acceptance polynomial, using the number of possible query outcomes and monomials. This yields an exp(O(q log N)) upper bound on the sum of absolute coefficients.

A.1 Proof of Theorem 2.10

  • The canonical acceptance polynomial has coefficient magnitude at most 2k for degree-k monomials, and its total absolute coefficient sum is at most exp(O(q log N)).The proof counts at most (CN^2)^k canonical monomials of degree k, using 3N possible queries and O(N) non-null responses per query.Source: §A.1 · pp. 28–29

A.2 Proof of Theorem 3.8

The proof expresses topology moments for a consistent colored pattern through partitions of its connected components among hidden blocks. Divisibility and a common denominator then yield a polynomial of degree O(q log q).

A.2 Proof of Theorem 3.8

  • The pattern probability is organized by partitions that group connected components placed in the same hidden block.For each partition class, the proof considers the probability that its components share a block and that their prescribed matching edges occur.Source: §A.2 · p. 29
  • Partition inclusion–exclusion and divisibility give each summand a numerator divisible by ℓ^(e-v+c).The divisibility follows after removing explicit ℓ^d factors; here β(F), the cycle-rank, is identified as e-v+c.Source: §A.2 · pp. 29–30
  • Putting the summands over a common denominator yields a polynomial B_F(M, ℓ) of degree O(q log q).The common denominator is formed from factors M − (2a − 1)ℓ.Source: §A.2 · p. 30

A.3 Proof of Theorem 3.10

The proof writes the formal acceptance gap as a polynomial H(M, ℓ) of degree O(q log q). It analyzes feasible acceptance-polynomial monomials through their signed colored graph patterns.

A.3 Proof of Theorem 3.10

  • The formal acceptance-probability gap is represented by a polynomial H(M, ℓ) of degree O(q log q).The acceptance polynomial has degree at most 2q, and each canonical monomial determines a consistent colored multigraph pattern with prescribed edge signs.Source: §A.3 · pp. 31–32
  • Forest-pattern monomials contribute zero to the formal acceptance gap because their prescribed sign probabilities agree in the YES and NO cases.This equality holds for every prescribed signing of a forest.Source: §A.3 · p. 31
  • For nonforest patterns, the cycle-rank is at least one, and the resulting summands retain degree O(q log q).The proof factors out one power of ℓ and bounds each summand's degree using βµ ≤ 2q and deg B_Fµ = O(q log q).Source: §A.3 · pp. 31–32

A.4 Proof of Theorem 3.12

The feasible acceptance gap differs from the formal gap by an exponentially small error, uniformly on G_N. For q ≤ c0N^(1/3)/log N, that error is o(1) throughout G_N.

A.4 Proof of Theorem 3.12

  • On G_N, the gap satisfies Δ(M, ℓ) = Δform(M, ℓ) + η(M, ℓ), with |η(M, ℓ)| ≤ 2 exp(C1q log N − c1N^(1/3)).The bound holds uniformly for σ ∈ {yes, no}.Source: §A.4 · p. 32
  • If q ≤ c0N^(1/3)/log N for sufficiently small c0, then η = o(1) for every parameter pair in G_N.This follows from the uniform error bound on G_N.Source: §A.4 · p. 32

A.5 Proof of Theorem 3.14

The proof approximates the reciprocal of a product of affine factors by truncating geometric-series expansions. Under the stated bound on those factors, the resulting polynomial has bounded degree and approximates the product’s reciprocal uniformly throughout the region.

A.5 Proof of Theorem 3.14

  • Degree at most 4d + 10 and relative error at most 10^-2 are achieved throughout R when |zi| ≤ 1/4.The same polynomial works simultaneously at every point of R.Source: §A.5 · pp. 33, 35
  • The construction relies on |zi| ≤ 1/4 for every i, which ensures the geometric series converge and supports the uniform approximation.The factors zi are affine in the original variables, so the degree bound transfers to those variables.Source: §A.5 · pp. 33–34
  • Truncating the total-degree expansion at J := 4d + 10 yields a polynomial A of degree at most J.The expansion groups products of geometric-series terms by total degree.Source: §A.5 · pp. 33–34

A.6 Proof of Theorem 3.15

The proof constructs a polynomial Aq from a total-degree truncation indexed by Iq. It establishes a uniform approximation bound over the stated region, with degree O(q log q).

A.6 Proof of Theorem 3.15

  • Degree O(q log q) and relative error at most 10^-2 hold for Aq throughout the stated region.The region has 1 ≤ ℓ ≤ R and |M − M0| ≤ R^3/2.Source: §A.6 · pp. 35–36
  • The index set Iq consists of pairs (a, r) with 1 ≤ a ≤ 2q and 1 ≤ r ≤ ⌊2q/a⌋.The total-degree truncation from the preceding lemma gives the polynomial Aq.Source: §A.6 · p. 35
  • For every i in Iq throughout the region, |zi(M, ℓ)| ≤ 1/4.This bound supplies the factor condition used in the approximation argument.Source: §A.6 · p. 35

A.7 Proof of Theorem 4.2

The proof bounds crossing edges for cuts of size at most N/2 by exposing partners in independent random matchings. A concentration bound and union bound are then applied across all such sets.

A.7 Proof of Theorem 4.2

  • At each exposure, at least N/4 unmatched visible vertices outside U remain, giving conditional crossing probability at least 1/5.This uses M0 ≤ 6N/5 for sufficiently large N.Source: §A.7 · p. 36
  • The expected number of crossing edges exposed across the c independent matchings is at least cu/10 for a set U of size u ≤ N/2.Each matching exposes ⌈u/2⌉ partners, with conditional crossing probability at least 1/5 per exposure.Source: §A.7 · p. 36
  • The proof applies a union bound over all sets U after concentration, using c ≥ 400 log N.The lemma’s displayed conclusion is stated to hold for every U of size at most N/2.Source: §A.7 · p. 36

A.8 Proof of Theorem 4.5

The proof transfers an edge-expansion condition on H to positive vertex expansion in R(H). It combines expansion inside each cloud with control of edges between clouds.

A.8 Proof of Theorem 4.5

  • If H has the stated edge-expansion bound, then R(H) has vertex expansion at least α > 0, depending only on β and h0.The condition bounds |eH(U, V(H) \ U)| below by βc min{|U|, N − |U|} for every U.Source: §A.8 · p. 36
  • Partial membership within clouds contributes crossing internal edges, while changing membership of replacement-graph vertices alters at most one external edge each.The proof separates the internal-edge and external-edge contributions to the cut.Source: §A.8 · pp. 36–37
  • The proof splits into cases at b = βt/(2(β + 1)); either the internal-edge bound or the external-edge bound is then proportional to t.The two lower bounds shown are h0β/[2(β + 1)] times t and βt/2.Source: §A.8 · p. 37
  • Maximum degree four limits each outside boundary vertex to at most four crossing edges.This converts the edge-boundary count into a bound on outside boundary vertices.Source: §A.8 · p. 37

A.9 Proof of Theorem 4.11

Theorem 4.11 shows that the constructed graph remains far from every α′-vertex-expander after up to n/4 edges are subdivided. Lemma A.10 shows that bounded subdivision preserves constant vertex expansion when the original graph has the stated edge-expansion property.

A.9 Proof of Theorem 4.11

  • For sufficiently large N, subdividing at most n/4 edges of G=R(H), each at most once, leaves G′ α′/12-far from every α′-vertex-expander.Here n=|V(G)|=Nc.Source: §A.9 · p. 37
  • The proof obtains this distance by showing that the fixed set needs at least α′n′/3 edge modifications to meet the required boundary, then normalizing by 4n′.Subdividing edges does not increase the maximum degree beyond four.Source: §A.9 · p. 38

A.10 Proof of Theorem 4.12

  • If a maximum-degree-four graph has the stated ρ edge-expansion bound, subdividing at most one quarter of its vertices’ count in edges preserves vertex expansion at a positive constant depending only on ρ.The proof bounds the new cut using original crossing edges and subdivision vertices, then uses the unchanged degree bound of four.Source: §A.10 · p. 38
Loading 2610.01752v1…