arXiv:2610.01752
Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
Chandrima Kayal, Sayantan Sen, Dániel Szabó
Abstract
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Θ(\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Ω(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Ω(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.
AI Summary
The paper studies the quantum query complexity of testing bipartiteness and expansion in the bounded-degree adjacency-list model, for constant distance parameters. Classical testers require $\widetilde\Theta(N^{1/2})$ queries, while known quantum algorithms use approximately $\widetilde O(N^{1/3})$. Previously, expansion testing had a $\widetilde\Omega(N^{1/4})$ quantum lower bound, and whether bipartiteness testing admitted an exponential quantum advantage remained open. It proves two-sided-error lower bounds of $\Omega(N^{1/3}/\log N)$ for bipartiteness testing and $\Omega(N^{1/3}/\log^{4/3}N)$ for expansion testing, matching the known quantum exponent. The expansion result concerns distinguishing constant-expansion graphs from graphs a constant distance from weaker expanders, within the parameter regime established by the construction. The proofs refine an existing polynomial-method framework based on random matchings within hidden vertex blocks. For bipartiteness, an intermediate signed-graph balancedness problem compares signs induced by vertex labels with independent random edge signs. Forest-pattern contributions cancel in the acceptance gap; tracking cycle rank reveals a block-parameter factor in the remaining numerator. Approximating the rational acceptance function’s reciprocal denominator by a low-degree polynomial enables a larger interpolation grid and the stronger degree bound. A constant-query path-gadget reduction transfers this bound to bipartiteness. For expansion, logarithmically many matchings ensure expansion after vertex sampling, and replacement gadgets reduce the maximum degree to four. The paper leaves open the exact logarithmic factors, dependence on a nonconstant distance parameter $\epsilon$, and dependence on the expansion parameters and their gap.
ChatGPT-6 Astra was used extensively in the development of this paper, including in exploring and refining proof ideas and in drafting and revising the text.
Central claim may not hold: The paper does not establish the advertised polylogarithmically matching expansion-testing upper bound for fixed expansion thresholds, because its presented parameter-dependent upper bound changes the rejection promise when its polynomial overhead is reduced to polylogarithmic size. Both lower-bound proofs conflate local algebraic pattern moments with probabilities under a full-sample overflow-fallback distribution, leaving their shared exact-rational-function and approximation argument unproved as written.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 38 pages