Регистрация11.04 // Моя поездка в D-Wave: по ту сторону мясного сэндвича
Скотт Ааронсон (wiki), адъюнкт-профессор факультета электротехники и информатики
Массачусетского Технологического Института © 2012
Перевод © 2012 spinore
Массачусетского Технологического Института © 2012
Перевод © 2012 spinore
На последней неделе я был в Ванкувере в связи с выступлением перед Университетом Британской Колумбии и перед ежегодным собранием Американской Ассоциации Содействия Развитию Науки. В рамках этой поездки в пятницу вечером мне, Джону Прескиллу, Джону Мартинису и Майклу Фридману любезно предложили съездить в штаб-квартиру D-Wave Systems в Burnaby (пригород Ванкувера). Мы начали поездку с конференцзала, где организаторы предложили нам печенье и газированную воду. У меня, как взрослого человека, пролетела в голове случайная мысль, что печенье может быть отравлено.
Затем мы сходили в лаборатории D-Wave: посмотрели под микроскопом на сверхпроводящие чипы; на системы охлаждения, использующиеся для охлаждения чипов до 20ти милликельвин. Мы действительно заходили внутрь гиганстких чёрных кубов, приготовленных D-Wave'ом на продажу, которые напоминали нам эпоху мейнфреймов (эти машины настолько велики частично из-за необходимости иметь системы охлаждения и частично — чтобы исправлять неполадки, позволяя инженерам заходить внутрь). Позже главный инженер D-Wave, Geordie Rose, выступил перед нами с двухчасовым докладом о самых последних экспериментальных результатах D-Wave, после чего мы все ушли на обед. Сотрудники D-Wave были очень гостеприимны с нами и не задумываясь отвечали на все наши вопросы.
Несмотря на моё, имевшее место почти год назад, заявление, что я увольняюсь с поста главного скептика D-Wave, я подумал, что было бы уместным рассказать читателям блога «Shtetl-Optimized» («Местечково-оптимизированное» (евр. рас.) — прим. пер.) о том, что нового я узнал из этой поездки. Я начну с трёх обоснованных утверждений, прежде чем перейти к более общим выводам.
- Утверждение 1: Сейчас D-Wave имеет 128-(ку)битную машину, которая может давать приближённые решения для конкретных NP-сложных минимизационных задач, а именно, для задачи минимизации энергии 90-100 спинов в модели Изинга с попарными взаимодействиями вдоль некоторого фиксированного графа (где машинный вход есть настраиваемые степени сопротивления взаимодействиям). Соответственно, настоящим сообщением я опровергаю свой печально известный комментарий от 2007го года о том, что 16ти-битная машина, которую D-Wave использовала для демонстрации решения судоку, не более вычислительно полезна, чем мясной сэндвич. К настоящему моменту D-Wave действительно сделала нечто, что более вычислительно полезно, чем мясной сэндвич; просто вопрос в том, является ли это «нечто» более полезно, чем ваш лаптоп. Geordie показал нам графики с D-Wave'овским квантовым отжигом, решающим свою задачу спинов Изинга «быстрее» чем классическим методом имитации отжига или методом поиска с запретами (слово «быстрее» здесь подразумевает пренебрежение временем на охлаждение отжигателя, что мне кажется правильным). К сожалению, данные не увеличивались до больших размеров на входе, в то время как те, которые-таки увеличивались, сравнивались скорее с полностью классическими алгоритмами, чем в эвристическими. (Конечно, здесь выносятся за рамки большие трудности, которые вероятно возникли бы при практическом применении D-Wave, начиная со сведения задач практической оптимизации к конкретной D-Wave'овской задаче на спины Изинга.) В итоге, хотя наблюдаемое ускорение вычислений и представляется определённо интересным, остаётся неясным, что с ним делать и, особенно, играет ли здесь роль квантовая когерентность.
- Это подводит меня к утверждению 2. Как я повторял здесь втечение нескольких лет (и это остаётся в силе), у нас нет реального доказательства того, что квантовая когерентность действительно играет роль в наблюдаемом ускорении вычислений, а также того, что запутанность между кубитами системы когда-либо действительно имела место. (Заметьте следующее: если допустить, что запутанности нет, существенность квантовой когерентности для ускорения вычислений становится совершенно неправдоподобной. Хотя пока что и не известно об эффективной симуляции на классических компьютерах тех квантовых, которые работают только с сепарабельными смешанными состояниями, мы совсем не знаем каких-либо примеров, где такие компьютеры позволяют ускорять вычисления.) Как отмечалось в этом блоге в прошлом году, D-Wave опубликовала прекрасную статью в Nature, где рассказывалось о квантовом туннелировании в 8ми-кубитной системе. Однако, когда я спросил об этом Мохаммада Амина, учёного из D-Wave, он ответил, что не думает, что эксперимент предоставил какие-либо доказательства существования запутанности между кубитами.
«Убедительным» способом продемонстрировать наличие запутанности между кубитами была бы демонстрация нарушения неравенства Белла. (Мы знаем, что это может быть сделано со сверхпроводящими кубитами, как было показано группой Schoelkopf'а в Йеле [а также другими коллективами] пару лет назад.) Кроме того, «убедительный» способ показать роль квантовой когерентности в возможном ускорении вычислений состоял бы в постепенном «уменьшении» когерентности в системе (например, путём добавления взаимодействия, которое бы постоянно измеряло кубиты в вычислительном базисе) и параллельной проверке того, что производительность отжигателя уменьшается до уровня, соответствующего классической имитации отжига. К сожалению, как сказали нам сотрудники D-Wave, никакой из подобных экспериментов не представляется возможным в их текущей установке — в основном потому, что у них нет возможности осуществлять произвольные локальные унитарные преобразования и измерения. Они сообщили, что хотят в будущем попытаться продемонстрировать наличие двухкубитной запутанности, а пока готовы услышать предложения по поводу других идей, как показать роль квантовости в возможном ускорении вычислений в их существуюшей установке.
- Утверждение 3: D-Wave в итоге смогло прояснить концептуальный момент, который смущал меня втечение лет. Я (и, возможно, многие другие!) полагали, будто бы D-Wave утверждает, что их кубиты декогерируют практически моментально (в частности, в таком случае запутанность практически точно никогда не имела бы места в процессе вычислений). Однако, как оказалось, D-Wave считает, что отсутствие запутанности не играет роли из-за какой-то сложной причины, связанной с энергетическими щелями (gap — прим. пер.). Я был далеко не единственным, кто считал такое утверждение невероятным: как было упомянуто выше, нет никакого доказательства того, что квантовый компьютер без запутанности может решать какую-либо проблему асимптотически быстрее, чем классический. Однако, это не то, что утверждает D-Wave: они думают, что их система декогерирует практически моментально в собственном энергетическом базисе, но она не декогерирует в вычислительном базисе, а поэтому, в частности, в последнем могла бы быть запутанность на промежуточных стадиях. Если так, то это было бы совершенно прекрасно — адиабатический алгоритм, который в любом случае не требует когерентности в собственном энергетическом базисе (в конечном счёте, общее утверждение состоит в том, что в процессе вычисления вы хотите находиться настолько близко к основному состоянию системы, насколько это возможно!). Я понимаю, что некоторые физики, знающие механизмы декогерентности, настроены чрезвычайно скептично по поводу возможности иметь быструю декогеренцию в энергетическом базисе без сопутствующей декогерентности в вычислительном базисе. Соответственно, теперь это, конечно, обязанность D-Wave — показать, что они поддерживают когерентность там, «где она нужна», но, по крайней мере, сейчас я понимаю, что они утверждают, и как это могло бы быть совместимым (если это вообще верно) с квантовым ускорением вычислений.
Давайте теперь перейдём к трём более широким вопросам, поднятым вышеcказанными утверждениями.
- Первый вопрос следующий: вместо того, чтобы добавлять всё больше кубитов и публиковать всё более тяжело оцениваемые рекламные заявления, оставляя при этом научную оценку своих приборов в состоянии неизвестности, почему бы D-Wave'у просто не сконцентрировать свои усилия на том, чтобы продемнстрировать запутанность, или другим способом получить более убедительное доказательство роли квантовости в наблюдаемом ускорении вычислений? Когда я спросил об этом Мохаммада Амина, он сказал, что если бы компания D-Wave последовала моему предложению, она бы опубликовала некоторые интересные исследовательские статьи и затем покинула бизес: при получении денег давление всегда оказывается в сторону всё большего числа кубит и всё более громких анонсов, а не в сторону более ясного понимания экспериментального оборудования D-Wave. Итак, дайте мне попытаться донести мысль до боссов мира: одиночный кубит, который вы понимаете, лучше, чем тысяча кубитов, поведение которых вы не понимаете. Существует причина, по которой академические группы, занимающиеся квантовыми вычислениями, концентрируются на задавливании декогеренции и демонстрировании запутанности для 2ух, 3ёх или 4ёх кубит: потому, что это путь, при котором вы знаете, что кубиты есть действительно кубиты! Как только вы показали, что основание считать кубиты настоящими твёрдое, вы можете пытаться масштабироваться вверх. Поэтому, пожалуйста, поддержите D-Wave, если они хотят потратить деньги на то, чтобы продемонстрировать нарушения неравенства Белла или другие явные доказательства того, что их кубиты работают вместе когерентно. Добро пожаловать, D-Wave!
- Второй вопрос касается того, что я уже много раз встречал в блогосфере: кто будет беспокоиться как работает система D-Wave'а, и используется ли там квантовая когерентность, если эта система решает практические задачи быстрее? Действительно, может быть, то, что строит D-Wave, есть, на самом деле, серия интересных, полезных, но всё же по существу «классических» приборов для отжига. Возможно, слово «квантовый» здесь работает как топор в каше из топора: привлечение денег, интереса и талантливых людей для построения чего-то такого, что хотя и изящно, но, в конечном итоге, слабо зависит от квантовой механики вообще. Если D-Wave'овский (буквально!) чёрный ящик решает проблемные задачи за такое-то и такое-то количество времени, какое нам дело до того, что там внутри?
Чтобы увидеть всю непосредственность этого вопроса, давайте рассмотрим простой мысленный эксперимент: допустим, D-Wave бы продавала классический, для специальных целей, стоимостью 10 миллионов долларов компьютер, сконструированный, чтобы осуществлять алгоритм имитации отжига для задач 90-битных изинговых спинов с некоторой фиксированной топологией, и при этом несколько лучший, чем уже существующие компьютерные кластеры. Получила ли бы D-Wave в таком случае хотя бы 5% от той публичной известности и того интереса, которые она испытывает к себе сейчас? Я думаю, что сама бы D-Wave была бы первой, кто ответил бы «нет». Действительно, Geordie Rose явно указывал во время своего доклада на захватывающую природу, стоящую за (как он сказал) «историей квантовых вычислений», и как она стала ключом к привлечению инвестиций. Причина беспокойства людей об этих вещах возникает не из-за того, что они хотят найти основные состояния спиновых систем в модели Изинга немного быстрее, но из-за того, что они хотят знать: достигла ли, в конечном счёте, человеческая раса новой формы вычислений или же нет. Так что то, как преподнести прибор, важно (мат вырезан цензурой — прим. пер.)! Я горжусь тем, что готов менять своё мнение практически обо всём при открытии новых фактов (как я это на самом деле сделал по поводу D-Wave), но моя уверенность в том, что чёрные ящики должны быть открыты, а объяснения предоставлены, есть нечто, что я отнесу в могилу.
- Наконец, ввиду скептического, но позитивного тона этого поста некоторые люди удивятся: сожалею ли я о моём раннем, более явном скептицизме по поводу D-Wave? Ответ — нет! Задавать вопросы — моя работа. Я поверю D-Wave'у сразу же, как только они ответят на мои вопросы (подобно тому, как это было в обсуждаемой поездке), когда бы это ни случилось, и изменю своё мнение соответственно, но я также не перестану ни спрашивать, ни извиняться за спрашивание до тех пор, пока доказательство квантового ускорения вычислений не станет ясным и бесспорным (чего ещё, конечно же, не прозошло). С другой стороны, я действительно сожалею о кидании гадостями, что возникло как итоговый результат моих и чужих скептических утверждений, утверждений D-Wave'а и людей, его поддерживающих, а также состязательной природы блогосферы. Первый раз я чувствую себя действительно искренне надеющимся всем моим сердцем, что компании D-Wave удастся доказать, что она может делать некоторый (не необходимо универсальный) вид масштабируемых квантовых вычислений. Такой успех доказал бы миру, что мои $100,000 в безопасности, и решительно бы опроверг скептиков квантовых вычислений, которые в своей критике сейчас порой заходят даже дальше, чем слепые сторонники D-Wave.
Источник: запись в блоге Скотта Ааронсона от 21го февраля 2012г.
Примечание переводичка: авторский способ выделения текста (наклонный шрифт, цвет и жирность) по возможности сохранён, собственные пояснения выделены серым цветом.
В итоге реализовалось в виде доклада в рамках DIQIP/QAlgo'14, слайды
Здесь есть слайды с других докладов, в т.ч. и по теме крипто. Из того, что запомнилось/удивило:
Хотят поднять инициативу на уровне европроектов, договориться с представителями отрасли и т.д. Слайды были, в общем-то, интересными, но на сайт не выложили. Будет время — скомпилирую из отснятого.
комментариев: 9796 документов: 488 редакций: 5664
Пока повеселили слайды Йожа. Ну точно, гранды все одинаковы. Раньше я такой стиль слайдов называл шамировским.
Сейчас вспоминаю, что свой первый доклад, в 2004-ом году, я делал с машиннонапечатанными прозрачками. Большинство других тогда делали вроде так же. И я не уверен, что опция подсоединить нормальный компьютерный проектор тогда конкретно у нас вообще была.
Ааронсон недавно разрыл тему и обнаружил, что всему виной
Там же:
За теми, кто использует 3D-моделирование, следят особо:
комментариев: 11558 документов: 1036 редакций: 4118
Не ходите, дети, в
АфрикуАмерику гулять.Весь тред тут.
Пишут, что уже:
arXiv опять блочит Tor-экситы. :-(
Экспериментальная демонстрация. Это что теперь, сдвиг парадигмы или в теории это уже было учтено? Вместо собственно квантовых вычислений появятся ещё и каузальные квантовые? Поидее, как мне кажется, в идею общего квантового вычисления эта схема так же влазит...
Эти экспериментаторы ссылаются на другую работу, теоретическую, PRL-2014:
В тексте:
Т.е. всё же это вроде сводится к стандартному формализму вычислений: из двух последовательностей гейтов, выбираемых вероятностно, можно сделать один, и всё описывать, как раньше. В заключении:
Похоже, картинка вырисовыается такая: раз оно не может дать более, чем полиномиальное ускорение, свдига парадигмы нет — классы теории сложности остаются в таких же отношениях друг с другом [см. слайды «complexity zoo»]. Однако, внутри конкретного класса сложности есть много моделей вычислений, между которыми возможны полиномиальные преимущества. Получается, что в рамках общего каркаса для какой-то проблемы нашли более оптимальный алгоритм в пределах того же класса сложности.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 9796 документов: 488 редакций: 5664
Вот именно. Пока считается, что против неё в симметрике только перебор, а квантовый перебор даёт преимущество лишь O(2n/2) вместо классического O(2n), где n — размер ключа, блока, внутреннего состояния и т.д.
А если получить представление о том, что внутри не чёрный ящик, а что-то конкретное, то теоретически можно как-то адаптировать и квантовый перебор (сортировку, поиск и пр.). И может оказаться, что шифр, для которого неизвестно классического варианта взлома, кроме как перебор грубой силой, оказывается нестойким к каким-то специфическим квантовым вычислениям.
Кстати, это вы из общих соображений заявляете, или где-то так было явно сказано? Берштейн так считает? Есть какие-то модельные симметричные шифры, ломаемые квантовым криптоанализом?