"Журнал «Компьютерра» N 9 от 06 марта 2007 года" - читать интересную книгу автора (Компьютерра Журнал 677)

D-Wave: кубитное шоу с моралью: D-Wave восхитила журналистов и возмутила ученых

Автор: Леонид Левкович-Маслюк

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

ДЕТАЛЬ

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

Канадская частная компания D-Wave объявила о предстоящей 13 февраля 2007 года публичной демонстрации квантового компьютера (КК) еще в январе. Пояснения в блоге основателя и директора D-Wave по технологиям (CTO) Джорди Роуза (Geordie Rose) привели многих буквально в ярость - и не удивительно! «Если вам нужен быстрый солвер для NP-полных задач, начинайте уже сейчас думать, чем загрузить серьезные мощности» - писал Роуз, сообщая, что во втором квартале 2007 года планирует открыть свободный дистанционный доступ пользователей к КК. Математиков эти новости сильно озадачили - ведь для таких задач эффективные квантовые алгоритмы неизвестны. Физиков же ошеломил стахановский график наращивания числа кубитов (масштабирования), вплоть до выхода на 1024 штуки (сейчас в Orion’е их 16) к концу 2008 года. В блогах, а потом и в прессе пошел серьезный разговор - как все это понимать?

Мы обратились за комментариями к трем специалистам по квантовому компьютингу: Юрию Ожигову, профессору кафедры квантовой информатики МГУ, Скотту Ааронсону (Scott Aaronson) - молодому блестящему математику из Института квантовых вычислений канадского университета Ватерлоо (scottaaronson.com/blog, именно он возглавил неформальную кампанию за пусть не «разоблачение», но серьезное уточнение формулировок, даваемых D-Wave), и Артуру Экерту - пионеру квантового крипто, основателю Центра квантовых вычислений в Кембриджском университете, «выдающемуся профессору» (distinguished professor) Национального университета Сингапура, лауреату ряда научных премий. Все три независимых мнения (они приведены во врезках) оказались весьма критическими.

Маленькое отступление: Артур Экерт был в составе сборной Польши по дзюдо на Московской олимпиаде 1980 года - а Джорди Роуз четырежды, вплоть до 2001 года, брал золото на канадских чемпионатах и по вольной и по греко-римской борьбе. Вот какие замечательные люди встретились на наших страницах, вот какие замечательные параллели возникли - а если читатель думает, что дальше мы будем клеймить D-Wave со ссылкой на авторитеты, то это ошибка. Можно сразу перейти к экспертным врезкам ( это не от слова «врезать»!), читать дальше или вообще бросить эту тему (а если сознание читателя уже находится в квантовой суперпозиции, все это можно делать одновременно!) - но авторский план таков: во-первых, установить, что причины конфликта - стилистические; во-вторых - вывести из произошедшего совсем не техническую мораль. Но сначала кратко о технологиях КК.

Время от времени появляются совершенно нереалистичные сообщения о решительных прорывах в проблеме квантового компьютера. Например, два года назад за рубежом анонсировался квантовый компьютер на фотонах, который якобы делал квантовое преобразование Фурье на 1024 кубитах. Одного из двух авторов анонса мы пригласили к нам на семинар, уточнили с ним вместе, что можно, а что нельзя называть квантовым компьютером - и недоразумение уладилось. Случай D-Wave похож на этот, но тут еще и мощная рыночная составляющая, которую я не готов обсуждать. По научной же составляющей возникает масса вопросов:

• Где протокол квантового вычисления с пошаговым распределением амплитуд для базисных состояний?

• Какой именно алгоритм реализован?

• Где демонстрация распределения амплитуд для основных вентилей (типа CNOT или Toffoli)? Такая демонстрация должна предоставляться при любой схеме квантового компьютера, в том числе и для адиабатических вычислений, которые анонсировали авторы.

• Где сравнение с идеальной моделью квантового вычисления? Ведь для 16 кубитов симуляцию на обычном компьютере можно провести элементарно, у нас на кафедре есть парочка таких симуляторов.

• Где детальное описание архитектуры компьютера? Основные элементы - кольца из алюминия и ниобия хорошо известны, но по схеме устройства непонятно, как организуется хранение запутанных состояний.

Ни на один из этих вопросов мы не получили ответа. Далее, специалистов по сверхпроводимости удивляет, что устройство так быстро переключается с задачи на задачу - системы управления сверхпроводящими элементами вряд ли могут такое обеспечить. Непонятно, почему доступ к устройству только дистанционный; непонятно, почему в планах по наращиванию числа кубитов только степени двойки: 16, 512, потом 1024 (а такое мы уже проходили). К сожалению, все это очень мешает всерьез относиться к разработке D-Wave. А серьезные разработки на таких технологиях существуют. Например, в группе Юрия Пашкина из NEC уже два года назад было создано устройство из двух кубитов на сверхпроводящих элементах. Об этом Пашкин докладывал на нашей конференции, и там все эти пять пунктов были детально разобраны, было и много другой информации, так как дело это сложное. Не сомневаюсь, что КК на трех кубитах появится очень скоро - все запутанные состояния для них уже получены экспериментально. Дальше будет труднее. О масштабируемости (присоединяем новое сверхпроводящее кольцо - и готов еще один кубит) - забудьте.

КК - это не ноутбук, и даже не Cray. Создание масштабируемого полнофункционального КК на 100 (сто) кубитов будет событием в естествознании, перед которым померкнет квантовая физика как таковая. Я лично думаю, что этого не произойдет никогда - в силу фундаментальных ограничений. А вот что будет сделано почти наверняка - ограниченный квантовый процессор. Это квантовое устройство, организующее запутанные состояния кубитов (просто запутать несколько десятков - уже сейчас не проблема), которые можно использовать для помощи классическим компьютерам (например, при моделировании молекул). Такая цель реальна. Но она достижима только на пути серьезных исследований с возможностью полного контроля и воспроизведения результатов.

Юрий Ожигов

«КТ» уже столько писала об этом удивительном предмете (впервые еще в 1997 году в номере 224, без малого десять лет назад, а в новостях КК теперь мелькает почти на каждой неделе) что и читатели, и авторы уже выработали у себя в голове некое рабочее представление о квантовом компьютере: там внутри совокупность частиц (кубитов), находящаяся в едином, «запутанном» квантовом состоянии, и эту совокупность постепенно подкручивают в абстрактном квантовом пространстве, то один кубит, то другой, до тех пор, пока она не займет там нужное положение - и тогда все это измеряют, и получают ответ. Чудо в том, что есть задачи, требующие запредельного счета на обычном компьютере, но решаемые (теоретически) очень быстро на КК. Не потому, что КК перемалывает те же биты быстрее, чем просто К. А за счет того, что квантовая система способна каким-то образом одновременно проживать все возможные варианты своего развития - и среди них можно (с хорошей вероятностью) выбрать тот, что кодирует решение требуемой задачи.

Если кого-то не удовлетворяют такие заклинания - надо лезть в книги. Могу поделиться личным опытом. Не так давно я нашел в себе силы разобрать простейший и исторически первый пример квантового вычисления, обгоняющего обычное, классическое. Это пример того, как в квантовом случае можно за одну операцию узнать ответ к задаче, которая в классике требует ровно двух операций. Тем, кто готов затратить время и силы - рекомендую. Производит впечатление! Потому что трюк основан именно на том, что частица одновременно проходит по двум разным путям. И это выражено самой простой, школьной математикой на основе самых-самых азов квантовой механики - самой, в свою очередь, подтвержденной на опыте теорией из всех физических теорий, хотя и неинтуитивной донельзя.

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

В нашумевшем эксперименте 2001 года, выполненном группой Айзека Чуаня (Isaac Chuang), КК состоял из одной молекулы, а кубитами были ядра входящих в нее атомов (семь штук). Воздействуя на эти ядра радиоимпульсами, удалось реализовать квантовый алгоритм факторизации - представить число 15 как 3х5. Этот подход относится к так называемым ЯМР-технологиям; считается, что много кубитов на них получить вряд ли удастся (сейчас рекорд - то ли 12, то ли 8, по данным разных экспертов).

Вот еще ряд технологий, с которыми активно экспериментируют. Ионные ловушки в полупроводнике - тут уже получены запутанные состояния ионов меди и магния (тоже все в районе десяти штук). Идет работа над кубитами на квантовых точках («искусственных атомах») - это особые зоны, состоящие примерно из миллиона атомов в полупроводнике, а внутри этих зон удерживаются один или несколько электронов. Кубит - пара квантовых точек, значение «ноль» соответствует состоянию «электрон в „левой“ точке», «единица» - электрон в «правой» точке, а в процессе счета - ну, элементарно, часть электрона в одной точке, часть в другой, причем эти части измеряются комплексными числами… Есть еще идея - применить цепочки ядерных спинов, нанометровые структуры в полупроводнике: в канал в кремнии имплантируется 104-106 ионов фосфора, и получается кубит. Наконец, p-контакт - кубит в виде перехода на границе высокотемпературных сверхпроводников, его энергия имеет два минимума (ноль и единица).

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

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

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

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

•

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

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

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

- Думаю, лет через десять. Скорее всего, это не будет КК, последовательно выполняющий цепочки квантовых операций. Новые идеи тут появляются очень часто - люди ищут такие подходы, где не нужно с огромной точностью контролировать индивидуальные кубиты. О АКК мы уже говорили. А недавно возникла идея одностороннего (one-way), или кластерного (cluster), КК. Это суп из большого количества запутанных частиц, он все время пополняется новыми частицами, некоторые из него исчезают, а постепенно вся система путем необратимых воздействий направляется к состоянию, описывающему решение задачи.

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

Артур Экерт, по телефону из Сингапура