stringtranslate.com

Ворота Тоффоли

В логических схемах вентиль Тоффоли (также вентиль CCNOT ), изобретенный Томмазо Тоффоли , представляет собой универсальный обратимый логический вентиль , а это означает, что любая классическая обратимая схема может быть построена из вентилей Тоффоли. Они также известны как ворота «контролируется-контролируется-не», что описывает их действие. Он имеет 3-битные входы и выходы; если первые два бита установлены в 1, он инвертирует третий бит, в противном случае все биты остаются прежними.

Фон

Логический вентиль L , потребляющий вход, является обратимым, если он удовлетворяет следующим условиям: L ( x ) = y — это вентиль, в котором для любого выхода y существует уникальный вход x . Вентиль L обратим, если существует вентиль L ´( y ) = x , который отображает y в x для всех y . Из обычных логических элементов NOT является обратимым, как видно из его таблицы истинности ниже:

Общий логический элемент И не является обратимым, поскольку все входы 00, 01 и 10 отображаются на выход 0.

Реверсивные ворота изучаются с 1960-х годов. Первоначальная мотивация заключалась в том, что реверсивные ворота рассеивают меньше тепла (или, в принципе, не рассеивают тепла). [1]

Более поздняя мотивация исходит от квантовых вычислений . В квантовой механике квантовое состояние может развиваться двумя путями: по уравнению Шредингера ( унитарные преобразования ) или путем их коллапса . Логические операции для квантовых компьютеров, примером которых является вентиль Тоффоли, представляют собой унитарные преобразования и, следовательно, развиваются обратимо. [2]

Универсальность и ворота Тоффоли

Любой обратимый вентиль, который потребляет свои входы и позволяет все входные вычисления, по принципу « ячейки» должен иметь не больше входных битов, чем выходных битов . Для одного входного бита существует два возможных обратимых вентиля. Один из них НЕТ. Другой — это идентификационный вентиль, который преобразует свой вход в выход без изменений. Для двух входных битов единственным нетривиальным логическим элементом является управляемый логический элемент НЕ (далее CNOT), который выполняет операцию XOR между первым битом и вторым битом и оставляет первый бит неизменным.

К сожалению, существуют обратимые функции, которые невозможно вычислить, используя только эти элементы. Другими словами, набор, состоящий из вентилей НЕ и XOR, не является универсальным . Чтобы вычислить произвольную функцию с помощью обратимых вентилей, необходим еще один вентиль. Одной из возможностей являются ворота Тоффоли , предложенные в 1980 году Тоффоли. [3]

Этот вентиль имеет 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}. По сути, это означает, что можно использовать вентили Тоффоли для создания систем, которые будут выполнять любые желаемые вычисления булевых функций обратимым образом.

Связанные логические элементы

Ворота Тоффоли могут быть построены из однокубитных Т- и Адамара -вентилей и минимум шести CNOT .

Связь с квантовыми вычислениями

Любой обратимый вентиль может быть реализован на квантовом компьютере , и, следовательно, вентиль Тоффоли также является квантовым оператором . Однако вентиль Тоффоли нельзя использовать для универсальных квантовых вычислений, хотя это и означает, что квантовый компьютер может реализовать все возможные классические вычисления. Вентиль Тоффоли должен быть реализован вместе с некоторыми по своей сути квантовыми вентилями, чтобы быть универсальным для квантовых вычислений. Фактически, достаточно любого однокубитного вентиля с действительными коэффициентами, который может создать нетривиальное квантовое состояние. [10] Ворота Тоффоли, основанные на квантовой механике, были успешно реализованы в январе 2009 года в Университете Инсбрука, Австрия. [11] Хотя реализация n -кубитного Тоффоли со схемной моделью требует 2 n вентилей CNOT, [12] наиболее известная верхняя граница составляет 6 n  - 12 вентилей CNOT. [13] Было высказано предположение, что квантовые компьютеры с захваченными ионами могут напрямую реализовать n -кубитный вентиль Тоффоли. [14] Применение взаимодействия многих тел может быть использовано для прямого управления затвором в захваченных ионах, ридберговских атомах и реализациях сверхпроводящих схем. [15] [16] [17] [18] Следуя темному многообразию, вентиль Хазали-Мёлмера C n -NOT [16] работает только с тремя импульсами, что отклоняется от парадигмы модели схемы.

Смотрите также

Рекомендации

  1. ^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. дои : 10.1147/рд.53.0183. ISSN  0018-8646.
  2. ^ Колин П. Уильямс (2011). Исследования в области квантовых вычислений . Спрингер . стр. 25–29, 61. ISBN. 978-1-84628-887-6.
  3. ^ Технический отчет 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 г.
  4. ^ Нильсен, Майкл Л.; Чуанг, Исаак Л. (2010). Квантовые вычисления и квантовая информация (10-е изд.). Издательство Кембриджского университета. п. 29. ISBN 9781107002173.
  5. ^ Баренко, Адриано; Беннетт, Чарльз Х.; Клив, Ричард; ДиВинченцо, Дэвид П.; Марголус, Норман; Шор, Питер ; Слитор, Тихо; Смолин, Джон А.; Вайнфуртер, Харальд (ноябрь 1995 г.). «Элементарные вентили для квантовых вычислений». Физический обзор А. 52 (5): 3457–3467. arXiv : Quant-ph/9503016 . Бибкод : 1995PhRvA..52.3457B. doi : 10.1103/PhysRevA.52.3457. PMID  9912645. S2CID  8764584.
  6. ^ Ю, Ненгкун; Дуань, Руняо; Ин, Миншэн (30 июля 2013 г.). «Для реализации вентиля Тоффоли необходимы пять двухкубитных вентилей». Физический обзор А. 88 (1): 010304. arXiv : 1301.3372 . Бибкод : 2013PhRvA..88a0304Y. doi :10.1103/physreva.88.010304. ISSN  1050-2947. S2CID  55486826.
  7. ↑ Ши, Сяо-Фэн (май 2018 г.). «Дойч, Тоффоли и CNOT Гейтс через Ридберговскую блокаду нейтральных атомов». Применена физическая проверка . 9 (5): 051001. arXiv : 1710.01859 . Бибкод : 2018PhRvP...9e1001S. doi : 10.1103/PhysRevApplied.9.051001. S2CID  118909059.
  8. ^ Дойч, Д. (1989). «Квантовые вычислительные сети». Труды Лондонского королевского общества. Серия А, Математические и физические науки . 425 (1868): 73–90. Бибкод : 1989RSPSA.425...73D. дои : 10.1098/rspa.1989.0099. ISSN  0080-4630. JSTOR  2398494. S2CID  123073680.
  9. ^ Маслов, Дмитрий (10 февраля 2016 г.). «Преимущества использования вентилей Тоффоли относительной фазы с применением для оптимизации Тоффоли с множественным управлением». Физический обзор А. 93 (2): 022311. arXiv : 1508.03273 . Бибкод : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311 . ISSN  2469-9926.
  10. ^ Ши, Яоюнь (январь 2003 г.). «И Тоффоли, и Controlled-NOT не нуждаются в особой помощи для выполнения универсальных квантовых вычислений». Квантовая информация и вычисления . 3 (1): 84–92. arXiv : Quant-ph/0205115 . Бибкод : 2002quant.ph..5115S. дои : 10.26421/QIC3.1-7.
  11. ^ Монц, Т.; Ким, К.; Гензель, В.; Рибе, М.; Вильяр, AS; Шиндлер, П.; Чвалла, М.; Генрих, М.; Блатт, Р. (январь 2009 г.). «Реализация квантовых ворот Тоффоли с захваченными ионами». Письма о физических отзывах . 102 (4): 040501. arXiv : 0804.0082 . Бибкод : 2009PhRvL.102d0501M. doi :10.1103/PhysRevLett.102.040501. PMID  19257408. S2CID  2051775.
  12. ^ Шенде, Вивек В.; Марков, Игорь Л. (15 марта 2008 г.). «О ЦНОТ-стоимости ворот ТОФФОЛИ». arXiv : 0803.2316 [квант-ph].
  13. ^ Маслов, Дмитрий (2016). «Преимущества использования вентилей Тоффоли относительной фазы с применением для оптимизации Тоффоли с множественным управлением». Физический обзор А. 93 (2): 022311. arXiv : 1508.03273 . Бибкод : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311. S2CID  5226873.
  14. ^ Кац, Ор; Цетина, Марко; Монро, Кристофер (8 февраля 2022 г.). « Взаимодействия тел между захваченными ионными кубитами посредством спин-зависимого сжатия». Письма о физических отзывах . 129 (6): 063603. arXiv : 2202.04230 . doi : 10.1103/PhysRevLett.129.063603. PMID  36018637. S2CID  246679905.
  15. ^ Ариас Эспиноза, Хуан Диего; Грунланд, Коэн; Маццанти, Маттео; Схоутенс, Карельская область; Герритсма, Рене (28 мая 2021 г.). «Высокоточный метод одношагового N -битного вентиля Тоффоли в захваченных ионах». Физический обзор А. 103 (5): 052437. arXiv : 2010.08490 . Бибкод : 2021PhRvA.103e2437E. doi : 10.1103/PhysRevA.103.052437. S2CID  223953418.
  16. ^ Аб Хазали, Мохаммадсадек; Мёлмер, Клаус (11 июня 2020 г.). «Быстрые мультикубитные ворота в результате адиабатической эволюции во взаимодействующих многообразиях возбужденного состояния ридберговских атомов и сверхпроводящих цепей». Физический обзор X . 10 (2): 021054. arXiv : 2006.07035 . Бибкод : 2020PhRvX..10b1054K. дои : 10.1103/PhysRevX.10.021054 . ISSN  2160-3308.
  17. ^ Айзенхауэр, Л.; Саффман, М.; Мёлмер, К. (4 сентября 2011 г.). «Мультибитные квантовые ворота CkNOT через блокаду Ридберга». Квантовая обработка информации . 10 (6): 755. arXiv : 1104.3916 . дои : 10.1007/s11128-011-0292-4. ISSN  1573-1332. S2CID  28732092.
  18. ^ Расмуссен, SE; Грунланд, К.; Герритсма, Р.; Схоутенс, К.; Зиннер, Северная Каролина (07 февраля 2020 г.). «Одношаговая реализация высокоточных n-битных вентилей Тоффоли». Физический обзор А. 101 (2): 022308. arXiv : 1910.07548 . Бибкод : 2020PhRvA.101b2308R. doi :10.1103/physreva.101.022308. ISSN  2469-9926. S2CID  204744044.

Внешние ссылки