Ворота Тоффоли
В логических схемах вентиль Тоффоли , также известный как вентиль CCNOT («контролируемый-контролируемый-не»), изобретенный Томмазо Тоффоли , представляет собой вентиль CNOT с двумя управляющими кубитами и одним целевым кубитом. То есть целевой кубит (третий кубит) будет инвертирован, если первый и второй кубиты оба равны 1. Это универсальный обратимый логический элемент, а это означает, что любая классическая обратимая схема может быть построена из элементов Тоффоли. Формально мы описываем ворота Тоффоли следующей таблицей истинности и матрицей:
Таблица истинности | матрицы перестановок Форма | ||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
Предыстория [ править ]
, потребляющий вход, Логический вентиль L является обратимым, если он удовлетворяет следующим условиям: (1) L ( x ) = y — это вентиль, в котором для любого выхода y существует уникальный вход x ; (2) Вентиль L обратим, если существует вентиль L ´( y ) = x , который отображает y в x для всех y .
Примером обратимого логического элемента является НЕ, который можно описать с помощью приведенной ниже таблицы истинности:
Вход | Выход | Условие (1) | Условие (2) |
---|---|---|---|
0 | 1 | х = 0 у = 1 | у = 1 х = 0 |
1 | 0 | х = 1 у = 0 | у = 0 х = 1 |
Общий логический элемент И не является обратимым, поскольку все входы 00, 01 и 10 отображаются на выход 0.
Вход | Выход | Условие (1) |
---|---|---|
00 | 0 | x не уникален для y = 0 |
01 | 0 | x не уникален для y = 0 |
10 | 0 | x не уникален для y = 0 |
11 | 1 | х = 11 у = 1 |
Реверсивные ворота изучаются с 1960-х годов. Первоначальная мотивация заключалась в том, что реверсивные ворота рассеивают меньше тепла (или, в принципе, не рассеивают тепла). [1]
Более поздняя мотивация исходит от квантовых вычислений . В квантовой механике квантовое состояние может развиваться двумя путями: по уравнению Шредингера ( унитарные преобразования ) или путем их коллапса . Логические операции для квантовых компьютеров, примером которых является вентиль Тоффоли, представляют собой унитарные преобразования и, следовательно, развиваются обратимо. [2]
Универсальность и ворота Тоффоли [ править ]
должен иметь не больше входных битов, чем выходных битов Любой обратимый вентиль, который потребляет свои входы и позволяет все входные вычисления, по принципу «ячейки» . Для одного входного бита существует два возможных обратимых вентиля. Один из них НЕТ. Другой — это идентификационный вентиль, который преобразует свой вход в выход без изменений. Для двух входных битов единственным нетривиальным логическим элементом является управляемый логический элемент НЕ (CNOT), который выполняет операцию XOR между первым битом и вторым битом и оставляет первый бит неизменным.
Таблица истинности | матрицы перестановок Форма | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
К сожалению, существуют обратимые функции, которые невозможно вычислить, используя только эти элементы. Например, AND не может быть достигнуто этими воротами. Другими словами, набор, состоящий из вентилей НЕ и XOR, не является универсальным . Для вычисления произвольной функции с использованием обратимых вентилей действительно можно использовать вентиль Тоффоли, предложенный Тоффоли в 1980 году. [3] Это также можно описать как сопоставление битов { a , b , c } с { a , b , c XOR ( a AND b )}. Это также можно понимать как операцию по модулю над битом c : { a , b , c } → { a , b , ( c + ab ) mod 2}, часто записываемую как { a , b , c } → { a , b , c ⨁ ab }. [4]
Ворота Тоффоли универсальны; это означает, что для любой булевой функции f ( x 1 , x 2 , ..., x m ) существует схема, состоящая из вентилей Тоффоли, которая принимает x 1 , x 2 , ..., x m и набор дополнительных битов . в 0 или 1 на выходы x 1 , x 2 , ..., x m , f ( x 1 , x 2 , ..., x m ) и некоторые дополнительные биты (называемые мусором). Например, вентиль НЕ может быть построен из вентиля Тоффоли, установив три входных бита в { a , 1, 1}, сделав третий выходной бит (1 XOR ( a AND 1)) = NOT a ; ( a AND b ) — третий выходной бит из { a , b , 0}. По сути, это означает, что можно использовать вентили Тоффоли для создания систем, которые будут выполнять любые желаемые вычисления булевых функций обратимым образом.
Связанные логические элементы [ править ]


- Гейт Фредкина — это универсальный обратимый 3-битный вентиль, который меняет местами последние два бита, если первый бит равен 1; операция контролируемого обмена.
- -битовый вентиль n Тоффоли является обобщением вентиля Тоффоли. Он принимает n бит x 1 , x 2 , ..., x n в качестве входных данных и выводит n битов. Первые n − 1 выходных битов — это просто x 1 , ..., x n −1 . Последний выходной бит: ( x 1 AND ... AND x n −1 ) XOR x n .
- Ворота Тоффоли могут быть реализованы пятью двухкубитными квантовыми вентилями . [5] но можно показать, что использовать меньше пяти невозможно. [6]
- Другой универсальный вентиль, вентиль Дойча , может быть реализован пятью оптическими импульсами с нейтральными атомами. [7] Ворота Дойча — это универсальные ворота для квантовых вычислений. [8]
- Ворота Марголуса (названные в честь Нормана Марголуса ), также называемые упрощенными воротами Тоффоли, очень похожи на ворота Тоффоли, но с -1 на диагонали: RCCX =diag(1, 1, 1, 1, 1, -1, X ) . Вентиль Марголюса также универсален для обратимых схем и действует очень похоже на вентиль Тоффоли, с тем преимуществом, что он может быть построен примерно с половиной CNOT по сравнению с вентилем Тоффоли. [9]
- Вентиль iToffoli был реализован в сверхпроводящих кубитах с парной связью путем одновременного применения некоммутирующих операций. [10]
с квантовыми Связь вычислениями
Любой обратимый вентиль может быть реализован на квантовом компьютере , и, следовательно, вентиль Тоффоли также является квантовым оператором . Однако вентиль Тоффоли нельзя использовать для универсальных квантовых вычислений, хотя это и означает, что квантовый компьютер может реализовать все возможные классические вычисления. Вентиль Тоффоли должен быть реализован вместе с некоторыми по своей сути квантовыми вентилями, чтобы быть универсальным для квантовых вычислений. Фактически, достаточно любого однокубитного вентиля с действительными коэффициентами, который может создать нетривиальное квантовое состояние. [11] Ворота Тоффоли, основанные на квантовой механике, были успешно реализованы в январе 2009 года в Университете Инсбрука, Австрия. [12] Хотя реализация n -кубитного Тоффоли со схемной моделью требует 2 n вентилей CNOT, [13] самая известная верхняя граница составляет 6 n - 12 вентилей CNOT. [14] Было высказано предположение, что квантовые компьютеры с захваченными ионами могут напрямую реализовать n -кубитный вентиль Тоффоли. [15] Применение взаимодействия многих тел можно использовать для прямого управления затвором в захваченных ионах, ридберговских атомах и реализациях сверхпроводящих схем. [16] [17] [18] [19] [20] [21] Следуя многообразию темного состояния, ворота Хазали-Мёлмера C n -NOT [17] работает только с тремя импульсами, что отклоняется от парадигмы модели схемы. Вентиль iToffoli был реализован за один этап с использованием трех сверхпроводящих кубитов с парной связью. [22]
См. также [ править ]
- Управляемые ворота НЕ
- Фредкинские ворота
- Реверсивные вычисления
- Биекция
- Квантовые вычисления
- Квантовый логический вентиль
- Квантовое программирование
- Адиабатическая логика
Ссылки [ править ]
- ^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183 . ISSN 0018-8646 .
- ^ Колин П. Уильямс (2011). Исследования в области квантовых вычислений . Спрингер . стр. 25–29, 61. ISBN. 978-1-84628-887-6 .
- ^ Технический отчет MIT/LCS/TM-151 (1980) и адаптированная и сокращенная версия: Тоффоли, Томмазо (1980). Дж. В. де Баккер и Дж. ван Леувен (ред.). Реверсивные вычисления (PDF) . Автоматы, языки и программирование, Седьмой коллоквиум. Нордвейкерхаут, Нидерланды: Springer Verlag. стр. 632–644. дои : 10.1007/3-540-10003-2_104 . ISBN 3-540-10003-2 . Архивировано из оригинала (PDF) 15 апреля 2010 г.
- ^ Нильсен, Майкл Л.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (10-е изд.). Издательство Кембриджского университета. п. 29. ISBN 9781107002173 .
- ^ Баренко, Адриано; Беннетт, Чарльз Х.; Клив, Ричард; ДиВинченцо, Дэвид П.; Марголус, Норман; Шор, Питер ; Слитор, Тихо; Смолин, Джон А.; Вайнфуртер, Харальд (ноябрь 1995 г.). «Элементарные вентили для квантовых вычислений». Физический обзор А. 52 (5): 3457–3467. arXiv : Quant-ph/9503016 . Бибкод : 1995PhRvA..52.3457B . дои : 10.1103/PhysRevA.52.3457 . ПМИД 9912645 . S2CID 8764584 .
- ^ Ю, Нэнкун; Дуань, Руняо; Ин, Миншэн (30 июля 2013 г.). «Для реализации вентиля Тоффоли необходимы пять двухкубитных вентилей». Физический обзор А. 88 (1): 010304. arXiv : 1301.3372 . Бибкод : 2013PhRvA..88a0304Y . дои : 10.1103/physreva.88.010304 . ISSN 1050-2947 . S2CID 55486826 .
- ^ Ши, Сяо-Фэн (май 2018 г.). «Дойч, Тоффоли и CNOT Гейтс через Ридберговскую блокаду нейтральных атомов». Применена физическая проверка . 9 (5): 051001. arXiv : 1710.01859 . Бибкод : 2018PhRvP...9e1001S . doi : 10.1103/PhysRevApplied.9.051001 . S2CID 118909059 .
- ^ Дойч, Д. (1989). «Квантовые вычислительные сети». Труды Лондонского королевского общества. Серия А, Математические и физические науки . 425 (1868): 73–90. Бибкод : 1989RSPSA.425...73D . дои : 10.1098/rspa.1989.0099 . ISSN 0080-4630 . JSTOR 2398494 . S2CID 123073680 .
- ^ Маслов, Дмитрий (10 февраля 2016 г.). «Преимущества использования вентилей Тоффоли относительной фазы с применением для оптимизации Тоффоли с множественным управлением» . Физический обзор А. 93 (2): 022311. arXiv : 1508.03273 . Бибкод : 2016PhRvA..93b2311M . doi : 10.1103/PhysRevA.93.022311 . ISSN 2469-9926 .
- ^ Ким, Ю.; Морван, А.; Нгуен, Л.Б.; Наик, РК; Юнгер, К.; Чен, Л.; Крейкебаум, Дж. М.; Сантьяго, ДИ; Сиддики, И. (2 мая 2022 г.). «Высокоточный трехкубитный вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой» . Физика природы . 18 (5): 783–788. arXiv : 2108.10288 . Бибкод : 2022NatPh..18..783K . дои : 10.1038/s41567-022-01590-3 .
- ^ Ши, Яоюнь (январь 2003 г.). «И Тоффоли, и Controlled-NOT не нуждаются в особой помощи для выполнения универсальных квантовых вычислений». Квантовая информация и вычисления . 3 (1): 84–92. arXiv : Quant-ph/0205115 . Бибкод : 2002quant.ph..5115S . дои : 10.26421/QIC3.1-7 .
- ^ Монц, Т.; Ким, К.; Гензель, В.; Рибе, М.; Вильяр, AS; Шиндлер, П.; Чвалла, М.; Генрих, М.; Блатт, Р. (январь 2009 г.). «Реализация квантовых ворот Тоффоли с захваченными ионами». Письма о физических отзывах . 102 (4): 040501. arXiv : 0804.0082 . Бибкод : 2009PhRvL.102d0501M . doi : 10.1103/PhysRevLett.102.040501 . ПМИД 19257408 . S2CID 2051775 .
- ^ Шенде, Вивек В.; Марков, Игорь Л. (15 марта 2008 г.). «О ЦНОТ-стоимости ворот ТОФФОЛИ». arXiv : 0803.2316 [ квант-ph ].
- ^ Маслов, Дмитрий (2016). «Преимущества использования вентилей Тоффоли относительной фазы с применением для оптимизации Тоффоли с множественным управлением». Физический обзор А. 93 (2): 022311. arXiv : 1508.03273 . Бибкод : 2016PhRvA..93b2311M . doi : 10.1103/PhysRevA.93.022311 . S2CID 5226873 .
- ^ Кац, Ор; Цетина, Марко; Монро, Кристофер (8 февраля 2022 г.). " -Взаимодействия тел между захваченными ионными кубитами посредством спин-зависимого сжатия». Physical Review Letters . 129 (6): 063603. arXiv : 2202.04230 . doi : /PhysRevLett.129.063603 . PMID 36018637. . S2CID 2466 79905 10.1103
- ^ Ариас Эспиноза, Хуан Диего; Грунланд, Коэн; Маццанти, Маттео; Схоутенс, Карельская область; Герритсма, Рене (28 мая 2021 г.). «Высокоточный метод одношагового N -битного вентиля Тоффоли в захваченных ионах». Физический обзор А. 103 (5): 052437. arXiv : 2010.08490 . Бибкод : 2021PhRvA.103e2437E . дои : 10.1103/PhysRevA.103.052437 . S2CID 223953418 .
- ^ Jump up to: Перейти обратно: а б Хазали, Мохаммадсадек; Мёлмер, Клаус (11 июня 2020 г.). «Быстрые мультикубитные ворота в результате адиабатической эволюции во взаимодействующих многообразиях возбужденного состояния ридберговских атомов и сверхпроводящих цепей» . Физический обзор X . 10 (2): 021054. arXiv : 2006.07035 . Бибкод : 2020PhRvX..10b1054K . дои : 10.1103/PhysRevX.10.021054 . ISSN 2160-3308 .
- ^ Айзенхауэр, Л.; Саффман, М.; Мёлмер, К. (4 сентября 2011 г.). «Мультибитные квантовые ворота CkNOT через блокаду Ридберга». Квантовая обработка информации . 10 (6): 755. arXiv : 1104.3916 . дои : 10.1007/s11128-011-0292-4 . ISSN 1573-1332 . S2CID 28732092 .
- ^ Расмуссен, SE; Грунланд, К.; Герритсма, Р.; Схоутенс, К.; Зиннер, Северная Каролина (07 февраля 2020 г.). «Одношаговая реализация высокоточных n-битных вентилей Тоффоли». Физический обзор А. 101 (2): 022308. arXiv : 1910.07548 . Бибкод : 2020PhRvA.101b2308R . дои : 10.1103/physreva.101.022308 . ISSN 2469-9926 . S2CID 204744044 .
- ^ Нгуен, Л.Б.; Ким, Ю.; Хашим, А.; Госс, Н.; Маринелли, Б.; Бхандари, Б.; Дас, Д.; Наик, РК; Крейкебаум, Дж. М.; Джордан, А.; Сантьяго, ДИ; Сиддики, И. (16 января 2024 г.). «Программируемые гейзенберговские взаимодействия между кубитами Флоке» . Физика природы . 20 (1): 240–246. arXiv : 2211.10383 . Бибкод : 2024NatPh..20..240N . дои : 10.1038/s41567-023-02326-7 .
- ^ Нгуен, Лонг Б.; Госс, Ной; Шива, Картик; Ким, Йосеп; Юнис, Эд; Цин, Бинчэн; Хашим, Акель; Сантьяго, Дэвид И.; Сиддики, Ирфан (29 декабря 2023 г.). «Расширение возможностей многомерных квантовых вычислений путем прохождения двойной бозонной лестницы» . arXiv.org . Проверено 8 апреля 2024 г.
- ^ Ким, Ю.; Морван, А.; Нгуен, Л.Б.; Наик, РК; Юнгер, К.; Чен, Л.; Крейкебаум, Дж. М.; Сантьяго, ДИ; Сиддики, И. (2 мая 2022 г.). «Высокоточный трехкубитный вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой» . Физика природы . 18 (5): 783–788. arXiv : 2108.10288 . Бибкод : 2022NatPh..18..783K . дои : 10.1038/s41567-022-01590-3 .
Внешние ссылки [ править ]
- CNOT и ворота Тоффоли в многокубитной настройке в демонстрационном проекте Wolfram.