Слово малое об обратимых вычислениях

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

Дальнейшее изложение будет проводиться с использованием многочисленных примеров на языке программирования Haskell. Дело в том, что по моему сугубому мнению, функциональное программирование находится намного ближе к модели квантовых вычислений, чем любой иной тип. Обосновывать эту точку зрения я сейчас не буду. Но суть в ином — для постижения модели квантовых вычислений нужен намного более суровый сдвиг парадигмы, чем, к примеру, такой сдвиг от структурного программирования к объектно-ориентированному и тем более к функциональному. Здесь нет ни слова о том, что кто-то из программистов находится выше или ниже, но лишь о том, что освоение новой модели — это реальный переворот в мозгах и способе алгоритмического мышления ^[1].

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

Необходимые исторические сведения

Если обратить своё пристальное внимание на элементы булевой алгебры, то мы увидим, что все элементы на два входа и один выход в процессе своей работы теряют информацию. Например, булева функция И, таблица истинности которой следующая:

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

Рольф Ландауэр ^[2] впервые задумался об этом аспекте вычислений в 1961 году, и из его размышлений родился принцип, который связывает информационную энтропию с энтропией термодинамической. Действительно, потеря информации связана с выделением тепла физическими вычислительными устройствами.

А что если реализовать такие вычислительные элементы, при работе которых не теряется информация? С точки зрения чистой (теоретической) логики в этом нет ничего сложного. Проблема заключена в ином — нужны такие элементы, при помощи которых можно было бы реализовать любую иную булеву функцию. На как, например, базис из стандартных элементов НЕ и ИЛИ, или одноэлементный базис И-НЕ.

Обратимые элементы с этим свойством были найдены. В этой статье мы рассмотрим пару таких элементов — элемент Тоффоли и элемент Фредкина.

Элемент Тоффоли

Логический элемент Тоффоли представляет собой булеву функцию, получающую на вход три бита и возвращающую три бита (то есть это функция типа f: {0, 1}³ → {0, 1}³). Её таблица истинности выглядит следующим образом:

Другое название этой функции — CCNOT, то есть Controlled-Controlled-NOT. Это название учитывает тот факт, что логическая функция НЕ применяется к третьему биту I тогда и только тогда, когда первые два бита имеют значение 1. Данная прекрасная функция не просто является обратимой (если присмотреться, то будет видно, что между входными и выходными тройками значений есть взаимно однозначное отображение), но и она одна может использоваться для выражения любой иной булевой функции. Доказательство этого факта простое — если зафиксировать значение входного бита I в 1, то функция представит собой элемент И-НЕ, который является базисным.

Давайте попробуем посмотреть это в деле. Реализуем определение элемента Тоффоли на языке Haskell. Вместе с тремя дополнительными сервисными функциями определение функции toffoli будет выглядеть следующим образом:

getX :: (Int, Int, Int) -> Int
getX (x, _, _) = x

getY :: (Int, Int, Int) -> Int
getY (_, y, _) = y

getZ :: (Int, Int, Int) -> Int
getZ (_, _, z) = z

toffoli :: Int -> Int -> Int -> (Int, Int, Int)
toffoli 1 1 0 = (1, 1, 1)
toffoli 1 1 1 = (1, 1, 0)
toffoli x y z = (x, y, z)

Здесь есть очень сильные упрощения:

1. Во-первых, для представления значений битов использован тип Int, что не совсем корректно. Лучше было бы использовать, хотя бы, тип Bool, а ещё лучше определить свой собственный тип-перечисление для этих целей. Но это было бы слишком громоздко для демонстрации. Здесь мы просто посмотрим на реализацию, и всё.
2. Из предыдущего упрощения следует то, что разработчику следует самостоятельно следить за корректностью значений. В эти функции вполне можно подать значения 2 и другие, не равные 0 или 1, и функции успешно отработают с точки зрения компилятора. Но мы не будем подавать такие значения, поскольку они выходят за область нашего рассмотрения — сейчас из всех целых чисел нас интересуют только 0 и 1.
3. Функция toffoli возвращает тройку, и это самый простой способ вернуть три значения в языке Haskell. В принципе, для этих целей можно было бы определить специальный тип, но для упрощения пусть будет так. И именно этим фактом вызвано определение сервисных функций getX, getY и getZ.

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

Итак, вот определения функций:

not :: Int -> Int
not = getZ . toffoli 1 1

and :: Int -> Int -> Int
and a b = getZ $ toffoli a b 0

nand :: Int -> Int -> Int
nand a b = getZ $ toffoli a b 1

or :: Int -> Int -> Int
or a b = not $ and (not a) (not b)

nor :: Int -> Int -> Int
nor a b = not $ or a b

xor :: Int -> Int -> Int
xor a b = getZ $ toffoli 1 a b

fanout :: Int -> (Int, Int)
fanout a = (getY t, getZ t)
  where
    t = toffoli 1 a 0

Необходимость операции дублирования бита, выраженной через обратимый элемент Тоффоли, совершенно обоснованна, поскольку в обычной логике эта операция необратима. А в квантовых вычислениях так просто разветвлять «провода» кубитов нельзя, поскольку это запрещает делать теорема о невозможности копирования квантового состояния.

То, что в вышеприведённом коде некоторые функции выражены не прямо через функцию toffoli, не обозначает, что мы не можем их выразить. Да, через один элемент Тоффоли не получается, но приходится через несколько — и для сокращения записи нам помогают уже определённые функции.

Элемент Фредкина

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

Этот элемент ещё называется CSWAP, то есть Controlled-SWAP. Эта функция обменивает значения входных битов I₁и I₂ тогда и только тогда, когда значение контролирующего бита C равно 1. При помощи этого элемента тривиальным образом кодируются операции булевой логики НЕ и И, а потому он является базисным. Собственно, вот так кодируются при помощи него все те же самые функции, которые были выражены ранее через функцию toffoli:

not' :: Int -> Int
not' a = getZ $ fredkin a 0 1

and' :: Int -> Int -> Int
and' a b = getZ $ fredkin a b 0

nand' :: Int -> Int -> Int
nand' a b = not' $ and' a b

or' :: Int -> Int -> Int
or' a b = not' $ and' (not' a) (not' b)

nor' :: Int -> Int -> Int
nor' a b = not' $ or' a b

xor' :: Int -> Int -> Int
xor' a b = or' (and' b $ not' a) (and' a $ not' b)

fanout' :: Int -> (Int, Int)
fanout' a = (getX f, getZ f)
  where
    f = fredkin a 1 0

К этому коду относятся те же самые соображения, что и к предыдущему — выражение функций через уже определённые не влияет на то, что все они выражены через элемент Фредкина.

Также тут надо отметить, что сами функции toffoli и fredkin являются обратимыми, а вот остальные функции, которые через них выражены, — уже нет. Почему? Да потому, что сервисные функции getX, getY и getZ теряют информацию, и они специально сделаны такими.

Выражение одного через другое

Теперь займёмся упражнениями более высокого порядка. Выразим-ка элемент Тоффоли через элемент Фредкина и наоборот. Это будет хорошим упражнением.

Выразить элемент Тоффоли — в этом нет ничего сложного, поскольку два первых входа не изменяются, а для третьего есть простейшая пропозиционная формула: O = I ⊕ C₁C₂. Так что определение будет таким:

toffoli' :: Int -> Int -> Int -> (Int, Int, Int)
toffoli' x y z = (x, y, xor' z $ and' x y)

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

Эта диаграмма показывает, что для выражения одного элемента Тоффоли, у которого три входа и три выхода, при помощи элемента Фредкина, оных элементов необходимо: 5 для выражения операции FANOUT (дублирование значения бита; красные прямоугольники F), 5 для операции И (синие прямоугольники F) и 4 для операции НЕ (зелёные прямоугольники F) — всего 14 элементов, которые в общем представляют 26 входов и выходов, из которых только по 3 являются значимыми. То есть 23 бита являются «мусорными», которые нужны лишь для обеспечения обратимости вычислений.

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

А вот выражение элемента Фредкина через элемент Тоффоли будет посложнее, поскольку у него два выходных бита, которые имеют более сложные пропозиционные формулы. Но тоже не ахти как сложно:

fredkin' :: Int -> Int -> Int -> (Int, Int, Int)
fredkin' x y z = (x, xor y s, xor z s)
  where
    s = and x $ xor y z

Заинтересованный читатель сможет попробовать нарисовать такую же приятную для взора диаграмму и посчитать на ней количество элементов Тоффоли и «мусорных» битов.

Вот и вся наука.

Пятничный бонус

Поскольку у нас сегодня пятница, вот вам, мои уважаемые читатели, небольшой бонус. Поразмышляем насчёт многострадального кота Шрёдингера. Вот я всегда думал, почему Эрвин Шрёдингер не смог объяснить свой «парадокс». Он же сам написал книгу «Что такое жизнь с точки зрения физики» ^[3].

Весь вопрос в восприятии. Только живое существо может воспринимать (даже амёба). А восприятие — это акт измерения, которое разрушает суперпозицию. Так что поместив в ящик кота, Шрёдингер сам посадил в ящик «средство измерения». Фотон, находясь в суперпозиции квантовых состояний после преодоления полупрозрачного зеркала, входит в таком состоянии в ящик и детектор. Но тут же система восприятия кота разрушает суперпозицию. И дело не в сознании, а именно в восприятии.

Когда у нас есть фотон в суперпозиции, и он попадает в некое измерительное устройство (не живое, а просто измерительное устройство), то и само устройство, хоть и является макрообъектом, входит в суперпозицию состояний «фотон засечён» — «фотон не засечён». Впрочем, возможно, я ошибаюсь. Эксперименты по проверке этого парадокса запланированы Роджером Пенроузом (я не в курсе, удалось ему их провести или нет), но он не будет сажать котов в коробки, это уж точно.

Или что это? Проблема Наблюдателя?

Автор: Darkus

Источник ^[4]