Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph model
The work establishes essentially tight quantum query lower bounds of Omega(e N1/3) for both bipartiteness and expansion testing in bounded-degree graphs. This completely characterizes the quantum query complexity for these problems up to polylogarithmic factors, refining previous classical and early quantum results.