過去・現在・未来

認識の客体としての「エンタングルする自然」の理解の進行と、認識の主体としての人間の認識能力の深化は、お互いに絡み合っていますが、相対的には独立の過程です。4月のセミナー「エンタングルする認識」では、後者に焦点を当てようと思います。 【エンタングルメントの実在の認識 -- CHSHゲーム】 「それは馬鹿げた遠隔作用だ。」 アインシュタインは、エンタングルメントのことをそう呼びました。確かにそれは、二つの量子がどんなに離れていても、片方の量子の状態を観測すると他方の量子の状態が瞬時に分かる現象のように見えます。 それは、アインシュタインが特殊相対論で確立した、ある事象の影響は光のスピードを上限としてしか他の事象に影響を及ぼさないという「事象の局所性」に反しているように見えます。物理的な「因果関係」は、局所的な性質を持ちます。 物理的な「実験」では、単純化していうと、実験の対象と観測機器と観測者の知覚が、すべて物理的な因果関係のチェーンで結ばれたされたシステムを構成しています。 それでは、そうした局所的な因果関係を破るエンタングルメントのような現象の実在は、どのような「実験的」手段で確かめることができるのでしょうか？　それは、物理的な因果関係に従わない「テレパシー」の存在を、物理的な因果関係に従う実験で証明しようというのに似ていないでしょうか？  ちなみに、こうした理論化は、1960年代になされたものですが、21世紀に入って、Interactive Proofの流れの中で再評価が行われ、次の認識の飛躍 MIP*=RE を準備することになりました。 詳しくは、セミナーで。 --------------------------------------------- 0または1を入力X,Yとして受け取り、0または1を出力A,Bとして吐き出す箱があるとしましょう。内部の仕掛けはわからないブラックボックスです。 ブラックボックスだとしても、入力と出力を観察すれば、両者の「相関 C」は知ることができます。入力と出力の「相関 C」は、入力X, Yが与えられた時の出力A, Bの条件付き確率で与えられます。C = P(A, B | X, Y) です。 今、ブラックボックスの入力 X, Yと出力 A, B が、ある関係 D(X,Y,A,B)=1を満たす時、青いランプがついて...

 【 3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #4 】 【「時空」を生み出す「原理」としてのエンタングルメント 】 アインシュタインは、量子論の中に二つの量子の奇妙なもつれあった関係が存在することを発見して、それを「パラドックス」として提示しました。三人の著者 Einstein, Podolsky, Rosenの頭文字をとって、「EPR論文」と呼ばれます。1935年の5月のことです。 二ヶ月後の7月に、アインシュタインはローゼンとともに、"The Particle Problem in the General Theory of Relativity" 「相対性の一般理論における粒子の問題」という論文を公開します。この論文を「ER論文」と呼びます。   このER論文は、二つのブラックホールを結ぶ「橋」が存在しうることを指摘した論文です。この「橋」は、"Einstein-Rosen Bridge" と呼ばれ、別名「ワームホール」とも呼ばれます。 アインシュタインは、1935年に、「エンタングルメント」（ただし、パラドックスとして）と「ワームホール」を発見しているのです。同時期にアインシュタインによってなされた、この二つの発見に何か関連があるのでしょうか？　 本来は、80年前になされるべきこうした問いかけを、現代に蘇らせたのは、あのマルデセーナとブラックホール／量子重力の専門家のサスキンドでした。 2013年の論文で、二人は、1935年にアインシュタインが発見した「エンタングルメント」と二つのブラックホールを結ぶ「ワームホール」は、スケールが全く違うのですが、同じものだという大胆な仮説を提示します。 「二つのブラックホールの間のワームホールは、二つのブラックホールのエンタングルメントによって生成される。」 時空の性質を記述する相対論（重力理論）と量子の世界を記述する場の量子論に「対応」が存在することをマルデセーナが発見したことは、既に述べました。ただ、その対応が、具体的にどんなものかについては、述べてきませんでした。 マルデセーナとサスキンドの主張は、AdS/CFT対応のもとで、相対論に現れる二つのブラックホールを結びつけるワームホールと、量子論に現れる二つの量子のエンタングルメントは、「対応...

【エンタングルメントのエントロピー】 マルデセーナの量子論と相対論（重力理論）の「対応」の発見をきっかけに、エンタングルメントの理解は、飛躍的に深まります。 突破口を開いたのは、二人の日本人、笠真生と高柳匡です。 「「時空」が、二つの部分 AとBに別れているとする。AとBの「境界部分」は、「時空」の「境界」なので、マルデセーナの理論にしたがって量子論で記述できるはず。」 「やってみたら、この「境界」は、なんと、量子論の「エンタングルメント」のエントロピーに対応するんだ！」 彼らは、「エンタングルメント」がエントロピーを持つことの、最初の発見者となります。（2006年） 先にマルデセーナの時空の「境界」の重要性の発見は、「再発見」かもしれないと書いたのですが、それには訳があります。時計を50年ほど巻き戻します。 ブラックホールは、観測可能な物理量としては、質量・電荷・角運動量の三つしか持たないと信じられてきました。ブラックホールは、極めて単純な構造の存在で、上の三つの物理量でその特徴を完全に記述できると。それを、物理学者のウィーラーは、「ブラックホールには毛がない」と表現しました。（「毛は、三本しかない」という意味です） 1973年、ベッケンシュタインは、これを覆す発見をします。彼は、ブラックホールが、先の三つの物理量の他に、エントロピー を持つこと、しかも、そのエントロピーが、ブラックホールの「地平」の表面積に比例することを見出します。 ブラックホールの「地平」とは、その一線を超えると、なにものも（光でさえ！）ブラックホールから脱出できなくなる、ブラックホールを周辺の時空とをへだてる「境界」のことです。 通常、ある空間のエントロピーは、その空間の体積に比例します。ブラックホールのエントロピーが、ブラックホールの体積（質量と言ってもいいです）ではなく、その地平の面積に比例すると言うのは、少し意外に思われるかもしれません。こうしたタイプの物理法則を「エリア則に従う」といいます。 笠-高柳によるエンタングルメントがエントロピーを持つことの発見は、このベッケンシュタインのブラックホールがエントロピーを持つことの発見に匹敵する重要な発見です。 笠-高柳の発見に刺激されて、ラムズダンクが続きます。彼は、こう考えます。（2010年） 「二つの時空 A, B があったとする。二...

【3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #2 】 量子論と相対論の「対応」の発見 エンタングルメントの発見をきっかけとした、アインシュタインの量子論批判と、ベルによるそれへの反論、量子論の擁護を見てきました。 ただ、こうした「論争」が、20世紀の科学の主要な関心事だったわけではありません。極微な世界を記述する量子力学と巨大な時空を記述する重力の理論である相対論という二つの物理学理論は、それぞれの領域で、大きな成功をおさめてきました。我々の物質・生命・宇宙に対する理解は、20世紀をつうじて飛躍的に進みました。 ただ、それぞれ異なる理論体系に基づく物理学が二つあるというのは、奇妙なことです。少なくない物理学者が、「これこそが、物理学の中心問題だ」と信じて、量子論と相対論を一つの物理学に「統一」する課題に取り組んできました。ただ、それは、20世紀には成功することはありませんでした。 20世紀も終わりの1997年、マルデセーナは21世紀の物理学の扉を開く重要な発見をします。 それは、d+1次元の時空を記述する重力理論AdS(Anti-de Sitter Space)と、d次元の場の量子理論CFT(Conformal Field Theory)が「対応」していることの発見です。この対応を「AdS/CFT対応」と言います。 この「対応」では、重力理論が d+1次元で量子論がd次元ですので、相対論（重力理論）と量子論の次元が一つずれていることに注意してください。スープの入った缶詰で例えて言えば、相対論は缶のない中身のスープの理論で、量子論はスープのないスープをつつむ缶の理論だと言うことです。 このことは、20世紀の多くの物理学者の努力にもかかわらず、相対論と量子論の「統一」の試みが成功しなかった理由を、ある意味で説明します。二つの理論は、棲んでいる世界の次元が違うのです。ブリキの缶の外側をいくらなぞっても、スープのことはわからないし、逆に、いくらスープを舐めても、缶のことはわからないのと同じです。 それにもかかわらず、重要なことは、二つの理論には「対応」が存在すると言うことです。 マルデセーナの発見は、「スープと缶は、無関係ではなく関係がある。」ということでした。「缶を調べれば、スープのことがわかり、スープを調べれば缶のことがわかる！」 ...

【3/27 「楽しい科学」ダイジェスト -- エンタングルメントをめぐるドラマ #1】 科学の世界は、いろいろなドラマに溢れています。 今回の 3/27「楽しい科学」では、「エンタングルメント」を舞台にしたドラマを紹介したいと思います。https://science-entanglement.peatix.com/ ------------------------------------------------------------ 最初の登場人物はアインシュタインです。彼は、量子論では、二つの量子がもつれあう奇妙な状態が現れることを発見します。1935年のことです。その現象に「エンタングルメント」という名前をつけたのは、シュレディンガーだと言われています。 アインシュタインは、もつれあう量子は強く関連した性質を持ち、一方の性質は他方の性質から簡単に決定できること、そのうえ、こうしたもつれあいは、二つの量子の距離に依存しないことに気付きます。 このことは、二つの量子がどんなに離れていても、一方の量子の状態を観測すれば、テレパシーのように、他方の量子の状態が分かることを意味します。「そんな馬鹿なことはありえない。それだと、光のスピードを超えて情報が伝わることになるじゃないか。」 彼は、量子論が不完全な理論であることを示す「パラドックス」として、「エンタングルメント」を提示したのです。ところが、ボーアをはじめとする量子論の陣営は、このアインシュタインの「量子論批判」を、事実上、無視します。 アインシュタインの「神はサイコロをふらない」という言葉がしめすように、彼は最後まで、量子論に懐疑的であったと言われています。 エンタングルメントをめぐるドラマで、アインシュタインに次ぐ重要な役割を演じる第二の登場人物は、ジョン・ベルです。彼と彼の業績が、多くの人にはあまり知られていないのは、とても残念なことです。 ベルは、アインシュタインらが量子論の不完全さを解決するものとして推進した「隠れた変数」理論を、理論的に否定することに成功します。しかも、自然が、「隠れた変数」理論という古典論に従うか、あるいはエンタングルメントを含む量子論に従うかは、実験的に検証できると指摘します。 事実、アスペたちは、1982年、ベルの主張が正しいことを実験で実証します。ここに、アインシュタインの発見か...

コロナの年、何をしてきたかまとめてみました。 毎月一回のペースでセミナーを開催しました。 3月以降のセミナーは、全てオンラインでした。 YouTubeの利用を拡大しました。 MaruLabo Top Page    (MaruLaboサイト) Maruyama Lectures 　(YouTubeサイト) 21/02/26 マルゼミ「 チューリングマシンの拡大と複雑性理論 」 20/01/29 マルレク基礎「 チューリングマシンを学ぼう！ 」 20/12/25 マルゼミ「 MIP*=RE入門 」 20/11/27 マルレク「 コンピュータサイエンスの現在 — MIP*=RE定理とは何か 」 20/10/15 マルレク「 量子コンピュータ入門 — 量子コンピュータと人工知能 」 20/09/18 マルレク「 人工知能と計算科学 」 20/08/28 マルゼミ「 量子通信入門 」 20/08/18 公開資料 「 MIP*=RE References 」 20/07/26 マルレク基礎「 エンタングルメントで理解する量子の世界 」 20/06/30 楽しい数学　「 2のn乗の話（チューリングマシンの話） 」 20/06/20 マルレク基礎「 ケット|k> で理解する量子の世界 」 20/05/15 マルレク基礎「 たとえ話で理解する量子の世界 」 20/05/05 マルレク「 AWSでの形式手法の利用 」 20/03/27 マルゼミ「 論理学入門 II — ラムダ計算と関数型言語 」  20/02/17 マルレク「 量子コンピュータの現在 — 量子優越性のマイルストーンの達成 」 20/01/28 マルゼミ「 論理学入門 I 」 19/11/28 マルレク「I T技術とCoqの世界 –証明 = プログラム = 計算の意味を考える 」 19/11/07 ハンズオン「 はじめてのCoq 」

先に見てきたのは、図の左側の n-exponential な時間で「検証可能」な複雑性を考えて、複雑性概念を拡張すると、ついには、「帰納的可算」のクラスに至るという話である。 n-exponential な数は、たとえそれがどんなに巨大なものであっても、有限な自然数であることに変わりはない。ただ、その有限の「無限」な連鎖の果てに、良く定義されたある意味自然な概念が、改めて、たち現れるのだ。 振り返ってみよう。 我々は、無限のものを認識できない。まず、認識の対象を形式的に有限な手段で定義可能なものに限る。「帰納的可算」というのは、そうした概念である。ただ、そこには、キチンと定義はできても、計算不可能だったり証明できないものが含まれる。 それで、「帰納的可算」の概念に手を入れ、キチンと定義され、かつ、計算可能なもの・証明可能なものを「帰納的」なものとして再定義する。「チューリング・マシンで実効的に計算可能なものが、計算可能である。」という「チャーチ・チューリングのテーゼ」は「計算可能性理論」（それは、「計算不可能性理論」でもあるのだが）の、ある意味、完成形である。 ただ、この「チャーチ・チューリングのテーゼ」の定義に従えば、「計算可能」であるはずなのだが、現実的には、どうしても計算できないものがたくさんあることに気付く。こうした実際には手に負えないものを、現実的に計算可能なものとを区別しようという動きが生まれる。「計算複雑性」の理論誕生の背景は、そうしたものだと思う。 こうして、「多項式時間」で計算できるものと、「多項式時間」では計算できないものとを区別しようという一つの基準が導入される。この基準は、ある意味合理的なものであった。1970年代に登場した複雑性理論は、コンピュータ・サイエンスの中心分野の一つとして発展し、成功する。それはいいことだ。 ただ、悪いニュースもある。いつの間にか、計算を科学する様々な分野に、次のような考えが生まれてくる。それは、もとの「チャーチ・チューリングのテーゼ」を修正した、「チューリング・マシンで多項式時間で計算可能なものが、計算可能である。」という考えが、「計算可能性」の定義として広まりはじめたことだ。それを「拡大されたチャーチ・チューリングのテーゼ」という。 「拡大されたチャーチ・チューリングのテーゼ」が、おそらく「誤り」であるだろうと...

前回、次のような、二つの対をなす複雑性のクラスを三つほど見てきた。  1.   NP        \(O(3^n)\)の証明時間               P         \(O(n)\)の検証時間   2.  NEXP     \(O(3^{2^n})\)の証明時間         EXP      \(O(2^n)\)の検証時間   3.  NEEXP   \(O(3^{2^{2^n}})\)の証明時間         EEXP    \(O(2^{2^n})\)の検証時間  一つ確認しておきたいのは、2番目の NEXPクラスは、NPクラスではないということである。NPクラスは、証明のの検証が多項式時間で終わるクラスのことだが、このNEXPクラスは、検証に指数関数的時間を要するクラスである。多項式時間では、このクラスの検証は終わらない。 同様に、3番目のNEEXPクラスは、NPクラスでもNEXPクラスでもない。それは、証明の検証に、はるかに長い時間を必要とする、それらよりずっと複雑なクラスである。 形から見れば、NP, NEXP, NEEXP, ...という延長上に、NEEEXPなり NEEEEXP ... といった複雑性クラスを考えることができそうである。また、それは、大きな認識の飛躍のようにも思えないかもしれない。 結果的には、確かにそうなのだが、そうしたアイデアは複雑性理論の中で、最初から「自然」に生まれたものではないことには注意が必要である。そのことは、複雑性理論の歴史を振り返ればわかる。 歴史的には、1番目の NPクラスとNP-完全の概念の定式化は、1971年の CookとLevinに遡る。この間紹介してきた「グラフの3色塗り分け問題」がNP-完全であることを示したのはKarpで1972年のことだ。197...

n個の頂点を持つグラフが3色で塗り分けられるかという問題は、代表的なNP-完全問題である。n個の頂点が3色に塗られたグラフは、\(3^n\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、容易ではない。この問題への答えが「YES」であることを示すこと、すなわち、このグラフが3色の塗り分けを持つことを「証明」するのは「むずかしい」。 ただ、その「証明」は、「これがこのグラフの3色の塗り分けだ」という形をしているはずである。こうした「証明」が与えられた時、その「証明」が「正しい」か否かの「検証」は、n個の頂点が「塗り分け」の条件を満たしているかのチェックで、多項式時間で可能である。その「検証」は、元のNP問題より「やさしい」問題で、多項式時間のクラスPに属する。 こうした、PとNPの関係を拡張して、次のようなクラスを考えることができる。 \(2^n\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考える。\(2^n\)個の頂点が3色に塗られたグラフは、\(3^{2^n}\)個存在する。それらのグラフの中から「塗り分け」の条件を満たすグラフを探すのは、もちろん容易ではない。この問題の複雑性クラスをNEXPと呼ぶ。 なぜ、NEXP（それは"N+EXP"だ）という名前がつくかは、次のように考えればいい。この問題が「YES」という解を持つなら、「これがこのグラフの3色の塗り分けだ」という「証明」を持つ。この「証明」が正しいことの「検証」は、\(2^n\)個の頂点を一つづつ調べて、それが「塗り分け」の条件を満たしているかチェックすればいい。 それは、\(3^{2^n}\)個のグラフを検索することの「むずかしさ」とくらべれば、\(2^n\)個の頂点のチェックは、はるかに「やさしい」ことだ。この「検証」の複雑性は、\(2^n\) すなわち、EXP(指数関数的時間の複雑性)に属することになる。 もちろん、EXPクラスは、けっして「やさしい」クラスではない。それは、PやNPよりもずっと複雑なクラスである。それにもかかわらず、NEXPクラスの「むずかしさ」と比べると、EXPクラスはずっと「やさしい」クラスなのだ。 同様に、\(2^{2^n}\)個の頂点を持つグラフが3色で塗り分けられるかという問題を考え、その複雑性NEEXPを考え...

 【 グラフの３色塗り分け問題 】 先に「リーマン予想」と等価な「グラフの３色塗り分け問題」があると書いたのだが、グラフの問題に置き換えたからといって、問題がやさしくなるわけではないことを、確認しておこう。 グラフの頂点を、{r(赤) , g(緑) , b(青) }の三色で塗る場合の数がいくつあるかを考えよう。 頂点の数が1つの場合には、{r}, {g}, {b}の 3通り、 頂点の数が2つの場合には、{rr}, {gg}, {bb}, {rg}, {gr}, {gb}, {bg}, {rb}, {br} の 9通り. 一般に頂点の数がn個の場合には、\(3^n\) 通りになる。 頂点の数が20個で頂点が3色に塗られたグラフの数は、\(3^{20}\)である。一つのグラフを見つけるのに1nano秒かかるとしてこの操作は、多分、数秒で終わるだろう。 nが大きくなるにつれて、この\(3^n\)は急速に増大する。n=30となると、\(3^{30}\)という数のグラフを枚挙する操作は、\(3^{30}\) nano秒の時間を要する。それは現在の宇宙が生まれてから現在までの時間の100倍以上の時間が必要になる。 n=30程度であっても、総当たりで、三色グラフを全部数え上げるのは、ほぼ、不可能だ。（「リーマン予想」を表現するグラフが、頂点数が30程度ということはないだろう。） ただ、n個の頂点を持つグラフを3色で「塗り分けろ」というのは、同じ色を持つ頂点は辺で結ばれていてはいけないということだ。 だから、もし、誰かが頂点数30のグラフの「3色塗り分け」を与えたとしよう。この時、この「3色塗り分け」が「正しい塗り分け」になっているかの「検証」は、30個の頂点について、その頂点と辺で結ばれている隣り合う頂点が違う色であることをチェックすれば、簡単に終わる。 一般に、n個の頂点からなるグラフでは、一つの頂点に対して、辺で結ばれた頂点は多くてもn-1個しかない。辺で結ばれた頂点の色が違うことのチェックは、 高々、\(n(n-1)/2\)回のチェックで終わってしまう。これは多項式時間で検証可能である。

先の投稿でこう書きました。 「歴史的には、現代の「複雑性理論」は、NPという複雑性のクラスと「NP-完全」という概念の発見によって始まります。」 複雑性理論の歴史については、以前、角川さんで行った「人工知能を科学する」という連続セミナーの第一回「人工知能と複雑性理論」 https://www.marulabo.net/docs/20180927-kadokawa/ で詳しく触れています。 NP-完全については、この連続セミナーの第三回で、「人工知能と量子コンピュータ — NP-完全問題とその含意」というテーマでお話しをしました。 https://www.marulabo.net/docs/20181119-kadokawa/　 これらの資料を読んでいただければと思います。 ただ、残念なことにい、3年前の僕の認識には、いくつかの点で不十分なところがありました。 例えば、「数学とNP問題」というブログで、こう書いています。 https://maruyama097.blogspot.com/2018/09/np.html 「ただ、こうした考えに立って、数学の証明の「正しさ」が、多項式時間で「検証可能」だということは、数学の証明可能な問題全体が、NPクラスに属するということにならないか？ な、わけはない。（とも、思うのだが。）」 「な、わけはない。（とも、思うのだが。）」と思っていたのが間違いでした。最初の直感に従って進めばよかったのですが、自分で打ち消しています。多項式長の証明を持つ数学的命題の全体は、NP-完全の代表的な例だということを、僕は、Irit Dinurの講演を聴いて確信しました。 こうした認識に従えば、NP-完全な問題は、すべて共通の単一のアルゴリズムに「還元」できますので、もしも、ある人が、リーマン予想を証明したとすれば、その証明がどんなに長いものだったとしても、その証明に対応したグラフの3色塗り分け問題があることになります。 つまり、少し複雑なグラフでしょうが、そのグラフのノードを3色に塗り分けられることを示せば、リーマン予想を解くことができるグラフがあるということです。 「な、わけはない」 と思ってはいけないのです。「NP-完全」というのは、そういう性質を持つのです。それに、多項式長の証明を持つ数学的命題の全体は、NP-完全であるという認識は、「数学的...

　リソースによる複雑性の階層 先に、「複雑さ」を、ある問題を計算するのに必要な時間とメモリーの大きさで分類するというアプローチを紹介しました。 ある時間\(T_0\)では解けないけれど、\(T_0\) より大きな時間 \(T_1\)では解ける 問題、あるいは、ある量のメモリー空間\(S_0\)では解けないけれど、\(S_0\) より大きなメモリー空間 \(S_1\)では解ける 問題を考えて、多くの計算リソース（時間、空間）を要する問題を「複雑な問題」と考えることは自然なことです。また、多くの計算リソースを要する問題を「むずかしい問題」、より少ない計算リソースを要する問題を「やさしい問題」と考えることができます。 こうした「時間複雑性」や「空間複雑性」といった階層が存在することは、ある問題をできるだけ効率的に、短いステップで少ないメモリーで書こうとするプログラマーが、日常的に意識していることです。 一つの問題には、それを解く複数のアルゴリズムが存在しえますので、ある問題にとって、それを解くアルゴリズムの数だけ具体的な実行計算複雑性が存在することになります。例えば、n個のものを大きさ順に並べ替えるSORT問題の実行計算複雑性は、bubble sortのアルゴリズムなら \(O(n^2)\)に、quick sort のアルゴリズムなら\(O(n log n)\)になります。  プログラマにとっての実践的な関心は、その下限を目指すことですが、下限を確定することは、理論的にも実践的にも簡単なことではありません。 　コルモゴロフの「複雑性」 複雑性については、今回のセミナーで扱うアプローチとは別の流儀があります。コルモゴロフは、ある対象の複雑性を「その対象を出力するプログラムの最小の大きさ」で定義します。これは、ある問題を解くアルゴリズムの実行計算複雑性の下限を追求するアプローチと、向いているベクトルはよく似ています。それをもっと抽象化・一般化したものです。 ある問題についての最小のプログラムを「エレガントなプログラム」と呼ぶことにすると、チャイティンは、「あるプログラムがエレガントであることを我々は証明できない」ことを証明しました。これを「チャイティンの不完全性定理」といいます。 これらについては、以前の僕のブログを参照ください。 　●「コルモゴロフの複雑性」 　　　...

以前、次のように書きました。 「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と。 それは、人間の認識の歴史について語ったものでしたが、具体的な計算の複雑さの尺度にも、この「長い時間と膨大な知識の集積」に対応する量があります。 それは、「その計算にどれぐらいの時間が必要か？」という時間の尺度と、「その計算にどのくらいのメモリー空間が必要か？」という空間の尺度です。前者を「時間計算量」、後者を「空間計算量」と言います。 チューリングマシンで言えば、「時間計算量」はある計算に必要なチューリングマシンの命令の「ステップ数」に、「空間計算量」はある計算に必要なチューリングマシンの「テープの長さ」に対応します。 決定性チューリングマシンで、\(O(f(x))\)で表される時間計算量の複雑性クラスを\({\bf DTIME}(f(x))\)で表し、同じく空間計算量の複雑性クラスを\({\bf DSPACE}(f(x))\)で表します。 \({\bf DTIME}(f(x)),  {\bf DSPACE}(f(x))\)のままでもいいのですが、代表的な複雑性クラスについては、次のような別名を付けます。ここで\(p(n)\)は、入力の大きさnについての多項式です。 時間複雑性については、 　　\({\bf P} = {\bf DTIME}(p(n))\) ; 「多項式時間」です。 　　\({\bf EXP} = {\bf DTIME}(2^{p(n)})\) ; 「指数関数的時間」です。 　　\({\bf 2-EXP} = {\bf DTIME}(2^{2^{p(n)}})\) ; 「二重指数関数的時間」です。 空間複雑性については、 　　\({\bf PSPACE} = {\bf DSPACE}(p(n))\) ; 「多項式空間」です。 　　\({\bf EXPSPACE} = {\bf DSPACE}(2^{p(n)})\) ; 「指数関数的空間」です。 　　\({\bf 2-EXPSPACE} = {\bf DSPACE}(2^{2^{p(n)}})\) ; 「二重指数関数的空間」です。 この時、 時間計算量では、\({\bf P} \subset {\bf EXP}\) という関係が成り立ちます。空間計算量では、\({\bf PSPACE} ...

先に、「\(n^2\) あるいは\(n \log(n)\)に対応した計算複雑性を考えることは、もちろんできます。\(n^2\)は、多項式時間のPに属しますが、\(n\log(n)\)は、nの多項式ではありません。Pとは別の、\(n\log(n)\)という計算複雑性を考えることは可能です。」と書きました。 ここでは、ある関数f(n)が、nが増えるにつれてどのように増大するかを具体的に見ておきましょう。次の図を見てください。 ここでは、次の8つの関数が表示されています。\(n!,  2^n,  n^2, n\log{n}, n, \sqrt {n}, \log {n}, 1 \) \(n!,  2^n,  n^2, n\log{n} \)が nと比べて急速に大きくなることがわかります。それでも、\(n! > 2^n >  n^2 > n\log{n} \)ですね。nが大きくなるにつれて、その差はもっと大きなものになります。例えば、n=10の時、\(2^n\)は1024ですが、\(n^2\)は100、\(n\log{n}\)は、10の自然対数は、2.302... ですので、約23になります。 二つの関数 f(x)とg(x)があって、xがある値以上の時、ある正の定数cが存在して、常に f(x)よりcg(x)が大きい時、\(f(x) \in O(g(x))\)と表します。これをBig O記法と言います。イメージとしては、関数の値の増大に一番寄与している項を上限として取り出したものです（他の項は捨てます）。関数の定数倍の定数cも捨てます。 例えば、\(f(x)=4x^3-2x^2+5 \)という関数のBig O 表記を考えましょう。xが大きくなるにつれてf(x)の値の増大に一番寄与するのは、\(4x^3\)の項です。\(f(x)=O(4x^3)\)ですが、この定数の部分も省略して、\(f(x)=O(x^3)\)と表すことができます。 この表記で、多項式中のnの最大次数をkとして、多項式 poly(n)は、\(O(n^k)\)と表すことができます。

 複雑性理論で、もっとも基本的なクラスは、「多項式時間で計算可能なクラス P」です。このクラスは、人間にとってコンピュータで実際に計算できる計算と、ほぼ同じものです。 「人間にとって」というのが、奇妙におもわれるかもしれませんが、これはこれで大事なことです。見かけは単純に見える問題でも、アルゴリズムによっては、その計算には信じられないほど長い時間がかかる計算があります。人間は、多分、計算終了まで待つことができません。 だいぶ前になりますが、一部では話題になった動画があります。「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」 https://www.youtube.com/watch?v=Q4gTV4r0zRs 是非、ご覧になってください。 こうした問題を「数え上げ問題」というのですが、複雑性理論で個数の数え上げが、重要な意味を持つことを初めて示したのは、日本のコンピュータ・サイエンティスト 戸田誠之助 氏です。彼は、日本人で唯一人のゲーデル賞の受賞者(19998年)です。

ここでは複雑性理論での「多項式時間」について話してみようと思います。 \(xもx^2もx^3もx\)の多項式です。もっと一般に、\(a_0+a_1x+a_2x^2+a_3x^3+...+a_nx^n \)の形の式を「xの多項式関数」と呼びます。それぞれの項が、\(x^n\)に係数\(a_n\)が掛かった形をしていて、それらの和で表される関数です。xの多項式関数を\(poly(x)\)で表します。 ただ、\(2^xや3^x\)は、xの多項式とは呼びません。\(a^x\)は、aについてみればaの多項式ですがxについてみればxの多項式ではありません。変数xが「x乗」の形である項の肩に現れる関数を「xの指数関数」と言います。 複雑性の理論では、多項式時間で計算される問題のクラスを Pで表します。 ただ、いくつか注意すべきことがあります。 第一に、何についての多項式かを決めておく必要があります。1+1よりは、1000+1000の方が計算には時間がかかります。一般に、入力に与えられるデータが単純なものより複雑なものに計算には時間がかかるはずです。入力の大きさをnで表した時、計算時間をnの関数\(f(n)\)で表します。「多項式時間で計算される」というのは、入力の大きさをnとする時、その計算時間が、多項式\( poly(n)\)で表せるということです。 第二に、注意すべきことは、計算量を時間ではかるには、二つのやり方があるということです。一つは、実際に実行時間を実時間ではかるやり方です。もう一つは、たとえて言えば、コンピュータで何クロックその処理にかかるのかをはかるやり方です。 複雑性理論での時間計算量は、後者のアプローチをとります。計算を、基本的な要素に分解して、その基本操作の何ステップで処理が終わるかで、時間をはかります。正確な定義は後で述べますが、直感的にいうとチューリングマシンの一命令の実行を時間の単位にします。 そうすると面白いことが起きます。 ある問題が多項式時間で計算される複雑性のクラスPに属するとします。ムーアの法則で、コンピュータの処理速度が指数関数的に増大したとしても、基本動作が早くなるだけで、処理に必要なステップが短くなる訳ではありません。ですので、実際の実行時間がいくら速くなっても、その問題が多項式時間のクラスPに属することに変わりはありません。 もっと面...

私たちの認識は単純なものから複雑なものに進みます。世界は複雑なものであふれているので、我々の認識もどんどん複雑になっていきます。ただ、こうした私たちの認識の前進がいつまでも続くとは限りません。私たちの認識は、しばしば、複雑さの前に立ちすくみます。複雑なものを理解するのには、長い時間と膨大な知識の集積が必要であることは、科学の歴史を見れば分かります。 僕は、対象の複雑さと認識の複雑さは同じものだと考えています。そうした認識は「複雑さ」そのものを対象とした認識が可能だということを意味します。現代の計算科学のもっとも活発な研究分野はの一つは「複雑性理論」なのですが、そうした理論が登場したことの意味は、そう考えれば、よく理解できると思います。 今回のセミナーでは、様々なチューリングマシンの拡大と複雑性のクラスの対応を紹介したいと思います。次のようなチューリングマシンを取りあげます。 https://turing-complex.peatix.com/view 　● 決定性チューリングマシン 　● 非決定性チューリングマシン 　● 確率性チューリングマシン 　● 量子チューリングマシン 先に、「複雑なものを理解するのには、長い時間と膨大な知識の集積が必要である」と書きましたが、このチューリングマシンによる複雑さのモデルでは、複雑なものを理解するのに必要な「長い時間」がチューリングマシンの「計算時間」に、「膨大な知識の集積」がチューリングマシンの「テープの長さ」に対応すると思って構いません。 「そんな単純化で大丈夫か？」 確かに。 もちろん、科学の歴史をチューリングマシンに喩えようと思っているわけではありません。ただ、こうした単純化（「抽象化」は、単純化に他なりません）された切り口が、「認識の有限性と対象の無限性」「古典論と量子論」「決定論と確率論」といった認識の大きな問題にアプローチする一つの有効な手段を提供するという話ができればと思っています。

7/6 ハンズオン「量子コンピュータで学ぶ量子プログラミング入門」https://lab-kadokawa82.peatix.com/　の演習の目標である「量子テレポーション」について、少し補足しようと思う。 「量子テレポーション」。なんとも奇妙な名前なのだが、それもそのはずで、命名者は、SF映画の「スタートレック」から、この名前を取ったらしい。 「量子テレポーテーション」技術は、「スタートレック」のように、物体そのものを瞬間移動することができるわけではない。それが可能とするのは、情報を移動することだけである。それは、現代のネットワーク技術が情報の移動をおこなっているのと同じである。 少し違うのは、「量子テレポーテーション」が、一つ一つの量子が持つ情報（それをqubitという。qubit = quantum bit 「量子ビット」の略である）を送り出し、受け取ることができることであり、またその為に「エンタングルメント」という量子の性質を利用することである。 重要なことは、量子情報理論の情報通信技術への応用においては、本格的な量子コンピューが登場する以前に、この「量子テレポーテーション」等の「量子通信技術」が、実用化するだろうということである。 では、どこに、この「量子通信」技術は使われるのであろうか？ それは、現在のコンピュータとコンピュータを接続する為にである。 量子コンピュータの時代というと、現代のコンピュータが全て量子コンピュータに置き換わる時代を想像するかもしれないのだが、それは正しくないだろう。現代のコンピュータ技術は、引き続き有用なものとして残り続けるだろう。 「量子コンピュータ」との対比で、現代のコンピュータを「古典コンピュータ」と呼ことがある。古典コンピュータと古典コンピュータとの通信に、まず「量子通信」技術が使われ始めるのである。 現代の通信技術の中核である「光通信」技術と「量子通信技術」は、実は、親和性が高い。また現代の通信技術の重要な課題であるセキュリティについても、「量子通信技術」では「量子暗号」技術と組み合わせると、飛躍的なセキュリティの向上が可能になる。 「量子通信」の導入によって、古典コンピュータと量子コンピュータのハイブリッドの時代が始まると、僕は考えている。 幸いなことに、すでに我々は、...

ダニエル・ハーローは、少しジム・キャリーに似ているイケメン物理学者である。 5月の連休に配信元のトラブルで、彼のビデオの一部が見れなかったので、セミナーがひとつ終わったこの土日、彼のレクチャーを6~7本ほどをYoutubeでまとめて観た。面白かった。 AMPSパラドックス（ブラックホールの情報問題の難問）を「量子複雑性」の理論で解決し、現在の物理学の中心的なスキーマであるAdS/CFT対応の解釈に「量子エラー訂正理論」を持ち込み、量子重力ではこれまでの物理のアイデアの支柱だった「対称性」が破れることを示すなど活躍が続いている。 彼のアプローチの特徴は、物理学に情報の理論を持ち込むこと。写真は、2年前のスタンフォードでのComplex Workshopの一コマ。テーマは、"Hardware+Software in Physics" 彼らしい問題意識だ。http://bit.ly/2WWZyUz　 2-30人ほどの小さな規模のワークショップだが、彼のセッションには、サスキンド、マルデセナ、アーロンソンが参加していた。すごい。（僕は、Youtubeで彼らの顔はよく知っているのだ。） arXivのおかげで、図書館がなくてもあまり困らなくなったのだが、Youtubeのおかげで学会に行かなくてもよくなっている。（ちょっと極論かもしれないが、物理に関しては、この数年のビデオ配信の広がりは目をみはるほどだ。） これまでは、論文を読むしかなかったのだが、最近、僕は、論文読む前に、著者とテーマでビデオを探す。そのあとで論文を読む。そっちの方がずっと効率的に学べる。 いい時代になったものだ。 （二日だけ自由な時間をとったのだが。また、セミナーの準備に戻らないと）

6/21 マルレク・サブゼミ「3時間で学ぶShorのアルゴリズム入門」のための予習用資料公開しました。 6/21マルレク・サブゼミ に多数のお申し込みありがとうございます。参加予定の方、お時間があったら、目を通していただけますか？https://www.marulabo.net/docs/miniguide/ 短い資料です（パワポ・スライド 50枚）。Shorのアルゴリズムには触れていません。量子情報理論の基本をまとめたものです。 今回参加されない方も、量子コンピュータを勉強する上での ミニ・ガイドとして利用いただけたらと思います。