Квантовое машинное обучение быстрее классического
Исследователи из IBM Quantum рассказали о потенциале квантовых методов машинного обучения. Опубликованная в Nature Physics статья показывает, что квантовые алгоритмы, хоть пока их не очень много, могут дать результат куда быстрее классических методов — при условии, что обучение проходит на одних и тех же данных.
Один из таких алгоритмов — алгоритм факторизации Шора, то есть, разложения чисел на простые множители. Суть алгоритма заключается в сведении задачи к поиску периода заданной функции. Эту часть выполняет квантовый компьютер, а факторизация осуществляется на классическом компьютере алгоритмом Евклида — примерно так, как нас учили в начальной школе.
Алгоритм Шора страшен для систем шифрования. Например, алгоритм RSA имеет открытый ключ, который может получить любой. На самом деле, этот ключ — произведение двух очень длинных простых чисел, именно они нужны для взлома шифра. Вручную или с помощью классических алгоритмов эти числа не найти — для взлома одной такой комбинации в 1993 году потребовалось полтора года вести расчёты на 1600 машинах. На одной машине такой процесс занял бы 2400 лет! А алгоритм Шора справился бы за сравнительно небольшое время.
Авторы исследования применили его для другой задачи — задачи дискретного логарифмирования. Сложность, которую обеспечивают классические методы машинного обучения в этой задаче экспоненциальна. Это значит, что время, затрачиваемое на расчёт, будет расти по экспоненте с увеличением чисел. Но учёные показали, что алгоритм Шора справится с дискретным логарифмированием за полиномиальное время, что намного лучше. А развитие квантовых методов сможет повысить скорость вычислений в будущем — в том числе и для распознавания котиков.
Задачи классификации — например, разбор изображений по разным категориям или поиск котиков на фото.