Loading article…
可逆計算とは、計算過程のすべてのステップが時間的に可逆である計算モデルのことです。これは、計算の出力が与えられれば、入力を完全に復元できることを意味します。ある状態から別の状態へと決定論的に進行するシステムでは、可逆性の重要な要件は、各状態とその後の状態との間に一対一の対応関係があることです。可逆計算は、従来とは異なる計算手法と考えられており、量子力学の原理が本質的に可逆性を保証する量子計算と密接に関連しています（量子状態が測定されたり「崩壊」したりしない限り）。[ 1 ]
この目的のために特に関心のある、密接に関連した2つの主要な可逆性のタイプがあります。物理的可逆性と論理的可逆性です。[ 2 ]
物理的エントロピーの増加をもたらさないプロセスは、物理的に可逆であると言われます。つまり、等エントロピーです。この特性を理想的に示す回路設計のスタイルがあり、これは電荷回復ロジック、断熱回路、または断熱コンピューティングと呼ばれています（断熱プロセスを参照）。実際には、非定常物理プロセスが完全に物理的に可逆または等エントロピーになることはありません。しかし、システムの進化を記述する物理法則が正確にわかっている場合、未知の外部環境との相互作用から十分に隔離されたシステムでは、完全な可逆性にどれだけ近づけるかという既知の限界はありません。
可逆コンピューティングの実装を目的とした技術の研究の動機は、コンピュータの計算エネルギー効率（つまり、単位エネルギー消費あたりに実行される有用な操作）を、不可逆ビット操作あたりkT ln(2)のエネルギー消費という基本的なフォン・ノイマン・ランダウアー限界[ 3 ] [ 4 ]を超えて改善する唯一の潜在的な方法を提供すると予測されている点にある。
ランダウアー限界は、2000 年代のコンピュータのエネルギー消費量の数百万分の 1 であり、2010 年代には数千分の 1 であった。[ 5 ]可逆コンピューティングの支持者は、このエネルギー消費量の大部分はアーキテクチャのオーバーヘッドによるものだと主張している。これらのオーバーヘッドは、コンピュータを動作させるために必要な配線、トランジスタ、メモリなどのシステムの非計算部分に関連するエネルギーコストである。彼らは、可逆コンピューティングの原理を採用しない限り、現在の技術ではエネルギー効率を大幅に向上させることは難しいと考えている。[ 6 ]
IBMで働いていたRolf Landauerが最初に主張したように、[ 7 ]計算プロセスが物理的に可逆であるためには、論理的にも可逆でなければなりません。Landauerの原理は、既知のnビットの情報を無意識に消去すると、常に熱力学的エントロピーでnkT ln(2)のコストが発生するという観察です。離散的で決定論的な計算プロセスは、古い計算状態を新しい計算状態にマッピングする遷移関数が1 対 1 関数である場合、つまり出力論理状態が計算操作の入力論理状態を一意に決定する場合、論理的に可逆であると言われます。
非決定論的（確率的またはランダムという意味で）な計算プロセスでは、古い状態と新しい状態の関係は単一値関数ではなく、物理的可逆性を得るために必要な条件は、計算が進むにつれて、可能な初期計算状態のアンサンブルのサイズが平均的に減少しないという、やや弱い条件になります。
ランダウアーの原理（そして実際には熱力学第二法則）は、物理学の根底にある可逆性の直接的な論理的帰結として理解することもできる。これは、力学の一般的なハミルトニアン形式、そしてより具体的には量子力学のユニタリー時間発展演算子に反映されている。[ 8 ]
可逆コンピューティングの実装とは、所望の計算操作を実行するための機構の物理的ダイナミクスを、実行される論理演算ごとに機構の完全な物理的状態に関する不確実性の総量が無視できるほど小さくなるように、非常に正確に特性評価し制御する方法を学ぶことに相当します。言い換えれば、機械内部で計算操作を実行する際に発生するアクティブエネルギーの状態を正確に追跡し、このエネルギーの大部分が熱として散逸するのではなく、後続の操作に再利用できる組織化された形で回収されるように機械を設計することです。
この目標を達成することは、計算のための超精密な新しい物理機構の設計、製造、特性評価において大きな課題となるものの、現時点ではこの目標が最終的に達成できないと考える根本的な理由はなく、いつの日か、内部で実行する有用な論理演算ごとに、1ビット分の物理的エントロピーをはるかに下回る量（そしてkT ln 2エネルギーをはるかに下回る量の熱）しか生成しないコンピュータを構築できるようになるだろう。
今日、この分野には膨大な学術文献が存在する。物理学者、電気技師、コンピュータ科学者によって、多種多様な可逆デバイスの概念、論理ゲート、電子回路、プロセッサアーキテクチャ、プログラミング言語、およびアプリケーションアルゴリズムが設計・分析されてきた。
この研究分野では、エネルギー効率の高いクロックおよび同期機構を含む、あるいは非同期設計によってこれらの必要性を回避する、高品質でコスト効率が高く、ほぼ可逆な論理デバイス技術の詳細な開発が待たれている。可逆コンピューティングに関する膨大な理論的研究が、フォン・ノイマン・ランダウアー限界を含む、エネルギー効率に対する短期的な様々な障壁を実際のコンピュータ技術が回避できるようにするための実用的な応用を見つけるには、このような堅実な工学的進歩が必要となる。これは、熱力学第二法則により、論理的に可逆なコンピューティングを使用することによってのみ回避できる可能性がある。[ 9 ]
計算演算が論理的に可逆であるとは、演算の出力（または最終状態）が入力（または初期状態）から計算でき、その逆もまた同様であることを意味します。可逆関数は単射でなければなりません。これは、可逆ゲート（および回路、つまり複数のゲートの組み合わせ）は、一般的に入力ビット数と出力ビット数が同じであることを意味します（すべての入力ビットが演算によって消費されると仮定した場合）。
インバータ（NOT）ゲートは、元に戻すことができるため、論理的には可逆です。ただし、NOTゲートは、その実装方法によっては、物理的に可逆ではない場合があります。
排他的論理和（XOR）ゲートは、2つの入力を単一の出力から一意に復元できないため、あるいは情報消去が不可逆であるため、不可逆です。しかし、XORゲートの可逆バージョンである制御NOTゲート（CNOT）は、入力の1つを2番目の出力として保持することで定義できます。CNOTゲートの3入力バリアントはトフォリゲートと呼ばれます。これは、2つの入力a、bを保持し、3番目のcを置き換えます。。 とこれによりAND関数が得られ、これにより、NOT関数が得られます。ANDとNOTを組み合わせると機能的に完全なセットになるため、トフォリゲートは汎用的で、（十分な数の初期化された補助ビットが与えられれば）任意のブール関数を実装できます。
可逆回路、その構築と最適化、および最近の研究課題に関する調査が利用可能です。[ 10 ] [ 11 ] [ 12 ] [ 13 ] [ 14 ]
可逆チューリングマシン（RTM）は、可逆計算における基礎的なモデルです。RTMは、遷移関数が可逆であるチューリングマシンとして定義され、各マシン構成（状態とテープの内容）が最大で1つの先行構成を持つことを保証します。これにより、後方決定性が保証され、計算履歴を一意に追跡することが可能になります。[ 15 ]
RTMの正式な定義は、過去数十年にわたって進化してきました。初期の定義は可逆な遷移関数に焦点を当てていましたが、より一般的な定式化では、ステップごとに制限されたヘッド移動とセル変更が許容されます。この一般化により、RTMの集合は合成（RTMの実行）に関して閉じていることが保証されます。続いてRTMを実行する結果として新しい RTM が生成される）と反転（RTM の逆もまた RTM である）により、可逆計算のためのグループ構造が形成される。これは、合成によって同じクラスのマシンが生成されない可能性がある古典的な TM の定義とは対照的である。[ 16 ] RTM のダイナミクスは、ローカル ルールに基づいて構成をマッピングするグローバル遷移関数によって記述できる。[ 17 ]
イヴ・ルセルは1963年の論文で可逆チューリングマシンを提案したが[ 18 ] 、ランダウアーの原理を知らなかったようで、それ以上このテーマを追求せず、残りのキャリアのほとんどを民族言語学に費やした。
1973年にチャールズ・H・ベネットが行った画期的な研究により、任意の標準チューリングマシンは可逆チューリングマシンでシミュレートできることが実証された。[ 19 ]ベネットの構成では、TMに補助的な「履歴テープ」を追加する。シミュレーションは3つの段階で進行する。[ 20 ]
この構成は、RTMが計算可能な関数に関して標準的なTMと計算的に同等であることを証明しており、この点において可逆性が計算能力を制限しないことを確立している。[ 20 ]しかし、この標準的なシミュレーション手法にはコストがかかる。履歴テープは計算時間とともに線形に増加する可能性があり、潜在的に大きなスペースオーバーヘッドにつながる。これはしばしば次のように表される。どこそしては、元の計算の空間と時間です。[ 19 ]さらに、履歴ベースのアプローチは、局所的な構成性で課題に直面します。この方法を使用して独立して可逆化された 2 つの計算を組み合わせることは簡単ではありません。これは、理論的には強力であるものの、ベネットの元の構成が必ずしも可逆計算を実現するための最も実用的または効率的な方法ではないことを示しており、大量の「ガベージ」履歴の蓄積を回避する方法の探索を促しています。[ 20 ]
RTMは、単射（1対1）な計算可能な関数の集合を正確に計算します。非単射関数（本質的に情報が失われる）を直接計算できないため、古典的な意味では厳密には普遍的ではありません。しかし、「RTM普遍性」と呼ばれる普遍性の一形態を持ち、自己解釈が可能です。[ 15 ]
ロンドンを拠点とするVaire Computingは、2025年にチップのプロトタイプを作成し、2027年にリリースする予定です。[ 21 ]
独自のバッテリーを備えたコンピュータなどの閉鎖系のエントロピーは減少しないため、このエントロピーは、復元されたビットあたり 0.6931 kT の熱を周囲に供給する発熱効果として他の場所に現れる必要があります。
