人工知能技術の力を得た今日のコンピューターは、人間と説得力のある会話をしたり、歌を作曲したり、絵を描いたり、チェスや囲碁をしたり、病気を診断したりすることができます。これらは、その技術的優秀さのほんの一例にすぎません。
これらの成功は、計算能力に限界がないことを示唆していると言えるかもしれません。それが真実であるかどうかを確認するには、コンピューターの強力さの要因を理解することが重要です。
コンピューターの性能には2つの側面があります。ハードウェアが1秒間に実行できる演算の数と、実行するアルゴリズムの効率です。ハードウェアの速度は物理法則によって制限されます。アルゴリズム（基本的には命令の集合）は人間によって記述され、コンピューターのハードウェアが実行できる一連の演算に変換されます。たとえコンピューターの速度が物理的な限界に達したとしても、アルゴリズムの限界によって計算上のハードルは残ります。
これらのハードルには、コンピュータでは解けない問題や、理論的には解けるものの、実際には今日のコンピュータの最高性能版でさえもその能力を超えている問題が含まれます。数学者やコンピュータ科学者は、仮想のマシンで問題を試して、解けるかどうかを判断しようとします。
架空の計算機
チューリングマシンとして知られる現代的なアルゴリズムの概念は、1936年にイギリスの数学者アラン・チューリングによって提唱されました。これは、紙の上で鉛筆を使って算術計算を行う様子を模倣した架空の装置です。チューリングマシンは、今日のすべてのコンピューターの基盤となっています。
手作業で計算するとより多くの紙が必要になる計算に対応するため、チューリングマシンでは仮想的な紙の供給量が無制限であると仮定されます。これは、空白か1つの記号が書かれた正方形で構成された、仮想的な無限のリボン、つまり「テープ」に相当します。
この機械は有限の規則によって制御され、テープ上の最初の記号列から処理を開始します。機械が実行できる操作は、隣接するマスへの移動、記号の消去、空白のマスへの記号の書き込みです。機械はこれらの操作を順番に実行することで計算を行います。機械が処理を終了、つまり「停止」すると、テープ上に残っている記号が出力または結果となります。
チューリングマシンとは何ですか?
コンピューティングは、多くの場合、答えが「はい」か「いいえ」の意思決定を伴います。類推すると、医療検査（問題の一種）は、患者の検体（問題のインスタンス）が特定の疾患指標（答えが「はい」か「いいえ」）を有しているかどうかを確認します。チューリングマシンでは、このインスタンスはデジタル形式で表現され、記号の初期列となります。
チューリング マシンを設計して、肯定的か否定的かを問わずすべてのインスタンスで停止し、そのインスタンスがどの答えを生成するかを正しく判断できる場合、問題は「解決可能」であると見なされます。
すべての問題が解決できるわけではない
多くの問題はチューリングマシンで解けるため、コンピュータで解くことができますが、そうでない問題も数多くあります。例えば、1961年に中国系アメリカ人の数学者ハオ・ワンが定式化したタイル問題の一種であるドミノ問題は、チューリングマシンでは解けません。
課題は、ドミノのセットを使ってグリッド全体を覆い、ほとんどのドミノゲームのルールに従って、隣接するドミノの端の目（ピップ）の数を一致させることです。ドミノのセットから始めて、そのセットがグリッドを完全に覆うかどうかを判断できるアルゴリズムは存在しないことが判明しました。
合理的に
多くの解決可能な問題は、妥当な時間内に停止するアルゴリズムによって解決できます。これらの「多項式時間アルゴリズム」は効率的なアルゴリズムであり、コンピュータを用いてこれらの問題を解くことが現実的であることを意味します。
多項式時間アルゴリズムを発見するための継続的な努力にもかかわらず、多項式時間アルゴリズムを持つ解ける問題が他に数千個存在することが知られていない。巡回セールスマン問題もその一つである。
巡回セールスマン問題とは、グラフと呼ばれる、いくつかの点が直接接続された点の集合が、任意の点から始まり、他のすべての点をちょうど一度ずつ通過し、元の点に戻る経路を持つかどうかを問う問題です。あるセールスマンが、ある近隣地域のすべての世帯をちょうど一度ずつ通過し、出発点に戻る経路を見つけたいとします。
巡回セールスマン問題は、目的地がいくつかを超えるとすぐに手に負えなくなります。
NP完全と呼ばれるこれらの問題は、1970年代初頭にアメリカ系カナダ人のスティーブン・クックとウクライナ系アメリカ人のレオニード・レビンという2人のコンピュータ科学者によって独立して定式化され、その存在が示されました。この研究を最初に発表したクックは、この功績により、1982年にコンピュータ科学界最高のチューリング賞を受賞しました。
正確に知るためのコスト
NP完全問題に対する最もよく知られたアルゴリズムは、本質的にすべての可能な答えの中から解を探すものです。数百点のグラフ上の巡回セールスマン問題をスーパーコンピュータで実行すると何年もかかります。このようなアルゴリズムは非効率的であり、数学的な近道が存在しないことを意味します。
現実世界でこれらの問題に対処する実用的なアルゴリズムは近似値しか提供できませんが、近似値は向上しつつあります。NP完全問題を解く効率的な多項式時間アルゴリズムが存在するかどうかは、21世紀初頭にクレイ数学研究所が提起した7つのミレニアム未解決問題の一つであり、それぞれ100万ドルの賞金が設定されています。
チューリングを超えて
チューリングの枠組みを超えた新しい計算形態は存在するのでしょうか？1982年、ノーベル賞受賞者のアメリカの物理学者リチャード・ファインマンは、量子力学に基づく計算というアイデアを提唱しました。
量子コンピュータとは何ですか?
1995年、アメリカの応用数学者ピーター・ショアは、整数を多項式時間で因数分解する量子アルゴリズムを発表しました。数学者たちは、チューリングの枠組みにおける多項式時間アルゴリズムではこのアルゴリズムを解くことは不可能だと考えています。整数の因数分解とは、その整数を割り切れる1より大きい整数を見つけることを意味します。例えば、整数688,826,081は、より小さい整数25,253で割り切れます。なぜなら、688,826,081 = 25,253 x 27,277だからです。
ネットワーク通信のセキュリティ確保に広く使用されているRSAアルゴリズムと呼ばれる主要なアルゴリズムは、大きな整数の因数分解の計算上の難しさに基づいています。ショア氏の研究結果は、量子コンピューティングが実現すれば、サイバーセキュリティの状況を一変させる可能性を示唆しています。
整数の因数分解やその他の問題を解くことができる本格的な量子コンピュータは構築できるのでしょうか？ 一部の科学者はそれが可能だと考えています。世界中の複数の科学者グループが量子コンピュータの構築に取り組んでおり、すでに小規模な量子コンピュータを構築しているグループもあります。
しかし、これまでに発明されたすべての新しい技術と同様に、量子コンピューティングでも新たな制限を課す問題が必ず発生するでしょう。
Jie Wang は、マサチューセッツ大学ローウェル校のコンピュータサイエンスの教授です。
この記事はクリエイティブ・コモンズ・ライセンスに基づきThe Conversationから転載されました。元の記事はこちらです。
