Kuliah Umum 演講訊息

【原定10/31演講，延期至11/28】

Abstract：

This study examines clusterability testing for a signed graph in the bounded-degree model. Our contribu6ons are two-fold. First, we provide a quantum algorithm with query complexity Õ(N^{1/3}) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [Adriaens and Apers, 2023]. Second, we prove an ΩV(N^{1/2}) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This seWles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.

20241128演講_陳國進博士 (鴻海研究院)