id: Гость   вход   регистрация
текущее время 12:18 29/03/2024
Владелец: spinore (создано 11/04/2012 14:17), редакция от 11/04/2012 16:30 (автор: spinore) Печать
Категории: криптография, шифрование с открытым ключом, разное, офф-топик, личности, квантовая криптография
https://www.pgpru.com/Новости/2012/МояПоездкаВD-WaveПоТуСторонуМясногоСэндвича
создать
просмотр
редакции
ссылки

11.04 // Моя поездка в D-Wave: по ту сторону мясного сэндвича


Скотт Ааронсон (wiki), адъюнкт-профессор факультета электротехники и информатики
Массачусетского Технологического Института © 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г.
Примечание переводичка: авторский способ выделения текста (наклонный шрифт, цвет и жирность) по возможности сохранён, собственные пояснения выделены серым цветом.


 
На страницу: 1, 2, 3, 4, 5, 6 След.
Комментарии [скрыть комментарии/форму]
— unknown (19/01/2015 17:47, исправлен 19/01/2015 17:47)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Бернштейн самой квантовой матчастью не занимается. А вот авторы, упоминаемые в этой и этой новости что-то ещё публиковали по теме.



Так, чтобы явно — нет, не было. Возможно, что я даже неверно понял некоторые намёки из работ. Но про то, что этот ваш бозонный сэмплинг можно применить в квантовых вычислениях — тоже никто открыто не говорил. Вы так хорошо информируете о трендах, что поневоле уже возникают мысли о том, а как это можно применить ещё? Правда, не зная матчасти можно нафантазировать откровенную чушь, поэтому ждём точных ссылок, если оно вдруг появится действительно кем-то реализованное :)

— Гость (19/01/2015 19:27)   <#>

Наверно, так, потому что иначе бессмыслица получается: BS собственно и начался с того, что для некоторой задачи вдруг обнаружили, что она решается быстро через BS, а классического аналогичного быстрого алгоритма для неё неизвестно. Потом нашли другую задачу, уже вроде как полезную.


ОК, смысл понятен. Можно проаппелировать даже в лоб к тем новостным ссылкам, может быть.


Предыдущие ссылки попались на глаза сулчайно — их отобрал для внутренних семинаров человек, который занимается BS, и кинул в рассылку. Вообще, если регулярно читать архив, можно много интересного узнавать, но я к этому так и не приучился — обычно ограничиваюсь гуглением по случаю, когда интересует какая-то конкретная узкая тема.
— unknown (19/01/2015 20:50)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Это отнимает много времени, как и вообще любой анализ большого количества информации. У меня вот за январь почти ничего не прочитано по тем разделам публикаций в разных архивах, которые мне обычно были интересны.
— Гость (19/01/2015 21:11)   <#>

Да. В исследовательсих группах есть такая мода — находить недавние инетерсные публикации, а потом разбирать их на саминаре. Т.е. кто-то должен прочитать чужую работу, попытаться понять, а потом выйти к доске и рассказать остальным, в чём там смысл и как что.


Так бухать меньше ж надо! В Европах второе января — уже рабочий день, как правило.
— unknown (19/01/2015 21:29, исправлен 19/01/2015 21:33)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Например, тот же алгебраический, в частности кубический криптоанализ стопорится на том, что при высоких уровнях алгебраической сложности нет эффективных методов поиска решения. Я просто не знаю, что будет, если взять и применить методы квантовых вычислений к уже известным методам криптоанализа. Таких публикаций нет потому что это принципиально невозможно/неперспективно или просто ещё никто не брался за эту тему? Например те, кто понимает в квантовых вычислениях, не понимают в криптоанализе симметрики, нет специалистов для таких исследований?


Для асимметрики всё сводится к определённой задаче и для неё можно определить эффективность квантовых вычислений, а вот симметрику пока рассматривали только как чёрный ящик, против которого работает лишь перебор.



Быть в тренде — это всё больше и больше необходимость. При том, что должны быть и исследователи, не замороченные ежедневным разбором текучки, наверное рабочие группы по какому-то такому принципу и будут дальше организовывать, а не только в целях обучения.



Должно же быть хоть что-то хорошее не только в этих ваших Европах ;)

— Гость (20/01/2015 00:39)   <#>

Мне не хватает квалификации грамотно ответить на этот вопрос.


Мне думается, что, скорей всего, так. Даже классический криптоанализ крайне сложен, а если его сделать квантовым, то всё сложное усложнится ещё в несколько раз. Лично у меня в общении с местными специалистами (а у нас довольно хорошие специалисты, должен сказать) сложилось впечатление, что в вопросах криптографии я часто понимаю больше, чем они. Я даже более сильную вещь скажу: общался с человеком из группы, которая профессионально занимается хэшами и связанными с этим вещами. Выяснилось, что этот челоек не знает такого слова, как «экстрактор».


Обучение — это обычно постусторонняя обязанность, стоящая на десятом месте в приоритетах, она ни на что не влияет, ей стараются уделать внимание по-минимуму, основное — исследования и публикации. Многие вообще не препоадют ничего и никогда, у кого-то есть один-два курса в год. Меня просили провести семинары по ТИ, но нас было несколько человек, мы менялись. В итоге в год мне надо было подготовиться и отбыть 4 занятия. Да и на те занятия мы ходили вдвоём. :-) А вообще, в хороших местах возможность не преподавать оговаривается явно как приятный бонус. К сожалению, чисто исследовательских позиций сейчас в Европе уже почти нигде не дают, хотя раньше давали. Исследовательских институтов — тоже кот наплакал, почти вся наука университетская. C точки зрения бюрократов основная цель университетов — осчастливливать дипломами, а не исследованиями заниматься.
— Гость (20/01/2015 03:06)   <#>

Да ё[censored]!!! Вы что, стопарик своему квантовому оракулу на НГ тоже налили? Что-то он слишком неслучаен. Откуда у вас инсайд? Вам достаточно спороть любую чушь, а потом заходишь в рассылку — она уже там! Париж-телеком на марше:

Quantum attacks against iterated block ciphers

An interesting corollary is that the time-space tradeoff for quantum attacks is very different from what classical attacks allow. This first result seems to indicate that composition resists better to quantum attacks than to classical ones because it prevents the quadratic speedup achieved by quantizing an exhaustive search. We investigate security amplification by composition further by examining the case of four iterations. We quantize a recent technique called the dissection attack using the framework of quantum walks. Surprisingly, this leads to better gains over classical attacks than for double iterations, which seems to indicate that when the number of iterations grows, the resistance against quantum attacks decreases. // Abstract


The situation in symmetric cryptography is more complicated. It is well known quantum computers can speed-up certain information processing tasks that are useful for the cryptanalysis of symmetric cryptosystems. This includes exhaustive search [Gro96] or collision finding [Amb07]. In fact, quantum cryptanalysis is often cited as a motivation to sudy quantum algorithms [BHT98, AS04, Zha13]. Since these quantum algorithms usually allow only polynomial speedups, this tends to spread the belief that the security against quantum adversaries can be restored by increasing the size of private keys.

This short answer to the question of security against quantum attacks leaves aside a number of issues. For example, it applies to generic attacks and not to cryptographic attacks. Roughly speaking, generic attacks work against constructions based on ideal functionalities, whereas cryptographic attacks try to attack their implementations. Attacking realistic, complex cryptosystems may require more effort than just applying basic quantum algorithms. This situation is well described by Daniel Bernstein [Ber10] // Стр. 1

Был Meet-in-the-middle классическим [1], [2] — стал квантовым, так и живём:

We prove that the attack against 2-encryption that consists in searching for collision is the most time-efficient, leading to a generic attack deserving to be called the quantum Meet-in-the-middle attack

A surprising corollary is that classical and quantum time-space tradeoffs are very different. In the classical case, the Meet-in-the-middle attack is time-efficient for an attacker that is willing to pay with more space, but the global time-space tradeoff is similar to the one achieved by an exhaustive search. Using quantum algorithms, the time-space tradeoff of the optimal algorithm of Ambainis is worse than an exhaustive search. While this may not be a surprise from the point of view of quantum complexity theory (see e.g. the conclusion of [BDH+ 05]), this suggests that the time-space tradeoff, a widely used gauge of classical attacks [DDKS12], may not be the correct figure of merit to evaluate quantum attacks.

We give a quantization of the dissection attack for four encryption recently introduced by Dinur, Dunkelman, Keller and Shamir [DDKS12]. This attack is essentially a composition of an exhaustive search with the basic Meet-in-the-middle algorithm. Surprisingly, it is better than previously known classical attacks solely based on the Meet-in-the-middle technique. Quantum query complexity theory developed good tools to quantize such compositions, but in order to quantify also time and space complexity, we use the framework of quantum walks. Our main finding in this case is that the resistance against quantum attacks decreases when the number of iterations goes from two to four. // Стр. 3

В благодарностях в статье упомянуты те лица, что засветились на «SHA-3 day».

P.S.: Это всё как бы в первую очередь для каскадных шифров, но можно вспомнить, что

Любой шифр можно также рассматривать как каскад и атаковать по частям, с просеиванием ключа при встрече посредине, это давно уже мейнстрим для построения атак

и тогда атака заиграет новыми красками. ☺ Просеивание ключа посередине — это же и есть man-on-the-side meet-in-the-middle?

В довершение политоффтоп про вышеупомянутого Амбаиниса: почему в Риге CS есть, а на всём остальном постсоветском пространстве нету? Почему аспиранты Амбаиниса постдочат у Ааронсона в MIT, а аспиранты из Москвы агрессивно пилят фанеру в XXI-ом веке выставляют такой стыд и срам на конференциях, что подойти стыдно? Наверно, интеграция в ЕС как-то благотворно действует, других объяснений не вижу.
— unknown (20/01/2015 09:41, исправлен 20/01/2015 10:02)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Да, общаюсь с ним напрямую, прямо из параллельной квантовой вселенной без классического канала, всё закачивают прямо в сознание ;)



Time Memory Trade Off (TMTO) — это всё ещё, по большей части, оптимизированный перебор (по ссылке была новость и подробный разбор темы в коментах). Да, им можно ломать и не каскад, а один шифр, даже без уязвимостей. Вот мысль прикрутить кванты к алгебраическому криптоанализу, хоть и более сложная, но может дать более эффектный теоретический результат. Ждём новостей из будущего.

— Гость (20/01/2015 19:05)   <#>
Вы хотите сказать, что meet-in-the-middle — частный случай «time-memory trade off»-атаки?
— unknown (23/01/2015 12:04)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Space-Time Tradeoff — это очень общий принцип, без него многое что было бы невозможно, в т.ч. и MeetITM — где-то же надо хранить ключи посредине для сравнения.

Интервью с Дейтчем. Как я понимаю, сейчас актуальны специализированные КК — analog quantum simulators, примерно тоже, что и в новости про D-wave.
— Гость (23/01/2015 13:21)   <#>

Тренд такой есть, старался о нём упомянуть в § "КК, квантовые вычисления и «coin tossing»".


sentaus'а на вас нет! Дойчем! Неужели вы не знаете базовые правила чтения немецкого?
— unknown (23/01/2015 13:44)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

Позор на мою седую голову! Раньше же это разбирали.
— Гость (23/01/2015 14:36)   <#>
Кажется, в русском ещё есть выражение "дойч-марки". Дойч — дословно "немецкий", "дойчланд" — Германия. Есть голова седая, то вы должны были в школе учить немецкий, без вариантов. :-)
— unknown (23/01/2015 16:09)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Ich verstehe dich besser als du mich! :-)
— pgprubot (23/05/2015 03:15)   профиль/связь   <#>
комментариев: 511   документов: 2   редакций: 70
... Ученые получили собственно российский кубит.

Цитата. Непонятно только, российский кубит логический или физический.
На страницу: 1, 2, 3, 4, 5, 6 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3