アナログコンピュータ用の数学的解法を開発、ノートルダム大：デジタルの限界に挑む

米ノートルダム大学などの研究チームが、デジタルコンピュータでは手に負えないNP困難問題について、最適解を発見する可能性があるアナログコンピュータ向けの解法を開発した。

[＠IT]

　米ノートルダム大学は2018年12月11日（米国時間）、同大学物理学部教授で、コンピュータ科学工学部併任教授のゾルタン・トロツカイ氏らの研究チームが、デジタルの枠組みを超えてコンピュテーションを進化させる新しい数学的アプローチの開発に取り組んでいることを明らかにした。

ゾルタン・トロツカイ氏（出典：ノートルダム大）

　2018年11月に「Nature Communications」で発表された同チームの最新の論文は、「NP困難問題」の最適解を発見できる可能性がある新しい数学的なアナログ“解法”を解説している。論文では充足最大化問題（MaxSAT問題）を扱った。

　NP困難とは、計算量理論で定義されている用語で、ある問題を解くためにどの程度の計算能力が必要なのかを指す用語。NP困難な問題では、必要な計算量が問題の規模に比例せず、指数関数的に増えてしまう。例えば問題の規模が100倍に拡大すると、必要な計算時間が100倍ではなく、2の100乗倍に増えてしまう。

　このような問題は世の中にありふれている。情報科学の教科書にある「巡回セールスマン問題」や「ナップサック問題」に限らず、例えばある種のスケジューリングやタンパク質の折りたたみ、バイオインフォマティクス、医療画像処理、ASIC（Application Specific Integrated Circuit）の回路設計などに関連するさまざまな問題がNP困難であり、実用的な規模の問題を解こうとしても既知の方法では、最適解を求めるまでに時間がかかりすぎてしまう。

　このような計算に適した手法として量子コンピュータが挙げられているものの、アナログコンピュータにも未来があるとした。

　研究チームは開発した手法を各種のNP困難問題でテストし、デジタルコンピュータを用いた場合よりもより優れた解に到達できる可能性があるという結論に達した。さらに解の算出に必要な時間が、デジタルコンピュータよりも短い可能性もあるという。

アナログコンピュータの課題とは

　アナログコンピュータは、20世紀初頭から半ばにかけて、潮の干満の予測や兵器の誘導、NASAの最初のロケット打ち上げなどに使用された。当初は歯車と真空管、後にトランジスタを使用し、変数をアナログの電圧で表すといった方法で、数学的な関数を直接実行し、ブラウン管上の波形や紙に出力するグラフとして瞬時に正しい答えを出すように作られていた。

　アナログコンピュータの課題は物理的にかさばるために扱いにくい上、ノイズ（信号の乱れ）に影響されやすく、問題に応じて回路などの構成を変更しなければならなかったことだ。そのため、1960年代以降、デジタルコンピュータに取って代わられた。

　その後、デジタルコンピュータの性能が現在の規模まで拡大しても、多くの変数を持つNP困難問題を解決できる性能には至っていない上に、成長の限界も見えてきている。そこで研究チームは、アナログコンピュータの復権というアイデアに至った。

　しかし、現在のアナログコンピュータには「アルゴリズム」という課題がある。アルゴリズム開発の長い歴史を持つデジタルコンピュータとは異なり、アナログコンピュータのアルゴリズムは、そうした知識ベースの蓄積がなく、設計が非常に難しい。実際に研究チームのアプローチは、デジタルコンピュータで使われるタイプのアルゴリズムとはあらゆる面で異なっている。

　今回の論文では数学的なアプローチに限って、アナログコンピュータの可能性を論じている。研究チームの次のステップは、新しいアプローチに基づくアナログコンピュータを設計、構築することだ。このコンピュータは、特定のタスクを想定したものだ。ノートルダム大学工学部で学際的な取り組みとして構築作業が行われる予定だ。

　「（新方式のアナログコンピュータの試作に当たって）現時点では主に、疑似容量やノイズ管理の改善など、解決すべき工学上の問題が残っている。だが、解決は可能だろう」（トロツカイ氏）