Краткое содержание

arXiv:2510.22540v2 Тип анонса: replace-cross Аннотация: Кластеризация на NISQ-аппаратуре ограничена загрузкой данных и малым числом кубитов. Мы представляем **qc-kmeans** — гибридный компрессионный $k$-means, который суммирует набор данных скетчем постоянного размера на основе Фурье-признаков и выбирает центроиды путем решения небольших QUBO-задач для каждой группы с использованием неглубоких QAOA-схем. Оценщик QFF-скетча является несмещенным со среднеквадратической ошибкой $O(\varepsilon^2)$ для $B,S=\Theta(\varepsilon^{-2})$, а пиковое требование к кубитам $q_{\text{peak}}=\max\{D,\lceil \log_2 B\rceil + 1\}$ не масштабируется с количеством образцов. Шаг уточнения с элитистским сохранением гарантирует невозрастание суррогатной стоимости. В симуляциях Qiskit Aer (глубина $p{=}1$) метод работал с $\le 9$ кубитами на низкоразмерных синтетических тестах и показал конкурентоспособную сумму квадратов ошибок относительно квантовых аналогов; время работы напрямую не сравнимо. На девяти реальных наборах данных (до $4.3\times 10^5$ точек) конвейер сохранял постоянное