Фредкинские ворота

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

Фон

Ворота Фредкина, ^[1] концептуализированный Эдвардом Фредкиным и Томмазо Тоффоли в Лаборатории компьютерных наук Массачусетского технологического института, представляет собой важнейшее достижение в области обратимых вычислений и консервативной логики. Разработанные в рамках консервативной логики, эти ворота предназначены для согласования вычислительных процессов с фундаментальными физическими принципами, такими как обратимость динамических законов и сохранение энергии. Техническое обоснование вентилей Фредкина основано на устранении неэффективности традиционных вычислений, где необратимые операции обычно приводят к значительному рассеиванию энергии.

В отличие от обычных логических вентилей, которые часто стирают информацию и таким образом рассеивают тепло согласно принципу Ландауэра, ^[2] Ворота Фредкина сохраняют обратимость — свойство, которое гарантирует, что информация не будет потеряна в процессе вычислений. Каждое выходное состояние вентиля однозначно определяет его входное состояние, что не только сохраняет информацию, но и соответствует принципам сохранения энергии. Эта характеристика особенно важна, поскольку спрос на вычислительную мощность растет, поэтому энергоэффективность становится ключевым фактором.

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

Определение

Основные ворота Фредкина ^[3] представляет собой управляемый вентиль подкачки (вентиль CSWAP), который отображает три входа $(C, I 1, I 2)$ на три выхода $(C, O 1, O 2)$ . Вход C напрямую отображается на C. выход Если C = 0, замена не выполняется; $I 1$ отображается в $O 1$ , а $I 2$ отображается в $O 2$ . В противном случае два выхода меняются местами, так что $I 1$ отображается на $O 2$ , а $I 2$ отображается на $O 1$ . Легко видеть, что эта схема обратима, т. е. «отменяет» себя при движении в обратном направлении. Обобщенный вентиль Фредкина размера n × n передает свои первые n − 2 входов без изменений на соответствующие выходы и меняет местами свои последние два выхода тогда и только тогда, когда все первые n − 2 входов равны 1.

Логика контролируемой замены: вентиль Фредкина, трехбитный вентиль управляемой замены, работает путем условной замены двух целевых битов в зависимости от состояния управляющего бита. Если бит управления равен 1, вентиль меняет местами целевые биты; если 0, биты проходят без изменений.

Таблица истинности

матрицы перестановок Форма

Вход			Выход
С	$я 1$	$я 2$	С	$О 1$	$Около 2$
0	0	0	0	0	0
0	0	1	0	0	1
0	1	0	0	1	0
0	1	1	0	1	1
1	0	0	1	0	0
1	0	1	1	1	0
1	1	0	1	0	1
1	1	1	1	1	1

${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&0&1&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\\end{bmatrix}}$

Реверсивные вычисления: вентиль является обратимым, что означает, что никакая информация не теряется во время вычислений. Это свойство соответствует принципам консервативной логики, сохраняя данные и уменьшая рассеивание энергии. Это хорошо соответствует закону сохранения массы в физике и помогает показать, что модель не расточительна.

Функции истинности с AND, OR, XOR и NOT

Ворота Фредкина можно определить с помощью функций истинности с AND , OR , XOR и NOT следующим образом:

О 1 = I 1 XOR S

,

О 2 = I 2 XOR S

,

C _выход = C _вход ,

где $S знак равно (я 1 XOR я 2) И C$ .

Альтернативно:

O 1 = (НЕ C И I 1) ИЛИ (C И I 2)

,

O 2 = (C И I 1) ИЛИ (НЕ C И I 2)

,

С _{на выходе} = С _{на входе} .

Полнота

Один из способов убедиться в универсальности вентиля Фредкина — это заметить, что его можно использовать для реализации И, НЕ и ИЛИ:

Если

I 2 = 0

, то

O 2 = C И I 1

.

Если

I 2 = 1

, то

O 1 = C OR I 1

.

Если

I 1 = 0

и

I 2 = 1

, то

2 = НЕ C.

O

Пример

Трехбитный полный сумматор (сложение с переносом) с использованием пяти вентилей Фредкина. Выходной бит «мусора» $g$ равен $(p NOR q),$ если $r = 0$ , и $(p NAND q),$ если $r = 1$ .

Входные данные слева, включая две константы, проходят через три вентиля, чтобы быстро определить четность. Биты 0 и 1 меняются местами для каждого установленного входного бита, в результате чего бит четности находится в 4-й строке, а бит четности — в 5-й строке.

Затем строка переноса и строка обратной четности меняются местами, если бит четности установлен, и снова меняются местами, если установлен один из $входных битов p$ или $q$ (не имеет значения, какой используется), и результирующий вывод переноса появляется в 3-й строке. .

Входы $p$ и $q$ используются только в качестве элементов управления воротами, поэтому на выходе они остаются неизменными.

Приложения

Реализация квантово-фотонного чипа

Недавние исследования продемонстрировали наличие вентиля Фредкина в программируемых кремниевых фотонных чипах. Эти чипы используют сеть интерферометров Маха-Цендера для эффективной маршрутизации фотонов, создавая универсальную и масштабируемую платформу, которая может обрабатывать несколько квантовых вентилей. Этот подход позволяет интегрировать вентили Фредкина в крупномасштабные квантовые процессоры, открывая путь для будущих достижений в области квантовых вычислений. ^[4]

Эффективная операция контролируемого свопа

В фотонной установке ворота Фредкина служат эффективным механизмом контролируемой замены, позволяющим условную замену целевых кубитов. Это особенно ценно при создании высокоточных состояний Гринбергера-Хорна-Цайлингера (GHZ), которые имеют решающее значение для квантовой связи и других протоколов. Таким образом, шлюз предоставляет мощный инструмент для квантовых протоколов, требующих эффективных условных операций. ^[5]

Оценка квантового состояния

Управляемые операции ворот Фредкина позволяют оценить перекрытие между квантовыми состояниями, не требуя ресурсоемкой томографии квантовых состояний. Это делает его особенно полезным для квантовой связи, измерений и криптографии, где эффективность и точность имеют первостепенное значение. ^[5]

Квантовые ворота Фредкина

25 марта 2016 года исследователи из Университета Гриффита и Университета Квинсленда объявили, что построили квантовые ворота Фредкина, которые используют квантовую запутанность частиц света для обмена кубитами . Наличие квантовых вентилей Фредкина может облегчить создание квантовых компьютеров . ^[5]^[6]

См. также

Квантовые вычисления
Столько же, сколько ворота
- Сколько это происходит?
Квантовое программирование
Ворота Тоффоли , которые представляют собой ворота «управляемый-управляемый-НЕ» .

Ссылки

^ Фредкин, Эдвард; Тоффоли, Томмазо (апрель 1982 г.). «Консервативная логика» . Международный журнал теоретической физики . 21 (3–4): 219–253. дои : 10.1007/bf01857727 . ISSN 0020-7748 .
^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе» . Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 . ISSN 0018-8646 .
^ Браун, Джулиан, В поисках квантового компьютера , Нью-Йорк: Touchstone, 2000.
^ Ли, Юань; Чжан, Хуэй; Ши, Ючжи; Чжоу, Сяоци; Лю, Ай Цюнь (15 сентября 2022 г.) . Ворота Тоффоли на универсальном программируемом кремниевом фотонном чипе» . npj Quantum Information . 8 (1). doi : 10.1038/s41534-022-00627-y . ISSN 2056-6387 .
^ Перейти обратно: ^а ^б ^с Квантовые ворота Фредкина Радж Б. Патель, Джозеф Хо, Франк Феррейрол, Тимоти К. Ральф и Джефф Дж. Прайд, Science Advances, 25 марта 2016 г., Vol. 2, нет. 3, e1501531, DOI: 10.1126/sciadv.1501531
^ «Квантовые вычисления теперь стали на большой шаг ближе благодаря новому прорыву: воротам Фредкина» .

Дальнейшее чтение

Фредкин, Эдвард ; Тоффоли, Томмазо (1982). «Консервативная логика» (PDF) . Международный журнал теоретической физики . 21 (3–4): 219–253. Бибкод : 1982IJTP...21..219F . дои : 10.1007/BF01857727 . S2CID 37305161 . Архивировано из оригинала (PDF) 17 октября 2006 г.

[1] Фредкин, Эдвард; Тоффоли, Томмазо (апрель 1982 г.). «Консервативная логика» . Международный журнал теоретической физики . 21 (3–4): 219–253. дои : 10.1007/bf01857727 . ISSN 0020-7748 .

[2] Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе» . Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 . ISSN 0018-8646 .

[3] Браун, Джулиан, В поисках квантового компьютера , Нью-Йорк: Touchstone, 2000.

[4] Ли, Юань; Чжан, Хуэй; Ши, Ючжи; Чжоу, Сяоци; Лю, Ай Цюнь (15 сентября 2022 г.) . Ворота Тоффоли на универсальном программируемом кремниевом фотонном чипе» . npj Quantum Information . 8 (1). doi : 10.1038/s41534-022-00627-y . ISSN 2056-6387 .

[:0-5] Перейти обратно: ^а ^б ^с Квантовые ворота Фредкина Радж Б. Патель, Джозеф Хо, Франк Феррейрол, Тимоти К. Ральф и Джефф Дж. Прайд, Science Advances, 25 марта 2016 г., Vol. 2, нет. 3, e1501531, DOI: 10.1126/sciadv.1501531

[6] «Квантовые вычисления теперь стали на большой шаг ближе благодаря новому прорыву: воротам Фредкина» .

[1]

[2]

[3]

[4]

[5]

[6]