Jump to content

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

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

Таблица истинности матрицы перестановок Форма
Вход Выход
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 0 1
1 1 0 1 1 1
1 1 1 1 1 0

Предыстория [ править ]

, потребляющий вход, Логический вентиль 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 между первым битом и вторым битом и оставляет первый бит неизменным.

Таблица истинности матрицы перестановок Форма
Вход Выход
0 0 0 0
0 1 0 1
1 0 1 1
1 1 1 0

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

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

Ворота Фредкина
Ворота Тоффоли могут быть построены из однокубитных Т- и Адамара -вентилей и как минимум шести CNOT .
  • Гейт Фредкина — это универсальный обратимый 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]

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

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

  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 . дои : 10.1103/PhysRevA.52.3457 . ПМИД   9912645 . S2CID   8764584 .
  6. ^ Ю, Нэнкун; Дуань, Руняо; Ин, Миншэн (30 июля 2013 г.). «Для реализации вентиля Тоффоли необходимы пять двухкубитных вентилей». Физический обзор А. 88 (1): 010304. arXiv : 1301.3372 . Бибкод : 2013PhRvA..88a0304Y . дои : 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. ^ Ким, Ю.; Морван, А.; Нгуен, Л.Б.; Наик, РК; Юнгер, К.; Чен, Л.; Крейкебаум, Дж. М.; Сантьяго, ДИ; Сиддики, И. (2 мая 2022 г.). «Высокоточный трехкубитный вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой» . Физика природы . 18 (5): 783–788. arXiv : 2108.10288 . Бибкод : 2022NatPh..18..783K . дои : 10.1038/s41567-022-01590-3 .
  11. ^ Ши, Яоюнь (январь 2003 г.). «И Тоффоли, и Controlled-NOT не нуждаются в особой помощи для выполнения универсальных квантовых вычислений». Квантовая информация и вычисления . 3 (1): 84–92. arXiv : Quant-ph/0205115 . Бибкод : 2002quant.ph..5115S . дои : 10.26421/QIC3.1-7 .
  12. ^ Монц, Т.; Ким, К.; Гензель, В.; Рибе, М.; Вильяр, AS; Шиндлер, П.; Чвалла, М.; Генрих, М.; Блатт, Р. (январь 2009 г.). «Реализация квантовых ворот Тоффоли с захваченными ионами». Письма о физических отзывах . 102 (4): 040501. arXiv : 0804.0082 . Бибкод : 2009PhRvL.102d0501M . doi : 10.1103/PhysRevLett.102.040501 . ПМИД   19257408 . S2CID   2051775 .
  13. ^ Шенде, Вивек В.; Марков, Игорь Л. (15 марта 2008 г.). «О ЦНОТ-стоимости ворот ТОФФОЛИ». arXiv : 0803.2316 [ квант-ph ].
  14. ^ Маслов, Дмитрий (2016). «Преимущества использования вентилей Тоффоли относительной фазы с применением для оптимизации Тоффоли с множественным управлением». Физический обзор А. 93 (2): 022311. arXiv : 1508.03273 . Бибкод : 2016PhRvA..93b2311M . doi : 10.1103/PhysRevA.93.022311 . S2CID   5226873 .
  15. ^ Кац, Ор; Цетина, Марко; Монро, Кристофер (8 февраля 2022 г.). " -Взаимодействия тел между захваченными ионными кубитами посредством спин-зависимого сжатия». Physical Review Letters . 129 (6): 063603. arXiv : 2202.04230 . doi : /PhysRevLett.129.063603 . PMID   36018637. . S2CID   2466 79905 10.1103
  16. ^ Ариас Эспиноза, Хуан Диего; Грунланд, Коэн; Маццанти, Маттео; Схоутенс, Карельская область; Герритсма, Рене (28 мая 2021 г.). «Высокоточный метод одношагового N -битного вентиля Тоффоли в захваченных ионах». Физический обзор А. 103 (5): 052437. arXiv : 2010.08490 . Бибкод : 2021PhRvA.103e2437E . дои : 10.1103/PhysRevA.103.052437 . S2CID   223953418 .
  17. ^ Jump up to: Перейти обратно: а б Хазали, Мохаммадсадек; Мёлмер, Клаус (11 июня 2020 г.). «Быстрые мультикубитные ворота в результате адиабатической эволюции во взаимодействующих многообразиях возбужденного состояния ридберговских атомов и сверхпроводящих цепей» . Физический обзор X . 10 (2): 021054. arXiv : 2006.07035 . Бибкод : 2020PhRvX..10b1054K . дои : 10.1103/PhysRevX.10.021054 . ISSN   2160-3308 .
  18. ^ Айзенхауэр, Л.; Саффман, М.; Мёлмер, К. (4 сентября 2011 г.). «Мультибитные квантовые ворота CkNOT через блокаду Ридберга». Квантовая обработка информации . 10 (6): 755. arXiv : 1104.3916 . дои : 10.1007/s11128-011-0292-4 . ISSN   1573-1332 . S2CID   28732092 .
  19. ^ Расмуссен, SE; Грунланд, К.; Герритсма, Р.; Схоутенс, К.; Зиннер, Северная Каролина (07 февраля 2020 г.). «Одношаговая реализация высокоточных n-битных вентилей Тоффоли». Физический обзор А. 101 (2): 022308. arXiv : 1910.07548 . Бибкод : 2020PhRvA.101b2308R . дои : 10.1103/physreva.101.022308 . ISSN   2469-9926 . S2CID   204744044 .
  20. ^ Нгуен, Л.Б.; Ким, Ю.; Хашим, А.; Госс, Н.; Маринелли, Б.; Бхандари, Б.; Дас, Д.; Наик, РК; Крейкебаум, Дж. М.; Джордан, А.; Сантьяго, ДИ; Сиддики, И. (16 января 2024 г.). «Программируемые гейзенберговские взаимодействия между кубитами Флоке» . Физика природы . 20 (1): 240–246. arXiv : 2211.10383 . Бибкод : 2024NatPh..20..240N . дои : 10.1038/s41567-023-02326-7 .
  21. ^ Нгуен, Лонг Б.; Госс, Ной; Шива, Картик; Ким, Йосеп; Юнис, Эд; Цин, Бинчэн; Хашим, Акель; Сантьяго, Дэвид И.; Сиддики, Ирфан (29 декабря 2023 г.). «Расширение возможностей многомерных квантовых вычислений путем прохождения двойной бозонной лестницы» . arXiv.org . Проверено 8 апреля 2024 г.
  22. ^ Ким, Ю.; Морван, А.; Нгуен, Л.Б.; Наик, РК; Юнгер, К.; Чен, Л.; Крейкебаум, Дж. М.; Сантьяго, ДИ; Сиддики, И. (2 мая 2022 г.). «Высокоточный трехкубитный вентиль iToffoli для сверхпроводящих кубитов с фиксированной частотой» . Физика природы . 18 (5): 783–788. arXiv : 2108.10288 . Бибкод : 2022NatPh..18..783K . дои : 10.1038/s41567-022-01590-3 .

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

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a7f5ea3890eadb88944e7c0d3bece39e__1715861160
URL1:https://arc.ask3.ru/arc/aa/a7/9e/a7f5ea3890eadb88944e7c0d3bece39e.html
Заголовок, (Title) документа по адресу, URL1:
Toffoli gate - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)