Компьютерра - Журнал «Компьютерра» № 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 записей за