Quantum algorithms for four problems in density peak clustering
Abstract
Clustering is a fundamental task in unsupervised learning. The goal is to partition unlabeled data into clusters such that similar elements are assigned to the same cluster, while elements in different clusters are dissimilar. We propose a quantum Monte Carlo approach to density estimation, a key routine in density peak clustering. Building on this approach, we develop quantum algorithms for the full clustering problem and three related tasks: decision clustering, cluster counting, and heavy cluster counting. For each one, we establish a polynomial quantum query speedup under assumptions on the scaling of dataset-dependent parameters. Numerical experiments suggest that these conditions are satisfied for several practically relevant settings.
Related
- Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
- Accelerating A*-Based Algorithms for Decoding Quantum Low-Density Parity-Check Codes
- Density-driven α-particle clustering in neutron-rich oxygen isotopes
- Density-Dependent Description of Clustering in Axially-Symmetric Nuclei
- Microscopic Investigation of α Clustering for the α Decay Based on the Density-Constrained Frozen Hartree-Fock Calculations
BibTeX
@misc{sousa2026quantum,
title = {{Quantum algorithms for four problems in density peak clustering}},
author = {Gonçalo Sousa and Duarte Magano},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08498},
eprint = {2610.08498},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08498},
}
RIS
TY - UNPB
TI - Quantum algorithms for four problems in density peak clustering
AU - Gonçalo Sousa
AU - Duarte Magano
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08498
UR - https://arxiv.org/abs/2610.08498
AB - Clustering is a fundamental task in unsupervised learning. The goal is to partition unlabeled data into clusters such that similar elements are assigned to the same cluster, while elements in different clusters are dissimilar. We propose a quantum Monte Carlo approach to density estimation, a key routine in density peak clustering. Building on this approach, we develop quantum algorithms for the full clustering problem and three related tasks: decision clustering, cluster counting, and heavy cluster counting. For each one, we establish a polynomial quantum query speedup under assumptions on the scaling of dataset-dependent parameters. Numerical experiments suggest that these conditions are satisfied for several practically relevant settings.
ER -