QTML 2025: Знаете ли вы, что означает Q? скачать в хорошем качестве

QTML 2025: Знаете ли вы, что означает Q?

Авторы: Арьян Корнелиссен, Жоао Ф. Доригелло, Алессандро Луонго и Эвин Танг Аннотация: Кластеризация — один из важнейших инструментов анализа больших наборов данных, и, пожалуй, самым популярным алгоритмом кластеризации является алгоритм Ллойда для k-средних. Этот алгоритм принимает n векторов в d-мерном пространстве и выдает k центроидных векторов, которые разделяют векторы на кластеры в зависимости от того, какой центроид находится ближе всего к конкретному вектору. Мы представляем классический алгоритм эпсилон-k-средних, который выполняет приблизительную версию одной итерации алгоритма Ллойда, со сложностью по времени, которая экспоненциально улучшается с увеличением размера данных n по сравнению с предыдущими классическими алгоритмами. Он соответствует времени выполнения квантового алгоритма q-средних, первоначально предложенного Керенидисом, Ландманом, Луонго и Пракашем (NeurIPS 2019). Насколько нам известно, это самый быстрый классический алгоритм для приблизительного k-средних. Затем мы обращаем внимание на квантовую среду и предлагаем улучшенную версию алгоритма q-средних. Наш новый квантовый алгоритм обеспечивает лучшее время выполнения, чем предыдущие квантовые подходы, и предлагает полиномиальное улучшение по сравнению с нашим классическим алгоритмом эпсилон-k-средних по нескольким параметрам. В отличие от предыдущих квантовых алгоритмов, наш метод не опирается на примитивы квантовой линейной алгебры. Вместо этого он использует QRAM для подготовки простых квантовых состояний на основе текущих назначений кластеров и применяет многомерную квантовую оценку амплитуды. Наконец, мы приводим первые квантовые и классические нижние границы для выполнения одной итерации задачи k-средних. Эти результаты показывают, что наши алгоритмы оптимальны по большинству соответствующих параметров. Этот доклад был представлен на конференции Quantum Techniques in Machine Learning (QTML) 2025 в Сингапуре.