A graph data structure is a powerful tool for representing entities and relations. Among graph algorithms, community detection plays a critical role. Realistic graphs can be as large as billions of nodes and edges, and global algorithms such as modularity optimisation and spectral methods scale poorly with these graphs. Thus, large graphs demand algorithms that detect clusters using only local information. A random-walk algorithm is one such example, yet whether a quantum random walk algorithm can provide useful enhancement remains unclear. Here, we propose a new algorithm based on quantum random walk combined with subgraph sampling to detect local clusters with an asymptotic computational complexity of \(\mathcal {O}({\sqrt{(1/\varPhi )}})\) in the conductance of the graph, giving a square-root quantum speed-up. Furthermore, this method provides a stronger bound on the maximum local conductance than its classical counterpart. We further demonstrate its performance on graph models and estimate the required resources for implementing the algorithm.