Квантове машинне навчання

Квантове машинне навчання — розділ науки на стику квантової фізики та інформатики, в якому розробляються та вивчаються методи машинного навчання, здатні ефективно використати паралелізм^[ru] квантових комп'ютерів.

Основні моделі навчання

У квантовому машинному навчанні застосовуються три основні моделі навчання:

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

Точне навчання

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

PAC-навчання

У цій моделі також шукається функція, що найточніше відповідає невідомій функції, проте можливість робити запити відсутня. Натомість є якийсь набір зразків. Математично метою є висування такої гіпотези про невідому функцію, яка найкраще відповідає невідомій функції на даному наборі зразків. Відмінністю квантового PAC-навчання від класичного є те, що дані зразки, взагалі кажучи, можуть перебувати в стані квантової суперпозиції. У загальному випадку це, однак, не дає значного виграшу, і квантовий алгоритм відрізняється за швидкістю від класичного лише на деякий сталий множник. Існує, щоправда, деякий клас невідомих функцій, для яких квантове PAC-навчання значно швидше від класичного.

Агностичне навчання

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

Історія

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

У 2000-х роках запропоновано і квантові алгоритми розв'язування деяких типових задач машинного навчання. Наприклад, у роботі 2006 року^[2] запропоновано варіант алгоритму Ґровера для задачі кластеризації.

Примітки

↑ 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.