2026-07-26T02:16:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20678 2024-08-26T09:43:29Z ddc:004 open_access

(Quantum) Complexity of Testing Signed Graph Clusterability Chen, Kuo-Chin Apers, Simon Hsieh, Min-Hsiu Quantum Algorithm classical Query lower Bound Graph Property testing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kuo-Chin Chen and Simon Apers and Min-Hsiu Hsieh 2024 Is Part Of LIPIcs, Volume 310, 19th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2024.8 urn:nbn:de:0030-drops-206786 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode