Эта работа была опубликована в сборнике материалов NeurIPS 2019, вы можете проверить соответствующую статью, а также плакат конференции.

Квантовое машинное обучение - очень горячая тема. Как сказал бы Иорданис Керенидис (мой научный руководитель): это «самая преувеличенная и недооцененная» тема в квантовых вычислениях. Это довольно молодое направление исследований направлено на разработку квантовых алгоритмов, которые выполняют задачи машинного обучения, таких как миллиардный рынок классификации кошек и собак.
Тебе не нужно ничего знать, я объясню.

Квантовые вычисления за 1 минуту

Теперь вы можете спросить: что такое квантовый алгоритм? Это просто последовательность команд, как и любой обычный алгоритм, но на этот раз это схема, состоящая из квантовых вентилей. Что такое квантовые ворота? Это похоже на классический вентиль, такой как ИЛИ, И, НЕ, который действует на кубиты, а не на биты. Что такое кубит? Ну, это квантовый бит: вместо 1 или 0 он может быть и тем, и другим . Например, с точки зрения непрофессионала, он может находиться в состоянии суперпозиции 25% | 0 ›+ 75% | 1›. Мы используем обозначения | 0 › и | 1›, чтобы помнить, что сейчас это квантовые состояния. В более общем смысле состояние кубита - ⍺ | 0 ›+ β | 1›, где ⍺ и β - комплексные числа, называемые амплитудами. С двумя кубитами вы можете иметь четыре комбинации | 00 ›, | 01›, | 10 ›и | 11› одновременно. 8 комбинаций с 3 кубитами и т. Д., Всегда существующих параллельно. Это квантовая физика! Примите это, даже если это необычно для нашего восприятия реальности. Например, кубит может быть атомом, фотоном, ионом или любой квантовой системой, которая может иметь два состояния. Как крохотный кот Шредингера.

Таким образом, вход квантового алгоритма состоит из кубитов. Если у вас n кубитов, у вас одновременно есть 2 ^ n конфигураций. Вы не впечатлены? С 300 кубитами у вас 2 ^ 300 состояний, это количество атомов во Вселенной!

Еще один важный факт: если вы измеряете набор кубитов, вы увидите не всю суперпозицию (вы не квантовую), а только одну из случайных конфигураций с вероятностью, связанной с амплитуда этой конфигурации.

Квантовое машинное обучение

Существует несколько базовых квантовых алгоритмов, которые используются в качестве строительных блоков для долгосрочного квантового машинного обучения (QML). Это будут алгоритмы для поиска собственных векторов матрицы, выполнения матричного умножения или инвертирования матрицы, оценки внутреннего произведения или расстояния между двумя векторами. Помните об этих важных квантовых концепциях: мы можем восстановить классическое описание квантового состояния с помощью нескольких измерений, и, что наиболее важно, нам необходимо иметь возможность загрузить вектор или набор векторов в одно квантовое состояние. Все эти подпрограммы позволяют выполнять задачи линейной алгебры с доказанным ускорением, часто экспоненциально быстрее по размеру матриц или векторов, и гарантируют количественную оценку ошибок.

Примечание. Существует множество исследований различных методов, называемых «квантовое машинное обучение», которые основаны на параметризованных квантовых схемах. Мы надеемся, что они могут быть очень полезными и мощными в краткосрочной перспективе, однако они не воспроизводят аналитически алгоритмы машинного обучения с проверенными гарантиями с точки зрения ускорения или точности. Наш подход больше ориентирован на информатику и рассчитан на долгосрочную перспективу.

Квантовое кодирование векторов

Это ключевая часть! Имея один вектор v размерности d, мы можем кодировать его, используя каждый его компонент в качестве квантовых амплитуд состояний, представляющих стандартный базис. И это можно сделать, используя только log (d).

Теперь мы можем определить квантовую кодировку для набора N векторов v_1,…, v_N нашего набора данных. Мы хотим начать с наложения векторов N, каждый из которых имеет размер d. Каждому вектору присваивается индекс i, поэтому мы создаем суперпозицию всех индексов, используя кубиты log (N).

Классический алгоритм k-средних

Кратко поговорим о классическом машинном обучении. Между контролируемыми и неконтролируемыми алгоритмами существует фундаментальное различие: первые обучаются на основе входных данных и их меток (я говорю вам, что это кошки, а это собаки, теперь обучайтесь), тогда как вторые обучаются без указания (я просто говорю вам найти две разные группы животных).

Алгоритм k-средних - один из самых простых алгоритмов обучения без учителя. Его цель - найти кластеры в наборе данных путем нахождения k идеальных центроидов. Тогда у каждой точки есть метка, соответствующая ее кластеру!

На каждой итерации для каждого вектора (точка) мы вычисляем их расстояние до каждого центроида ( черная звезда). Итак, необходимо вычислить расстояния k x N. Это много, если у вас есть несколько миллионов точек данных.

Одна итерация алгоритма выполняет две простые вещи:
1) Мы обновляем метку для каждого вектора, глядя на его текущий ближайший центроид.
2) Мы обновляем каждый центроид путем усреднения векторов в каждом кластере.

Квантовые k-средние

В нашей статье мы разработали квантовый аналог алгоритма k -средний, названный q-means. Шаги на самом деле такие же, но все делается в квантовой суперпозиции.

1 - Мы начинаем с квантовой суперпозиции всех векторов в наборе данных и вычисляем одновременно все расстояния до каждого из k центроидов.
2 - Мы затем можно пометить все векторы одновременно, выбрав их ближайший центроид. Все метки написаны в квантовом состоянии, тоже в суперпозиции.
3 - Затем мы измеряем кубиты метки. Квантовая физика говорит нам, что мы случайно увидим только одну метку: это означает, что оставшееся квантовое состояние является суперпозицией всех векторов с этой меткой! Это чисто квантовый трюк.
4 - Используя умножение квантовых матриц, мы можем получить квантовое состояние, описывающее новый центроид.
5 - Мы выполняем томографию, чтобы получить классическая версия нового центроида
6 - Мы повторяем последние шаги, пока не получим k новых центроидов.

Анализ: поскольку векторы N всегда использовались в суперпозиции, время выполнения этого алгоритма логарифмически зависит от N! Зависимость от k и d почти аналогична классической k -средней, которая линейна по N.

Имейте в виду, что это чисто теоретический алгоритм, который еще не был протестирован на реальном квантовом компьютере или классическом симуляторе! Если вам интересно, пожалуйста, попробуйте реализовать!

Можем ли мы запустить этот алгоритм?

Возникает важный вопрос: как мы можем проверить качество и сходимость нашего квантового алгоритма? Есть 3 варианта:
- Запустить схему на реальном квантовом компьютере, но пока это невозможно.
- Запустить схему на классическом эмуляторе квантовых схем, что возможно, но ограничено по количеству кубитов.
- Поскольку q -средство выполняет те же шаги, что и k -средство, мы можем классически реализовать его версию (на python) путем комбинирования k -средних с дополнительными «квантовыми» ошибками, такими как случайность и шум при оценке центроидов, для имитации q -средних.

Следующие шаги

С помощью квантовых подпрограмм для линейной алгебры, описанных выше, в частности оценки внутреннего продукта, теперь мы можем представить квантовые алгоритмы для нескольких других случаев машинного обучения: Квантовые нейронные сети, Квантовые сверточные нейронные сети, Модели квантовых гауссовских смесей. , может быть, квантовая спектральная кластеризация. Это увлекательно, и все придется переписывать.

🎄Можно ли получить на Рождество квантовый компьютер?

Нет.
Посмотрим правде в глаза, эти алгоритмы намного опережают нас. Для них требуется много хороших кубитов с исправлением ошибок, но они также требуют квантового ОЗУ (QRAM), необходимого для создания начального кодирования квантового вектора, которое также может быть сложно построить.

Зачем тогда беспокоиться?
Во-первых, если есть шанс, что эти алгоритмы однажды могут быть использованы, мы должны взглянуть на них и посмотреть, к чему это нас приведет. Мы не должны ждать, чтобы изучить алгоритмы, и мы должны начать с основ, чтобы наверстать упущенное в более сложных методах. Классический ML - это очень быстрорастущая область, и некоторые современные идеи могут помочь QML. Вот почему презентация QML на NeurIPS 2019 была прекрасной возможностью!

Более того, уже очень важно нарисовать карту наших будущих возможностей. Сейчас мы должны изучить, что мы можем или не можем делать с квантовым компьютером в долгосрочной перспективе. Для людей, создающих квантовые компьютеры, также важно знать, какие фундаментальные требования необходимы в алгоритмах QML, какая инициализация состояния нам нужна для обеспечения ускорения, как мы будем выполнять линейную алгебру, какой уровень точности требуется и скоро.

Время покажет !

использованная литература

[1] С. Ллойд, М. Мохсени, П. Ребентрост [2013]
Квантовые алгоритмы для контролируемого и неконтролируемого машинного обучения
»[2] Н. Вибе, А. Капур, К. Svore [2014]
« Квантовые алгоритмы для методов ближайшего соседа для обучения с учителем и без учителя »
[3] С. Чакраборти, А. Гилен, С. Джири [2018]
«Возможности блочно-кодированных матричных мощностей: улучшенные методы регрессии за счет более быстрого гамильтонового моделирования
[4] Г. Брассар, П. Хойер, М. Моска, А. Тэпп [2000]
« Квантовое усиление и оценка амплитуды »