Кажется, скоро мы увидим работающий квантовый компьютер?

Буквально на этой неделе, в понедельник, 7 декабря, Google опубликовала статью о результатах совместной работы с NASA по созданию кода для квантового компьютера канадской компании D-Wave Systems. В общем смысле их опыты показывают, что канадская машина может отрабатывать код в 100 млн раз быстрее, чем классический одноядерный процессор, но только для специфических задач. А именно использовался алгоритм квантового отжига и алгоритм имитации отжигадля сравнения. Статья ещё находится на рецензировании, но уже вызвала шквал реакции в стиле «SkyNet уже близок» (1, 2 — на английском, 3, 4 — на русском, даже на пикабу есть пост радости). Почему-то практически все СМИ (особенно непрофильные) решили, что Google заявил о создании работающего квантового компьютера, но так ли это?

Ещё с 2013 года Google и NASA совместно работают над созданием кода для квантового компьютера канадской компании D-Wave Systems. А сама эта компания уже с 2007 года заявляет о создании квантого компьютера, из раза в раз увеличивая количество кубитов* в компьютере. В июне 2015 года они достигли более 1000 кубитов в своем компьютере D-Wave 2X, и именно его и использовали Google в своей работе. Чтобы вы понимали стоимость этой машины, приведу стоимость более ранней версии D-Wave One (128 кубитов) — 11 миллионов долларов. А выглядят эти машины, как старые добрые мэйнфреймы, в виде чёрных кубов. Такой размер частично обусловлен необходимостью иметь систему охлаждения, ведь чипы нужно охлаждать до 20-и милликельвин.

Для начала стоит вспомнить историю: все это время вокруг D-Wave существует изрядная доля критики. Сначала её критиковали за неспособность доказать, что её компьютер решает какие-либо задачи быстрее, чем обычный. Потом часть критики сняли исследованиями, но остался вопрос — удается ли ввести в состояние квантовой запутанности кубиты этого компьютера или нет? Потому что если кубиты не находятся в запутанном состоянии, то, строго говоря, это не квантовый компьютер. Вот хорошая статья (переведена на русский) от 21 февраля 2012 года доцента MIT Скотта Ааронсона. В ней он признается, что часть критики снимает, но вопрос о том можно ли называть компьютеры D-Wave квантовыми для него остался открытым. Когда он спрашивал в компании, почему они, вместо того, чтобы все больше и больше добавлять кубиты и увеличивать ничем не подкрепленные рекламные обещания, не занимаются доказательством квантовости компьютера (например, достаточно убедительна была бы демонстрация нарушения неравенства Белла), то ему ответили, что при таком подходе они уже покинули бизнес. Потому что инвесторы, дающие деньги на проект, оказывают давление как раз в сторону все большего числа кубит и все более громких анонсов, а не в сторону более ясного понимания экспериментального оборудования D-Wave. Совсем недавно проводились исследования, косвенно доказывающие квантовую природу этого компьютера, что поумерило пыл критиков.

Так вот, возвращаясь к Google, с чьим исследованием можно частично ознакомиться у них в блоге, — смогли ли они убедить критиков, что этот компьютер действительно является квантовым и что он действительно решает реальные задачи быстрее классического? Как видно по ленте твиттера D-Wave, ребят-разработчиков уже поздравляют и сами они на грани праздника. :) Но практически в то же время, что и пост в блоге Google, вышел пост главного критика, Скотта Ааронсона, и обзор эксперта по этой теме Мэттиаса Тройера. Ниже я приведу выжимку из обзора.

Итак, что сделали в Google? Они взяли три алгоритма (в скобочках указано обозначение на графике): Квантовый отжиг (D-Wave — Quantum annealing D-Wave), Имитация отжига (SA — Simulated Annealing), Квантовый Монте Карло (QMC — Quantum Monte Carlo).

Алгоритмы отжига — это алгоритмы нахождения глобального минимума некоторой функции среди некоторого набора решений кандидатов, которые в том числе оперируют вероятностями (подробнее в вики). В своем исследование, они взяли классическую NP-полную задачу Number Partitioning, где дается какой-то список положительных значений и цель — разделить эти значения на две группы так, чтобы сумма групп отличаласт между собой минимально. Вот в применении к этой задаче и были получены данные, проиллюстрированные на графике ниже.

Основные выводы:

- Квантовый отжиг, реализованный на D-Wave, достигает глобального минимума значительно быстрее, чем алгоритм имитации отжига, имплементированный на обычном процессоре. Причем экспоненциально с увеличением сложности задачи. Чем больше сложность, тем больше разрыв. И главный вывод, что D-Wave обеспечивает это преимущество.

- При сравнении же квантового отжига на D-Wave с квантовым Монте Карло (который на самом деле не совсем квантовый), реализованном опять-таки на классической архитектуре, глобальный оптимум достигается первым алгоритмом в 108 раз быстрее, хотя ускорение уже не зависит от сложности задачи, а является постоянным. С одной стороны, такое ускорение все ещё имеет практическое значение, с другой — не нужно забывать, что это ускорение наблюдается только для случаев симуляции квантового компьютера обычным. Иными словами, алгоритм квантового отжига хорошо ложится на архитектуру квантового компьютера, когда как сравниваемые с ним имитационный алгоритм и «квантовый» Монте-Карло являются в каком-то смысле неестественными, неоптимальными алгоритмами для архитектуры классического процессора.

- Это ускорение исчезает в сравнии алгоритма квантового отжига с оптимальным алгоритмом для обычного процессора, например, с алгоритмом Шелби.

Иначе говоря, у Google есть возможные доказательства того, что с достаточным количеством кубитов и достаточно большой по размеру проблемой, вычисления на квантовом компьютере будут быстрее для очень специфичной задачи по сравнению с неоптимальным классическим алгоритмом. Можно предположить, что увеличение количества кубитов позволит D-Wave победить и оптимальные классические алгоритмы, но каких-то оснований считать так — сейчас нет. Возможно, это ускорение по большей части связано с довольно узкоспециализированным железом D-Wave, чем с квантовой механикой вообще. Ведь D-Wave чип сравнивают с классическим чипом, который фактически имитирует архитектуру D-Wave.

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

В заключение, стоит сказать: конечно, значимость этого исследования преувеличена, хотя бы потому, что подобные исследования уже были. Но это никак не умаляет значимости самой области квантовых компьютеров, где в последние два года все больше и больше новостей. Ведь кроме D-Wave есть ещё очень много других разработок и команд, которые концентрируются не столько на увеличении кубитов, сколько на понимании работы кубита, контроле и поддержки помехоустойчивости. Это принципиально другой подход: сначала разобраться с одной единицей, а потом уже масштабировать. Группа Джона Мартина в Google, одного из авторов обсуждаемого материала, как раз этим и занимается, и сейчас у них есть суперпроводящие кубиты, имеющие лучшее время когерентности (время, в течение которого кубит сохраняет свои квантовые способности), чем у D-Wave. А в ближайшем будущем планируют собрать пул из 40 таких кубитов. В России квантовыми компьютерами занимается РКЦ, был уже создан кубит. Если конкретно, то занимается этим Алексей Устинов, его лекцию можете посмотреть тут. Поэтому мы имеем неплохие шансы нагнать технологическое отставание в момент нового скачка.

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

P.S.

*Элемент классического компьютера может хранить только 0 или 1, а кубит, как единичный элемент квантового компьютера может находиться в суперпозиции, т.е. одновременно кодировать 0 и 1. Два кубита — это суперпозиция уже 4 состояний. Три кубита — восьми. В роли кубитов могут выстпуать атомы или электроны, а данные могут кодироваться, например, спином. Часто говорят про преимущество квантового компьютера в параллелизме вычислений. Но это не совсем так, это кажется параллелизмом. На самом деле квантовый компьютер позволяет проводить вычисления в суперпозиционном состояние, пока поддерживается суперпозиция. Но это возможно только если структура задачи позволяет каким-то образом отметать ошибочные результаты, оставляя единственно верный.

iwtkl