Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
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 Θ̃(√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 Õ(N1/3) queries, showing a polynomial speedup. They also proved that Ω̃(N1/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 Ω̃(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. 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.
Related
- Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements
- Optimal inequalities for completely bounded polynomials and the limitations of quantum query algorithms
- Resource Compatibility in Optimal Quantum Symmetry Testing
- Optimal Stabilizer Testing and Learning with Limited Quantum Memory
- Optimal Quantum Junta Testing without Inverse Queries
BibTeX
@misc{kayal2026nearoptimal,
title = {{Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model}},
author = {Chandrima Kayal and Sayantan Sen and Dániel Szabó},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.01752},
eprint = {2610.01752},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.01752},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
AU - Chandrima Kayal
AU - Sayantan Sen
AU - Dániel Szabó
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.01752
UR - https://arxiv.org/abs/2610.01752
AB - 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 Θ̃(√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.
ER -