PROFILPELAJAR.COM

Вентиль Тоффолі (також вентиль CCNOT) — у логічних схемах вентиль, винайдений Томмазо Тоффолі, є універсальним оборотним логічним вентилем, що означає, що будь-яка оборотна схема може бути побудована з вентилів Тоффолі. Він також відомий як вентиль «контрольоване-контрольоване-НЕ», який описує його дію. Він має 3-бітові входи та виходи; якщо перші два біти встановлені в 1, він інвертує третій біт, інакше всі біти залишаються незмінними.

Основи

Логічний вентиль L є оборотним, якщо для будь-якого виходу y існує унікальний вхід x, такий що виконується L(x) = y. Якщо вентиль L є оборотним, існує зворотний вентиль L′, який відображає y в x, де L′(y) = x. Із загальноприйнятих логічних входів вентиль «НЕ» є оборотним, як це видно з таблиці істинності нижче.

ВХІД	ВИХІД
0	1
1	0

Однак у загальному випадку вентиль «І» не є оборотним. Входи 00, 01 і 10 відображаються на виході в 0.

Оборотні вентилі вивчали з 1960-х років. Початковою мотивацією було те, що оборотні вентилі розсіюють менше тепла (або, в принципі, не розсіюють тепла).^[1] Якщо розглянути логічний вентиль як щось, що споживає подане на вхід, інформація втрачається, оскільки на виході наявно менше інформації, ніж на вході. Через цю втрату інформації втрачається енергія до навколишнього середовища у вигляді тепла через термодинамічну ентропію.^[2] Іншим способом зрозуміти це є те, що заряди в ланцюзі стікають на землю забираючи з собою невелику кількість енергії, коли вони змінюють стан. Оборотний вентиль лише переміщує стани, і оскільки інформація не втрачається, енергія зберігається.

Більш недавня мотивація походить від квантових обчислень. Квантова механіка вимагає, щоб перетворення були оборотними і дозволяє більш загальні обчислення, ніж класичні комп'ютери (принцип суперпозиції).

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

Будь-який оборотний вентиль, який споживає свої вхідні дані та дозволяє всі вхідні обчислення, повинен мати не більше вхідних бітів, ніж вихідні біти, за принципом Діріхле. Для одного вхідного біта існує два можливих оборотних вентиля. Один з них НЕ. Інший — вентиль ідентичності, який відображає свої вхідні дані у вихідні дані без змін. Для двох вхідних бітів єдиним нетривіальним вентилем є вентиль «контрольоване-НЕ», який виконує операцію «Виключне АБО» першого біта і другого біта і залишає перший біт незмінним.

Таблиця істинності

Форма матриці перестановки

INPUT		OUTPUT
0	0	0	0
0	1	0	1
1	0	1	1
1	1	1	0

${\begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&1\\0&0&1&0\\\end{bmatrix}}$

На жаль, є оборотні функції, які неможливо обчислити, використовуючи лише ці вентилі. Іншими словами, набір, що складається з вентилів NOT і XOR, не є універсальним. Щоб обчислити довільну функцію за допомогою оборотних вентилів, нам потрібен інший вентиль. Одним з можливих є вентиль Тоффолі, запропонований Тоффолі в 1980 році.^[3]

Цей шлюз має 3-бітові вхід та вихід. Якщо встановлено перші два біти, він змінює на протилежне значення третій біт. Далі наведена таблиця вхідних і вихідних бітів:

Таблиця істинності

Форма матриці перестановки

INPUT			OUTPUT
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

${\begin{bmatrix}1&0&0&0&0&0&0&0\\0&1&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&0&0&1&0&0&0&0\\0&0&0&0&1&0&0&0\\0&0&0&0&0&1&0&0\\0&0&0&0&0&0&0&1\\0&0&0&0&0&0&1&0\\\end{bmatrix}}$

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

Вентиль Тоффолі універсальний; це означає, що для будь-якої булевої функції f(x₁, x₂, …, x_m), існує ланцюг, що складається з вентилів Тоффолі, який приймає x₁, x₂, …, x_m та деякі додаткові біти, які мають значення 0 або 1 для виходів x₁, x₂, …, x_m, f(x₁, x₂, …, x_m), а також додаткові біти (що називаються сміттєвими). По суті, це означає, що можна використовувати вентиль Тоффолі для побудови систем, які оборотно виконуватимуть обчислення будь-якої бажаної булевої функції.

Пов'язані логічні вентилі

Вентиль Фредкіна — це універсальний оборотний 3-бітовий вентиль, який міняє місцями два останні біти, якщо перший біт дорівнює 1; реалізує операцію керованого обміну.
n — бітовий вентиль Тоффолі є узагальненням вентиля Тоффолі. Це приймає n біт x₁, x₂, …, x_n у якості входів і віддає n бітів. Перші n−1 вихідних бітів це просто x₁, …, x_n−1. Останній вихідний біт (x₁ AND … AND x_n−1) XOR x_n . Вентиль Тоффолі може бути реалізовано з п'яти двохкубітних квантових вентилів.^[4]Насправді для реалізації вентиля Тоффолі потрібно мінімум п'ять двохкубітних квантових вентилів.^[5]

Пов'язаний з ними квантовий вентиль Дойча може бути реалізований за допомогою п'яти оптичних імпульсів з нейтральними атомами.^[6] Вентиль Дойча — це універсальний вентиль для квантових обчислень.^[7]

Відношення до квантових обчислень

Будь-які оборотні вентилі можуть бути реалізовані на квантовому комп'ютері, отже, вентиль Тоффолі також є квантовим оператором. Однак вентиль Тоффолі не може бути використаний для універсальних квантових обчислень, хоча це означає, що квантовий комп'ютер може реалізувати всі можливі класичні обчислення. Вентиль Тоффолі повинен бути реалізований разом з деякими по суті квантовими вентилями, щоб бути універсальним для квантових обчислень. Насправді достатньо будь-якого одиночного кубіта з реальними коефіцієнтами, який може створити нетривіальний квантовий стан.^[8] Вентиль Тоффолі на основі квантової механіки був успішно реалізований в січні 2009 року в Університеті Інсбрука, Австрія.^[9] Хоча реалізація n-кубітового Тоффолі вимагає 2n CNOT вентилів,^[10] застосування взаємодії багатьох тіл може безпосередньої використовувати для роботи вентиль на атомах Ридберга та реалізації надпровідних ланцюгів.^[11]^[12]^[13]

Примітки

↑ Landauer, R. (July 1961). Irreversibility and Heat Generation in the Computing Process. IBM Journal of Research and Development. 5 (3): 183—191. doi:10.1147/rd.53.0183. ISSN 0018-8646.
↑ Landauer, R. (July 1961). Irreversibility and Heat Generation in the Computing Process. IBM Journal of Research and Development. 5 (3): 183—191. doi:10.1147/rd.53.0183.
↑ Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: Toffoli, Tommaso (1980). J. W. de Bakker and J. van Leeuwen (ред.). Reversible computing (PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. с. 632—644. doi:10.1007/3-540-10003-2_104. ISBN 3-540-10003-2. Архів оригіналу (PDF) за 15 квітня 2010.
↑ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (Nov 1995). Elementary gates for quantum computation. Physical Review A. American Physical Society. 52 (5): 3457—3467. arXiv:quant-ph/9503016. Bibcode:1995PhRvA..52.3457B. doi:10.1103/PhysRevA.52.3457. PMID 9912645. S2CID 8764584.
↑ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (30 липня 2013). Five two-qubit gates are necessary for implementing the Toffoli gate. Physical Review A. 88 (1): 010304. arXiv:1301.3372. Bibcode:2013PhRvA..88a0304Y. doi:10.1103/physreva.88.010304. ISSN 1050-2947. S2CID 55486826.
↑ Shi, Xiao-Feng (May 2018). Deutsch, Toffoli, and CNOT Gates via 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.
↑ Deutsch, D. (1989). Quantum Computational Networks. Proceedings of the Royal Society of London. Series A, Mathematical and Physical Sciences. 425 (1868): 73—90. Bibcode:1989RSPSA.425...73D. doi:10.1098/rspa.1989.0099. ISSN 0080-4630. JSTOR 2398494. S2CID 123073680.
↑ Shi, Yaoyun (Jan 2003). Both Toffoli and Controlled-NOT need little help to do universal quantum computation. Quantum Information & Computation. 3 (1): 84—92. arXiv:quant-ph/0205115. Bibcode:2002quant.ph..5115S.
↑ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, A. S.; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (Jan 2009). Realization of the Quantum Toffoli Gate with Trapped Ions. Physical Review Letters. American Physical Society. 102 (4): 040501. arXiv:0804.0082. Bibcode:2009PhRvL.102d0501M. doi:10.1103/PhysRevLett.102.040501. PMID 19257408. S2CID 2051775.
↑ Shende, Vivek V.; Markov, Igor L. (15 березня 2008). On the CNOT-cost of TOFFOLI gates. arXiv:0803.2316 [quant-ph].
↑ Khazali, Mohammadsadegh; Mølmer, Klaus (11 червня 2020). Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited-State Manifolds of Rydberg Atoms and Superconducting Circuits. Physical Review X (англ.). 10 (2): 021054. Bibcode:2020PhRvX..10b1054K. doi:10.1103/PhysRevX.10.021054. ISSN 2160-3308.
↑ Isenhower, L.; Saffman, M.; Mølmer, K. (4 вересня 2011). Multibit CkNOT quantum gates via Rydberg blockade. Quantum Information Processing (англ.). 10 (6): 755. arXiv:1104.3916. doi:10.1007/s11128-011-0292-4. ISSN 1573-1332. S2CID 28732092.
↑ Rasmussen, S. E.; Groenland, K.; Gerritsma, R.; Schoutens, K.; Zinner, N. T. (7 лютого 2020). Single-step implementation of high-fidelity n -bit Toffoli gates. Physical Review A. 101 (2): 022308. arXiv:1910.07548. Bibcode:2020PhRvA.101b2308R. doi:10.1103/physreva.101.022308. ISSN 2469-9926. S2CID 204744044.