# (Quantum) complexity of testing signed graph clusterability

arXiv: https://arxiv.org/abs/2311.10480 · HTML: https://mlsanity.com/paper/2311.10480/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2023.

## Built on by (most cited first, 1 of 1)

- [Learning structural balance of graphs from quantum spectral features](https://mlsanity.com/paper/2609.11736/) (2026)

## Abstract (arXiv)

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(N1/3) for testing clusterability, which yields a polynomial speedup over the best classical clusterability tester known [arXiv:2102.07587]. Second, we prove an tildeOmega(√N) classical query lower bound for testing clusterability, which nearly matches the upper bound from [arXiv:2102.07587]. This settles the classical query complexity of clusterability testing, and it shows that our quantum algorithm has an advantage over any classical algorithm.