ПОИСК Статьи Рисунки Таблицы Соотношение между классическим и квантовым вычислением из "Классические и квантовые вычисления" Классический объект, соответствующий унитарному оператору, — перестановка. Любой перестановке G Е — В естественно сопоставляется унитарный оператор G в пространстве Б , действующий по правилу G x) Gx). [c.56] Аналогично определению 5.1, можно определить обратимые классические схемы, реализующие перестановки. [c.56] Определение 6Л. Обратимая классическая схема. Пусть Л — некоторое множество перестановок вида G В/ — В (базис). Обратимая классическая схе.ма в базисе А — это последовательность перестановок Ui[Ai, . . ., Ui[Ai, где Aj —. множест,ва битов, Uj G Л. [c.56] Перестановка, реализуема.я обратимой схемой. Это произведение перестановок Ui[Ai] . .. 7i[Ai]. [c.56] В каких случаях функцию, заданную булевой схемой, можно реализовать обратимой схемой Обратимые схемы реализуют только перестановки. Преодолеть эту трудность можно так. Вместо вычисления функции В — В будем вычислять функцию Рц, ВГ + — В + , заданную соотношением Рф(х,у) = (x,yfb F(x)) (здесь 0 означает побитовое сложение по модулю 2). Тогда значение F(x) можно получить так Fg)(x,0) = (х,Р(х)]. [c.56] А вот перестановок на трёх битах уже достаточно, чтобы реализовать любую функцию. Прн этом ие обязательно использовать все перестановки, достаточно включить в базис лишь две функции — отрицание -I н элемент Тоффоли / р (ж, у, z) i— (ж, у, z fb ху). При этом имеется в виду реализуемость в расширенном смысле, т. е. можно брать напрокат биты в состоянии О и возвращать их после окончания вычислений в том же состоянии. [c.57] Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли. [c.57] Лемма 6.1. Пусть функция i К — П реализуется булевой схемой размера. L в некотором базисе Л. Тогда. можно реа.лизоеать функцию (х,0) I— (F(x),G(x)) обратимой схе.мой раз.мера 0(Ь) в базисе Aeg, состоящем из функций /ф (f G Л), а также функции ф (x,ij) (х,х(Ьу). [c.57] Замечание 6.1. Помимо полезного ответа F(x) схема, указанная в формулировке леммы, производит мусор G x). [c.57] Замечание 6.2. Содержательный смысл операции (Щ) — обратимое коиирование бита (еслп начальное значение у равно 0). В литературе эта операция обычно называется ontrolled NOT но причинам, которые станут ясными пз дальнейшего. [c.57] Поскольку начальные значения дополнительных неременных были равны О, их конечные значения будут такими же, как и в булевой схеме. [c.57] Осталось поменять местами биты, чтобы получить указанный в условии формат ответа. [c.58] Лемма 6.2 (очистка мусора). В условиях леммы 1 можно произвести вычисление функции Fp обратимой схемой размера 0(L + п + т) (с использованием с]ополнитсльных битов). [c.58] Доказательство. Для очистки мусора будет использована обратимость. Изобразим процесс вычисления Fp схемой, аналогичной той, что приведена в доказательстве леммы 6.1. [c.58] С другой стороны, если ёмкость дисков будет расти столь же быстро, как в настоящее время, то к концу ХХП1 века для форматирования жёсткого диска потребуется энергия, соответствующая годовому излучению Солнца. [c.59] Лемма об очистке мусора показывает, что можно избежать таких потерь энергии, связанных с необратимостью вычислений. [c.59] Можно также показать, что любое вычисление, требующее памяти L, можно реализовать обратимым образом с использованием памяти, ие превышающей Приведём набросок доказательства. [c.59] Чтобы вычислить Va- F x,z), вычислим F Q,z), занесём результат в одну донолинтельную ячейку, затем вычислим F i,z) и занесём результат в другую ячейку. После вычислим Мх F x,z) = F Q, z) / F(i, z) и результат занесём в третью ячейку. Чтобы убрать мусор, прокрутим все вычисления, кроме последнего шага, в обратном направлении. [c.59] Разобравшись аналогичным образом с формулой Зх F x,z), приходим к такому выводу добавление квантора ио булевой переменной увеличивает требуемую память ие более чем иа константу битов. [c.59] В заключение сформулируем теорему о вычислении обратимых функций, которая является прямым обобщением леммы 6.2. [c.59] Вернуться к основной статье