stringtranslate.com

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

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

Таблица истинности и матрица следующие:

Фон

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

Примером обратимого логического вентиля является НЕ , который можно описать с помощью его таблицы истинности ниже:

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

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

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

Описание оборудования

Классический вентиль Тоффоли реализован на языке описания оборудования, таком как Verilog:

модуль toffoli_gate ( вход u1 , вход u2 , вход in , выход v1 , выход v2 , выход out ); всегда @( * ) begin v1 = u1 ; v2 = u2 ; out = in ^ u1 && u2 ; end endmodule

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

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

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

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

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

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

Любой обратимый вентиль может быть реализован на квантовом компьютере , и, следовательно, вентиль Тоффоли также является квантовым оператором . Однако вентиль Тоффоли не может быть использован для универсальных квантовых вычислений, хотя это означает, что квантовый компьютер может реализовать все возможные классические вычисления. Вентиль Тоффоли должен быть реализован вместе с некоторыми изначально квантовыми вентилями, чтобы быть универсальным для квантовых вычислений. Фактически, достаточно любого однокубитного вентиля с действительными коэффициентами, который может создать нетривиальное квантовое состояние. [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]

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

Ссылки

  1. ^ Ландауэр, Р. (июль 1961 г.). «Необратимость и выделение тепла в вычислительном процессе». IBM Journal of Research and Development . 5 (3): 183–191. doi :10.1147/rd.53.0183. ISSN  0018-8646.
  2. ^ Колин П. Уильямс (2011). Исследования в области квантовых вычислений . Springer . С. 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) 2010-04-15.
  4. ^ Нильсен, Майкл Л.; Чуан, Айзек Л. (2010). Квантовые вычисления и квантовая информация (10-е изд.). Cambridge University Press. стр. 29. ISBN 9781107002173.
  5. ^ Баренко, Адриано; Беннетт, Чарльз Х.; Клив, Ричард; ДиВинченцо, Дэвид П.; Марголус, Норман; Шор, Питер ; Слейтор, Тихо; Смолин, Джон А.; Вайнфуртер, Харальд (ноябрь 1995 г.). «Элементарные вентили для квантовых вычислений». Physical Review A. 52 ( 5): 3457–3467. arXiv : quant-ph/9503016 . Bibcode : 1995PhRvA..52.3457B. doi : 10.1103/PhysRevA.52.3457. PMID  9912645. S2CID  8764584.
  6. ^ Юй, Ненгкунь; Дуань, Руньяо; Ин, Миншэн (2013-07-30). "Для реализации вентиля Тоффоли необходимо пять двухкубитных вентилей". Physical Review A. 88 ( 1): 010304. arXiv : 1301.3372 . Bibcode : 2013PhRvA..88a0304Y. doi : 10.1103/physreva.88.010304. ISSN  1050-2947. S2CID  55486826.
  7. ^ Ши, Сяо-Фэн (май 2018 г.). «Deutsch, Toffoli и CNOT Gates через Rydberg Blockade of Neutral Atoms». Physical Review Applied . 9 (5): 051001. arXiv : 1710.01859 . Bibcode : 2018PhRvP...9e1001S. doi : 10.1103/PhysRevApplied.9.051001. S2CID  118909059.
  8. ^ Deutsch, D. (1989). «Квантовые вычислительные сети». Труды Лондонского королевского общества. Серия A, Математические и физические науки . 425 (1868): 73–90. Bibcode : 1989RSPSA.425...73D. doi : 10.1098/rspa.1989.0099. ISSN  0080-4630. JSTOR  2398494. S2CID  123073680.
  9. ^ Маслов, Дмитрий (2016-02-10). "Преимущества использования вентилей Тоффоли с относительной фазой в приложении к оптимизации Тоффоли с множественным управлением". Physical Review A. 93 ( 2): 022311. arXiv : 1508.03273 . Bibcode : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311 . ISSN  2469-9926.
  10. ^ Ким, Y.; Морван, A.; Нгуен, LB; Наик, RK; Юнгер, C.; Чен, L.; Крейкебаум, JM; Сантьяго, DI; Сиддики, I. (2 мая 2022 г.). «Высокоточный трехкубитовый вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой». Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Bibcode :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
  11. ^ Ши, Яоюнь (январь 2003 г.). «И Toffoli, и Controlled-NOT нуждаются в небольшой помощи для выполнения универсальных квантовых вычислений». Quantum Information & Computation . 3 (1): 84–92. arXiv : quant-ph/0205115 . Bibcode : 2002quant.ph..5115S. doi : 10.26421/QIC3.1-7.
  12. ^ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, AS; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (январь 2009 г.). "Реализация квантового затвора Тоффоли с захваченными ионами". Physical Review Letters . 102 (4): 040501. arXiv : 0804.0082 . Bibcode :2009PhRvL.102d0501M. doi :10.1103/PhysRevLett.102.040501. PMID  19257408. S2CID  2051775.
  13. ^ Шенде, Вивек В.; Марков, Игорь Л. (2008-03-15). «О стоимости CNOT вентилей TOFFOLI». arXiv : 0803.2316 [quant-ph].
  14. ^ Маслов, Дмитрий (2016). «Преимущества использования вентилей Тоффоли с относительной фазой в приложении к оптимизации Тоффоли с множественным управлением». Physical Review A. 93 ( 2): 022311. arXiv : 1508.03273 . Bibcode : 2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311. S2CID  5226873.
  15. ^ Katz, Or; Cetina, Marko; Monroe, Christopher (2022-02-08). " Взаимодействие тел между захваченными ионными кубитами посредством спин-зависимого сжатия". Physical Review Letters . 129 (6): 063603. arXiv : 2202.04230 . doi : 10.1103/PhysRevLett.129.063603. PMID  36018637. S2CID  246679905.
  16. ^ Ариас Эспиноза, Хуан Диего; Грунланд, Коэн; Маццанти, Маттео; Схоутенс, Карельская область; Герритсма, Рене (28 мая 2021 г.). «Высокоточный метод одношагового N -битного вентиля Тоффоли в захваченных ионах». Физический обзор А. 103 (5): 052437. arXiv : 2010.08490 . Бибкод : 2021PhRvA.103e2437E. doi : 10.1103/PhysRevA.103.052437. S2CID  223953418.
  17. ^ ab Khazali, Mohammadsadegh; Mølmer, Klaus (2020-06-11). "Быстрые многокубитные вентили с адиабатической эволюцией во взаимодействующих возбужденных многообразиях ридберговских атомов и сверхпроводящих цепях". Physical Review X. 10 ( 2): 021054. arXiv : 2006.07035 . Bibcode : 2020PhRvX..10b1054K. doi : 10.1103/PhysRevX.10.021054 . ISSN  2160-3308.
  18. ^ Айзенхауэр, Л.; Саффман, М.; Мёльмер, К. (2011-09-04). "Многобитовые квантовые вентили CkNOT через блокаду Ридберга". Квантовая обработка информации . 10 (6): 755. arXiv : 1104.3916 . doi : 10.1007/s11128-011-0292-4. ISSN  1573-1332. S2CID  28732092.
  19. ^ Расмуссен, SE; Гроенланд, K.; Герритсма, R.; Схоутенс, K.; Циннер, NT (2020-02-07). «Одношаговая реализация высокоточных n-битных вентилей Тоффоли». Physical Review A. 101 ( 2): 022308. arXiv : 1910.07548 . Bibcode : 2020PhRvA.101b2308R. doi : 10.1103/physreva.101.022308. ISSN  2469-9926. S2CID  204744044.
  20. ^ Нгуен, Л. Б.; Ким, Ю.; Хашим, А.; Госс, Н.; Маринелли, Б.; Бхандари, Б.; Дас, Д.; Наик, РК; Крейкебаум, Дж. М.; Джордан, А.; Сантьяго, ДИ; Сиддики, И. (16 января 2024 г.). «Программируемые взаимодействия Гейзенберга между кубитами Флоке». Nature Physics . 20 (1): 240–246. arXiv : 2211.10383 . Bibcode : 2024NatPh..20..240N. doi : 10.1038/s41567-023-02326-7 .
  21. ^ Нгуен, Лонг Б.; Госс, Ноа; Сива, Картик; Ким, Йосеп; Юнис, Эд; Цин, Бинчэн; Хашим, Акель; Сантьяго, Дэвид И.; Сиддики, Ирфан (29.12.2023). «Расширение возможностей высокоразмерных квантовых вычислений путем преодоления двойной бозонной лестницы». arXiv.org . Получено 08.04.2024 .
  22. ^ Ким, Y.; Морван, A.; Нгуен, LB; Наик, RK; Юнгер, C.; Чен, L.; Крейкебаум, JM; Сантьяго, DI; Сиддики, I. (2 мая 2022 г.). «Высокоточный трехкубитовый вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой». Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Bibcode :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .

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