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

Журнал Компьютерра

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

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

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

О достоинствах и подводных камнях АКК во врезке рассказывает Артур Экерт. «Элементная база», на которой работает Orion - решетка размером 4х4 из сверхпроводящих элементов, колец из алюминия и ниобия. "Состояние кубита здесь зависит от наличия или отсутствия магнитного потока через кольцо. Этот поток для таких колец тоже квантуется. Как организовать взаимодействие кубитов? Детали, возможно, известны специалистам по сверхпроводимости; в препринте, на который ссылаются разработчики, речь идет об индуктивной связи через контур", - пояснил нам Юрий Ожигов.

Именно непроясненность принципиальных деталей и разочаровала академическое сообщество, следящее за проектом.

Жить NP-полной жизнью нелегко

•

В пресс-релизах 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) с характерной для опытного топ-менеджера прямотой заявил, что созданная его фирмой машина не настоящий квантовый компьютер, а специализированное устройство, использующее квантовую механику для решения практически важных задач. «Работать над универсальным КК - потеря времени, - сказал он.
– Можно потратить сотни миллиардов долларов и ничего не добиться».