過去・現在・未来

先に、数学の「複雑性理論」という分野には "Oracle（神託）" という考え方があることを紹介した。どんな問題にも、「正しい」答えをすぐに返してくれるという、架空の「全知全能」であるシステムのことだ。 ただ、まったくの「御都合主義」にも見えるそうした仮定は、実は、現代の我々の日常に深く入り込んでいる。古代ギリシャのOracleを引き合いに出さなくても、僕は、"Google" という用語を使った方がわかりやすいと思うのだが。 今回は、このOracleの少し変わったバージョンMerlinを紹介する。ランダムな振る舞いをするOracleだと思えばいい。このMerlinは「全知全能」である点は「普通」のOracleと変わりないのだが、ただ、クセがある。不誠実なのだ。人間の問いかけに、いつも「正しい」答えを返すとは限らない。ときどき、わざと間違った答えを返す。（こっちを、"Google"と呼んだ方がいいのかも） ただ、これだけだと、単なる「神頼み」にしかならないので、人間の知の数学的モデルとしてはつまらない。そこで、もう一人のAuthurが登場する。Authurは、Merlinほどの能力はないのだが、誠実である。その上、彼は、Merlinがいうことが正しいか正しくないかの判断を「正しく」行う能力は持っている。 Merlinが「数学的証明」を提供し、Authurがその証明を「検証」するというシステムがあった時、このシステムで何がわかるかを考えるのを「Merlin-Authur問題」という。 僕は、Scott Aaronsonの"Quantum Computing since Democritus"  https://goo.gl/dwjtsc  で、この問題を知ったのだが、そうでなければ、ずっと「Merlin-Authur問題」を、二人のMerlinとAuthurという名前の数学者が考えた問題だと思っていた可能性がある。（原論文は、L.Babal  "Trading group theory for randomness" https://dl.acm.org/citation.cfm?id=22192 ) 実は、Merlinは魔法使いで、Arthurは

「オラクル(神託)」は、かつてギリシャのデルファイのアポロ神殿の巫女が行った予言のこと。古代ギリシャでは、社会的に重要な意思決定は、すべてこのデルファイの神託を仰いで行われたらしい。最高位の巫女は、Phythiaという。この名前は、地球の中心に存在すると信じられていた巨大な蛇 Python に由来する。 OracleもDelphiもApolloもPythonも、IT業界では別の意味で、会社名・プロダクト名として有名なのだが、欧米人にはギリシャの古典を愛する人が、現在も（IT業界にも）存在するのだと思う。それは、かつての日本人が、中国の古典を愛していたのと同じだ。 ところで、数学にも "Oracle" という概念があるのだ。それは、どんな問題に対しても瞬時に正しい答えを返してくれるシステムを仮定して、それを Oracle という。 それは、複雑性理論の中心的なツールだ。例えば、次のように使う。 $$P^A$$ という複雑性のクラスは、クラスA-完全のOracleが与えられたときに、P(決定問題が多項式時間)で解ける問題のクラスで、$$NP^A$$は、クラスA-完全のOracleが与えられたときに、NP(yesの場合の決定問題が多項式時間）で解ける問題のクラスということにするのである。だから、$$P^{NP}$$は、NP-完全な問題へのOracleが与えられたとき、決定問題が多項式時間で解ける問題のクラスになる。 なんて勝手な想定なんだ、数学に「神託」を導入するなんてトンデモナイと思うかもしれないが、そうすることによって「複雑性の階層」に対する見通しが、とてもよくなるのだ。ここでは、そのことを詳しくは論じないが、我々の日常でも、このOracleの利用に相当することが実際にあるのである。 たとえば、Pythonでプログラムを組んでいるとしよう。数値計算にnumpyを使う時、我々は必ずしもnumpyが行っている処理の詳細を理解する必要はない。我々が、それに期待するのは、それが「正しい答え」を「確実」に返してくれることである。 数学でも同様である。数学の証明は「厳密」なことを是とするのだが、全ての証明の細部を書く必要はない。例えば、何千年前の「ピタゴラスの定理」の証明を、全ての数学的証明がくりかえす必要はないのだ。数学的に「確定」

チューリングのディジタル・アーカイーブをチェックしていたら、とてもとても面白い論文を見つけた。 "Intelligent machinery, a heretical theory" 「知的機械、ある異端的理論」 https://goo.gl/Rcwku6 有名な Mind誌に寄稿した50年の彼の論文 "COMPUTING MACHINERY AND INTELLIGENCE"  https://goo.gl/p5ttGY  のあと、51年のどこかでの講義ノートの草稿だ。 僕が驚いたのは、前半の機械による数学的証明に関する部分と、後半の機械の「教育」（かれは、"Learning"ではなく"Education"という言葉を使っている）に関する部分だ。 全然、「異端的(heretical)」でも「異教的」でもないじゃないか。現在の我々から見ると、どんぴしゃりの「正統派」の洞察である。 機械による数学的証明について、彼はいう。 「機械は、例えば、プリンキピア・マセマティカの形式的証明の妥当性をテストできるだろうし、そうした体系のある命題が証明可能か証明不可能かさえも、教えてくれるだろう。その命題が証明可能でも証明不可能でもない場合には、マシンは結果を返すことなくずっと動き続けるので、満足できる振る舞いをしないかもしれないのだが。 ... 数学者だって、フェルマーの定理が真か偽か数百年考えているのだから。」 こうした認識は、アーロンソンが、複雑性理論の嚆矢として高く評価している、1956年のゲーデルからフォン・ノイマンにあてた手紙と通底するものだ。（それについては、僕の「ナッシュとゲーデル」  https://goo.gl/vjSLx1  を読んでほしい。） もっと面白いのは、機械が間違ったことを言ってもいいという、次のような主張だ。 「私の主張は、機械たちが、人間の心の振る舞いを非常に正確にシミュレートするように構成できるということだ。機械は、時には間違いをおかすだろうし、時には、新しい面白いことをいうかもしれない。」 それは、人間だって同じだろうと彼はいう。機械が間違った証明をしても、 「そうした機械の教育は、高

10/15の「楽しい数学：計算理論入門」 http://mathnight3.peatix.com/ 　の準備で、チューリング・マシンでのプログラミングの練習をしているのだが、なかなか苦戦している。 カウンターもスタックもないし、「状態」の数をできるだけ減らそうとすると、いろいろ難しい。（でも、パズルみたいで面白い。） ・ E((()))()(())E といった、EとEとの間の括弧がバランスが取れているかをチェックせよ。（失敗） 右に進んで最初の右括弧')'を探して、他の文字'X'に置き換え、今度は左に進んで、左括弧'('を探して、それも'X'に置き換えて、また右括弧')'を探すの繰り返せばいい。状態は「右」と「左」の二つで十分。うまくいけば右のEに到達し、まずければ左のEに落ちる。 と思ったのだが、これだと、明らかにバランスが取れていない、例えば、E((((Eも、右のEに届いてしまう。右のEに届いたら、もう一度チェックが必要。状態「Check」を使えばできるのだけれど、なんとか二つの状態でできないか、思案中。 ・0と1からなる文字列の長さを計算せよ。（できた！でも、ずるい） 左から右に進んで、現れる0を全部1に置き換える。これでいい。ただし、長さは、1進数。nは、n個の1で表すことにすればいい。 ・自然数 m,n のかけ算を行え。（なんとかできるかも） これも1進数で考えれば、m個の1を、n回、右のほうにコピーしてやればいい。 まず、コピーの処理を考えたのだが（図）、状態が7つもあって気にくわない。それに、1進法のかけ算のためだけなら、0のコピーは考える必要はないしね。 問題は、「n回」コピーの部分。データ構造（というかテープの構造、工夫しないと） ・1進数を2進数に変換せよ。 これは、大昔、どっかでやり方を見た気がする。ちょっとスマートな方法があったはず。ググろう。 問題は、あと10日で、「万能チューリングマシン」にたどり着くことができるかということ。 ガンバリマス。

今回のマルレクのテーマは、「量子アルゴリズム入門」です。 https://q-algorithm.peatix.com/view メディア的には、量子コンピュータへの関心を訴求する一番大きなポイントは、Google, IBM, Microsoft をはじめとする大手ITベンダーが、50-100qubitの中規模の量子コンピュータを実際に作り上げる取り組みを精力的に進めていることが大きいかもしれません。それは、確かに重要な変化です。 ただ、現在起きている変化は、それだけではありません。量子コンピュータをハードウェアだとすると、その上で走るソフトウェアに相当する「量子アルゴリズム」の研究・開発が、爆発的に進んでいます。 90年代にショアの素因数分解のアルゴリズムが発表された時は、ハードウェアの実現の見通しとは独立に、アルゴリズムそのものに、非常に大きな関心が集まりました。むしろ、そこで膨らんだ期待が、ハードウェア上の制約で、その実現がすぐには難しいと分かった時に、量子コンピュータそのものに対する失望に変わったように思います。 冒頭にも書きましたように、量子コンピュータのデバイスとしての実現可能性をめぐる状況は、90年代とははっきり変わって来ています。それ以上に重要なことは、この分野のイノベーションは、ショアのアルゴリズムの発見がそうであったように、先行する理論的探求によってに牽引されるということです。 現在、多くの研究者を巻き込み、深い結果が出て来ている量子アルゴリズムの研究動向は、量子コンピュータの未来を占う上で、決定的と言っていい重要な意味を持っています。 今回のマルレクでは、量子アルゴリズムの「金字塔」といっていい、ショアのアルゴリズムの中核である「量子フーリア変換」のやさしい解説を行いたいと思います。この間、展開して来た「紙と鉛筆で学ぶ量子情報理論演習」の内容は、きっと役にたつと思います。 時間の最後に、現在の量子アルゴリズムの世界で、ゲート型の量子コンピュータとアニーリング型量子コンピュータをつなぐ理論としても、また、3SATのような「NP-完全問題」に対する量子コンピュータの側からの挑戦としても注目され、量子複雑性の理論にも大きな刺激を与えている、"Local Hamilt

丸山の今月の講演予定です。 10/6 「紙と鉛筆で学ぶ 量子コンピュータの基礎」 　　マイクロソフト会場　@ Microsoft 品川 　　https://quantum-basic.peatix.com/ 10/15 楽しい数学 第三夜 　「計算理論入門 --「やさしい計算」と「むずかしい計算」」 　　@ DMM 六本木一丁目 　　http://mathnight3.peatix.com/　 10/26 連続ナイトセミナー　人工知能を科学する 第二回 　「人工知能と自然言語」 　　@ 角川 市ヶ谷 　　https://lab-kadokawa70.peatix.com/ 前回のマルレク「自然言語とコンピュータ概論」の3時間バージョンです。 11/2 マルレク 第四回 　「量子アルゴリズム入門」 　　@ Microsoft 品川 マルレク第四回「量子アルゴリズム入門」の概要は、今週中にまとめますので、少しお待ちください。 当初、「拡大する量子アルゴリズム」として、前々回のマルレク第二回「量子コンピューティングの現状と課題」の資料 https://goo.gl/wgTmPV のAppendixに入れていた最近の動向を紹介するつもりでしたが、少し考えが変わりました。 来年から「紙と鉛筆で学ぶ 量子情報理論 II -- 量子アルゴリズム」というのを始めるつもりなのですが、今度のマルレクは、その入門的な概論にしようと思っています。 ショアのアルゴリズムの中核である 量子フーリエ変換の話を中心にまとめようと思っています。この間の「紙と鉛筆」のセミナーにいらした方、きっと理解できると思いますので、是非、聴きに来てください。 最後にお願いです。 10/15のDMMさんでの「楽しい数学」ですが、運営を手伝っていただけるスタッフを募集しています。無料で、この回の聴講ができます。また、希望があれば、すでに締め切っております、10/6のMicrosoftさんでの「紙と鉛筆」の聴講も可能にするようにします。 丸山まで、メッセージ、あるいはメール fujio.maruyama@gmail.com いただけますか？