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

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

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

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

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

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

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

PAC-навчання

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

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

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

Історія

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

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