Loading article…
論理回路において、トマソ・トフォリが発明したトフォリゲートは、 CCNOTゲート（「制御-制御-非」）としても知られ、2つの制御量子ビットと1つのターゲット量子ビットを持つCNOTゲートです。つまり、1番目と2番目の量子ビットが両方とも1の場合、ターゲット量子ビット（3番目の量子ビット）は反転されます。これは普遍的な可逆論理ゲートであり、つまり、あらゆる古典的な可逆回路はトフォリゲートから構築できます。
真理値表と行列は次のとおりです。
背景
入力消費論理ゲート L は、次の条件を満たす場合可逆的です: (1) L ( x ) = yは、任意の出力yに対して一意の入力xが存在するゲートです。 (2) すべてのyに対してy をxにマッピングするゲートL´ ( y ) = xが存在する場合、ゲートL は可逆的です。
可逆論理ゲートの例としてはNOTがあり、これは以下の真理値表で説明できます。
入力 00、01、10 はすべて出力 0 にマッピングされるため、 共通ANDゲートは可逆ではありません。
可逆ゲートは1960年代から研究されてきました。当初の目的は、可逆ゲートは熱をあまり放散しない（または原理的に熱を放散しない）ということでした。[1]
より最近の動機は量子コンピューティングから来ています。量子力学では、量子状態はシュレーディンガー方程式（ユニタリー変換）またはその崩壊の2つの方法で進化します。トフォリゲートがその一例である量子コンピューターの論理演算はユニタリー変換であり、したがって可逆的に進化します。[2]
ハードウェアの説明
古典的な Toffoli ゲートは、Verilog などのハードウェア記述言語で実装されます。
モジュールtoffoli_gate (入力u1 、入力u2 、入力in 、出力v1 、出力v2 、出力out );常に@( * )で開始v1 = u1 ; v2 = u2 ; out = in ^ ( u1 && u2 );終了endmodule
普遍性とトフォリゲート
入力を消費し、すべての入力計算を許可する可逆ゲートは、ピジョンホール原理により、入力ビット数が出力ビット数を超えてはなりません。 入力ビットが 1 つの場合、2 つの可逆ゲートが考えられます。 1 つは NOT です。 もう 1 つは、入力を変更せずに出力にマッピングするアイデンティティ ゲートです。 入力ビットが 2 つの場合、唯一の非自明なゲートは制御 NOT ゲート(CNOT) です。これは、最初のビットを 2 番目のビットにXOR し、最初のビットを変更せずに残します。
残念ながら、これらのゲートだけでは計算できない可逆関数があります。たとえば、ANDはこれらのゲートでは実現できません。言い換えると、NOTゲートとXORゲートからなるセットは普遍的ではありません。可逆ゲートを使用して任意の関数を計算するために、1980年にToffoliによって提案されたToffoliゲートは確かに目的を達成できます。[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]
Toffoli ゲートはユニバーサルです。つまり、任意のブール関数 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 ) といくつかの追加ビット (ガベージと呼ばれる) を出力する Toffoli ゲートで構成された回路があります。たとえば、NOT ゲートは、3 つの入力ビットを { a 、 1 、 1 } に設定して、3 番目の出力ビット (1 XOR ( a AND 1)) = NOT aにすることで、Toffoli ゲートから構築できます。つまり、( a AND b ) は、{ a、b 、 0 }からの 3 番目の出力ビットです。基本的に、これは、Toffoli ゲートを使用して、任意のブール関数の計算を可逆的に実行するシステムを構築できることを意味します 。
関連する論理ゲート
- Fredkin ゲートは、最初のビットが 1 の場合に最後の 2 ビットを交換する、制御されたスワップ操作を行う、汎用的な可逆 3 ビット ゲートです。
- nビットの Toffoli ゲートは、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です。
- トフォリゲートは5つの2量子 ビット量子ゲートで実現できるが[ 5]、5つ未満では実現できないことが示されている[6] 。
- もう一つのユニバーサルゲートであるドイッチゲートは、中性原子を含む5つの光パルスによって実現できます。[7]ドイッチゲートは量子コンピューティングのためのユニバーサルゲートです。[8]
- マーゴラスゲート（ノーマン・マーゴラスにちなんで名付けられた）は簡易トフォリとも呼ばれ、トフォリゲートに非常に似ているが、対角線に−1がある：RCCX = diag(1, 1, 1, 1, 1, −1, X )。マーゴラスゲートは可逆回路にも普遍的で、トフォリゲートと非常によく似た動作をするが、トフォリゲートに比べてCNOTの約半分で構成できるという利点がある。[9]
- iToffoliゲートは、非可換操作を同時に適用することにより、ペアワイズ結合を備えた超伝導量子ビットに実装されました。[10]
量子コンピューティングとの関係
任意の可逆ゲートは量子コンピュータに実装できるため、トフォリゲートは量子演算子でもあります。ただし、トフォリゲートは、量子コンピュータがすべての可能な古典的計算を実装できることを意味しますが、汎用的な量子計算には使用できません。トフォリゲートは、量子計算に汎用的であるためには、いくつかの本質的に量子ゲートとともに実装される必要があります。実際、非自明な量子状態を作成できる実係数を持つ単一量子ビットゲートであれば十分です。[11]量子力学 に基づくトフォリゲートは、2009年1月にオーストリアのインスブルック大学で実現されました。[12]回路モデルによるn量子ビットのトフォリの実装には2 n CNOTゲートが必要ですが、[13]最もよく知られている上限は6 n − 12 CNOTゲートです。[14]トラップされたイオン量子コンピュータは、 n量子ビットのトフォリゲートを直接実装できる可能性があることが示唆されています。[15]多体相互作用の応用は、トラップされたイオン、リュードベリ原子、超伝導回路実装におけるゲートの直接操作に使用できる。[16] [17] [18] [19] [20] [21]暗状態多様体に従って、Khazali-Mølmer C n -NOTゲート[17]は、回路モデルのパラダイムから逸脱し、わずか3つのパルスで動作する。iToffoliゲートは、ペアワイズ結合を備えた3つの超伝導量子ビットを使用して1つのステップで実装された。[22]
参照
参考文献
- ^ Landauer, R. (1961 年 7 月)。 「コンピューティング プロセスにおける不可逆性と熱生成」。IBM Journal of Research and Development。5 (3): 183–191。doi :10.1147/rd.53.0183。ISSN 0018-8646 。
- ^ コリン・P・ウィリアムズ (2011).量子コンピューティングの探究.シュプリンガー. pp. 25–29, 61. ISBN 978-1-84628-887-6。
- ^ 技術レポート MIT/LCS/TM-151 (1980) および適応および要約版: Toffoli, Tommaso (1980)。 JW de Bakker およびJ. van Leeuwen (編)。可逆コンピューティング(PDF)。オートマトン、言語とプログラミング、第 7 回コロキウム。オランダ、ノールドワイケルハウト: Springer Verlag。 632–644ページ。土井：10.1007/3-540-10003-2_104。ISBN 3-540-10003-22010年4月15日時点のオリジナル（PDF）よりアーカイブ。
- ^ ニールセン、マイケル L.、チュアン、アイザック L. (2010)。量子計算と量子情報(第 10 版)。ケンブリッジ大学出版局。p. 29。ISBN 9781107002173。
- ^ Barenco, Adriano; Bennett, Charles H.; Cleve, Richard; DiVincenzo, David P.; Margolus, Norman; Shor, Peter ; Sleator, Tycho; Smolin, John A.; Weinfurter, Harald (1995 年 11 月). 「量子計算のための基本ゲート」. 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.
- ^ Yu, Nengkun; Duan, Runyao; Ying, Mingsheng (2013-07-30). 「Toffoli ゲートを実装するには 5 つの 2 量子ビット ゲートが必要です」. 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 (2018年5月). 「Deutsch、Toffoli、CNOTゲートによる中性原子のRydberg遮断」. Physical Review Applied . 9 (5): 051001. arXiv : 1710.01859 . Bibcode :2018PhRvP...9e1001S. doi :10.1103/PhysRevApplied.9.051001. S2CID 118909059.
- ^ Deutsch, D. (1989). 「量子計算ネットワーク」. 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.
- ^ Maslov, Dmitri (2016-02-10). 「相対位相トフォリゲートを使用する利点と多重制御トフォリ最適化への応用」. Physical Review A . 93 (2): 022311. arXiv : 1508.03273 . Bibcode :2016PhRvA..93b2311M. doi : 10.1103/PhysRevA.93.022311 . ISSN 2469-9926.
- ^ Kim, Y.; Morvan, A.; Nguyen, LB; Naik, RK; Jünger, C.; Chen, L.; Kreikebaum, JM; Santiago, DI; Siddiqi, I. (2022年5月2日). 「固定周波数超伝導量子ビットのための高精度3量子ビットiToffoliゲート」. Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Bibcode :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
- ^ Shi, Yaoyun (2003 年 1 月). 「Toffoli と Controlled-NOT はどちらも、普遍的な量子計算を行うためにほとんど助けを必要としません」. Quantum Information & Computation . 3 (1): 84–92. arXiv : quant-ph/0205115 . Bibcode :2002quant.ph..5115S. doi :10.26421/QIC3.1-7.
- ^ Monz, T.; Kim, K.; Hänsel, W.; Riebe, M.; Villar, AS; Schindler, P.; Chwalla, M.; Hennrich, M.; Blatt, R. (2009 年 1 月). 「トラップされたイオンによる量子トフォリゲートの実現」. Physical Review Letters . 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. (2008-03-15). 「TOFFOLI ゲートの CNOT コストについて」. arXiv : 0803.2316 [quant-ph].
- ^ Maslov, Dmitri (2016). 「相対位相トフォリゲートを使用する利点と多重制御トフォリ最適化への応用」. Physical Review A. 93 ( 2): 022311. arXiv : 1508.03273 . Bibcode :2016PhRvA..93b2311M. doi :10.1103/PhysRevA.93.022311. S2CID 5226873.
- ^ 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.
- ^ アリアス・エスピノーザ、フアン・ディエゴ;グローンランド、コーエン。マッツァンティ、マッテオ。スハウテンス、カレリャン。ゲリツマ、ルネ (2021-05-28)。 「トラップされたイオンにおけるシングルステップNビット Toffoli ゲートの高忠実度手法」。物理的レビュー A . 103 (5): 052437.arXiv : 2010.08490。ビブコード:2021PhRvA.103e2437E。土井：10.1103/PhysRevA.103.052437。S2CID 223953418。
- ^ 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.
- ^ Isenhower, L.; Saffman, M.; Mølmer, K. (2011-09-04). 「Rydberg ブロッケードによるマルチビット CkNOT 量子ゲート」.量子情報処理. 10 (6): 755. arXiv : 1104.3916 . doi :10.1007/s11128-011-0292-4. ISSN 1573-1332. S2CID 28732092.
- ^ Rasmussen, SE; Groenland, K.; Gerritsma, R.; Schoutens, K.; Zinner, NT (2020-02-07). 「高忠実度nビットToffoliゲートのシングルステップ実装」. Physical Review A . 101 (2): 022308. arXiv : 1910.07548 . Bibcode :2020PhRvA.101b2308R. doi :10.1103/physreva.101.022308. ISSN 2469-9926. S2CID 204744044.
- ^ Nguyen, LB; Kim, Y.; Hashim, A.; Goss, N.; Marinelli, B.; Bhandari, B.; Das, D.; Naik, RK; Kreikebaum, JM; Jordan, A.; Santiago, DI; Siddiqi, I. (2024年1月16日). 「フロケ量子ビット間のプログラム可能なハイゼンベルグ相互作用」. Nature Physics . 20 (1): 240–246. arXiv : 2211.10383 . Bibcode :2024NatPh..20..240N. doi : 10.1038/s41567-023-02326-7 .
- ^ Nguyen, Long B.; Goss, Noah; Siva, Karthik; Kim, Yosep; Younis, Ed; Qing, Bingcheng; Hashim, Akel; Santiago, David I.; Siddiqi, Irfan (2024). 「デュアルボゾンラダーを横断することで量子ビットベースの量子プロセッサを強化する」Nature Communications . 15. arXiv : 2312.17741 . doi :10.1038/s41467-024-51434-2.
- ^ Kim, Y.; Morvan, A.; Nguyen, LB; Naik, RK; Jünger, C.; Chen, L.; Kreikebaum, JM; Santiago, DI; Siddiqi, I. (2022年5月2日). 「固定周波数超伝導量子ビットのための高精度3量子ビットiToffoliゲート」. Nature Physics . 18 (5): 783–788. arXiv : 2108.10288 . Bibcode :2022NatPh..18..783K. doi : 10.1038/s41567-022-01590-3 .
外部リンク
- Wolfram デモンストレーション プロジェクトにおけるマルチ量子ビット設定での CNOT と Toffoli ゲート。