過去・現在・未来

稚内の家も停電中。本当に、北海道全部、停電しているのだ。 携帯はつながるが、電池が充電できない。「車から携帯に充電できるよ」と彼女に伝えたのだが「車庫の電動シャッターが開かない」と言われる。 長い停電が、冬でなくてよかった。暖房は石油だが、FFストーブもボイラーも電気がないと動かないのだ。暖房がないと、稚内は厳しい。 稚内は、電気の回復を待つだけで、不便だが被害は軽い。札幌方面は、全貌はまだわからないが、大きな被害が起きているようだ。 これだけ全国各地で災害が続けば（東北の大震災含めて）、いまのところ災害空白域の関東にも何かが起きる可能性は高いと思ってしまう。 いま、東京で生活しているのだが、稚内に帰ろうかなと、ふと思う。 帰った途端、大停電がおきて、凍死したりして。

「数学とNP問題」というのは、少し奇妙なタイトルかもしれない。 というのも、PやNPといったクラスを扱う「複雑性理論」自身が、数学の一分野だからである。正確にいうと、複雑性理論は、数学理論であると同時に、現在では、物理理論の一部でもある（もちろん、計算機科学の一分野でもある）。 そのためには、BQP(量子チューリングマシンで「多項式時間」で計算可能なクラス)が、現在の複雑性の理論では重要なクラスになっていることを説明しなければならないのだが、それについては、ショアのアルゴリズムを紹介した後で述べようと思う。 ここでは、数学理論としての複雑性の理論に、問題を限ってみよう。 NPクラスの説明によく用いられるのは、素因数への分解問題である。ある自然数Nを「多項式時間」で素因数に分解するアルゴリズムは、現在では、まだ見つかっていない。（多分、そんな多項式時間アルゴリズムは見つからないだろうと感じている人が多いのだが、かといって、そのことが確定しているわけではない。） 一般の数Nではなく、条件を緩めて、Nは二つの素数の積であることがわかっていたとしても、Nが大きな数になると、Nを素因数に分解すること、すなわち、N=pqであるような二つの素数 p, q を見つけることは、極めて難しくなる。 ただ、N, p, q が具体的に与えられているなら、「Nは、素数pと素数qに、素因数分解される」という主張は、簡単に検証できる。pとqを掛けて、その結果がNに等しいことを示せばいいのだから。掛け算は、もちろん簡単な計算で、多項式時間で終わる。 こうした、その問題を解くのが「多項式時間」で終わるかどうかはわからなくても、具体的な値で与えられたその問題の「答え」と言われるものが、本当に「正しい答え」であるかどうかを「多項式時間」でチェックできる問題のクラスを、NPという。素因数分解問題は、NP問題である。 （ちなみに、「答え」（なるもの）が与えられた時、それが「間違った答え」であるかどうかを「多項式時間」でチェックできる問題のクラスを、 co-NP問題という。素因数分解問題は、co-NP問題でもある。） こうしたことや、NP問題である素因数分解問題に現れる「難しさ」と「易しさ」の「非対称性」が、現在の公開キー暗号の基礎になっていることは、多くの人が既に知ってい

別のポスト 「文法を計算する１」 で、次のように書いた。 「複雑性の理論では、計算可能なもっとも簡単なクラスを「多項式時間で計算可能： P」と呼ぶのだが、我々の言語能力は、明らかにクラスPに属するはずだ。だって、「多項式時間」どころではなく、リアルタイムに相手の話す言葉が文法にかなっているかを判断して聞き取り、リアルタイムに文法的に正しい文を生成してしゃべることができるのだから。」 もっとも、こうした議論は、そのままでは、理論的には「正しい」議論という訳ではない。 一つには、この議論は、リアルタイムに人間と同等の言語能力を示すシステムを構成しない限り、単なる予想であって、証明されたものではないからである。もう一つ、別の問題もある。それは、この議論は、言語能力のような人間の現実の諸能力を、数学的に定義された複雑性理論上のクラス（この場合はP）に、関連づけているからである。 後者の指摘の方が、より深い問題に根ざしているのだが、多少の飛躍をまじえて言うと、それについては、僕は、「人間の認識の形式的で数学的なモデルが構築可能である」と考えている。それは、形式としては数学的な表現を取りながら、物理学が、実在の運動法則の理論であることと同じである。物理学が、数学的形式をまとうことが必然であるように、認識の理論には、認識の理論の数学が必要なのである。 こうした認識論的な立場からは、言語の領域について言えば、その中核である「文法」の本質を「計算可能性」と捉える「計算主義的言語理論」は、僕には、魅力的である。そして、こうした立場が、「実際に、そうしたシステムは、作れていないじゃないか」という、先の前者の指摘に、実際にそうしたシステムを作り上げることで応えようとする試みをドライブすることになると考えている。 ところで、複雑性理論のコンテキストの中にいると(特に、 degree of unsolvability の議論)、何かPが「簡単」な計算のクラスに見えてくることがあるのだが、現実的には、それは大きな錯覚である。 世の中の「正しく動く」コンピューター・プログラムは、全てクラスPに属するのだし、クラスPに属する問題の数を、簡単なものから数え上げることも、現実的には不可能なのである（これについては、あとで「いそがしいビーバー問題」というのを紹介する。） 「

昨日から申し込みを受け付けていた「紙と鉛筆で学ぶ量子コンピュータの基礎」ですが、IBM, Google, Microsoft の三会場ともに、満席になりました。 たくさんのお申し込み、ありがとうございました。 年内、200人に「量子コンピュータの基礎」の6時間レクチャーをしようと思っていたのですが、300人にできそうです。 あらためて、IBM, Google, Microsoftさんの協力に感謝します。

「楽しい数学：第三夜」を、10月15日、 DMMさん（六本木一丁目）で開催します。 開催が遅れたことを、お詫びします。告知、申し込みページは、9月末に開設します。 こころよく会場を提供していただいたDMMさんに、感謝しています。 「楽しい数学：第三夜」のテーマは、 　「「やさしい計算」と「むずかしい計算」」 です。わかりやすい「計算理論」の入門にしたいと思っています。 有名なゲーデルの不完全性定理と、これもまた有名なチューリング・マシンの話をします。あと、あまり有名ではないゲーデルの完全性定理の話をします。 時間があれば、「計算可能性の理論」から「複雑性の理論」への進化を紹介したいと思っています。 冒頭に、次のような「思考実験」の課題をあげています。興味があれば、自分の頭で考えてみてください。 思考実験１：二桁の数どうしの計算について、小学校で習った足し算・引き算・掛け算の計算の仕方を、すべて「文章」で記述してみよう。それぞれ、400字以内にまとめられるか？ 思考実験２：「二分の一を三分の二で割る」を、「例え話」で説明せよ。 思考実験３：ある人が、「私の言うことはすべて嘘である」と言ったとしよう。この人のこの言葉は嘘だろうかか？ 嘘ではないだろうか？ 「楽しい数学」、引き続き、よろしくお願いします。

「紙と鉛筆で学ぶ」というセミナーやっているんですが、20代前半の若者に「鉛筆、持ってません」と言われました。なるほど。 https://quantum-basic.peatix.com/ もちろん、ボールペンでも万年筆でも毛筆でも、構いませんよ。 ところで、「紙」は、持っているのかな？ （そういえば、この前のセミナーでは、全部、タブレットとスタイラスで、でも「手書き」で「計算」している人いました。）

受け付けページです。 https://quantum-basic.peatix.com/ 本セミナーは、丸山が展開してきた「紙と鉛筆で学ぶ量子情報理論基礎演習 I」の無料リピート版です。 開催の日時・会場は、次の通りです。 　　1. 9/15 13:00~19:00 会場 IBM 箱崎 　　2. 9/22 13:00~21:00 会場 Google 六本木 　　3. 10/6 13:00~19:00 会場 Microsoft 品川 第二ラウンドのGoogle会場では、同社のフレームワーク cirq の解説が含まれています。この回は、Googleさんが、夕食を提供してくれるそうです。（夕食が出るのは、この回のみです。） 土曜の午後半日を使うコースです。それぞれの予定に合わせて、三会場からお選びください。開催の日時・場所・コンテンツが異なりますので、ご注意ください。 満席が予想されますので、お一人で複数の会場に申し込むのはご遠慮ください。 　　------------- 　　セミナー概要 　　------------- 本セミナーは、初心者を対象に、現在、関心が高まっている量子コンピュータを、その基礎から学ぶことを目的にしています。 本セミナーの基本的獲得目標は、「量子ゲート」型量子コンピュータを構成する「量子ゲート」の基本的な働きを理解することです。 量子の奇妙な振る舞いを理解する為には、我々の感覚や直感に頼ることはできません。量子の理解の為には、数学の助けが必要です。 ただし、「量子ゲート」の働きを知るだけなら、とても簡単な数学の助けを借りるだけでいいのです。それは、高校数学のちょっとした延長線上にある、ベクトルと行列の演算を理解できればいいだけです。 本セミナーでは、ベクトルと行列を学んでいない人にも、その計算ができるように、補講のコマを設けています。 量子コンピュータが、実際に目の前になくても、我々は「紙と鉛筆」で「計算」することで、量子コンピュータの働きを理解することができるのです。 本セミナーでは、量子コンピュータの基礎原理として、次の三つのことを学びます。 　　1.　重ね合わせの原理 　　2.　観測の原理 　　3.　状態変化の原理 その上で、n個の量