フレドキン門

フレドキン ゲート(制御スワップ ゲート、保守的論理ゲートとも呼ばれる) は、エドワード フレドキンが発明した可逆コンピューティングに適した計算回路です。このゲートは汎用性があり、あらゆる論理演算や算術演算をフレドキン ゲートだけで構成できます。フレドキン ゲートは、3 つの入力と 3 つの出力を持つ回路またはデバイスで、最初のビットを変更せずに送信し、最初のビットが 1 の場合に限り、最後の 2 ビットを入れ替えます。

MITコンピュータサイエンス研究所のエドワード・フレドキンとトマソ・トフォリによって概念化されたフレドキンゲート^[1]は、可逆コンピューティングと保守的論理の分野における極めて重要な進歩を表しています。保守的論理の枠組み内で開発されたこのゲートは、力学法則の可逆性やエネルギー保存などの基本的な物理原理にコンピューティングプロセスを合わせるように設計されています。フレドキンゲートの技術的根拠は、不可逆な操作が通常、大幅なエネルギー消費につながる従来のコンピューティングの非効率性に対処することに根ざしています。

従来の論理ゲートは、多くの場合、ランダウアーの原理に従って情報を消去し、熱を発散しますが、^[2]フレドキンゲートは可逆性を維持します。可逆性は、計算プロセス中に情報が失われないことを保証する特性です。ゲートの各出力状態は、その入力状態を一意に決定します。これにより、情報が保存されるだけでなく、エネルギー保存の原則にも適合します。この特性は、計算能力の需要が増大するにつれて特に重要になり、エネルギー効率が重要な考慮事項になります。

Fredkin ゲートの発明は、計算処理のエネルギー フットプリントを最小限に抑えるという探求から生まれました。これにより、処理速度と電力消費の点で効率的であるだけでなく、環境的に持続可能なコンピューティング システムの構築が可能になります。可逆コンピューティングの原理を具体化することにより、Fredkin ゲートはデジタル計算に関連するエネルギー コストを削減する実用的なソリューションを提供し、より持続可能なコンピューティング テクノロジーへの大きな転換を示しています。

基本的なフレドキンゲート^[3]は、 3 つの入力( C、I ₁、I ₂ )を 3 つの出力( C、O ₁、O ₂ )にマッピングする制御 スワップゲート(CSWA​​P ゲート)です。C入力はC出力に直接マッピングされます。C = 0 の場合、スワップは実行されません。I _1はO ₁に、I _{2 は}O ₂にマッピングされます。 それ以外の場合は、2 つの出力がスワップされ、I _1はO ₂に、I _{2 は}O ₁にマッピングされます。 この回路は可逆的、つまり逆方向に実行すると「元に戻る」ことが簡単にわかります。 一般化されたn  ×  nフレドキンゲートは、最初のn − 2 入力を変更せずに対応する出力に渡し、最初のn − 2 入力がすべて 1 の 場合にのみ、最後の 2 つの出力をスワップします 。

• 制御 SWAP ロジック: 3 ビットの制御 SWAP ゲートである Fredkin ゲートは、制御ビットの状態に基づいて 2 つのターゲット ビットを条件付きでスワップすることによって動作します。制御ビットが 1 の場合、ゲートはターゲット ビットを交換します。0 の場合、ビットは変更されずに通過します。

• 可逆コンピューティング: ゲートは可逆的であるため、計算中に情報が失われることはありません。この特性は、データを保持し、エネルギーの散逸を減らすという保守的な論理の原則と一致しています。これは物理学における質量保存則とよく一致しており、モデルが無駄ではないことを示すのに役立ちます。

Fredkin ゲートは、次のようにAND、OR、XOR、NOTを使用した真理関数を使用して定義できます。

O ₁ = I ₁ XOR S、

O ₂ = I ₂ XOR S、

C_出力= C_入力、

ここで、S = ( I ₁ XOR I ₂ ) AND Cです。

あるいは:

O ₁ = ( CかつI ₁ではない) または ( CかつI ₂ )、

O ₂ = ( CかつI ₁ ) または ( CかつI ₂でない)、

C_出力= C_入力。

Fredkin ゲートが普遍的であることを確認する 1 つの方法は、AND、NOT、OR を実装するために使用できることを観察することです。

I ₂ = 0の場合、O ₂ = CかつI ₁です。

I ₂ = 1の場合、O ₁ = C OR I ₁です。

I ₁ = 0かつI ₂ = 1の場合、O ₂ = NOT Cとなります。

真理値表は、Verilog などのハードウェア記述言語でエンコードできます。

モジュールfredkin_gate (入力u 、入力x1 、入力x2 、出力v 、出力y1 、出力y2 );常に@( * )開始v = u ; y1 = ( ~ u & x1 ) | ( u & x2 ); y2 = ( u & x1 ) | ( ~ u & x2 );終了endmodule  
      
      
  
      
            
            

5 つの Fredkin ゲートを使用した3 ビットの全加算器(キャリー付き加算)。「ガベージ」出力ビットgは、r = 0の場合は( p NOR q )、r = 1の場合は( p NAND q )になります。

左側の入力 (2 つの定数を含む) は 3 つのゲートを通過して、パリティをすばやく決定します。0 ビットと 1 ビットは、設定された入力ビットごとに入れ替わり、4 行目にパリティ ビット、5 行目にパリティの反転が生成されます。

次に、パリティ ビットが設定されている場合はキャリー行と逆パリティ行が入れ替わり、pまたはq入力ビットのいずれかが設定されている場合は再度入れ替わり (どちらが使用されるかは関係ありません)、結果のキャリー出力が 3 行目に表示されます。

p入力とq入力はゲート制御としてのみ使用されるため、出力には変更されずに表示されます。

最近の研究では、プログラム可能なシリコンフォトニックチップ上でフレドキンゲートが実証されています。これらのチップは、マッハツェンダー干渉計のネットワークを使用して光子を効率的にルーティングし、複数の量子ゲートを処理できる多用途でスケーラブルなプラットフォームを作成します。このアプローチにより、フレドキンゲートを大規模な量子プロセッサに統合できるようになり、将来の量子コンピューティングの進歩への道が開かれます。^[4]

フォトニックセットアップでは、フレドキンゲートは効果的な制御されたSWAPメカニズムとして機能し、ターゲット量子ビットの条件付きスワップを可能にします。これは、量子通信やその他のプロトコルにとって非常に重要な、忠実度の高いグリーンバーガー・ホーン・ツァイリンガー（GHZ）状態を生成する際に特に役立ちます。したがって、このゲートは、効率的な条件付き操作を必要とする量子プロトコルに強力なツールを提供します。^[5]

フレドキンゲートの制御された操作により、リソースを大量に消費する量子状態トモグラフィーを必要とせずに量子状態間の重なりを推定することができます。これにより、効率と精度が最も重要となる量子通信、測定、暗号化に特に役立ちます。^[5]

2016年3月25日、グリフィス大学とクイーンズランド大学の研究者らは、光の粒子の量子もつれを利用して量子ビットを交換する量子フレドキンゲートを開発したと発表した。量子フレドキンゲートが利用可能になれば、量子コンピュータの構築が容易になるかもしれない。^{[5] [6]}

• 量子コンピューティング
• 量子ゲート
  • 量子回路
• 量子プログラミング
• Toffoli ゲートは、 controlled-controlled-NOT ゲートです。

• Fredkin, Edward ; Toffoli, Tommaso (1982). 「保守的論理」(PDF) . International Journal of Theoretical Physics . 21 (3–4): 219–253. Bibcode :1982IJTP...21..219F. doi :10.1007/BF01857727. S2CID 37305161. 2006年10月17日時点の オリジナル(PDF)からアーカイブ。