Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Схема ворот Тоффоли

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

Фон [ править ]

Логический вентиль L, потребляющий входные данные, является обратимым, если для любого выхода y существует уникальный вход x такой, что применение L ( x ) = y . Если вентиль L обратим, существует обратный вентиль L ', который отображает y в x, для которого L ' ( y ) = x . От обычных логических вентилей НЕ обратимо, как видно из его таблицы истинности ниже.

ВХОДВЫХОД
01
10

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

Реверсивные ворота изучаются с 1960-х годов. Первоначальная мотивация заключалась в том, что обратимые ворота рассеивают меньше тепла (или, в принципе, не нагревают). [1] Если мы думаем, что логический вентиль потребляет свой вход, информация теряется, поскольку на выходе содержится меньше информации, чем на входе. Эта потеря информации приводит к потере энергии в окружающей среде в виде тепла из-за термодинамической энтропии . [ необходима цитата ] Другой способ понять это - то, что заряды в цепи заземлены и, таким образом, утекают, забирая с собой небольшое количество энергии, когда они меняют состояние. Обратимые ворота только перемещают состояния, а поскольку информация не теряется, сохраняется энергия. [ цитата необходима]

Более поздняя мотивация исходит из квантовых вычислений . Квантовая механика требует, чтобы преобразования были обратимыми [ необходима цитата ] и допускает более общие состояния вычислений, чем классические компьютеры ( суперпозиции ).

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

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

Таблица истинностиФорма матрицы перестановок
ВХОДВЫХОД
 0  0  0  0 
0101
1011
1110

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

Этот вентиль имеет 3-битные входы и выходы. Если установлены первые два бита, он переворачивает третий бит. Ниже представлена ​​таблица входных и выходных битов:

Таблица истинностиФорма матрицы перестановок
ВХОДВЫХОД
 0  0  0  0  0  0 
001001
010010
011011
100100
101101
110111
111110

Это также можно описать как отображение битов {a, b, c} на {a, b, c XOR (a AND b)}.

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

Связанные логические ворота [ править ]

Вентиль Тоффоли может быть построен из вентилей с одним кубитом и минимум шести CNOT .
  • Ворота Фредкина является универсальным обратимым 3-битовым затвором , что свопы последних два бита , если первый бит равен 1; операция с контролируемым свопом.
  • П -битных вентиль тоффоль представляет собой обобщение Toffoli ворота. Он принимает 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 .
  • Вентиль Тоффоли может быть реализован с помощью пяти двухкубитных квантовых вентилей . [3]

(Можно показать, что это оптимум, то есть его нельзя реализовать, используя менее пяти. [4] )

  • Связанный с этим квантовый вентиль, ворота Дойча , может быть реализован с помощью пяти оптических импульсов с нейтральными атомами. [5] Ворота Дойча - универсальные ворота для квантовых вычислений. [6]

Отношение к квантовым вычислениям [ править ]

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

См. Также [ править ]

  • Фредкинские ворота
  • Обратимые вычисления
  • Биекция
  • Квантовые вычисления
  • Квантовые ворота
  • Квантовое программирование
  • Адиабатическая логика

Ссылки [ править ]

  1. ^ Ландауэр, Р. (июль 1961 г.). «Необратимость и тепловыделение в вычислительном процессе». Журнал исследований и разработок IBM . 5 (3): 183–191. DOI : 10.1147 / rd.53.0183 . ISSN  0018-8646 .
  2. ^ Технический отчет MIT / LCS / TM-151 (1980) и адаптированная и сокращенная версия: Toffoli, Tommaso (1980). JW de Bakker и J. van Leeuwen (ред.). Обратимые вычисления (PDF) . Автоматы, языки и программирование, Седьмой коллоквиум. Нордвейкерхаут, Нидерланды: Springer Verlag. С. 632–644. DOI : 10.1007 / 3-540-10003-2_104 . ISBN  3-540-10003-2. Архивировано из оригинального (PDF) 15 апреля 2010 года.
  3. ^ Баренко, Адриано; Беннетт, Чарльз Х .; Клив, Ричард; Ди Винченцо, Дэвид П .; Марголус, Норманн; Шор, Петр ; Sleator, Тихо; Смолин, Джон А .; Вайнфуртер, Харальд (ноябрь 1995 г.). «Элементарные ворота для квантовых вычислений». Физический Обзорный . Американское физическое общество. 52 (5): 3457–3467. arXiv : квант-ph / 9503016 . Bibcode : 1995PhRvA..52.3457B . DOI : 10.1103 / PhysRevA.52.3457 . PMID 9912645 . S2CID 8764584 .  
  4. ^ Ю, Нэнкун; Дуань, Руньяо; Инь Миншэн (30.07.2013). «Для реализации вентиля Тоффоли необходимо пять двухкубитных вентилей». Physical Review . 88 (1): 010304. arXiv : 1301.3372 . Bibcode : 2013PhRvA..88a0304Y . DOI : 10.1103 / physreva.88.010304 . ISSN 1050-2947 . S2CID 55486826 .  
  5. ^ Ши, Сяо-Фэн (май 2018 г.). «Deutsch, Toffoli и CNOT Gates через Ридбергскую блокаду нейтральных атомов». Применена физическая проверка . 9 (5): 051001. arXiv : 1710.01859 . Bibcode : 2018PhRvP ... 9e1001S . DOI : 10.1103 / PhysRevApplied.9.051001 . S2CID 118909059 . 
  6. ^ Дойч, Д. (1989). «Квантовые вычислительные сети». Труды Лондонского королевского общества. Серия А, Математические и физические науки . 425 (1868): 73–90. Bibcode : 1989RSPSA.425 ... 73D . DOI : 10,1098 / rspa.1989.0099 . ISSN 0080-4630 . JSTOR 2398494 . S2CID 123073680 .   
  7. ^ Ши, Yaoyun (январь 2003). «И Тоффоли, и Контролируемое НЕ нуждаются в небольшой помощи для выполнения универсальных квантовых вычислений». Квантовая информация и вычисления . 3 (1): 84–92. arXiv : квант-ph / 0205115 . Bibcode : 2002quant.ph..5115S .
  8. ^ Monz, T .; Kim, K .; Hänsel, W .; Riebe, M .; Villar, AS; Schindler, P .; Chwalla, M .; Hennrich, M .; Блатт, Р. (январь 2009 г.). «Реализация квантовых ворот Тоффоли с захваченными ионами». Письма с физическим обзором . Американское физическое общество. 102 (4): 040501. arXiv : 0804.0082 . Bibcode : 2009PhRvL.102d0501M . DOI : 10.1103 / PhysRevLett.102.040501 . PMID 19257408 . S2CID 2051775 .  
  9. ^ Хазали, Mohammadsadegh; Мёльмер, Клаус (11.06.2020). "Быстрые многокубитные вентили путем адиабатической эволюции во взаимодействующих многообразиях возбужденных состояний ридберговских атомов и сверхпроводящих цепей" . Physical Review X . 10 (2): 021054. Bibcode : 2020PhRvX..10b1054K . DOI : 10.1103 / PhysRevX.10.021054 . ISSN 2160-3308 . 
  10. ^ Isenhower, L .; Saffman, M .; Мёльмер, К. (04.09.2011). «Многобитные квантовые ворота CkNOT через блокаду Ридберга». Квантовая обработка информации . 10 (6): 755. arXiv : 1104.3916 . DOI : 10.1007 / s11128-011-0292-4 . ISSN 1573-1332 . S2CID 28732092 .  
  11. ^ Расмуссен, SE; Groenland, K .; Герритсма, Р .; Schoutens, K .; Зиннер, Н.Т. (07.02.2020). «Пошаговая реализация n -битных вентилей Тоффоли с высокой точностью». Физический Обзорный . 101 (2): 022308. arXiv : 1910.07548 . Bibcode : 2020PhRvA.101b2308R . DOI : 10.1103 / physreva.101.022308 . ISSN 2469-9926 . S2CID 204744044 .  
  12. ^ Шенде, Вивек V .; Марков Игорь Львович (2008-03-15). «О CNOT-стоимости ворот TOFFOLI». arXiv : 0803.2316 [ квант-ф ].
  13. ^ Маслов, Дмитрий (2015-08-13). «О преимуществах использования относительной фазы Тоффоли с приложением для множественного управления оптимизацией Тоффоли». arXiv : 1508.03273 [ квант-ф ].

Внешние ссылки [ править ]

  • CNOT и Тоффоли Гейтс в мульти-кубитном сеттинге на демонстрационном проекте Wolfram Demonstrations Project.