Журнал «Компьютерра» N 9 от 06 марта 2007 года - Журнал Компьютерра

•

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

• На вопрос об этом D-Wave отвечает: «все верно, но нас интересуют не точные, а приближенные решения, и не любых NP-полных задач, а только важных для практики». Однако и для таких задач ничто не указывает на возможность радикального ускорения при помощи КК. Для многих NP-полных задач получить приближенный ответ так же трудно, как точный. Более того, неизвестно, будет ли «адиабатический квантовый алгоритм», который D-Wave предлагает использовать, работать на практических задачах лучше, чем классический алгоритм - например, метод имитации отжига (simulated annealing).

• Демонстрация, проведенная D-Wave, сама по себе ничего не доказывает. Глядя на нее, невозможно сказать, не ограничились ли они тем, что построили 16-битный классический компьютер (не по 16-битной архитектуре - а просто состоящий ровно из 16 битов). Задачи, которые были показаны, ничего не стоит решить на обычном компьютере, даже на графическом калькуляторе - и когда об этом говорят, как о «первом коммерческом квантовом компьютере», это комедия какая-то. Вполне возможно, что D-Wave действительно сделала нечто интересное на своих сверхпроводящих кубитах. Но по такой демонстрации экспертам со стороны невозможно это оценить, не зная технических деталей: каково время декогеренции? Каковы перспективы масштабируемости? Увы, именно детали такого рода D-Wave, по-видимому, до сих пор не раскрывает, ссылаясь на озабоченность проблемами с интеллектуальной собственностью. Многие журналисты готовы толковать любые сомнения в пользу D-Wave. Но академический подход возлагает бремя доказательства на D-Wave, и только на нее.

• Допустим, что КК может лишь слегка ускорить решение NP-полных задач. Допустим, что машина, предъявленная D-Wave, немасштабируема и подвержена шумам. Но даже при этих допущениях - если бы D-Wave удалось создать 16-кубитный КК, хоть чуть-чуть обгоняющий классический, это было бы огромным научным достижением. К сожалению, неясно, удалось ли D-Wave это сделать.

Ведь они сравнивают скорость квантового алгоритма на своем КК с худшим, что есть в классике - с прямым перебором вариантов. Но на практике никто так задачи не решает. Честно было бы сравнить скорость работы квантового алгоритма с какой-нибудь классической оптимизацией типа имитации отжига. Насколько я знаю, такого сравнения не делалось.

D-Wave объявила, что построила лишь специализированный, а не универсальный КК. Но это мало что меняет. Недавно было доказано (arXiv:quant-ph/0405098), что на адиабатическом квантовом компьютере можно реализовать и универсальный КК. Значит, в данном случае правомерно ставить вопрос о возможностях такого компьютера и о том, насколько D-Wave продвинулась в его построении.

Я постарался объяснить, почему публичные заявления D-Wave по обоим этим вопросам выглядят очень ненадежно.

Скотт Ааронсон

Стилистика и мораль

Разные наблюдатели были разочарованы разными вещами и в разной степени. Скотт Ааронсон был больше всего разочарован лихими обещаниями по поводу NP-полных задач. Сила его разочарования была такова, что блог Скотта, наряду с блогом Дейва Бэкона (Dave Bacon, dabacon.org/pontiff), известного также как «Квантовый понтифик», стал в январе-феврале основным полем дискуссий и источником технической информации о D-Wave, концентрируя сотни очень компетентных и часто острых замечаний. Ааронсон даже успел дать комментарий для Nature, который был опубликован накануне демонстрации, 12 февраля, где он подчеркивал необоснованность претензий компании на ускорение решения NP-полных задач [Geoff Brumfiel, «Quantum computing at 16 qubits», Nature, 12 февраля 2007].

Но мне бы хотелось подчеркнуть нечто иное - Джорди Роуз, основатель и CTO D-Wave, и раньше цитировавший научные работы Ааронсона, прилежно отвечал на его критику. Причем не просто отвечал, а попросту соглашался с ней, и даже неоднократно - утверждая, что никогда и не претендовал на экспоненциальное ускорение NP-полных задач, а в лучшем случае - на квадратичное, давно полученное Гровером в его знаменитом квантовом алгоритме поиска (позволяющем найти нужную запись из N записей за

• N попыток, причем без всякой дополнительной структуры данных). Кстати, СЕО D-Wave Герб Мартин (Herb Martin) с характерной для опытного топ-менеджера прямотой заявил, что созданная его фирмой машина не настоящий квантовый компьютер, а специализированное устройство, использующее квантовую механику для решения практически важных задач. «Работать над универсальным КК - потеря времени, - сказал он. - Можно потратить сотни миллиардов долларов и ничего не добиться».

Если очень внимательно вчитаться в бойкие лозунги D-Wave (подхваченные множеством изданий, включая и такие солидные, как The Economist), легко убедиться, что формально недобросовестных утверждений там нет. Но D-Wave не дала и объяснений своей технологии специалистам на уровне академических стандартов.

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

Скотт Ааронсон согласен с этим: «Если бы D-Wave воздержалась от таких диких преувеличений, я уверен, что реакция на их работу была бы куда более благожелательной».

Вопрос в том, чья реакция для компании важнее - те 300 статей в центральной прессе всего мира, которые в основном повторили запрограммированные для прессы лозунги - или раздражение сообщества экспертов. Точного ответа я не знаю, но в целом ситуация знакома любому, кто работал с инвесторами хайтека. Инвесторы почему-то часто хотят как раз диких преувеличений: квантовый компьютер! искусственный интеллект! алгоритмы человеческого мозга! Может быть, такая шумовая завеса лучше «продает» новый, еще не созданный продукт?..

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

Вот в этом я и вижу главную для нас, здешних читателей, айтишников и научников, мораль этой истории. В конце концов, технологии как таковые - ну куда они денутся? Так или иначе, загадки D-Wave прояснятся (кстати, не исключено, что мы познакомимся с компанией поближе; там много любопытного, в том числе интересный «русский след», как среди разработчиков, так и в совете директоров, куда входит Алексей Андреев, директор Американской бизнес-ассоциации российских экспатриантов). Да и вообще, недавно кто-то в блогах смешно написал, что «под виндой и квантовый комп будет круто тормозить».

Главное для нас в этой истории - увидеть - повторю: реально работающее, мгновенно оцененное, свободно вырабатываемое мнение научного сообщества. Ведь здесь такая история, как с D-Wave, невозможна по многим причинам. Знаете, есть исторический анекдот: Петра I в каком-то городе не встретили, как положено, салютом, он рассвирепел - как посмели?!. Градоначальники забубнили: на это есть семь причин: первая - пороху нет, вторая… но тут Петр сказал - хватит! Так и у нас: во-первых, нет таких проектов. Во-вторых, нет научного сообщества… хватит?

Десять лет до квантового супаПерспективен ли подход, примененный D-Wave?

- D-Wave анонсировала адиабатический КК (АКК). Потенциальное преимущество этого подхода - он не требует цепочек квантовых операций, индивидуального контроля над кубитами. Однако применимость АКК к решению вычислительно сложных задач, в том числе NP-полных, зависит от того, как будут меняться параметры системы при увеличении числа кубитов. Важнейший параметр АКК - так называемый зазор (gap), расстояние между основным и следующим за ним уровнем энергии. Чем меньше зазор, тем больше времени нужно для эволюции АКК к решению задачи. Вопрос - насколько больше? Оказывается, тут вполне возможен экспоненциальный рост, что лишает смысла всю затею. Есть примеры, для небольшого числа кубитов, когда АКК в теории должен работать хорошо. Но все-таки масштабируемость я считаю здесь маловероятной.

Как же все это проверить?

- Только одним способом - построить установку. За это взялась D-Wave, и мне такой подход очень нравится. Не нравится мне другое - их суперрекламные заявления. Они очень опасны потому, что могут дискредитировать в глазах общества квантовый компьютинг как таковой.