Kuo-Chin Chen

This study examines clusterability testing for a signed graph in the bounded-degree model. Our contributions are two-fold. First, we provide a quantum algorithm with query complexity tildeO(N^1/3) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Florian Adriaens and Simon Apers. Testing cluster properties of signed graphs.]. Second, we prove an tildeØmega(sqrtN) classical query lower bound for testing clusterability, which nearly matches the upper bound from citeadriaens2021testing. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.