過去・現在・未来

【 ショアのアルゴリズムと量子計算複雑性 】　 1990年代に入って、「対話型証明 = Interactive Proof」の導入によって、証明の概念が大きく変わったことは前回述べました。 1990年代、計算複雑性の世界では、対話型証明と並んでもう一つの大きな前進がありました。それは、1980年代にファインマンらによって始まった量子コンピュータ研究の流れの中で、計算複雑性の概念が、量子コンピュータの計算複雑性に拡大されたことです。 1993年、ベルンシュタインとヴァジラーニは、量子チューリング・マシンの上に、量子チューリング・マシンが多項式時間で計算可能な複雑性のクラス BQPを定義し、それがチューリング・マシンが多項式時間で計算可能な複雑性のクラスPを完全に包摂することを発見します。 古典的なコンピュータが多項式時間では計算できない問題が、量子コンピュータでは多項式時間で計算できる可能性があることが、複雑性理論の言葉で示されたのです。 1994年、ショアは驚くべき発表を行います。コンピュータでは多項式時間では解くことが難しいと考えられていた「素因数分解問題」を、量子コンピュータでは多項式時間で解くことができることを彼は見出したのです。「ショアのアルゴリズム」の発見です。 ショアのアルゴリズムの発見は、量子コンピュータの世界だけでなく、さまざまな分野の多くの人に強烈な影響を与えました。 量子コンピュータの研究に多くの人が加わるようになりました。素因数分解の困難さを、暗号の安全性の基礎に置いていた暗号技術も深刻な反省を迫られることになりました。その余波は、今も続いています。 理論的には、ショアのアルゴリズムは、ヴァジラーニたちが示した、複雑性クラスPの外側にあり（古典コンピュータでは多項式時間では計算できない）、かつ複雑性クラスBQPの内側にある（量子コンピュータでは多項式時間で計算できる）計算の実例を与えるものでした。 計算複雑性の研究も、ヴァジラーニのBQP、ショアのアルゴリズムの発見に大きな刺激を受けます。こうして、1970年代、クック、レビン、カープらによって始められた計算複雑性理論は、1990年代、対話型証明と量子複雑性を中心に、大きく変貌することになります。  -------------------------------- 「複雑性の新しいクラスBQPの

【 証明と検証 -- 証明とは何か？ 】 ここまで、2019年のGoogleの「量子優越性」の実証実験、1982年のファインマンの自然をシミレートする量子コンピュータのアイデア、1964年の自然の非局所性を示す「ベルの定理」と、時間を遡ってきましたが、ここから、時間を普通の流れに戻します。 ファインマンの提唱で量子コンピュータの取り組みがはじまった1982年は、アスペたちが「ベルの定理」の実証実験に成功した年でもあります。この1982年をターニング・ポイントとして、現代科学を捉えるのは、面白いかもしれません。 前回、物理学の理論は、基本的には、実験によって検証されることが求められるということと、ただ、物理学の理論を実験で検証するのは、なかなか難しくなっているという話をしました。 確かに、実験による検証を、物理理論の正しさの要件にする必要はないという考えはあり得うるかもしれません。それは、「物理学の数学化」と言っていい考えなのですが、数学的な正しさ、体系性のある理論、「美しい理論」は多くの人を惹きつけるものです。 ただ、ここでは、逆の話をしたいと思います。数学の「正しさ」についての考え方も大きく変わってきていると言う話です。1990年代に入って、数学的証明についての考え方に大きな転換が起きます。"Interactive Proof" 「対話型証明」の登場です。 Interactive Proofの特徴は、「証明者」と「検証者」を分離し、証明を 「証明者」と「検証者」の両者の「対話」の過程として捉え返すことです。 証明は、もともとが正しい推論によって導かれているから正しいのだと考えることと、正しいと検証されるから正しい証明だと考えることは別のことです。Interactive Proofのアプローチでは、正しいと検証されたものが正しい証明であるとされます。 物理理論が実験による検証が必要であるように、数学もそれが正しいことを示すためには、検証というプロセスが必要だと言うことです。 さらに興味深いことは、こうしたアプローチでは、これまで決定論的に進行すると思われていた「数学的証明」は、非決定論的で確率的な性格を帯びることになります。非決定論的で確率的！　これは古典論的な物理学に対する量子論的な物理学の特徴と同じものです。 「物理の数学化」だけをみている

【 証明と実験 】 物理では、有名な実験がたくさんあります。ノーベル物理学賞の多くは、そうした実験に与えられています。最近ですと、LIGOでの重力波の検出、CERNの加速器LHCでのヒッグス粒子の検出等が有名です。今回取り上げるベルの定理とアスペによる実験での検証も、その一つです。 物理学の理論は、「基本的には」実験によって検証されることが求められます。 理論と実験とは、二つの異なるプロセスです。物理学が、この二つのプロセスを要求していることは、実験を必要としない数学との大きな違いです。数学にとって必要なことは、実験ではなく証明です。 ただそのことは、実験で検証されていない理論が、物理学的には正しい理論とは認められないことを意味しません。 重力波やブラックホールの存在は、近年まで実験的には検証されたわけではありませんでした。そのことを理由に、それらの存在を予見したアインシュタインの重力理論は正しいとは認められないという科学者はいないと思います。 事実、現在多くの物理学者が正しいと信じている物理理論、たとえば超弦理論は、実験によって検証されているわけでは必ずしもありません。 理論と実験による検証との間に、こうしたズレが起きるのには、いくつかの理由があります。 一つには、正しい物理理論がすぐに実験によってその正しさが検証されるとは限らないからです。 今回の例でいえば、アインシュタインがエンタングルメントを発見したのは1935年。ベルが理論的にエンタングルメントの実在性を示したのは 1964年。30年近くかかっています。ただ、ベルが示したのは、それは理論的な証明でした。 アスペが実験でそれを検証したのは 1982年。ベルの定理から20年近く、アインシュタインらのEPR論文からは、50年近くかかっています。（一般に広く知られるようになったのは、多分、2022年のノーベル賞からです。） 理論と実験による検証にずれが生ずるもう一つの理由があります。それは、検証実験に膨大なエネルギーを必要として、既存の技術では実験装置自体、構築できない理論も存在するからです。 20世紀の量子論の集大成である素粒子の「標準モデル」の最後のピースであるヒッグス粒子が21世紀に検出されたのは、CERNの加速器の能力がこの粒子を検出できるまで拡大・増強されたからに他なりません。（あるいは、到達可能なエネ

 【 ちょうど、40年前を振り返る 】 今回のセミナーの「量子計算の古典的検証」と言うテーマは、新しい、というか、歴史的に形成されたものです。 そのルーツは、「量子的に計算する機械 ＝ 量子コンピュータ」を人間が作り始めたことにあります。量子コンピュータが存在しなければ、その出力を検証しようと言う問題意識が生まれる訳ありませんからね。 今回のセッションは、前回のセッションが取り上げたGoogle-IBM論争の「3年前」より、すこし歴史を遡ります。量子コンピュータのルーツである、ちょうど「40年前」のファインマンの論文を取り上げます。 「40年前」というのは、時期的には、アスぺやクラウザーたちが、ベルの定理の実証実験で成果を上げた時期です。今回のノーベル賞受賞の対象になった研究です。 ファインマンとクラウザーには接点があるようです。「量子論の基礎を研究したい」という若いクラウザーに、ファインマンは、「そんなの時間の無駄だ。量子論はもう完成している。そんなことより、もっときちんと計算しろ。」と言ったそうです。多分、60年代か70年代のことだと思います。 （ノーベル賞受賞後のインタビューで、クラウザーはそんなことを語っていたのですが、今見に行ったら、そんな発言はきれいに削除されていました。魚拓とっとけばよかった。） とまれ、このファインマンの40年前の論文は、とても重要なものです。 彼の主張の力点は、古典的なコンピュータでは、量子の世界、ひいては自然のシミレーションなぞ出来はしないということに置かれています。 注意してほしいのは、彼のいう「古典的コンピュータ」の能力の理解は、正確なものだということです。それは、セル・オートマトンや「万能チューリングマシン」の能力に等しいことを、彼はよく理解していました。 そうだとしたら、量子コンピュータが可能にするものから、我々は何を学ぶことができるのでしょう？　それは、今回のセミナーの「量子計算の古典的検証」という問題に直結します。 この疑問に答えるために、もう少しだけ歴史を遡りたいと思います。次回のセッションは、ベルやアスぺやクラウザーの問題意識を取り上げます。 -------------------------- 「ファインマンの洞察」を公開しました。 https://youtu.be/KH0mm79fMqk?list=PLQIrJ

【 3年前の10月に起きたことを振り返る 】 11月のセミナーでは、量子コンピュータの計算の正しさを、古典コンピュータ（現在の、普通のコンピュータのこと）で検証できるのかという、「量子計算の古典的検証」問題を取り上げます。 これがどういう問題かを示すために、今回は、ちょうど3年前の2019年の10月に起きた、「量子超越性」をめぐるGoogleとIBMの論争を、改めて紹介しようとおもいます。 2019年の10月、Googleは量子コンピュータの歴史のマイルストーンとも言うべき重要な論文を発表をします。それは、普通のコンピュータなら一万年かかる計算を量子コンピュータは3分で行うことができたとして、「量子超越性」を実証的に示すことが出来たと言うものでした。 それに対して、IBMは、現存のスーパーコンピュータを使えばその計算は一万年ではなく二日半で終わるとして、Googleの実験は「量子超越性」を実証したものとは言えないと反論しました。 この論争は、量子コンピュータの行う計算を古典的な手段で検証することの難しさを表しています。注意してほしいのは、この論争でGoogleもIBMも、「一万年」「二日半」というコンピュータでの計算を実際に行ったわけではないと言うことです。 「「量子超越性」をめぐる論争」を公開しました。 https://youtu.be/6C3ML6NoKC8?list=PLQIrJ0f9gMcOQHQ6KmWuUxuRZkHT-2gZ- スライドのpdf https://drive.google.com/file/d/1LhXVnbJXSGZU3cgTzTbxz2TDPRrVBUwR/view?usp=sharing blog：「3年前の10月に起きたことを振り返る 」　 https://maruyama097.blogspot.com/2022/11/310.html まとめページ「量子計算の古典的検証 」 https://www.marulabo.net/docs/cvqc/ 参考資料「量子コンピュータの現在 -- 量子優越性のマイルストーンの達成 --」 https://www.marulabo.net/docs/q-supremacy/

【 7/30 マルレク 「並列・分散アルゴリズムの基礎」講演ビデオ公開 】 MatuLaboでは、開催したセミナーの講演ビデオを公開しています。 今回は、7月30日に開催されたマルレク「並列・分散アルゴリズムの基礎」の公開です。 ---------------------------- このセミナーには、大きく二つの目的があります。 第一は、「排他制御 Mutual Exclusion 」「生産者・消費者同期 Producer-Consumer Synchronization 」といった基本的な並列アルゴリズムを、改めて学ぶことです。 これらのアルゴリズムは、1960年代の半ばにダイクストラらによって定式化されたもので、計算科学のいわば「古典」と言ってもいいものです。 ただ、こうした知識が、現代では不要になったわけではありません。 セミナーの第二の目的は、こうした並列・分散アルゴリズムの基礎理論が、現代ではどのように捉え返され新しい理論化がなされているのか、その一端を紹介することです。 ---------------------------- 次が、講演ビデオの再生リストのURLです。 https://www.youtube.com/watch?v=BS0UByMriBM&list=PLQIrJ0f9gMcOxhU_wwXXGuExXdLqRKuWP この再生リストは、次の四つのビデオを含んでいます。 ● 並列・分散アルゴリズムの基礎 (1) 排他制御 ダイクストラ https://youtu.be/BS0UByMriBM?list=PLQIrJ0f9gMcOxhU_wwXXGuExXdLqRKuWP ● 並列・分散アルゴリズムの基礎 (2) 排他制御 ランポート https://youtu.be/LnVpLb2WFI8?list=PLQIrJ0f9gMcOxhU_wwXXGuExXdLqRKuWP ● 並列・分散アルゴリズムの基礎 (3) 生産者消費者同期 https://youtu.be/EwZsNCYsFow?list=PLQIrJ0f9gMcOxhU_wwXXGuExXdLqRKuWP ● 並列・分散アルゴリズムの基礎 (4) アルゴリズムの正しさへのアプローチ https://youtu.be/Qg9FzNcTC78?list=PLQIrJ0f9g

【 ベルの定理のブルース 】 面倒な話が続いたので、今回は、休憩です。 1990年の1月に、ベルはCERNで "Indeterminism and non locality 非決定論と非局所性"という講演をします。ビデオが残っています。 https://www.youtube.com/watch?v=3l9HtG-VZCU&t=1909s   　遠隔作用がないという立場をとれば、決定論になる。 　ただ、決定論の立場をとれば、遠隔作用が出てくる。 ベルが発見したのは、簡単にいうとそういうことなのですが、それがミュージシャンを刺激して「ベルの定理のブルース」という曲ができたと、講演の中で楽譜と歌詞の一部紹介しています。 (  https://quantumtantra.tumblr.com/post/101941768645/bells-theorem-blues-doctor-bell-say-we  から曲が聞けます。) 　Doctor Bell say we connected 　He call me on the phone 　Doctor Bell say united 　He call me on the phone 　But if we really together, baby 　How come I feel so all alone? 　ドクターベルは、私たちはつながっているという 　彼も、電話をかけてきてそういう 　ドクターベルは私たちは一体だという 　彼も、電話をかけてきてそういう 　でも、私たちが本当に一緒なら、あなた 　どうして、私はいつも一人だと感じるの？ 　It’s so easy to forget you 　Last night I did it fifty times 　And I never think about you 　Except from nine to nine 　Since we got tangled up in quantum honey 　Can’t get that sweet thing off my mind. 　あなたを忘れるのは簡単なこと 　昨日の夜は、50回もそうした 　あなたのことなど考えもしない 　9時から9時までの時間以外は 　私たちは、量子のよ