マルレク「エンタングルする認識」 ダイジェスト #3

【 量子コンピュータの能力の認識 -- BQPクラス 】

先に、「人間の能力をコンピュータが超える」という「シンギュラリティ」の議論は、かなり怪しいと書きました。その大きな理由の一つは、「人間の能力」と一括りにするけど、人間の能力は非常に多様で複雑だからです。

例えば、前回の議論では、「全能者」の存在を仮定して「全能者」と「人間」の対話で認識できることを考えようというアプローチを紹介しました。そうした新しい推論方法を思いつく能力を機械が持てるかどうか、僕は懐疑的です。それにしても、そうしたアイデアやそのアプローチで得られる認識結果は、最終的には「人間の能力」に属します。

もっとも僕は、人間の数学的・論理的推論能力に関して言えば、それは機械的なモデルを持つと考えています。それは、おそらくチューリング・マシンの持つ能力に等しいと考えています。また、先日紹介したInteractive Proofのアプローチは、きちんと数学的に定義できます。

人間と機械の能力の比較は、いろいろ難しい問題があるのですが、機械と機械の能力の比較は、どちらも人間が作ったものですので、それよりは簡単にできます。この点で、近年、重要な認識が生まれています。

それは、私たちが普段使っているコンピュータの計算能力を、量子コンピュータの計算能力が上回っている認識が、理論的にだけではなく、実験的にも確立され始めているということです。

私たちが普段使っているコンピュータを「古典コンピュータ」と呼ぶことにします。今使っているものを「古典」と呼ぶのは抵抗があるかもしれませんが。どちらも人間から見れば機械です。どちらも「コンピュータ」と呼ばれます。ただその動作原理は全く異なった機械です。その違いをはっっきりさせるため、「古典」「量子」を頭につけます。

機械だけの世界に限れば、量子コンピュータの登場を、古典コンピュータに対する「シンギュラリティ」と呼ぶことは可能です。機械＝コンピュータの世界では、それは「量子優越性」と呼ばれています。

2019年の10月23日は、特別な日です。それは、Googleが、古典コンピュータに対して量子コンピュータの能力が遥かに高いこと、「量子優越性」を実験的に実証した日です。

この点については、丸山の資料「量子コンピュータの現在 — 量子優越性のマイルストーンの達成 —」https://www.marulabo.net/docs/q-supremacy/　をご覧ください。講演の要点は、手短にPodcastにまとめられています。

理論的には、量子コンピュータが古典コンピュータを上回る能力を持つことは、量子チューリングマシンの構成を通じて、1990年代に既に明らかにされていました。

古典コンピュータが多項式時間で計算可能なクラスを Pで表し、量子コンピュータが多項式時間で計算可能なクラスを BQPで表すと、PはすっぽりとBQPに含まれていることは、明らかになっていました。これは、古典コンピュータでは多項式時間では計算できないが、量子コンピュータでは多項式時間で計算できる計算が存在することを意味します。

この有名な例が、「ショアのアルゴリズム」です。ショアは、現在のコンピュータ、古典コンピュータでは解くのに膨大な時間がかかる「素因数分解」を、量子コンピュータでは、高速に計算可能するアルゴリズムを発見しました。

人間の数学的・論理的推論能力が古典的チューリングマシンの能力に等しいだろうという僕の考えは、先に書きました。それでは、量子チューリングマシンの能力は、我々の認識能力にとってどのような意味を持つのでしょうか？

詳しくは、セミナーで。