Битва компов или убийца квантовой мечты

Классические и квантовые компьютеры в борьбе за превосходство

В недавнем отчете Национальных академий наук, инженерии и медицины США (в том числе среди ведущих исследователей Google и Microsoft) подчеркиваются технические препятствия на пути создания практически полезных квантовых компьютеров.

Физик-теоретик Сет Ллойд из Массачусетского технологического института (Кембридж) говорит, что шумиха вокруг квантовых вычислений просто  выходит из-под контроля.

Так нужен ли квантовый компьютер?

Высококлассная работа 18-летней программистки нанесла удар по квантовой теории. Эвин Танг (Ewin Tang) «научила» старый компьютер новому трюку, который, как ранее считалось, решается только в квантовой системе.

Эвин Танг. Аспирант, Вашингтонский университет.
В 18 лет уже работает над докторской диссертацией по теоретической информатике. Она попала в заголовки, когда разработала вычислительный метод, который, по ее словам, «убрал квант» из квантового алгоритма, позволяя обычным компьютерам решать определенную проблему так же быстро, как квантовый компьютер.
Получила место в списке Forbes «30 до 30 лет» в науке за разработку метода, который позволяет классическому компьютеру решать «проблему рекомендаций»
Ее алгоритм предлагает эффективное решение основной проблемы машинного обучения, которая моделирует задачу прогнозирования предпочтений пользователя по неполным данным на основе взаимодействия людей с сайтами, такими как Amazon и Netflix.

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

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

Но что важно, квантовый алгоритм решения, который разрабатывался именно для этой задачи, теперь стал спорным и не единственным. Тем более, пока нет возможности запустить его на реальной машине.

В конце 2018 года Танг, которая сейчас учится и работает в Вашингтонском университете Сиэтла, нанесла второй удар по «квантовой религии». Она и два ее коллеги запустили алгоритмы для определенных задач машинного обучения.

Мем. «Эвин Тан против квантового сообщества. Тактика шока и страха»

Классике быть!

Перед Эвин Танг была поставлена задача подтвердить недавнее открытие «квантовых теоретиков» Керенидиса и Пракаша. (Иорданис Керенидис и Анупам Пракаш - исследователи из Университета Парижа Дидро и Калифорнийского университета в Беркли)

В 2016 году они опубликовали алгоритм квантовых рекомендаций, который мог бы решить проблему экспоненциально быстрее, чем классический компьютер, полагаясь, отчасти, на случайную выборку пользовательских предпочтений. Иными словами ученые утверждали,  что не существует быстрого классического алгоритма для решения проблемы. Правда они не смогли окончательно доказать это!

За доказательство рьяно взялась Эдвин Танг! Но, после того, как исследователь представила свои результаты на семинаре в Калифорнийском университете в Беркли в июне 2018, членам сообщества квантовых вычислений пришлось согласиться, что ее новый классический алгоритм перевернул двухлетнее открытие… с ног на голову.

С ног на голову. Суть работы Танг

Изучаемая Танг система рекомендаций предлагала  продукты для пользователей на основе данных о пользовательских предпочтениях. При этом моделировалось заполнение матрицы m ? n малого ранга k. Стратегия исследования была основана на квантовом алгоритме Керенидиса и Пракаша: вместо того, чтобы реконструировать полный список предпочтений пользователя, проводится поиск только случайной выборки у из предпочтений пользователя. Основным результатом являлся алгоритм, который выбирал записи с высоким весом из аппроксимации низкого ранга входной матрицы во времени, не зависящем от m и n.

Шах квантовой теории! Будет ли мат?

Оказалось, что алгоритм квантового машинного обучения (QML) Керенидиса и Пракаша, одного из самых сильных кандидатов на доказуемо экспоненциальное ускорение в QML, на самом деле не дает экспоненциального ускорения по сравнению с классическими алгоритмами!

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

Вот так, бойкая и умная Танг создала свой «квантово-вдохновленный классический алгоритм для систем рекомендаций»!

Как недавно она шутила в GeekWire (GeekWire - американский новостной веб-сайт, посвященный технологиям, который охватывает стартапы и признанные технологические компании): «В итоге мы получили результат в обучении квантовой машины, и в качестве приятного побочного эффекта появился классический алгоритм».

Рекомендательные алгоритмы когда-то считались одним из самых простых для понимания приложений квантового компьютера. Исследования показали, что квантовый алгоритм действительно дает значительно более быстрые результаты, чем лучшие классические вычислительные алгоритмы. До Танг никто не отваживался использовать классический  компьютер  для получения аналогичных результатов.

Убийца квантовой мечты

Компьютерное сообщество ответило на новость мемами, в которых, например, Танг сравнивали с гладиатором, убивающим надежды и мечты квантового сообщества.

Хотя гуру этой области знаний утверждают, что такое использование классических вычислений на самом деле является успехом квантовых вычислений, потому что они показывают, как квантовый образ мышления может оказать влияние, так это еще и без реальных квантовых компьютеров!

Ученые и разработчики не устают повторять, что  квантовые компьютеры обладают доказанным преимуществом. Например, в веб-поиске, при делении больших целых чисел на простые или моделирование электронных свойств материалов.

И все же, даже после новости от IBM, квантовые компьютеры - это долгая в решении и затратная технология поиска проблем, которые необходимо решать. Между тем поражает, насколько далеко могут простираться классические стратегии решения современных алгоритмов обычным современным инструментарием.

Исследования в области квантовых устройств предполагают определенный уровень вычислительной мощности. Пока же такие компании, как Cray, Rigetti Computing и IBM работают над моделями элементарного квантового компьютера.

Квантовый компьютер и квантовый проект остаются похвальными целями. Но это не единственный путь в будущее.