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

The gist In this work, we prove essentially tight omega(e N1/3) quantum query lower bounds for both bipartiteness and expansion testing in the bounded-degree model, thereby completely characterizing the quantum query complexity of these problems up to polylogarithmic factors.

Classical and Quantum Lower Bounds

In the classical setting, it is known that Θ(e √N) queries are necessary and sufficient for both these testing problems (Goldreich and Ron, 1999, 2000 & 2002) 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 Oe(N1/3) queries, showing a polynomial speedup They also proved that omega(e N1/4) queries are necessary for expansion testing, but the possibility of an exponential quantum advantage for bipartiteness testing remained open In this work, we prove essentially tight omega(e N1/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.

Bipartiteness Testing Lower Bound

The proof for bipartiteness testing relies on a reduction from balancedness property testing to bipartiteness testing Theorem 3.1 states that in order to distinguish with probability at least 2/3 if G is bipartite, or ε-far from being bipartite, omega(N1/3/ log N) quantum queries are necessary. The hard instance construction involves a signed graph where the yes distribution corresponds to balanced graphs and the no distribution corresponds to far from balanced graphs Lemma 3.3 shows that for a graph H with m edges sampled from the no distribution, Pr[fr(H, b) ≤ τm] ≤ 2(N-(1-h2(τ))m), which implies that at (M0, 1), the yes distribution is supported on balanced signed graphs while the no distribution has frustration index at least 0.026N with probability 1 − 2(-omega(N)).

Expansion Testing Lower Bound

The lower bound for expansion testing requires considering more complex hard instances than those used for bipartiteness testing For expansion testing, the construction uses c = Θ(log N) perfect matchings instead of three perfect matchings to bypass a bottleneck where any vertex in the final graph has a constant probability of losing all of its matching neighbors. The proof involves constructing an intermediate graph with degree Θ(log N) and then using a replacement-graph gadget to transform it into a final graph of maximum degree 4. Lemma 4.3 shows that for every fixed α' > 0, every graph H in the support of P(c),feas M0,2 contains a set U such that ∂H(U) = ∅. This implies that H is α'/3c-far from every α'-vertex-expander.

Technical Framework and Proof Strategy

The core of the proof utilizes the framework of [ACL11] which uses the polynomial method The acceptance probability of a quantum algorithm making q queries is a real multilinear polynomial of degree at most 2q in the response indicators Lemma 2.9 states that every surviving monomial specifies a partial response table, and for nonforest patterns, there is a factor of l when writing the expression over the common denominator. The main result is derived by defining P(M, l) = 1/2 H(M, l)Aq(M, l), where H and Aq are polynomials of degree O(q log q). The final contradiction arises from showing that deg P = O(q log q), which implies q = Ω N1/3 log N, contradicting the initial assumption for small enough constant c0.

Final Bounds and Reductions

The paper establishes near-optimal lower bounds for both problems: omega(N1/3/ log N) quantum queries are necessary for bipartiteness testing and omega(N1/3/(log N) 4/3) quantum queries are necessary for expansion testing. The reduction from the signed graph instance to a simple graph G(H, b) shows that G is bipartite if and only if (H, b) is balanced, and minedges deleted from G(H, b) to make it bipartite = fr(H, b). This leads to the conclusion that for graphs whose number of vertices are not of the form of 7N, we can add at most six isolated vertices to handle every sufficiently large N. The final statement follows immediately >.

Open Problems and Future Directions

One problem left open by this work is determining the exact power of log(N) in the complexities of both bipartiteness and expansion testing Another interesting question is how the complexity of these problems depends on the property testing distance parameter ε, i.e., what if we let ε depend on N rather than considering it a constant. Similarly, the dependence of the query complexity of expansion testing on the expansion parameter could be further examined. The authors believe that these ideas are potentially useful beyond the applications in this work.

Acknowledgments and AI Usage

The authors are grateful to Frédéric Magniez for initial discussions and the project idea of improving the expansion testing lower bound and exploring the possibility of adapting the method for bipartiteness testing CK is supported by French PEPR integrated project EPiQ (ANR-22-PETQ-0007) and partially supported by ANR Grant FLITTLA (ANR-21-CE48-0023) SS’s research is supported by the NRF Investigatorship award (NRF-NRFI10-2024-0006) CQT Young Researcher Career Development Grant (25-YRCDG-SS) and the grant ANR-18-IDEX-0001 between Université Paris Cité and National University of Singapore DS’s research is supported by the German Federal Ministry of Research, Technology and Space (QuSol, 13N17173), by the Deutsche Forschungsgemeinschaft under Germany’s Excellence Strategy – EXC-2111 – 390814868, and by the Munich Quantum Valley Statement of AI usage: 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. Important concepts and ideas were manually factored out and written down in a (hopefully) intuitive, understandable way. The authors take full responsibility for the correctness and content of the paper.

References

[AA23] Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs. In WWW, pages 49–59. ACM, 2023 [ACL11] Andris Ambainis, Andrew M Childs, and Yi-Kai Liu. Quantum property testing for bounded-degree graphs. In International Workshop on Approximation Algorithms for Combinatorial Optimization, pages 365–376. Springer, 2011 [Ape20] Simon Apers. Expansion testing using quantum fast-forwarding and seed sets. Quantum, 4:323, 2020 [AS04] Scott Aaronson and Yaoyun Shi. Quantum lower bounds for the collision and the element distinctness problems. Journal of the ACM (JACM), 51(4):595–605, 2004 [BBC+01] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778–797, 2001 [BCG+20] Shalev Ben-David, Andrew M. Childs, András Gilyén, William Kretschmer, Supartha Podder, and Daochen Wang. Symmetries, graph properties, and quantum speedups. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 [BFNR03] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig. Quantum property testing. In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 480–488, 2003 [BY22] Arnab Bhattacharyya and Yuichi Yoshida. Property Testing: Problems and Techniques. Springer Nature, 2022 [CAH24] Kuo-Chin Chen, Simon Apers, and Min-Hsiu Hsieh.

1. System can perform near-optimal quantum query lower bound proofs for bipartiteness testing on bounded-degree graphs, requiring exactly omega(N(1/3)/log N) queries to distinguish between a bipartite graph and one ε-far from bipartite.

2. System can prove the necessity of omega(N(1/3)/log 4/3 N) quantum queries for expansion testing, distinguishing an α-expander from one ε-far from being α'-expander, where the gap is controlled by the parameters.

3. System can design and execute quantum property testers that achieve a polynomial speedup, specifically demonstrating that Oe(N(1/3)) queries are sufficient for testing both bipartiteness and expansion testing.

4. System can utilize a reduction from balancedness testing to bipartiteness testing to establish the same near-optimal lower bound for bipartiteness, showing that the quantum query lower bound extends to bipartiteness testing as well.

5. System can implement an exact simulation of adjacency-list queries on a graph with maximum degree four using at most two queries to the original signed graph, ensuring that a query to au,j or pu,j in G is answered by querying (u, j) in H and checking the returned endpoint and sign.

6. System can adapt classical property testing algorithms for expansion into a quantum setting by employing a replacement-graph gadget to transform an intermediate graph of maximum degree "c" into a final graph with maximum degree four.

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 Θ(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 (N 1/3) queries, showing a polynomial speedup. They also proved that Ω(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 Ω(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.