Классная история про "битву" классических и квантовых алгоритмов. Есть такая задачка по подбору рекомендаций для пользователя на основании его профиля и общей базы пользователей (пример: какой фильм вам порекомендовать в Netflix). Задачка вычислительно емкая.

Несколько лет назад в работе Iordanis Kerenidis и Anupam Prakash, "Quantum Recommendation Systems", авторы показали, как получить экспоненциальное ускорение относительно существующих классических алгоритмов за счет использования квантового компьютера (работа теоретическая). Это был отличный пример алгоритма, показывающего, зачем нужен квантовый компьютер. И также это было отличной заявкой на иллюстрацию преимущества симбиоза машинного обучения и квантовых вычислений. Было только одно но: они не доказывали в работе, что классический алгоритм с сопостовимыми результатами не возможен.

В общем, Ewin Tang (University of Texas), вдохвовившись результами и логикой работы квантового компьютера, смог создать "классический" аналог, также с экспоненциальным ускорением. В целом, это отличная иллюстрация того, что одновременное изучение квантовых и классических алгоритмов может быть новые идеи даже для текущего поколения машин.

Новость: https://www.quantamagazine.org/teenager-finds-classical-alternative-to-quantum-recommendation-algorithm-20180731/
Публикация: https://arxiv.org/pdf/1807.04271.pdf