Sayantan Sen

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

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 pro...