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