(Quantum) Complexity of Testing Signed Graph Clusterability

  • Event Date: 2024-09-30
  • Quantum information and communication
  • Speaker: Dr. Kuo-Chin Chen (Hon Hai (Foxconn) Quantum Computing Research Center)  /  Host: Prof. Yueh-Nan Chen (NCKU)
    Place: R36173, 1F, Dept. of Physics, Building of Science College, NCKU

Time:12:10, Monday, September 30, 2024
Speaker:Dr. Kuo-Chin Chen
              Hon Hai (Foxconn) Quantum Computing Research Center
Title: (Quantum) Complexity of Testing Signed Graph Clusterability
Place : R36173, 1F, Dept. of Physics, Building of Science College, NCKU

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.TQC.2024.8

1/0