Классический объект, соответствующий унитарному оператору, — перестановка. Любой перестановке $$G\colon\cb^k \to \cb^k$$ естественно сопоставляется унитарный оператор $$\ha{G}$$ в пространстве $$\BB^{\otimes k}$$, действующий по правилу $$\ha{G}\ket{x}\bydef\ket{Gx}$$.
Аналогично определению 5.1, можно определить обратимые классические схемы, реализующие перестановки.
Определение 6.1. Обратимая классическая схема. Пусть $$\calA$$ — некоторое множество перестановок вида $$G\colon\cb^k\to\cb^k$$ (базис). Обратимая классическая схема в базисе $$\calA$$ — это последовательность перестановок $$U_1[A_1],\dots, U_l[A_l]$$, где $$A_j$$ — множества битов, $$U_j\in\calA$$.
Перестановка, реализуемая обратимой схемой. Это произведение перестановок $$U_l[A_l]\cdot\ldots\cdot U_1[A_1]$$.
Перестановка $$U$$, реализуемая схемой в расширенном смысле. Это такая перестановка, что произведение перестановок$$W=U_l[A_l]\cdot\ldots\cdot U_1[A_1]$$ (действующее на $$N$$ битов, $$N\geq n$$ ) для любого $$x\in\cb^n$$ удовлетворяет условию $$W(x,0^{N-n})=\left(Ux,0^{N-n}\right)$$.
В каких случаях функцию, заданную булевой схемой, можно реализовать обратимой схемой? Обратимые схемы реализуют только перестановки. Преодолеть эту трудность можно так. Вместо вычисления функции $$F\colon{} \cb^n\to\cb^m$$ будем вычислять функцию $$F_\oplus\colon{} \cb^{n+m}\to\cb^{n+m}$$, заданную соотношением $$F_\oplus(x,y)\double=(x,y\oplus F(x))$$ (здесь $$\oplus$$ означает побитовое сложение по модулю 2). Тогда значение $$F(x)$$ можно получить так: $$F_\oplus(x,0)=(x,F(x))$$.
Чтобы можно было вычислять функции, заданные булевыми схемами в полном базисе, недостаточно взять базис для обратимых схем из перестановок на двух битах. Оказывается, что любая перестановка на двух битах $$g\colon{} \cb^2\to \cb^2$$ является линейной функцией (при естественном отождествлении множества $$\cb$$ и поля из двух элементов $$\FF_2$$ ): $$g(x,y) =(ax\oplus by\oplus c, dx\oplus ey\oplus f)$$, где $$a$$, $$b$$, $$c$$, $$d$$, $$e$$, $$f\in\FF_2$$. Поэтому все функции, вычисляемые обратимыми схемами в базисе из перестановок на двух битах, являются линейными.
А вот перестановок на трех битах уже достаточно, чтобы реализовать любую функцию. При этом не обязательно использовать все перестановки, достаточно включить в базис лишь две функции — отрицание $$\neg$$ и элемент Тоффоли $$\wedge_\oplus\colon (x,y,z)\mapsto(x,y,z\oplus xy)$$. При этом имеется в виду реализуемость в расширенном смысле, т.е. можно брать напрокат биты в состоянии 0 и возвращать их после окончания вычислений в том же состоянии.
Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли.
Лемма 6.1. Пусть функция $$F\colon\cb^n\to\cb^m$$ реализуется булевой схемой размера $$L$$ в некотором базисе $$\calA$$. Тогда можно реализовать функцию $$(x,0)\mapsto (F(x),G(x))$$ обратимой схемой размера $$O(L)$$ в базисе { $$\calA_\oplus$$, состоящем из функций $$f_\oplus$$ ( $$f\in\calA$$ ), а также функции $$\qxor\colon(x,y)\mapsto(x,x\oplus y)$$.
Замечание 6.1. Помимо "полезного" ответа $$F(x)$$ схема, указанная в формулировке леммы, производит "мусор" $$G(x)$$.
Замечание 6.2. Содержательный смысл операции $$\qxor$$ — обратимое копирование бита (если начальное значение $$y$$ равно $$0$$ ). В литературе эта операция обычно называется Controlled NOT по причинам, которые станут ясными из дальнейшего.
Замечание 6.3. Применяя функцию $$(\leftrightarrow)\colon(a,b)\mapsto(b,a)$$ можно менять биты местами в записи. Обратите внимание, что для перестановок битов достаточно также иметь в базисе $$\qxor$$, так как$$(\leftrightarrow)[j,k]\double=\null\qxor[j,k]\qxor[k,j]\qxor[j,k].$$
Доказательство. Возьмем схему, вычисляющую $$F$$. Пусть входные переменные — это $$x_1,\dots,x_n$$. Вспомогательные переменные схемы и биты результата — это $$x_{n+1},\dots, x_{n+L}$$ ; в обратимой схеме сопоставим им дополнительные биты, имеющие в начальном состоянии значение 0.
Каждое присваивание в схеме имеет вид $$x_{n+k}:=f_k(x_{j_k},\dots,x_{l_k})$$, $$f_k\in\calA$$, $$j_k,\dots,l_k<n+k$$. В обратимой схеме аналогом присваивания будет действие перестановки $$(x_{j_k},\dots,x_{l_k},x_{n+k}):=(f_k)_\oplus(x_{j_k},\dots,x_{l_k}$$, $$x_{n+k})$$, т.е. $$x_{n+k}:=x_{n+k}\oplus f_k(x_{j_k},\dots,x_{l_k})$$.
Поскольку начальные значения дополнительных переменных были равны 0, их конечные значения будут такими же, как и в булевой схеме.
Осталось поменять местами биты, чтобы получить указанный в условии формат ответа.
Весь процесс вычисления удобно представить следующей схемой (над прямоугольниками подписано количество битов, внутри — их содержимое):
Лемма 6.2. (очистка мусора). В условиях леммы $$1$$ можно произвести вычисление функции $$F_\oplus$$ обратимой схемой размера $$O(L+n+m)$$ (с использованием дополнительных битов).
Доказательство. Для очистки мусора будет использована обратимость. Изобразим процесс вычисления $$F_\oplus$$ схемой, аналогичной той, что приведена в доказательстве леммы 6.1.
Замечание 6.4. Обратимыми вычислениями заинтересовались при попытке ответить на вопрос, какая энергия необходима для вычислений (классических). Анализ показал, что потери энергии можно устремить к нулю для всех вычислительных операций, кроме необратимых. Когда производится необратимая операция (например, стирание бита), два различных логических значения ( $$0$$ и $$1$$ ) становятся одинаковыми ( $$0$$ ). Однако физические законы на микроуровне являются обратимыми, поэтому отличие между старыми состояниями ( $$0$$ и $$1$$ ) должно сохраниться в каких-то неконтролируемых физических степенях свободы. Это можно интерпретировать как возрастание беспорядка (энтропии), которое в конечном счете проявится в окружающей среде в виде тепла. Величина энергии, требуемой для стирания одного бита, очень мала ( $$\approx kT$$ ), но конечна. Потеря энергии из-за необратимого стирания информации при форматировании жесткого диска емкостью 1 Гб равна $$3\cdot 10^{-11}$$ Дж, что примерно соответствует затратам энергии на сдвиг головки диска на половину диаметра атома водорода. Это на много порядков меньше реального перемещения головки при форматировании.
С другой стороны, если емкость дисков будет расти столь же быстро, как в настоящее время, то к концу XXIII века для форматирования жесткого диска потребуется энергия, соответствующая годовому излучению Солнца.
Лемма об очистке мусора показывает, что можно избежать таких потерь энергии, связанных с необратимостью вычислений.
Можно также показать, что любое вычисление, требующее памяти $$L$$, можно реализовать обратимым образом с использованием памяти, не превышающей $$L^{O(1)}$$. Приведем набросок доказательства.
Поскольку задача TQBF PSPACE-полна, то достаточно вычислять на небольшой памяти значение формулы$$\exists\, x_1\:\forall\, y_1\:\dots\:\exists\, x_M\:\forall\, y_M\: f(x_1,y_1,\dots,x_M,y_M,z)$$ при условии, что $$f(\cdot)$$ вычислима булевой схемой небольшого размера $$L$$. Покажем, что в этом случае значение формулы 6.1 можно вычислить на памяти $$O(L+M)$$. Вычисление будет организовано рекурсивно, начиная с внутренних кванторов.
Чтобы вычислить $$\forall\, x\: F(x,z)$$, вычислим $$F(0,z)$$, занесем результат в одну дополнительную ячейку, затем вычислим $$F(1,z)$$ и занесем результат в другую ячейку. После вычислим $$\forall\, x\: F(x,z)\double=F(0,z)\wedge F(1,z)$$ и результат занесем в третью ячейку. Чтобы убрать мусор, прокрутим все вычисления, кроме последнего шага, в обратном направлении.
Разобравшись аналогичным образом с формулой $$\exists\, x\: F(x,z)$$, приходим к такому выводу: добавление квантора по булевой переменной увеличивает требуемую память не более чем на константу битов.
В заключение сформулируем теорему о вычислении обратимых функций, которая является прямым обобщением леммы 6.2.
Теорема 6.1. Пусть $$F$$ и $$F^{-1}$$ вычислимы булевыми схемами размеров $$\leq L$$. Тогда $$F$$ реализуется обратимой схемой размера $$O(L+n)$$.
Доказательство. Дается следующей схемой вычислений (для простоты не указаны биты, которые "берутся напрокат" при вычислении из леммы 6.2.
Классический объект, соответствующий унитарному оператору, — перестановка. Любой перестановке $$G\colon\cb^k \to \cb^k$$ естественно сопоставляется унитарный оператор $$\ha{G}$$ в пространстве $$\BB^{\otimes k}$$, действующий по правилу $$\ha{G}\ket{x}\bydef\ket{Gx}$$.
Аналогично определению 5.1, можно определить обратимые классические схемы, реализующие перестановки.
Определение 6.1. Обратимая классическая схема. Пусть $$\calA$$ — некоторое множество перестановок вида $$G\colon\cb^k\to\cb^k$$ (базис). Обратимая классическая схема в базисе $$\calA$$ — это последовательность перестановок $$U_1[A_1],\dots, U_l[A_l]$$, где $$A_j$$ — множества битов, $$U_j\in\calA$$.
Перестановка, реализуемая обратимой схемой. Это произведение перестановок $$U_l[A_l]\cdot\ldots\cdot U_1[A_1]$$.
Перестановка $$U$$, реализуемая схемой в расширенном смысле. Это такая перестановка, что произведение перестановок$$W=U_l[A_l]\cdot\ldots\cdot U_1[A_1]$$ (действующее на $$N$$ битов, $$N\geq n$$ ) для любого $$x\in\cb^n$$ удовлетворяет условию $$W(x,0^{N-n})=\left(Ux,0^{N-n}\right)$$.
В каких случаях функцию, заданную булевой схемой, можно реализовать обратимой схемой? Обратимые схемы реализуют только перестановки. Преодолеть эту трудность можно так. Вместо вычисления функции $$F\colon{} \cb^n\to\cb^m$$ будем вычислять функцию $$F_\oplus\colon{} \cb^{n+m}\to\cb^{n+m}$$, заданную соотношением $$F_\oplus(x,y)\double=(x,y\oplus F(x))$$ (здесь $$\oplus$$ означает побитовое сложение по модулю 2). Тогда значение $$F(x)$$ можно получить так: $$F_\oplus(x,0)=(x,F(x))$$.
Чтобы можно было вычислять функции, заданные булевыми схемами в полном базисе, недостаточно взять базис для обратимых схем из перестановок на двух битах. Оказывается, что любая перестановка на двух битах $$g\colon{} \cb^2\to \cb^2$$ является линейной функцией (при естественном отождествлении множества $$\cb$$ и поля из двух элементов $$\FF_2$$ ): $$g(x,y) =(ax\oplus by\oplus c, dx\oplus ey\oplus f)$$, где $$a$$, $$b$$, $$c$$, $$d$$, $$e$$, $$f\in\FF_2$$. Поэтому все функции, вычисляемые обратимыми схемами в базисе из перестановок на двух битах, являются линейными.
А вот перестановок на трех битах уже достаточно, чтобы реализовать любую функцию. При этом не обязательно использовать все перестановки, достаточно включить в базис лишь две функции — отрицание $$\neg$$ и элемент Тоффоли $$\wedge_\oplus\colon (x,y,z)\mapsto(x,y,z\oplus xy)$$. При этом имеется в виду реализуемость в расширенном смысле, т.е. можно брать напрокат биты в состоянии 0 и возвращать их после окончания вычислений в том же состоянии.
Задача 6.1. Докажите для обратимых схем полноту базиса, состоящего из отрицания и элемента Тоффоли.
Лемма 6.1. Пусть функция $$F\colon\cb^n\to\cb^m$$ реализуется булевой схемой размера $$L$$ в некотором базисе $$\calA$$. Тогда можно реализовать функцию $$(x,0)\mapsto (F(x),G(x))$$ обратимой схемой размера $$O(L)$$ в базисе { $$\calA_\oplus$$, состоящем из функций $$f_\oplus$$ ( $$f\in\calA$$ ), а также функции $$\qxor\colon(x,y)\mapsto(x,x\oplus y)$$.
Замечание 6.1. Помимо "полезного" ответа $$F(x)$$ схема, указанная в формулировке леммы, производит "мусор" $$G(x)$$.
Замечание 6.2. Содержательный смысл операции $$\qxor$$ — обратимое копирование бита (если начальное значение $$y$$ равно $$0$$ ). В литературе эта операция обычно называется Controlled NOT по причинам, которые станут ясными из дальнейшего.
Замечание 6.3. Применяя функцию $$(\leftrightarrow)\colon(a,b)\mapsto(b,a)$$ можно менять биты местами в записи. Обратите внимание, что для перестановок битов достаточно также иметь в базисе $$\qxor$$, так как$$(\leftrightarrow)[j,k]\double=\null\qxor[j,k]\qxor[k,j]\qxor[j,k].$$
Доказательство. Возьмем схему, вычисляющую $$F$$. Пусть входные переменные — это $$x_1,\dots,x_n$$. Вспомогательные переменные схемы и биты результата — это $$x_{n+1},\dots, x_{n+L}$$ ; в обратимой схеме сопоставим им дополнительные биты, имеющие в начальном состоянии значение 0.
Каждое присваивание в схеме имеет вид $$x_{n+k}:=f_k(x_{j_k},\dots,x_{l_k})$$, $$f_k\in\calA$$, $$j_k,\dots,l_k<n+k$$. В обратимой схеме аналогом присваивания будет действие перестановки $$(x_{j_k},\dots,x_{l_k},x_{n+k}):=(f_k)_\oplus(x_{j_k},\dots,x_{l_k}$$, $$x_{n+k})$$, т.е. $$x_{n+k}:=x_{n+k}\oplus f_k(x_{j_k},\dots,x_{l_k})$$.
Поскольку начальные значения дополнительных переменных были равны 0, их конечные значения будут такими же, как и в булевой схеме.
Осталось поменять местами биты, чтобы получить указанный в условии формат ответа.
Весь процесс вычисления удобно представить следующей схемой (над прямоугольниками подписано количество битов, внутри — их содержимое):
Лемма 6.2. (очистка мусора). В условиях леммы $$1$$ можно произвести вычисление функции $$F_\oplus$$ обратимой схемой размера $$O(L+n+m)$$ (с использованием дополнительных битов).
Доказательство. Для очистки мусора будет использована обратимость. Изобразим процесс вычисления $$F_\oplus$$ схемой, аналогичной той, что приведена в доказательстве леммы 6.1.
Замечание 6.4. Обратимыми вычислениями заинтересовались при попытке ответить на вопрос, какая энергия необходима для вычислений (классических). Анализ показал, что потери энергии можно устремить к нулю для всех вычислительных операций, кроме необратимых. Когда производится необратимая операция (например, стирание бита), два различных логических значения ( $$0$$ и $$1$$ ) становятся одинаковыми ( $$0$$ ). Однако физические законы на микроуровне являются обратимыми, поэтому отличие между старыми состояниями ( $$0$$ и $$1$$ ) должно сохраниться в каких-то неконтролируемых физических степенях свободы. Это можно интерпретировать как возрастание беспорядка (энтропии), которое в конечном счете проявится в окружающей среде в виде тепла. Величина энергии, требуемой для стирания одного бита, очень мала ( $$\approx kT$$ ), но конечна. Потеря энергии из-за необратимого стирания информации при форматировании жесткого диска емкостью 1 Гб равна $$3\cdot 10^{-11}$$ Дж, что примерно соответствует затратам энергии на сдвиг головки диска на половину диаметра атома водорода. Это на много порядков меньше реального перемещения головки при форматировании.
С другой стороны, если емкость дисков будет расти столь же быстро, как в настоящее время, то к концу XXIII века для форматирования жесткого диска потребуется энергия, соответствующая годовому излучению Солнца.
Лемма об очистке мусора показывает, что можно избежать таких потерь энергии, связанных с необратимостью вычислений.
Можно также показать, что любое вычисление, требующее памяти $$L$$, можно реализовать обратимым образом с использованием памяти, не превышающей $$L^{O(1)}$$. Приведем набросок доказательства.
Поскольку задача TQBF PSPACE-полна, то достаточно вычислять на небольшой памяти значение формулы$$\exists\, x_1\:\forall\, y_1\:\dots\:\exists\, x_M\:\forall\, y_M\: f(x_1,y_1,\dots,x_M,y_M,z)$$ при условии, что $$f(\cdot)$$ вычислима булевой схемой небольшого размера $$L$$. Покажем, что в этом случае значение формулы 6.1 можно вычислить на памяти $$O(L+M)$$. Вычисление будет организовано рекурсивно, начиная с внутренних кванторов.
Чтобы вычислить $$\forall\, x\: F(x,z)$$, вычислим $$F(0,z)$$, занесем результат в одну дополнительную ячейку, затем вычислим $$F(1,z)$$ и занесем результат в другую ячейку. После вычислим $$\forall\, x\: F(x,z)\double=F(0,z)\wedge F(1,z)$$ и результат занесем в третью ячейку. Чтобы убрать мусор, прокрутим все вычисления, кроме последнего шага, в обратном направлении.
Разобравшись аналогичным образом с формулой $$\exists\, x\: F(x,z)$$, приходим к такому выводу: добавление квантора по булевой переменной увеличивает требуемую память не более чем на константу битов.
В заключение сформулируем теорему о вычислении обратимых функций, которая является прямым обобщением леммы 6.2.
Теорема 6.1. Пусть $$F$$ и $$F^{-1}$$ вычислимы булевыми схемами размеров $$\leq L$$. Тогда $$F$$ реализуется обратимой схемой размера $$O(L+n)$$.
Доказательство. Дается следующей схемой вычислений (для простоты не указаны биты, которые "берутся напрокат" при вычислении из леммы 6.2.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.