(Quantum) Complexity of Testing Signed Graph Clusterability
Dr. Kuo-Chin Chen - Hon Hai (Foxconn) Quantum Computing Research Center
-
2024-09-30 12:10:00 ~
2024-09-30 13:10:00See event details for additional info.
-
R36173, 1F, Dept. of Physics, Building of Science College, NCKU
Open in map -
This event is open to:
Everyone
-
NTD 0
(Quantum) Complexity of Testing Signed Graph Clusterability
Dr. Kuo-Chin Chen - Hon Hai (Foxconn) Quantum Computing Research Center
|
DATE |
2024-09-30 |
|
|
|
|
TIME |
12:10-13:10 |
|
|
|
|
PLACE |
R36173, 1F, Dept. of Physics, Building of Science College, NCKU |
|
|
|
|
FIELD |
Quantum Information Science |
|
|
|
|
SPEAKER |
Dr. Kuo-Chin Chen - Hon Hai (Foxconn) Quantum Computing Research Center |
|
|
|
|
TITLE |
(Quantum) Complexity of Testing Signed Graph Clusterability |
|
|
|
|
ABSTRACT |
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 Õ(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 Ω̃(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [Adriaens and Apers, 2023]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.
This work has been published in the proceedings of TQC 2024, and you can find it at the following link. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs. |
|
|