Theory Seminar: Quantum property testing of graph bipartiteness

Dr. Dániel Szabó
LMU
QIC Seminar, at the Seminar Room
Tuesday, September 22, 11:30 CET 

The talk’s topic is the quantum query complexity of bipartiteness property testing in the bounded-degree model. In the classical setting, Goldreich and Ron (1999 & 2002) proved that the optimal query complexity (up to poly-logarithmic factors) is $\widetilde{\Theta}(\sqrt{n})$, where $n$ denotes the number of vertices in the input graph $G$. Naturally, this problem has also been studied in the quantum setting: Ambainis, Childs, and Liu (2011) designed a quantum algorithm for bipartiteness testing that performs $\widetilde{O}(n^{1/3})$ queries, thereby showing a polynomial quantum advantage for this problem. However, despite being a fundamental problem, no non-trivial quantum lower bound has been known. In our work, we prove the first polynomial quantum query lower bound of $\Omega(n^{1/12})$ queries for one-sided error bipartiteness testing. Our proof uses a novel adaptation of the compressed permutation oracle framework of Carolan (2026). Using the same technique, we also prove similar quantum query lower bounds for other important problems such as cycle-freeness and minor-freeness testing.