エントロピーと計算の複雑さ

研究者は、消去ビットがエネルギーを消費しなければならないことを示していますが、計算複雑度$
F(n)$のアルゴリズムのエネルギー消費の平均を調べた研究はありますか?私は、計算上の複雑さ$
F(n)$がエネルギーの平均消費量に相関していると考えています。

ベストアンサー

はい、しかし、これまでの仕事のほとんど(最近は下記を参照)は、不可逆的な計算を可逆的なものに変えることに集中しており、それによってエントロピーの生成を避けることを望んでいます。
(注:計算を実行するために必要な energy と、計算によって生成され、通常は熱の形で環境に放出される
entropy 。)

LandauerとBennettの元々の分析によれば、いくつかの研究者が$ kT
ln(2)$エントロピーを作成する必要があります(以下、怖い引用符がある理由を参照)。
1つの研究では、可逆的なチューリングマシンをリバーシブルなものでシミュレートすることが提案されていましたが、これはエントロピーが発生しないことを示唆していました。非可逆TMを可逆的なものでシミュレートする方法のための時空トレードオフを示すいくつかの研究がある。

最近になって、

デメイン、リンチ、ミラノ、およびティアギ。 エネルギー効率のよいアルゴリズム、2016。

部分的に可逆的なアルゴリズムを研究しました。つまり、エントロピーを支払う場合、標準的なアルゴリズムタスクのために、上記の不可逆性から可逆性の一般的なシミュレーションを改善することができます。リバーシブルコンピューティングは、それに専念する研究者コミュニティ全体を持っています。これは10年目になる
Reversible Computing カンファレンスです。

実際、長い間、LandauerとBennettには、計算不可逆性とエントロピー生成との関係が、タグラインによって示唆されているよりも微妙であることが知られています。ビットを消去すると、
ln(2)$エントロピー。しかし、過去20年ほどの間、非平衡統計力学は、この微妙な関係が、エントロピー差のみならずKLの相違をも含む正確な数値方程式によって取り込まれるという点にまで進んでいる。

Kolchinsky & Wolpert, Dependence of dissipation on the initial distribution
over states
. J. Stat. Mech. 2017 (arXiv
link
)

(およびその中の参考文献)。

我々は、サンタフェ研究所でワークショップを開催しました
2017年8月には(いくつかの研究者の名前を見て関連性のあるタイトルを見ることができます)、物理学と熱力学的計算の複雑さの両方で全く新しい一連の質問が提起されます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です