id: Гость   вход   регистрация
текущее время 11:04 19/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 След.
Комментарии [скрыть комментарии/форму]
— Гость (04/01/2014 05:12)   <#>
Интернет — свидетель.
У сотрудников посольств есть тригер на слово "квантовый"
Вопросы — что будете изучать, откуда узнали об универе, покрывает ли универ расходы на обучение. На первый ответил — физику. И тут пауза такая секунд пять. Он молчит, я молчу. Дай, думаю, еще что-нибудь скажу. Добавил, что там много физик вообще разных, например, квантовая механика. Он такой сразу: «О, а ты разбираешься в квантовой механике?» Ну а мне-то что? Не будет же он проверять. Да, говорю, интересуюсь. Он удовлетворенно кивнул и снова печатает.

И напрямую интересуются.
Вы занимались квантовыми компьютерами?
Я не знаю, чем был вызван этот вопрос со стоорны сотрудников посольства и как они там собираются использовать соответствующую информацию. Оба моих собеседника ответили офицеру на этот вопрос отрицательно и да, получили визы.
— Гость (04/01/2014 15:57)   <#>
По первой ссылке дальше:

Как потом нам пояснил профессор, не стоит говорить консулам об экспериментах и прочем. Тогда и список публикаций не спросят и т.д. Зачем едете? — Учиться, делать расчеты, моделирование.

Короче, она не в тему. У сотрудников посольства цель — выловить нелегальных мигрантов, а также выезжающих по подставным документам или рисковую категорию, которая, возможно, пойдёт в стране в криминал, т.к. не сможет обеспечить себе существование. Ради этой цели они могут задавать произвольные вопросы. Кто по семейным обстоятельствам выезжал — так могли попросить семейные фотографии показать, задать внезапные вопросы о ком-то из сфотографированных и т.д. Цель не в самих этих вопросах, а в том, чтобы соймать отвечающего на лжи, если он на самом деле врёт. И публикации, как дальше в цитате написано, просят ради того же: чтобы убедиться, что пытающийся въехать в страну никого не обманывает. Чем больше критериев для проверки на вшивость, тем больше могут попросить, чтоб «наверняка».

Вторая ссылка более по теме, но подробностей там нет, у кого они спрашивали: студентов, случайных людей, въезжающих в США, или учёных. Судя по блогу автора, он, по всей видимости, к физике отношения не имел, но такой вопрос получил, звучит занимательно. Правда, в ответ на его твит было:

При собеседовании сотрудникам одной телеком-конторы в посольстве США часто задавали вопрос: пишут ли они антивирусы

Т.е. если эффект действительно существует, то, по всей видимости, касается не только КК. Зачем им может понадобиться такая информация — тоже непонятно. То ли как бонус, увеличивающий шансы на выдачу визы, то ли наоборот, как сдерживающий фактор (чтоб не узнали, там работая, больше, чем положено).

Кстати, сам вопрос статьи «вы занимались квантовыми компьютерами?» звучит довольно абсурдно. С одной стороны, если его понимать расплывчато, то к разработке КК имеет косвенное отношение так много людей, что они сами об этом не подозревают. Туда можно записать специлистов по оптике, сверхпроводникам или ещё какой ФТТ, которые никогда не позицинировали применение своих результатов для КК, равно как и тех, кто занимался КТИ как чистой математикой. С другой стороны, если понимать узко и буквально, есть только горстка экспериментаторов, явно позицинирующая свою работу как разработку экспериментальных квантовых вычислений, а также горстка теоретиков, занимающихся квантовыми алгоритмами и вычислениями как математикой (и тех и других в мире мало), причём даже среди них далеко не все занимаются криптографически полезными квантовыми вычислениями/компьютерами. К примеру, D-Wave ими не знимается.
— Гость (04/01/2014 16:52)   <#>
В штатах тоже было забавно с визой: в начале заявили с присвистом, типа вах вах, да ты же аж целых пол года был в штатах 10 лет назад! И вот опять хочешь??? Да у тебя еще и штатовские права есть!? вах вах! Потом, вах вах да ты еще и в криптографии разбираешься!

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

Хотелось бы понимать какие могут быть ещё препятствия, чтобы не "раскатывать губу" раньше времени.
вы были связаны с гос. сектором, криптографией и прочей атрибутикой? если да, то снова проверка;

Первое звучит как плюс, а последующие упоминания — как минус.
— Гость (07/01/2014 00:56)   <#>

Мнение более осведомлённых людей, ознакомившихся с документами: АНБ ничуть не ближе к КК, чем открытая наука. Буквально недавно 3 кубита были у NEC, но третий играл роль управляющего, поэтому произвольный трёкубитовый gate сделан не был. Но это ещё было несколько лет назад, а сейчас, возможно, три полноценных кубита (для универсальных квантовых вычислений) уже есть, потому что NEC упорно работал в этом направлении, и никаких концептуальных препятствий этому не было видно.
— Гость (10/01/2014 19:40)   <#>
Интервью с Ааронсоном в Washington Post на тему АНБ/QC:

We know a lot more in the last year about what's going on with these devices. After they sold to Lockheed, an independent group led by Matthias Troyer actually did independent investigations of this machine. What they found briefly is that there is pretty good circumstantial evidence that there's some kind of quantum annealing behavior, which means that there's a little bit of quantumness there.

Not even D-Wave is claiming that what they have or what they't trying to do is a full-scale quantum computer. They're not even trying to get universal quantum computer. A universal one is one that can do any quantum computation, like Shor's factoring algorithm. D-Wave is aiming to build something much more limited. [D-Wave uses an approach called] adiabatic optimization.

There's no evdience that [D-Wave's device is a] practical computer. Even if you could build this adiabatic optimization approach totally perfectly, you still wouldn't know if there's a practically important speedup using quantum computers. It's very different than the situation with Shor's factoring algorithm. If you could do it, we're extremely confident we could get this speedup. With the optimization problem, we don't really know if we'd get a speedup. It's going to boil down to people trying it out and seeing what happens.

Там же про QKD:

Another response that you could take, ironically, is to switch to quantum cryptography. It's a completely different way of doing encryption. It uses fiber-optic cables that can transmit photons that maintain polarization. Cryptography based on quantum mechanics, the uncertainty principle. This is actually practical right now. There are companies that sell quantum crypto devices: ID Quantique and Magiq. People are selling these devices. They do work, but there is a limited market for them. It's an exotic solution to a problem that most people think is solved with existing cryptography. Some people joke that the point of quantum computers is to create a market for quantum cryptography.

Про скейлинг (рост числа кубитов):

To build a reliable, scalable quantum computer, you don't have to get it perfectly isolated. Only have to get it very well isolated. If you can get the amount of interaction below a certain threshold, then you can start applying these very clever error-correcting codes. Assuming you're below this threshold, it's like you've passed a critical point for a nuclear weapon, you start correcting errors faster than they're introduced. There's this critical point where once you pass it you should be able to scale it up in principle to be as big as you want.

Until you're at that point, nothing you do is going to [look all that] impressive. You don't get half a nuclear explosion if you're below that critical mass. Experimentalist are focusing on getting a real understanding of how the qubits behave with the idea being that once you have good enough qubits then you can scale it up. Until you do that trying to scale up with dirty qubits, it's like juggling on a unicycle. It's on impressive parlor trick good for generating headlines, but we know from the beginning that it's going to crap out before too long.

So most people know the real goal is not to get more and more qubits, but to get better and better qubits, because that's what's ultimately going to be needed.

Наконец, собственно про АНБ (аргументы в пользу того, почему у них нет большего прогресса, чем у других):

How likely do you think it is that the NSA has succeeded in creating practical quantum computers?

People have speculated about that possibility and joked about it for a long time. I don't know. I don't have the security clearance. But there are some things that make me think it's not likely. One of them is that we know who the best experimentalists are, and yes the NSA is interested and talks to them and funds them, but we haven't seen them hoovering them up like the Manhattan project.

The more important thing is that if your goal is to read people's e-mail, there are so many more straightforward ways to go about that than building a quantum computer. It's an exotic possibility that captures people's imagination, but in reality, when these systems are broken, it's not by bashing down the fortress, it's by finding a back door. Finding a bug in the implementation or rigging the standards and strong-arming Microsoft and Google into just giving you backdoors. If the NSA were able to break all of this strong crypto, why would they be going to all this effort to do these things?

Snowden himself said properly implemented strong crypto is one of the things you can rely on. There are so many more prosaic possibilities I'd want to examine before considering the possibility that the NSA is building a quantum computer.

There's also just that it looks to most of us like [quantum computing is] in a basic research stage. It doesn't look like it's at the point where people could say here's how much money it would take and here's how many years it would take and we can build a device. We still don't know. We're still just trying to figure out which are the basic architectures. Maybe in 5 or 10 or 20 years it becomes a question of time and money and manpower and how much do people want this thing. Right now, it's a research question of how do you do it at all.



По приведённой ссылке на блог Ааронсона:

Here’s an analogy: imagine that a biotech startup claimed that, by using an expensive and controversial new gene therapy, it could cure patients at a higher rate than with the best available conventional drugs—basing its claim on a single clinical trial. Imagine that this claim was widely repeated in the press as an established fact. Now imagine that closer examination of the clinical trial revealed that it showed nothing of the kind: it compared against the wrong drugs. And imagine that a more relevant clinical trial—mostly unmentioned in the press—had also been done, and discovered that when you compare to the right drugs, the drugs do better. Imagine that someone wrote a blog post bringing all of this to public attention.

And now imagine that the response to that blogger was the following: “aha, but isn’t it possible that some future clinical trial will show an advantage for the gene therapy—maybe with some other group of patients? Even if not, isn’t it possible that the startup will manage to develop an effective gene therapy sometime in the future? Betcha didn’t consider that, did you? And anyway, at least they’re out there trying to make gene therapy work! So we should all support them, rather than relentlessly criticizing. And as for the startup’s misleading claims to the public? Oh, don’t be so naïve: that’s just PR. If you can’t tune out the PR and concentrate on the science, that’s your own damn problem. In summary, the real issue isn’t what some clinical trial did or didn’t show; it’s you and your hostile attitude.”

In a different context, these sorts of responses would be considered strange, and the need to resort to them revealing. But the rules for D-Wave are different.

Alex Selby has a detailed new post summarizing his comparisons between the D-Wave device (as reported by McGeoch and Wang) and his own solver—finding that his solver can handily outperform the device and speculating about the reasons why.

In other news, Catherine McGeoch spoke on Friday in the MIT quantum group meeting. Incredibly, she spoke for more than an hour, without once mentioning the USC results that found that simulated annealing on a standard laptop (when competently implemented) handily outperformed the D-Wave machine, or making any attempt to reconcile those results with hers and Wang’s. Instead, McGeogh used the time to enlighten the assembled experts about what quantum annealing was, what an exact solver was, etc. etc., then repeated the speedup claims as if the more informative comparisons simply didn’t exist. I left without asking questions, not wanting to be the one to instigate an unpleasant confrontation, and—I’ll admit—questioning my own sanity as a result of no one else asking about the gigantic elephant in the room.

Не буду всё копипастить, но по приведённой Ааронсоном ссылке на блог Alex Selby есть разбор полётов:

I was curious to see whether these claims could be true, and whether the current D-Wave machine could possibly be useful as a computational device right now. (The short answer, I believe, is “no”, if you don’t want to read any further.)

И в секции «Conclusion»:

I imagine it will need to reach at least the promised 2048 qubits (and would really need to be doing some sort of quantum annealing) before it becomes something computationally useful, though even at that point the advantage over software is not totally clear. Of course, all this would not detract from the fascinating and wonderful achievement of D-Wave if the device really is doing something non-trivially non-classical. That is surely the interesting question and it would indicate whether something along these lines could eventually be made computationally useful (and much more). But I believe that’s a research question (a very interesting one), rather than a practical one right now.

Текст большой, очень технический, и сделать из него короткую выжимку сути за разумное время трудно.

Далее у Ааарносона по той же ссылке:

the same USC paper that reported the quantum annealing behavior of the D-Wave One, also showed no speed advantage whatsoever for quantum annealing over classical simulated annealing. In more detail, Matthias Troyer’s group spent a few months carefully studying the D-Wave problem—after which, they were able to write optimized simulated annealing code that solves the D-Wave problem on a normal, off-the-shelf classical computer, about 15 times faster than the D-Wave machine itself solves the D-Wave problem! Of course, if you wanted even more classical speedup than that, then you could simply add more processors to your classical computer, for only a tiny fraction of the $10 million that a D-Wave One would set you back.

И на аргумент «не мешайте нам получать деньги на полезные вещи хотя бы таким образом, через hype» (топор в каше из топора):

Suppose that, unlike in the “stone soup” scenario I outlined above, it eventually becomes clear that quantum annealing can be made to work on thousands of qubits, but that it’s a dead end as far as getting a quantum speedup is concerned. Suppose the evidence piles up that simulated annealing on a conventional computer will continue to beat quantum annealing, if even the slightest effort is put into optimizing the classical annealing code. If that happens, then I predict that the very same people now hyping D-Wave will turn around and—without the slightest acknowledgment of error on their part—declare that the entire field of quantum computing has now been unmasked as a mirage, a scam, and a chimera. The same pointy-haired bosses who now flock toward quantum computing, will flock away from it just as quickly and as uncomprehendingly. Academic QC programs will be decimated, despite the slow but genuine progress that they’d been making the entire time in a “parallel universe” from D-Wave. People’s contempt for academia is such that, while a D-Wave success would be trumpeted as its alone, a D-Wave failure would be blamed on the entire QC community.

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

P.S. Пост длинный, там много интересного, читайте по ссылкам, если интересно.
— unknown (10/01/2014 20:25)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
There are companies that sell quantum crypto devices: ID Quantique and Magiq. People are selling these devices. They do work, but there is a limited market for them. It's an exotic solution to a problem that most people think is solved with existing cryptography. Some people joke that the point of quantum computers is to create a market for quantum cryptography.

С самого начала до всяких Сноуденов было подозрение, что рынок этот будет не вполне безобидным: если уже встроенным в интеловые процы ГСЧ никто не доверяет. Крупные централизованные компании и корпорации легко поддаются государственному контролю.

Спасибо за отслеживание актуальных материалов и компетентных мнений по теме.
— Гость (10/01/2014 20:46)   <#>
BosonSampling is a proposal by me and Alex Arkhipov for a rudimentary kind of quantum computer: one that would be based entirely on generating single photons, sending them through a network of beamsplitters and phaseshifters, and then measuring where they ended up. BosonSampling devices are not thought to be capable of universal quantum computing, or even universal classical computing for that matter. And while they might be a stepping-stone toward universal optical quantum computers, they themselves have a grand total of zero known practical applications. However, even if the task performed by BosonSamplers is useless, the task is of some scientific interest, by virtue of apparently being hard! In particular, Alex and I showed that, if a BosonSampler can be simulated exactly in polynomial time by a classical computer, then P#P = BPPNP, and hence the polynomial hierarchy collapses to the third level. Even if a BosonSampler can only be approximately simulated in classical polynomial time, the polynomial hierarchy would still collapse, if a reasonable-looking conjecture in classical complexity theory is true. For these reasons, BosonSampling might provide an experimental path to testing the Extended Church-Turing Thesis—i.e., the thesis that all natural processes can be simulated with polynomial overhead by a classical computer—that’s more “direct” than building a universal quantum computer. (As an asymptotic claim, obviously the ECT can never be decisively proved or refuted by a finite number of experiments. However, if one could build a BosonSampler with, let’s say, 30 photons, then while it would still be feasible to verify the results with a classical computer, it would be fair to say that the BosonSampler was working “faster” than any known algorithm running on existing digital computers.)

Boson Sampling — «hot topic» сейчас, тоже предложенный Ааронсоном. У нас от Рауля скоро доклад ожидается по теме (тем более, что Ааронсон его идеи заценил):

A commenter named RaulGPS has offered yet another great observation that, while forehead-slappingly obvious in retrospect, somehow hadn’t occurred to us. Namely, Raul points out that the argument given in this post, for the hardness of Scattershot BosonSampling, can also be applied to answer open question #4 from my and Alex’s paper...

One other announcement: following a suggestion by commenter Rahul, I hereby invite guest posts on Shtetl-Optimized by experimentalists working on BosonSampling, offering your personal views about the prospects and difficulties of scaling up.

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

У гауссовых состояний и квантовой оптики пока не было почти никаких реальных применений кроме CV QKD и всякой редкой экзотики типа иллюзионизма. Более того, интерес к гауссовым состояниям частично подугас, когда показали, что с помощью них далеко не всё можно сделать из квантовых операций/протоколов* (тем более, произвольные вычисления). А тут вот так раз... и пришла идея, откуда не ждали.


Вам спасибо за интерес.

*Например, с помощью только них нельзя сделать исправление ошибок.
— Гость (10/01/2014 21:32)   <#>

С точки зрения науки всё это мелочи. Когда-нибудь, через много лет, когда QKD станет такой же обыденностью, как разъём RJ45 на столе, проблема будет решаться тем же способом: есть много поставщиков; есть те, кто следит за темой и ищет закладки; есть разные крупные игроки на рынке, и их интересы противоположны. Что-то простое, может быть, смогут собирать даже любители из деталей, которые более-менее неподконтрольны для встраивания закладок противником. Intel — это конкрентоспособные хорошие процессоры, но никто не запрещает покупать малопопулярные слабые китайские для более критичных к безопасности объектов или даже компоновать технику так, чтобы бэкдор только от одного из производителей не был критичным, т.е. чтоб для взлома требовался согласованный бэкдор от китайцев и Intel'а, например (стоит, к примеру, два файерволла: один на Intel'е, а другой китайский). Я к тому клоню, что в будущем разницы большой не будет: современный проц или QKD или ещё что-то. Это оно только сейчас кажется диковинкой.

И ещё один оффтоп, но связанный с этим, о котором не так давно думал: вот есть такая известная Boston Dynamics, которая делает человекоподобных и животноподобных роботов. Их ролики все видели, в представлении это не нуждается. Когда поначалу шли разговоры о кибернетике и робототехнике, специалисты говорили, что это дорого, непрактично, неудобно, не окупится и вообще даже не взлетит. А те всё равно работали. Потом появились компьютеры, которые вывели робототехнику на тот уровень, который без них был принципиально немыслим. Вполне естественно, что этот прогресс не коснулся стран бышего СССР уже ни в каком виде. Тем не менее, и на этой стадии ещё был скептицизм. Даже сейчас, когда они показывают некоторые свои прототипы, которые бегают, что-то переносят, что-то перекидывают, имитируют, люди скажут, что дорого и непрактично, аппелируя к расходу топлива, стоимости, уязвимости перед противником и т.д. Однако, бегающие быстрее людей механические животные уже слегка наводят ужас. С одной стороны — ещё есть доля скептицизма, что это когда-нибудь станет массовым, практичным и востребованным, с другой стороны — уже есть боязнь, что «кто-то делает и вон как уже умеет, а мы ещё даже не начинали». Т.е. сначала было рано, а потом вдруг оказывается поздно, середины нету.

Когда преимущества какой-нибудь сумасшедшей технологии доходят до такой степени, что рядовому потребителю становится понятна их перспективность, оказывается уже поздно, потому что у тех, кто на них поставил вовремя, уже 30 лет опыта и куча своих технологических секретов, а у скептиков ноль (вспомните тот же курс bitcoin'а хотя бы). И если скептики вступят в гонку, им, чтобы догнать, надо бежать быстрее первопроходцев, потому что последние тоже не стоят; они будут продолжать бежать вперёд и тогда, когда вы встурпите в гонку. Получится как с процессорами: могут повторить только то, что первые звёзды рынка делали ещё лет 10 назад, т.е. не могут сделать конкурентоспособную вещь.

В коммерческом секторе это сказывается больнее, т.к. завязано на коммерческую тайну и неразглашаемые технологии, но тот же эффект виден и в открытой науке: хотя вся информация публично доступна через arXiv, книги и журналы, кто-то где-то над этим работал уже лет 20, и потому имеет в голове связную картину того происходящего в области. И таких людей много, за ними стоит научная школа, традиции, терминология, общий консенсус какой-то... А макаки, которые впервые читают эти книжки, способы разве что их перевести на русский или пересказать своими словами, ничего реально нового и интересного к уже представленным знаниям они добавить не в состоянии. И когда они начинают вникать, изучать, идти вперёд, их коллеги, имеющие опыт, тоже на месте не стоят, из-за чего получается ровно то же самое: когда одни знакомятся с понятием кубита и простейших операций, другие уже думают в теории квантовой сложности протоколов, уйдя на несколько толстых книг вперёд в понимании; когда одни строят криптографию на принципе медведя, другие уже давно перевели её на рельсы теории сложности, смысл которой первым даже примерно не понятен, они продолжают его считать «чисто буржуйской фишкой»; когда одни кричат в академиях «что может измениться в курсе матанализа за последние сто лет?», отказываясь учиться и пествуя одну и ту же Священную Программу™, написанную сто лет назад, другие уже нашли применение гомологиям и строгают на них квантовые методы коррекции ошибок, кооперируясь с физиками.
— Гость (17/01/2014 20:58)   <#>
The optimal scenario is one of a provable quantum speedup, where there exists a proof that no classical algorithm can outperform a given quantum algorithm. Perhaps the best known example is Grover's search algorithm, which exhibits a provable quadratic speedup over the best possible classical algorithm, assuming an oracle. // Стр. 2

Была «доказуемая безопасность», а теперь ещё будет и «доказуемое квантовое ускорение».

We did not find evidence of limited quantum speedup for the DW2 relative to simulated annealing in our particular benchmark set when we considered the ratio of quantiles of time to solution, which is the relevant quantity for the performance of a device as an optimizer. // Стр. 10

DW2 = D-Wave 2.

There are several candidate explanations for the absence of a clear quantum speedup in our tests. Perhaps quantum annealing simply does not provide any advantages over simulated (quantum) annealing or other classical algorithms for the problem class we have studied; or, perhaps, the noisy implementation in the DW2 cannot realize quantum speedup and is thus not better than classical devices. Alternatively, a speedup might be masked by calibration errors, improvements might arise from error correction, or other problem classes might exhibit a speedup. Future studies will probe these alternatives and aim to determine whether one can find a class of problem instances for which an unambiguous speedup over classical hardware can be observed. // Стр. 10

Из недавно вышедшей работы на тему того, как сравнивать классический SA с квантовым применительно к D-Wave (вплоть до 503-ёх кубитов). Работа от внешних исследователей, не имеющих непосредственного отношения к D-Wave.
— unknown (17/01/2014 21:11)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664
Вы там присмотритесь ещё получше к бозонному сэмплингу на гауссовых состояниях. А то он вроде тоже даже толком не кубит, но вдруг на его основе внезапно чего-то такое необычное можно создать, протокол передачи бита каким-нибудь не таким способом :)
— Гость (17/01/2014 22:41)   <#>
По D-Wave'у обещают Google+-семинар на следующей неделе (по как раз этой статье), но, во-первых, там, как всегда, плохо слышно, и трудно разобрать, что говорят; во-вторых, далеко от границ моей компетентности (поэтому понятно ещё меньше); в-третьих, работа написана неплохо, и то основное, что можно из неё извлечь для себя, уже извлёк, просто полистав pdf'ку; в-четвёртых, время по другим делам поджимает конкретно, поэтому, наверно, не пойду.

По BS должен был быть семинар на этой неделе, но его перенесли на неопределённое время позже. Ориентировочно ожидается короткий доклад на планёрке следующей неделе. Помимо этого, скоро должны быть какие-то постеры на QIP-2014:1

Anthony Leverrier and Raul Garcia-Patron. Does Boson Sampling need Fault-Tolerance? [постер, arXiv]

Christian Gogolin, Martin Kliesch, Leandro Aolita and Jens Eisert. Boson-Sampling in the light of sample complexity: a review [постер, arXiv]

а также quantum rump session с хохотушками и пивом. Реннер — председатель программного комитета, а у Винтера, Лукина,2 Прескилла3 и Troyer'а пленарные доклады.


1Ежегодная TOP-1-конференция по всему QCS (quantum computer science). Из примерно 420 участников, представляющих практически все «научно развитые» страны мира, нет ни одного из стран бывшего СССР. Впрочем, в классической CS всё точно так же. Это настоящий успех. Исключение — Латвия из-за там обосновавшейся группы Амбаиниса.
2Тот самый, который стал широко известен после его эксперимента с «остановкой света».
3Один из отцов-основателей КТИ.
— Гость (15/03/2014 00:35)   <#>
Помимо BS открывается ещё одна перспектива для QCS в CV:

Our approach leads to an operational way to define, and adapt, to arbitrary continuous quantum systems, quantum protocols and algorithms developed for discrete systems. Using the presented results, we show how to realize the Grover search algorithm using continuous variables Perola Milman

Интересно, до факторизации на «фотонном компьютере» прогресс дойдёт? ☺
— Гость (15/03/2014 02:01)   <#>
Слава знаменитых КК-институций Империи Зла FVEY не даёт покоя европейцам. Местное зло решило не отставать и забабахало свой КК-центр с блэкджеком и шлкуртизанками. И правда, сколько можно kill-switch'и продавать, да с анонимными сетями бороться? Пора переходить к делу, брать быка за рога.
— Гость (23/03/2014 06:55)   <#>

Conduct basic research in quantum physics and architecture/engineering studies to determine if, and how, a cryptologically useful quantum computer can be built. // Стр. 1

Demonstrate dynamical decoupling and complete quantum control on two filesemiconductor qubits. A qubit is the basic "building block" of a quantum computer. This will enable initial scaling towards large systems in related and follow-on efforts. // Стр. 2

Continue research of quantum communications technology to support the development of novel Quantum Key Distribution (QKD) attacks and assess the security of new QKD system designs. // Стр. 3

Про «полупроводниковые» кубиты** есть мнение, что это всем известные квантовые точки, но если исходить из вышеприведённой pdf-ссылки, то это зонтик, под которым объединены следующие 4 подхода к созданию КК:

  1. Kane quantum computer.
  2. Loss-DiVincenzo quantum computer.
  3. Quantum dot charge based semiconductor quantum computer. Про этот тип есть статья на quantiki и ещё одна.
  4. Diamond-based quantum computer.

Более полный список физических моделей КК (не только на «полупроводниковых кубитах») есть здесь, их там уже 16.

В общем и целом всё уже сказано в [1], [2]. Нечего к этому добавить. Кстати, там тоже речь шла в основном о полупроводниковых кубитах.


footnote: it is also a starting point of Boson sampling and computational complexity analysis for LOQC [Linear Optical Quantum Computing]

Но LOQC — вроде как оптический, а не полупроводниковый КК.

P.S. Про D-Wave недавно сказали, что последние исследования всё более убедительно показывают, кто некоторый вид запутанности (а, следовательно, и квантовости в эффектах) у них действительно наблюдается, только вот сомнений в том, что именно этот тип запутанности будет хоть сколь-нибудь полезен для вычислений, ровно столько же, как и раньше.

**Не путать со «сверхпроводящими» на джосефсоновских переходах — то, что делает, например, D-Wave.
— Гость (21/06/2014 11:21)   <#>

Статью приняли в журнал «Science». По этому поводу жёлтые новости выпустили анонсы.
На страницу: 1, 2, 3, 4, 5, 6 След.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3