Обратимые вычисления

[kaipa]

Разбирая завал на столе, нашел распечатку статьи Conservative Logic. Совершенно не помню, когда ее распечатал "на потом". Начал читать, стало интересно. Основная мысль -- создание схемотехники, "работающей" не по традиционной логической схеме (в дискретной математике это называется СФЭ -- схема функциональных элементов), а по совсем другой, основное свойство которой сохранение (отсюда conservative) энергии, которая в традиционных системах совершенно расточительно рассеивается. Необходимым образом в таких схемах вытекает обратимость вычислительных и логических процессов. Статья старая, 1982г. Погуглил, нашелся вольный перевод этой статьи год назад на Хабре, веб-сайт критиков консервативной партии США и... почти все. Меня это очень озадачило, так как тема казалась важной. Я предположил, что само название "Консервативная логика" скорее всего не прижилось, и оказался прав. В современном мире это направление называется обратимыми вычислениями, а соответствующая схемотехника -- адибатической логикой.

На самом деле тут проблема очень глубокая и принципиальная, уходящая в самые основы современного понимания устройства мира. Из связи термодинамической и информационной энтропии следует, что любые манипуляции с информацией приводят к рассеиванию энергии. Есть даже теоретическая оценка минимума энергии, которая равна E ≥ kT ln2 на один бит. Это было известно все довольно давно, уже лет 50, но только сейчас, когда вычислительные мощности впечатляюще выросли, начинает по-настоящему припекать. Так, 100-петафлопсные суперкомьютеры (кажется, такие уже есть), излучают только "теоретического" тепла порядка 1 мегаватт, а практически гораздо больше. А это уже сегодняшний день. Завтра суперкомьютеры могут быть в 10-100-1000 раз мощнее, и соответственно вырастет количество теряемой энергии. Обратимые вычисления тут решают теоретически сразу две вещи. Во-первых, энергия не рассеивается, а используется. Как именно это может быть достигнуто, можно прочитать в вышеупомянутой статье. А во-вторых, появляется возможность "делать" схемы еще более "мелкими". Сейчас мешает термодинамический шум.

В настоящее время исследования в этой области проводятся в MIT и University of Florida. Уже есть прототипы чипов на адиабатической логике, а список текущих проектов показывает, что разрабатывается все, от физики, до системы программирования и теории сложности.

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

Comments

[vincentfischer.livejournal.com]

> Обратимость перпендикулярна квантовым вычислениям.
в смысле? у вас система (после приготовления и до измерения - ну то есть на всё время работы) описывается гамильтонианом, как вы будете без обратимости жить? на каждом гейте требуется обратимость. так что связь совершенно прямая, собственно, Беннет и прочие думали как раз о квантовых вычислениях, когда боролись за это.

(если бы вы расшарили личные сообщения, мы бы могли познакомиться, если вы не против, кстати)

[ushastyi.livejournal.com]

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

[vincentfischer.livejournal.com]

а вот вам книжка в ответ :)

http://www.booksgid.com/other/22900-kvantovyjj-kompjuter-i-kvantovye.html

если не скачается тут, у меня есть своя пиратская в электронном виде

[ushastyi.livejournal.com]

Судя по именам, действительно, сборник классических статей. Спасибо.

[ushastyi.livejournal.com]

Честно говоря, я не очень понимаю суть квантовых вычислений (пытался въехать пару раз, но ничего в голове не осталось). Если там и есть обратимость -- то как бесплатный побочный эффект. Обратимость в том смысле, в котором она получается в консервативной или адиабатический логике -- это свойство модели вычислений, которым, очевидно, могут обладать разные модели, квантовые и нет.

[vincentfischer.livejournal.com]

давайте я отвечу, как сам понимаю, а детали и изложение построже вы сможете прочитать в синей книжке

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

я держу в голове эту простую схему работы (типа "электромеханическая аналогия"), когда речь заходит о кв, и пока ни разу не видел противоречий, если есть возражения, можно обсудить.

[ushastyi.livejournal.com]

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

Квантовую аналогию я понял. Но Вы делаете как минимум два неявных предположения, которые надо как-то обосновать:
1) коробка -- замкнутая система. Что в случае квантовых преобразований обеспечить непросто
2) квантовые преобразования обратимы во времени. Что, насколько я понимаю, совсем не так. В силу вероятностной природы всех преобразований.

[vincentfischer.livejournal.com]

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

> коробка -- замкнутая система. Что в случае квантовых преобразований обеспечить непросто
это как раз одна из технических трудностей и направление борьбы :) но в конце-концов в идеальном случае кк будет изолирован от окружающего мира на время работы. ещё время работы должно быть достаточно большим, ну и так далее. там полно технических проблем пока.

> квантовые преобразования обратимы во времени. Что, насколько я понимаю, совсем не так.
так-так, пока вы не сделали измерение .