フレドキンゲート
フレドキンゲート（英: Fredkin gate）は、エドワード・フレドキンが提案した可逆論理ゲートである。単独でfunctional completeness (en:Functional completeness) を有しているので、任意の論理演算をフレドキンゲートだけを使って構成できる。
基本フレドキンゲートは、3つの入力 (C, I1, I2) と3つの出力 (C, O1, O2) を写像する「制御付き交換ゲート」である。入力 C はそのまま出力 C に対応する。C = 0 の場合交換はなされず、I1 は O1 に、I2 は O2 に対応する。そうでない場合2つの出力は交換され、I1 は O2 に、I2 は O1 にマッピングされる。入力と出力を入れ替えても同じに動作することから、この回路が可逆性であることは容易に示すことができる。これをさらに一般化した n×n フレドキンゲートは、最初の n-2 個の入力をそのまま対応する出力に出力し、残る2つは最初の n-2 個の入力が全て1の場合だけ交換して出力する。
| 入力 | 出力 | ||||
|---|---|---|---|---|---|
| C | I1 | I2 | C | O1 | O2 |
| 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 | 1 | 0 |
| 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 1 |
フレドキンゲートは可逆3ビットゲートであり、最初のビットが1の場合に残る2ビットを交換して出力する。真理値表を右に示す。
0と1の個数が保存されるという便利な特性があり、ビリヤードボールモデルで入力されたボールの数と出力ボール数が同じになるのと同じである。これは物理学における質量保存の法則にもうまく対応し、このモデルが無駄ではないことを示す助けにもなっている。
XORゲートとANDゲートによる論理関数
[編集]フレドキンゲートをXORゲートとANDゲートで構成する場合、次のようになる。
- O1 = I1 XOR S
- O2 = I2 XOR S
- S = (I1 XOR I2) AND C
背景
[編集]フレドキンゲート[1] は、MITコンピュータ科学研究所の エドワード・フレドキンとトマソ・トフォリによって考案され、 可逆計算と保存論理の分野における画期的な進歩であった。 保存論理の枠組み内で開発されたこのゲートは、 計算プロセスを力学法則の可逆性やエネルギー保存則といった 根本的な物理原理に整合させるよう設計されている。 フレドキン・ゲートの技術的根拠は、非可逆操作が通常多大なエネルギー散逸を もたらす従来型計算の非効率性に対処することに根ざしている。
従来の論理ゲートは、ランダウアーの原理[2]に従い情報を消去し熱を 発生させる場合が多いが、フレドキンゲートは可逆性を維持する。 この特性により、計算過程で情報が失われることはない。 ゲートの各出力状態は入力状態を一意に決定し、 情報を保持するだけでなくエネルギー保存の法則にも沿う。 計算能力の需要が高まる中、エネルギー効率が重要な考慮事項となるため 、この特性は特に重要である。
フレドキンゲートの発明は、計算処理のエネルギー消費を最小化するという 探求から生まれた。これにより、処理速度と電力消費の効率性だけでなく、 環境持続可能性にも優れた計算システムの構築が可能となる。 可逆計算の原理を具現化したフレドキンゲートは、 デジタル計算に伴うエネルギーコスト削減への実用的な解決策を提供し、 より持続可能な計算技術への重要な転換点を示している。
関連項目
[編集]論理ゲート | |
|---|---|
| 論理ゲート | |
| 関連項目 | |
出典
[編集]- ^ Fredkin, Edward; Toffoli, Tommaso (April 1982). “Conservative logic”. International Journal of Theoretical Physics 21 (3–4): 219–253. Bibcode: 1982IJTP...21..219F. doi:10.1007/bf01857727. ISSN 0020-7748.
- ^ Landauer, R. (July 1961). [http://dx.doi.org/10.1147/rd.53.0183 “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.