М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 52
Текст из файла (страница 52)
Точнее говоря, принцип Ландауэра можно сформулировать следующим образом. Принцип Ландауэра (первая форма). При стирании компьютером одного бита информации в окружающую среду неминуемо диссипирует энергия в количестве, не меньшем, чем йвТ!и 2, где йв — универсальная константа, известная как постояинал Бсльцл«она, а Т вЂ” температура окружающей среды. С помощью законов термодинамики принципу Ландауэра можно придать дру- гую форму с использованием энтропии, а не энергии. Принцип Ландауэра (вторая форма).
При стирании компьютером одного бита информации энтропия окружающей среды возрастает не менее, чем на йв 1п 2, где йв — постоянная Вольцмана. Обоснование принципа Ландауэра — это физическая задача, выходящая за рамки нашей книги (см. по этому поводу раздел «История и дополнительная литератураэ в конце главы). Если, однако, принять принцип Ландауэра как данность, то возникает целый ркц интересных вопросов.
Прежде всего принцип Ландауэра дает только нижнюю границу для количества энергии, диссипируемой при уничтожении информации. Насколько существующие компьютеры близки к этой границе? Оказывается не очень близки: компьютеры 2000 г. диссипируют энергию в размере примерно 500йвТ 1п 2 на каждую логическую операцию. Хотя существующие компьютеры и далеки от границы Ландауэра, проблема сокращения энергопотребления является принципиальной и интересной, причем наряду с теоретическим интересом есть и практический интерес: если производительность компьютеров будет возрастать согласно закону Мура, то будет возрастать и количество диссипируемой энергии, если только величина энергии, диссипируемой за одну операцию, не будет уменьшаться по меньшей мере с той же скоростью, с какой растет производительность компьютеров.
Если бы все вычисления производились обратимым образом, то из принципа Ландауэра не следовала бы диссипация энергии, поскольку никакая информация при таком вычислении не уничтожается. Конечно, не исключено, что потери энергии при вычислениях могут быть неизбежны ввиду какого-то другого физического принципа; к счастью, оказывается, что это не так. Но возможно ли проводить универсальные вычисления без потери информации? Физики могут схитрить, сказав, что ответ на этот вопрос должен быть положительным, поскольку согласно нашему современному пониманию физических законов они в основе своей обратимы. Зная конечное состояние замкнутой 3.2.
Анализ вычислительных задач 20б физической системы, на основе законов физики можно определить начальное состояние системы. Бели мы верим в эти законы, то должны заключить, что в необратимых логических элементах, таких как АХО или ОН, скрыты какие-то обратимые вычисления. Но где же она, зта скрытая обратимость, и можно ли ее использовать для построения явным образом обратимых компьютеров? Для реализации обратимых универсальных вычислений, мы будем использовать модели двух типов.
Первая модель — компьютер, построенный из биллиардных шаров и стенок, — обеспечивает красивую конкретную реализацию принципов обратимых вычислений. Вторая модель, основанная на обратимом логическом элементе, известном как элемент Тоффоли (с которым мы впервые встретились в подрэзд. 1.4.1), реализует более абстрактный подход к обратимым вычислениям, который будет нам в дальнейшем очень полезен при обсуждении квантовых вычислений. Возможно также построить обратимые машины Тьюринга, обладающие свойством универсальности; мы, однако, не будем ими заниматься, поскольку для квантовых вычислений схемные модели оказываются гораздо полезнее.
Основной принцип работы компьютера на биллиардных шарах проиллюстрирован на рис. 3.14. Биллиардные шары вводятся в компьютер слева, отскакивают от стенок и друг от друга и выходят из компьютера справа. Наличие или отсутствие шара в данном месте интерпретируется как логическэл единица или нуль соответственно. Эта модель замечательна тем, что она явным образом обратима, поскольку ее работа основана на законах классической механики.
Более того, эта модель оказывается униеерсалычой в том смысле, что с ее помощью можно имитировать любое вычисление в стандартной схемной модели. а' Рис. 3.14. Простой компьютер на биллиардных шарах с тремя входными и тремя выходными битами (входные биты слева, выходные — справа). Наличие или отсутствие шара интерпретируется как 1 или 0 соответственно. Пустые кружки обозначают потенциальные пути. В данном примере реализован классический обратимый элемент Фредкина, обсуждаемый в тексте. Разумеется, компъютер на биллиардных шарах, если его когда-нибудь построят, окажется весьма неустойчивым.
Как подтвердит любой игрок в биллиард, биллиардный шар, катящийся без трения по гладкой поверхности, легко 20б Глава 3. Введение в информатику отклоняется от пути даже при малых возмущениях. Для реализации вычислений на биллиардной модели необходимо ее безупречное функционирование и отсутствие внешних возмущений, вызываемых, например, тепловыми шумами.
В противном случае необходимо периодически вносить поправки, а информацию, полученную при этих поправках, надо будет уничтожать, что требует затрат энергии. Затраты энергии необходимы для того, чтобы уменьшить влияние шумов, без чего реальный компьютер работать не может. В нашем изложении мы проигнорируем влияние шумов на биллиардный компьютер и сконцевтрируем внимание на основные принципы обратимых вычислений. а' Ь' с' Рис.
3.1б. Таблица значений для элемента Фреднина и его условное обозначение. Биты а и Ь меняются местами, если управляющий бит с установлен в единицу, в противном случае они не меняются. С помощью биллиардного компьютера можно элегантно реализовать обратимый универсальный логический элемент, известный как элемент Фредкима, свойства которого хорошо отражают общие принципы обратимых логических элементов и схем. Элемент Фредкина имеет три входных бита а, Ь и с и три выходных бита а', Ь' и с'. Вит с — это 1рзрсвлдющий битл, значение которого под действием элемента Фредкина не меняется, т. е.
с' = с. Этот бит называется управляющим, поскольку от него зависит, что происходит с остальными двумя битами а и Ь. Если с равен О, то а и Ь не меняются, т. е. а' = а, Ь' = Ь. Если с равен 1, то значения битов а и 6 обмениваются: а' = 6, Ь' = а. Таблица значений для элемента Фредкина приведена на рис. 3.15. Легко видеть, что элемент Фредкина обратим, поскольку по выходным битам аг, 6' и с' можно определить входные биты а, 6 и с. Для этого достаточно подать а', 6' и с' на вход еще одного элемента Фредкина. Упражнение 3.29 (элемент Фредкина обратен самому себе). Покажите, что при последовательном использовании двух элементов Фредкина выход будет совпадать со входом. Изучая пути биллиардных шаров на рис. 3.14, нетрудно понять, что изображенный на этом рисунке биллиардный компьютер реализует элемент Фред- кина: Упражнение 3.30.
Проверьте, что изображенный на рис. 3.14 биллиардный компьютер реализует элемент Фредкина. 3.2. Анализ вычислительных задач 207 В дополнение к обратимости элемент Фредкина обладает еще одним интересным свойством: при его применении число единиц не меняв«под. В терминах биллиардного компьютера это соответствуег тому, что из элемента Фредкина выходит столько же шаров, сколько в него входит. Иногда эту мысль выражают такими словами: элемент Фредкина является консереатиивныль Эти свойства обратимости и консервативности представляют интерес для физиков, поскольку их можно мотивировать с помощью основных физических принципов.
Законы природы обратимы (за возможным исключением постулата измерения в квантовой механике, который обсуждался в подразд. 2.2.3). Консервативность логического элемента можно рассматривать как свойство, аналогичное сохранению массы или энергии (в биллиардной модели она в точности соответствуег сохранению массы) . ху х х у х у х 1 х х Рис. 3.1б. Конфигурации элемента Фредкина экаиаалентны элементам А!«О (слеаа) и пот(е центре), а также функции СНО55ОНЕН (спрааа), Конфигурация, укаэанная а центре, аыполняет также операцию РА!»ООТ, поскольку на аыход выдаются дае копии бита я Обратите внимание, что для каждой иэ этих операций требуются вспомогательные биты, приготоаленные е стандартных состояниях (например, О а первой строке элемента А!т'О) и что еыход, вообще говоря, содержит «муеор», не нужный для дальнейших вычислений.
Элемент Фредкина не только обратим и консервативен, он является еще и универсальным логическим элементом! Как показано на рис. 3.16, с помощью этого элемента можно реализовать функции АВР, )1ОТ, СВОЯЯОНЕВ и РАХО()Т, так что с помощью комбинации элементов Фредкина можно моделировать любую классическую схему! Чтобы реализовать с помощью элемента Фредкина необратимые элементы, например АМП, использовались две идеи. Во-первых, мы допускаем на входе вспомогательные биты, приготовленные в стандартных состояниях 0 и 1.
Во-вторых, на выходе допускаем «мусор», не нужный для дальнейших вычислений. Роль этих мусорных и вспомогательных битов только в том, что они делают вычисление обратимым. В качестве причины необратимости элементов, таких как АХО и ОВ., можно рассматривать то обстоятельство, что в них зти вспомогательные и мусорные биты «спрятаиы». Итак, по любой классической схеме, вычисляющей функцию 7"(х), можно построить обратимую схему, состоящую исключительно из элементов Фредкина, которая, получив на входе х и вспомогательные биты в стандартном состоянии а, вычисляет 7"(х) и «мусорный» результат д(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
