Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Вентиль Тоффолі також вентиль CCNOT у логічних схемах вентиль винайдений Томмазо Тоффолі є універсальним оборотним логіч

Вентиль Тоффолі

Вентиль Тоффолі

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

image
Позначення вентиля Тоффолі на схемі

Основи

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

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

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

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

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

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

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

Таблиця істинності Форма матриці перестановки
INPUT OUTPUT
 0   0   0   0 
0 1 0 1
1 0 1 1
1 1 1 0

image

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

Цей шлюз має 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

image

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

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

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

image
Вентиль Тоффолі може бути сконструйований з одиничних кубітних вентилів і мінімум шести вентилів CNOT.
  • Вентиль Фредкіна — це універсальний оборотний 3-бітовий вентиль, який міняє місцями два останні біти, якщо перший біт дорівнює 1; реалізує операцію керованого обміну.
  • n — бітовий вентиль Тоффолі є узагальненням вентиля Тоффолі. Це приймає n біт x1, x2, …, xn у якості входів і віддає n бітів. Перші n−1 вихідних бітів це просто x1, …, xn−1. Останній вихідний біт (x1 AND … AND xn−1) XOR xn . Вентиль Тоффолі може бути реалізовано з п'яти двохкубітних квантових вентилів.Насправді для реалізації вентиля Тоффолі потрібно мінімум п'ять двохкубітних квантових вентилів.
  • Пов'язаний з ними квантовий вентиль Дойча може бути реалізований за допомогою п'яти оптичних імпульсів з нейтральними атомами. Вентиль Дойча — це універсальний вентиль для квантових обчислень.

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

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

Примітки

  1. 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.
  2. 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.
  3. Technical Report MIT/LCS/TM-151 (1980) and an adapted and condensed version: (1980). J. W. de Bakker and (ред.). (PDF). Automata, Languages and Programming, Seventh Colloquium. Noordwijkerhout, Netherlands: Springer Verlag. с. 632—644. doi:10.1007/3-540-10003-2_104. ISBN . Архів оригіналу (PDF) за 15 квітня 2010.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Shi, Yaoyun (Jan 2003). Both Toffoli and Controlled-NOT need little help to do universal quantum computation. . 3 (1): 84—92. arXiv:quant-ph/0205115. Bibcode:2002quant.ph..5115S.
  9. 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.
  10. Shende, Vivek V.; Markov, Igor L. (15 березня 2008). On the CNOT-cost of TOFFOLI gates. arXiv:0803.2316 [quant-ph].
  11. 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.
  12. 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.
  13. 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.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Ventil Toffoli takozh ventil CCNOT u logichnih shemah ventil vinajdenij Tommazo Toffoli ye universalnim oborotnim logichnim ventilem sho oznachaye sho bud yaka oborotna shema mozhe buti pobudovana z ventiliv Toffoli Vin takozh vidomij yak ventil kontrolovane kontrolovane NE yakij opisuye jogo diyu Vin maye 3 bitovi vhodi ta vihodi yaksho pershi dva biti vstanovleni v 1 vin invertuye tretij bit inakshe vsi biti zalishayutsya nezminnimi Poznachennya ventilya Toffoli na shemiOsnoviLogichnij ventil L ye oborotnim yaksho dlya bud yakogo vihodu y isnuye unikalnij vhid x takij sho vikonuyetsya L x y Yaksho ventil L ye oborotnim isnuye zvorotnij ventil L yakij vidobrazhaye y v x de L y x Iz zagalnoprijnyatih logichnih vhodiv ventil NE ye oborotnim yak ce vidno z tablici istinnosti nizhche VHID VIHID 0 1 1 0 Odnak u zagalnomu vipadku ventil I ne ye oborotnim Vhodi 00 01 i 10 vidobrazhayutsya na vihodi v 0 Oborotni ventili vivchali z 1960 h rokiv Pochatkovoyu motivaciyeyu bulo te sho oborotni ventili rozsiyuyut menshe tepla abo v principi ne rozsiyuyut tepla Yaksho rozglyanuti logichnij ventil yak shos sho spozhivaye podane na vhid informaciya vtrachayetsya oskilki na vihodi nayavno menshe informaciyi nizh na vhodi Cherez cyu vtratu informaciyi vtrachayetsya energiya do navkolishnogo seredovisha u viglyadi tepla cherez termodinamichnu entropiyu Inshim sposobom zrozumiti ce ye te sho zaryadi v lancyuzi stikayut na zemlyu zabirayuchi z soboyu neveliku kilkist energiyi koli voni zminyuyut stan Oborotnij ventil lishe peremishuye stani i oskilki informaciya ne vtrachayetsya energiya zberigayetsya Bilsh nedavnya motivaciya pohodit vid kvantovih obchislen Kvantova mehanika vimagaye shob peretvorennya buli oborotnimi i dozvolyaye bilsh zagalni obchislennya nizh klasichni komp yuteri princip superpoziciyi Universalnist i ventil ToffoliBud yakij oborotnij ventil yakij spozhivaye svoyi vhidni dani ta dozvolyaye vsi vhidni obchislennya povinen mati ne bilshe vhidnih bitiv nizh vihidni biti za principom Dirihle Dlya odnogo vhidnogo bita isnuye dva mozhlivih oborotnih ventilya Odin z nih NE Inshij ventil identichnosti yakij vidobrazhaye svoyi vhidni dani u vihidni dani bez zmin Dlya dvoh vhidnih bitiv yedinim netrivialnim ventilem ye ventil kontrolovane NE yakij vikonuye operaciyu Viklyuchne ABO pershogo bita i drugogo bita i zalishaye pershij bit nezminnim Tablicya istinnosti Forma matrici perestanovki INPUT OUTPUT 0 0 0 0 0 1 0 1 1 0 1 1 1 1 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 displaystyle begin bmatrix 1 amp 0 amp 0 amp 0 0 amp 1 amp 0 amp 0 0 amp 0 amp 0 amp 1 0 amp 0 amp 1 amp 0 end bmatrix Na zhal ye oborotni funkciyi yaki nemozhlivo obchisliti vikoristovuyuchi lishe ci ventili Inshimi slovami nabir sho skladayetsya z ventiliv NOT i XOR ne ye universalnim Shob obchisliti dovilnu funkciyu za dopomogoyu oborotnih ventiliv nam potriben inshij ventil Odnim z mozhlivih ye ventil Toffoli zaproponovanij Toffoli v 1980 roci Cej shlyuz maye 3 bitovi vhid ta vihid Yaksho vstanovleno pershi dva biti vin zminyuye na protilezhne znachennya tretij bit Dali navedena tablicya vhidnih i vihidnih bitiv Tablicya istinnosti Forma matrici perestanovki 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 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 displaystyle begin bmatrix 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 0 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 amp 0 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 amp 0 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 amp 0 0 amp 0 amp 0 amp 0 amp 0 amp 1 amp 0 amp 0 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 1 0 amp 0 amp 0 amp 0 amp 0 amp 0 amp 1 amp 0 end bmatrix Ce takozh mozhna opisati yak vidobrazhennya bitiv a b c v a b c XOR a AND b Ventil Toffoli universalnij ce oznachaye sho dlya bud yakoyi bulevoyi funkciyi f x1 x2 xm isnuye lancyug sho skladayetsya z ventiliv Toffoli yakij prijmaye x1 x2 xm ta deyaki dodatkovi biti yaki mayut znachennya 0 abo 1 dlya vihodiv x1 x2 xm f x1 x2 xm a takozh dodatkovi biti sho nazivayutsya smittyevimi Po suti ce oznachaye sho mozhna vikoristovuvati ventil Toffoli dlya pobudovi sistem yaki oborotno vikonuvatimut obchislennya bud yakoyi bazhanoyi bulevoyi funkciyi Pov yazani logichni ventiliVentil Toffoli mozhe buti skonstrujovanij z odinichnih kubitnih ventiliv i minimum shesti ventiliv CNOT Ventil Fredkina ce universalnij oborotnij 3 bitovij ventil yakij minyaye miscyami dva ostanni biti yaksho pershij bit dorivnyuye 1 realizuye operaciyu kerovanogo obminu n bitovij ventil Toffoli ye uzagalnennyam ventilya Toffoli Ce prijmaye n bit x1 x2 xn u yakosti vhodiv i viddaye n bitiv Pershi n 1 vihidnih bitiv ce prosto x1 xn 1 Ostannij vihidnij bit x1 AND AND xn 1 XOR xn Ventil Toffoli mozhe buti realizovano z p yati dvohkubitnih kvantovih ventiliv Naspravdi dlya realizaciyi ventilya Toffoli potribno minimum p yat dvohkubitnih kvantovih ventiliv Pov yazanij z nimi kvantovij ventil Dojcha mozhe buti realizovanij za dopomogoyu p yati optichnih impulsiv z nejtralnimi atomami Ventil Dojcha ce universalnij ventil dlya kvantovih obchislen Vidnoshennya do kvantovih obchislenBud yaki oborotni ventili mozhut buti realizovani na kvantovomu komp yuteri otzhe ventil Toffoli takozh ye kvantovim operatorom Odnak ventil Toffoli ne mozhe buti vikoristanij dlya universalnih kvantovih obchislen hocha ce oznachaye sho kvantovij komp yuter mozhe realizuvati vsi mozhlivi klasichni obchislennya Ventil Toffoli povinen buti realizovanij razom z deyakimi po suti kvantovimi ventilyami shob buti universalnim dlya kvantovih obchislen Naspravdi dostatno bud yakogo odinochnogo kubita z realnimi koeficiyentami yakij mozhe stvoriti netrivialnij kvantovij stan Ventil Toffoli na osnovi kvantovoyi mehaniki buv uspishno realizovanij v sichni 2009 roku v Universiteti Insbruka Avstriya Hocha realizaciya n kubitovogo Toffoli vimagaye 2n CNOT ventiliv zastosuvannya vzayemodiyi bagatoh til mozhe bezposerednoyi vikoristovuvati dlya roboti ventil na atomah Ridberga ta realizaciyi nadprovidnih lancyugiv PrimitkiLandauer 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 1980 J W de Bakker and red PDF Automata Languages and Programming Seventh Colloquium Noordwijkerhout Netherlands Springer Verlag s 632 644 doi 10 1007 3 540 10003 2 104 ISBN 3 540 10003 2 Arhiv originalu PDF za 15 kvitnya 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 lipnya 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 3 1 84 92 arXiv quant ph 0205115 Bibcode 2002quant ph 5115S Monz T Kim K Hansel 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 bereznya 2008 On the CNOT cost of TOFFOLI gates arXiv 0803 2316 quant ph Khazali Mohammadsadegh Molmer Klaus 11 chervnya 2020 Fast Multiqubit Gates by Adiabatic Evolution in Interacting Excited State Manifolds of Rydberg Atoms and Superconducting Circuits Physical Review X angl 10 2 021054 Bibcode 2020PhRvX 10b1054K doi 10 1103 PhysRevX 10 021054 ISSN 2160 3308 Isenhower L Saffman M Molmer K 4 veresnya 2011 Multibit CkNOT quantum gates via Rydberg blockade Quantum Information Processing angl 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 lyutogo 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

Дата публікації:
Топ