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

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

Основные модели обучения

В квантовом машинном обучении применяются три основные модели обучения:

• точное обучение (exact learning) на основе запросов принадлежности (membership queries)
• вероятностно приблизительно корректное обучение (Probably Approximately Correct, PAC)
• агностическое обучение (agnostic learning)

Точное обучение

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

PAC-обучение

В этой модели также ищется функция, наиболее точно соответствующая неизвестной функции, однако возможность делать запросы отсутствует. Вместо этого имеется некий набор образцов. Математически целью является выдвижение такой гипотезы о неизвестной функции, которая наилучшим образом соответствует неизвестной функции на данном наборе образцов. Отличием квантового PAC-обучения от классического является то, что данные образцы, вообще говоря, могут находиться в состоянии квантовой суперпозиции. В общем случае, это, однако, не даёт значительного выигрыша, и квантовый алгоритм отличает по скорости от классического лишь на некоторый постоянный фактор. Существует, правда, некоторый класс неизвестных функций, для которого квантовое PAC-обучение значительно быстрее классического.

Агностическое обучение

В этой модели дана последовательность из n бит и задачей является поиск гипотезы, наилучшим образом предсказывающая n+1 бит. Так же, как и в PAC-модели, квантовые алгоритмы здесь оказываются в общем случае ненамного быстрее классических.

История

Корни квантового машинного обучения лежат в двух крупных направлениях теоретической информатики, возникших практически одновременно в 1980-х годах: машинном обучении и квантовой информатики. Первой работой, попытавшейся задействовать квантовые эффекты для улучшения методов машинного обучения стала работа Надера Бшути и Джеффри Джексона 1999 года^[1], в которой они предложили использовать для обучения так называемые квантовые выборки, то есть выборки, находящиеся в состоянии квантовой суперпозиции нескольких классических выборок.

В 2000-х годах были предложены и квантовые алгоритмы для решения некоторых типичных задач машинного обучения. Например, в работе 2006 года^[2] был предложен вариант алгоритма Гровера для задачи кластеризации.