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

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

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

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

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

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

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

PAC-обучение

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

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

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

История

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

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

Примечания

N. H. Bshouty and J. C. Jackson. Learning DNF over the uniform distribution using a quantum example oracle. SIAM Journal on Computing, 28(3):1136–1153, 1999. Earlier version in COLT’95.
E. Aimeur, G. Brassard, and S. Gambs. Machine learning in a quantum world. In Proceedings of Advances in Artificial Intelligence, 19th Conference of the Canadian Society for Computational Studies of Intelligence, volume 4013 of Lecture Notes in Artificial Intelligence, pages 431–442, 2006.