11.04 // Моя поездка в D-Wave: по ту сторону мясного сэндвича
Массачусетского Технологического Института © 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г.
Примечание переводичка: авторский способ выделения текста (наклонный шрифт, цвет и жирность) по возможности сохранён, собственные пояснения выделены серым цветом.
комментариев: 9796 документов: 488 редакций: 5664
Бернштейн самой квантовой матчастью не занимается. А вот авторы, упоминаемые в этой и этой новости что-то ещё публиковали по теме.
Так, чтобы явно — нет, не было. Возможно, что я даже неверно понял некоторые намёки из работ. Но про то, что этот ваш бозонный сэмплинг можно применить в квантовых вычислениях — тоже никто открыто не говорил. Вы так хорошо информируете о трендах, что поневоле уже возникают мысли о том, а как это можно применить ещё? Правда, не зная матчасти можно нафантазировать откровенную чушь, поэтому ждём точных ссылок, если оно вдруг появится действительно кем-то реализованное :)
Наверно, так, потому что иначе бессмыслица получается: BS собственно и начался с того, что для некоторой задачи вдруг обнаружили, что она решается быстро через BS, а классического аналогичного быстрого алгоритма для неё неизвестно. Потом нашли другую задачу, уже вроде как полезную.
ОК, смысл понятен. Можно проаппелировать даже в лоб к тем новостным ссылкам, может быть.
Предыдущие ссылки попались на глаза сулчайно — их отобрал для внутренних семинаров человек, который занимается BS, и кинул в рассылку. Вообще, если регулярно читать архив, можно много интересного узнавать, но я к этому так и не приучился — обычно ограничиваюсь гуглением по случаю, когда интересует какая-то конкретная узкая тема.
комментариев: 9796 документов: 488 редакций: 5664
Это отнимает много времени, как и вообще любой анализ большого количества информации. У меня вот за январь почти ничего не прочитано по тем разделам публикаций в разных архивах, которые мне обычно были интересны.
Да. В исследовательсих группах есть такая мода — находить недавние инетерсные публикации, а потом разбирать их на саминаре. Т.е. кто-то должен прочитать чужую работу, попытаться понять, а потом выйти к доске и рассказать остальным, в чём там смысл и как что.
Так бухать меньше ж надо! В Европах второе января — уже рабочий день, как правило.комментариев: 9796 документов: 488 редакций: 5664
Например, тот же алгебраический, в частности кубический криптоанализ стопорится на том, что при высоких уровнях алгебраической сложности нет эффективных методов поиска решения. Я просто не знаю, что будет, если взять и применить методы квантовых вычислений к уже известным методам криптоанализа. Таких публикаций нет потому что это принципиально невозможно/неперспективно или просто ещё никто не брался за эту тему? Например те, кто понимает в квантовых вычислениях, не понимают в криптоанализе симметрики, нет специалистов для таких исследований?
Для асимметрики всё сводится к определённой задаче и для неё можно определить эффективность квантовых вычислений, а вот симметрику пока рассматривали только как чёрный ящик, против которого работает лишь перебор.
Быть в тренде — это всё больше и больше необходимость. При том, что должны быть и исследователи, не замороченные ежедневным разбором текучки, наверное рабочие группы по какому-то такому принципу и будут дальше организовывать, а не только в целях обучения.
Так бухать меньше ж надо! В Европах второе января — уже рабочий день, как правило.Должно же быть хоть что-то хорошее не только в этих ваших Европах ;)
Мне не хватает квалификации грамотно ответить на этот вопрос.
Мне думается, что, скорей всего, так. Даже классический криптоанализ крайне сложен, а если его сделать квантовым, то всё сложное усложнится ещё в несколько раз. Лично у меня в общении с местными специалистами (а у нас довольно хорошие специалисты, должен сказать) сложилось впечатление, что в вопросах криптографии я часто понимаю больше, чем они. Я даже более сильную вещь скажу: общался с человеком из группы, которая профессионально занимается хэшами и связанными с этим вещами. Выяснилось, что этот челоек не знает такого слова, как «экстрактор».
Обучение — это обычно постусторонняя обязанность, стоящая на десятом месте в приоритетах, она ни на что не влияет, ей стараются уделать внимание по-минимуму, основное — исследования и публикации. Многие вообще не препоадют ничего и никогда, у кого-то есть один-два курса в год. Меня просили провести семинары по ТИ, но нас было несколько человек, мы менялись. В итоге в год мне надо было подготовиться и отбыть 4 занятия. Да и на те занятия мы ходили вдвоём. :-) А вообще, в хороших местах возможность не преподавать оговаривается явно как приятный бонус. К сожалению, чисто исследовательских позиций сейчас в Европе уже почти нигде не дают, хотя раньше давали. Исследовательских институтов — тоже кот наплакал, почти вся наука университетская. C точки зрения бюрократов основная цель университетов — осчастливливать дипломами, а не исследованиями заниматься.
Да ё[censored]!!! Вы что, стопарик своему квантовому оракулу на НГ тоже налили? Что-то он слишком неслучаен. Откуда у вас инсайд? Вам достаточно спороть
любую чушь, а потом заходишь в рассылку — она уже там! Париж-телеком на марше:Был Meet-in-the-middle классическим [1], [2] — стал квантовым,
так и живём:В благодарностях в статье упомянуты те лица, что засветились на «SHA-3 day».
P.S.: Это всё как бы в первую очередь для каскадных шифров, но можно вспомнить, что
и тогда атака заиграет новыми красками. ☺ Просеивание ключа посередине — это же и есть
man-on-the-sidemeet-in-the-middle?В довершение политоффтоп про вышеупомянутого Амбаиниса: почему в Риге CS есть, а на всём остальном постсоветском пространстве нету? Почему аспиранты Амбаиниса постдочат у Ааронсона в MIT, а аспиранты из Москвы
агрессивно пилят фанеру в XXI-ом векевыставляют такой стыд и срам на конференциях, что подойти стыдно? Наверно, интеграция в ЕС как-то благотворно действует, других объяснений не вижу.комментариев: 9796 документов: 488 редакций: 5664
Да, общаюсь с ним напрямую, прямо из параллельной квантовой вселенной без классического канала, всё закачивают прямо в сознание ;)
man-on-the-sidemeet-in-the-middle?Time Memory Trade Off (TMTO) — это всё ещё, по большей части, оптимизированный перебор (по ссылке была новость и подробный разбор темы в коментах). Да, им можно ломать и не каскад, а один шифр, даже без уязвимостей. Вот мысль прикрутить кванты к алгебраическому криптоанализу, хоть и более сложная, но может дать более эффектный теоретический результат. Ждём новостей из будущего.
комментариев: 9796 документов: 488 редакций: 5664
Space-Time Tradeoff — это очень общий принцип, без него многое что было бы невозможно, в т.ч. и MeetITM — где-то же надо хранить ключи посредине для сравнения.
Интервью с Дейтчем. Как я понимаю, сейчас актуальны специализированные КК — analog quantum simulators, примерно тоже, что и в новости про D-wave.
Тренд такой есть, старался о нём упомянуть в § "КК, квантовые вычисления и «coin tossing»".
sentaus'а на вас нет!Дойчем! Неужели вы не знаете базовые правила чтения немецкого?комментариев: 9796 документов: 488 редакций: 5664
Позор на мою седую голову! Раньше же это разбирали.
комментариев: 9796 документов: 488 редакций: 5664
комментариев: 511 документов: 2 редакций: 70
Цитата. Непонятно только, российский кубит логический или физический.