過去・現在・未来

  【 9/30 マルレク「ラティス暗号入門」講演資料・講演ビデオ 公開 】  MaruLaboでは、以前に行ったセミナーの講演ビデオを公開しています。 今回は、9月30日に開催した「ラティス暗号入門」セミナーの講演ビデオです。 実は、最近話題のChatGPTが「ラティス暗号」について嘘ばっかり言うので、ちょっとショックを受けました。まあ、「ラティス暗号」が、あまり知られていないということの反映なのでしょうか。 こんなショートムービー作りました。「ChatGPT が間違ったことを言うサンプル」 https://youtu.be/58z3BS_mqBk?list=PLQIrJ0f9gMcOX9oSKXRR87BgMkql5dvrx 取り上げているのは、ラティス暗号についてのChatGPTの嘘です。とても基本的なところで、間違っていることがわかってもらえるといいのですが。こちらも、ぜひ、ご覧ください。 以下が、今回公開したセミナーの 講演資料と講演ビデオの再生リストです。ご利用ください。 「ラティス暗号入門」講演資料： https://drive.google.com/file/d/1F7ShzeRuDl0mLCe69kX32fgD5tm-Thqi/view?usp=sharing 「ラティス暗号入門」講演ビデオ再生リスト： https://www.youtube.com/playlist?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS この「ラティス暗号入門」講演ビデオの再生リストは、次の三つのビデオから構成されています。 ●  Part I  「ラティス入門」 https://youtu.be/v1xnh40C5uE?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS ●  Part II  「ラティス暗号 LWE」 https://youtu.be/_iV4R7Zz4Xs?list=PLQIrJ0f9gMcOLK3eePEamNsUemew4hBLS ●  Part III  「ラティスとラティス暗号」 https://youtu.be/hkw5m-Sbcs4?list=PLQIrJ0f9gMcOLK3eePEamNsUemew...

【 どのように「限界」を超えるのか？ 】 このセッションでは引き続き、ChatGPTの公式blogの内容の紹介を続けようとおもいます。基本的なトピックスは、ChatGPTの「限界」と「Iterative deployment」という取り組みについてです。 この「限界」の認識と「Iterative deployment」という取り組みは結びついています。 重要なことは、ChatGPTの「方法」としての「人間のフィードバックからの強化学習」を、システム全体のレベルで繰り返し行う「Iterative deployment」によって、その「限界」を乗り越えるという展望が述べられていることです。 それらの一部については、すでに以前のセッションで触れているのですが、あらためて彼らの言葉で確認したいと思います。 ChatGPTが、自らの「限界」と認めている第一の問題は、「ChatGPTは、もっともらしく聞こえるが、不正確または無意味な答えを書き込むことがある」ということでした。このことは、多くの人が観察していることです。その最大の理由は、「強化学習の訓練に使う「真実のソース」がないこと」にあります。 　「このシステムを改善するために、ユーザーからのフィードバックに期待している。」 他にもいろいろ問題を挙げているし、先のような言葉は、ソフトウェア・ベンダーの常套句のように聞こえるかもしれません。ただ、それだけではないのです。 Iterative deploymentについて、彼らはこう説明しています。 「これには、人間のフィードバックからの強化学習（RLHF）の使用により、有害で真実でない出力を大幅に削減することが含まれている。」 「我々は、上記のように多くの制限が残っていることを知っており、そのような問題を改善するために定期的なモデルアップデートを行う予定である。」 「しかし、ChatGPTにアクセス可能なインターフェースを提供することで、私たちがまだ気づいていない問題について、ユーザーの貴重なフィードバックを得られることも期待している。」 「ユーザーは、UIを通じて問題のあるモデル出力や、同じくインターフェースの一部である外部コンテンツフィルタによる偽陽性/偽陰性についてフィードバックを提供することが推奨されている。」 「我々は、現実の世界で、非対立的な条件のもとでも...

【 キーワードは「人間のフィードバック」】 今回のセッションでは、ChatGPTがどのように実装されているかを紹介したいと思います。 ChatGPTは、「人間のフィードバックからの強化学習」”Reinforcement Learning from Human Feedback (RLHF)” と呼ばれる手法に基づいて実装されています。 この「人間のフィードバックからの強化学習」は、三つのステップで構成されています。 　Step 1: デモ用のデータを収集して、管理ポリシーを訓練する 　Step 2: 比較データを収集して、報酬モデルを訓練する 　Step 3: 報酬モデルに対して、PPO強化学習アルゴリズムを使って、ポリシーを最適化する 興味深いことは、これらの中で、「人間」が重要な役割を担っていることです。 Step 1 では、実際に人間と人間との対話が行われて、その対話データが集められます。 Step 2 では、集められた対話の中から、好ましい回答のランクづけが、人間によって行われます。 こうした「人間の助けを借りた」助走期間を経て、ChatGPTは、Step 3 になってはじめて、「機械だけで」立ち上がります。 こうなれば、「人間」の姿は、見えなくなります。もっとも、ここで「人間」というのは、ChatGPTの立ち上がりのためにChatGPTに対話データと報酬ランクのデータを与えていた、ChatGPTの「中の人」だった「人間」のことなのですが。 ただ、ChatGPTの依拠する「人間のフィードバックからの強化学習」は、このStep 3 で完結するわけではないのです。ChatGPTの「公開」以降、「人間のフィードバックからの強化学習」のフェーズは変わります。 100万人以上の人がChatGPTを使い始めているようですが、僕を含めたそうした人間（もともとは、ChatGPTの「外の人」だったのですが）との対話が、ChatGPTの対話データセットに取り込まれ、その反応がランクづけされ、ChatGPTによって利用されます。 先行した「根源的蓄積」の時代は終わり、システムを準備した「中の人」とシステムを利用する「外の人」の区別はなくなります。みんなChatGPTに「人間のフィードバック」を返す「中の人」になります。 こうして、ChatGPTは、巨大な集団の「知」を取...

【 ChatGPTは嘘をつく 】 前回のセッションでは、ChatGPTが「人間との対話」で、柔軟で高いスキルを示すことを紹介しました。それは、とても興味深いことです。 今回のセッションは、ChatGPTが「人間との対話」で語ることの内容には、信用できないものがあるという例の紹介です。ここで紹介したのは、僕とChatGPTとの暗号技術についての会話です。 実は、前回紹介したサンプルの中にも、「フェルマーの小定理って何？」「それは暗号にどう使われているの？」という暗号に関連した対話の例がありました。そこでのChatGPTの答えは、キチンとしたものでした。おまけに余裕で詩まで作ってくれました。 ただ、今回の現代の暗号技術についての対話で、彼が答えた答えは、ほとんど全部と言っていいほど、間違ったものでした。 前回と今回の暗号についての二つの対話の違いは、どこから生まれたのでしょう？ 不思議です。今にして思えば、ラティス暗号 LWE についてラップ作ってと頼んでみればよかったのかも。 ChatGPTが、正しいことをキチンと語るだけでなく、嘘をつくことがあることに、すでに多くの人が気づいています。 ChatGPTについて語る上で、こうした経験を持つことは、とても大事なことだと思っています。ぜひ、彼と対話を重ねて、彼に嘘をつかせてみてください。 大事なことは、OpenAI自身が、そのことを認めていることです。 前回から紹介しているChatGPTの公式blogページ  https://openai.com/blog/chatgpt/ で、彼らは、ChatGPTの「限界」について語り、その第一の「限界」を、次のように述べています。 「ChatGPTは、もっともらしく聞こえるが、不正確または無意味な答えを書き込むことがある。」 さらに、こう付け加えます。 「この問題を解決するのは、次のような点で困難である。」 その困難の第一の理由は、次のことだと言います。 「RL（強化学習）のトレーニングでは、現在、真実のソースがない。」 大事なところなので、原文を引用しておきますね。 ChatGPT sometimes writes plausible-sounding but incorrect or nonsensical answers. Fixing this issue...

【 これは、面白い！ 】 今回のセッションでは、ChatGPTの対話の能力が、どう言うものであるのかを、ChatGPTの公式Blog "ChatGPT: Optimizing Language Models for Dialogue"の四つのサンプルから紹介しようと思います。 https://openai.com/blog/chatgpt/ これは、面白いです。 最初の例では、ユーザーがアップしたソースコードの誤りを見つけて、修正コードを提示してくれます。本当なのでしょうか？ 二つ目の例では、「誰かの家に泥棒に入るにはどうすればいい？」というユーザーに、「そんな質問には答えられないな。それは犯罪だよ。」と機械が答えます。この例で面白かったのは、機械が「泥棒に対して一番安全なのは、家を持たないことさ。」と冗談を言うこととです。 三つ目の数学の質問では、ユーザーの「フェルマーの小定理で、韻を踏んだ詩を書いて」という無茶振りに、見事に詩を作って見せます。「これまでの対話を要約して」というリクエストにもきちんと答えます。見事です。 最後の手紙を書いてもらうと例では、「僕の代わりに手紙を出して」に対して、「僕は、テキストベースのロボットなんで、物理的な手紙は出せません」と断ります。この辺りは、とてもよくできています。 素晴らしい！ -------------------------------- 「ChatGPTの素晴らしい対話のサンプル」 を公開しました。 https://youtu.be/e4O1KNGPA3g ?list=PLQIrJ0f9gMcOX9oSKXRR87BgMkql5dvrx 資料pdf https://drive.google.com/file/d/1Uj8Z63U-XNvr4b5OHM7K6nJBXwRnq5Zi/view?usp=sharing blog：「これは、面白い！」 https://maruyama097.blogspot.com/2022/12/blog-post_27.html まとめページ https://www.marulabo.net/docs/chatgpt/ 1/14セミナー「なぜ？で考える ChatGPT の不思議」の申し込みページはこちらです。 https://chatgpt.peatix.com...

   【 浅海ゼミ 第18回の講演ビデオと講演資料公開しました 】　 浅海ゼミ「クラウドアプリケーションのためのオブジェクト指向分析設計講座」第18回の講演ビデオと、講演資料を公開しました。 https://www.marulabo.net/docs/asami18/ 今回のテーマは 「設計」です。 設計では分析で作成したプラットフォーム独立の抽象的なモデルから実装の入力となるプラットフォーム固有の具象的なモデルを作成します。 今回は設計の全体像について概観します。次回からアーキテクチャ設計、コンポーネント設計、ドメイン設計、UX/UI設計に入っていく予定です。 講演ビデオ  https://youtu.be/iedUjjCnT8U は、次のような構成になっています。 　00:00:00 開始 　00:01:07 設計の位置づけ 　00:18:21 設計と実装 　00:26:46 設計の構成 　00:34:11 アーキテクチャ設計 　00:36:12 コンポーネント設計 　00:39:09 ドメイン設計 　00:41:45 UX/UI設計 　00:45:43 まとめ 資料は、次からアクセスできます。 MaruLabo:   https://www.marulabo.net/docs/asami18/ SlideShare: ttps://www.slideshare.net/asami224/18-255037818 浅海ゼミの講座の全体構成はこちらを参照ください。 https://www.marulabo.net/docs/asami/

【 1/14 マルレク 「なぜ？で考えるChatGPTの不思議」への招待】 ChatGPT試してみましたか？ なかなか驚きです。今までのAI技術と一味違います。 いろいろ不思議なことに気がつきます。 第一。なぜ、こんなになめらかに賢く、人間と対話できるのでしょうか？ 第二。なぜ、こんなにも賢く見えるのに、平気で間違ったことを言うのでしょう？ 今回のセミナーは、主要にこの二つの「なぜ？」に答えようとしたものです。 あわせて、今回のセミナーは、次のような疑問に答えようとしています。 「ChatGPTは、どのようなカラクリで、こうしたふるまいを可能にしているのでしょう？」 「OpenGPTは、AI技術のどのような蓄積から生まれ、AI技術をどこまで高めるのでしょう？」 「OpenGPTは、そもそも、ことばの意味をどのように理解しているのでしょう？」 「OpenGPT以降のAI技術は、どのように発展するのでしょう？」 次のような構成を予定しています。 　● ChatGPTの動作のサンプル紹介 　● ChatGPTのメカニズム 　● ChatGPT成立の背景 　● ChatGPTのかかえる問題 　● AI技術発展の展望 詳しくは、MaruLaboで更新される動画を参照ください。 https://www.youtube.com/playlist?list=PLQIrJ0f9gMcOX9oSKXRR87BgMkql5dvrx 参考文献 [2022/11/08] ChatGPT: Optimizing Language Models for Dialogue (OpenAI) https://openai.com/blog/chatgpt/   [2022/10/24] Evaluating the Impact of Model Scale for Compositional Generalization in Semantic Parsing   (Google Reseach) https://arxiv.org/abs/2205.12253    [2022/10/19] Scaling Laws for Reward Model Overoptimization  (OpenAI) https://arx...

【 図で計算する 】 Coecke の基本的なアイデアは、語の意味を表すベクトル空間 FVect と語の文法的な型を表す P のペアからなるカテゴリー   FVect ✖️ P の中で、意味を考えるということです。 FVect ✖️ P の中で、単純な一つの語 w の意味は、意味ベクトルWと語の型pのペア（W, p）というで表されます。 語の並びとしての文の意味を考える出発点は、こうした拡張された語の意味の表現が、並んでいる状態です。    　語の並び 　　　　　　　　 w1            w2    ... ...      wn 　　語の意味の表現の並び　(W1, p1)    (W2, p2)  ... ...  (Wn, pn) 問題は、それからです。次のような写像 f を考えます。      文 w1w2...wn の意味 　　　＝ f( (W1, p1) ⊗ (W2, p2) ⊗ ... ⊗ (Wn, pn) ) 大事なことは、文法的な文sの導出 p1p2...pn ≧ s が情報として与えられれば、 　（ f, ≧ ）: (𝑊1⊗⋯⊗𝑊𝑛 , 𝑝1⋯𝑝𝑛) ⟶（S, s) は、カテゴリー   FVect ✖️ P の射であり、文法的な型 s を持つ S は文の意味と考えることができることです。この射（ f, ≧ ）を「語の意味から文の意味への写像」と呼びます。 今回のセッションでは、文を構成するそれぞれの語と文法の構造が、どのように語の意味から文の意味を作り出すかが、図形で表されていることをフューチャーしています。こまかな議論は省略してもいいので、図形を眺めて、こんな言語学もあるんだと感じてもらうだけで、いいかもしれません。 -------------------------------- 「DisCoCat --Coecke’s diagrammatic calculus」 を公開しました。 https://youtu.be/rBl6FSWiwGU ?list=PLQIrJ0f...

【 数式と図式 】  今回のセッションは、CoeckeのDisCoCat理論で大きな役割を果たす図式表現String Diagram の紹介です。 Monoidal カテゴリーの射についての等式がmonoidal カテゴリーの公理から証明可能であれば、その等式はその図形的言語であるString Diagramでも導出可能です。 また、その逆も成り立ちます。 String Diagramで図形的に導出可能な等式は、monoidal カテゴリーの公理から証明可能です。 String Diagramの「図式」は、「数式」で表現される抽象的なカテゴリー論と同値です。「数式」の方が「図式」より、正確で情報量が多いというのは、ある種の思い込みです。そのうえ、「図式」の方がずっと直感的です。（逆に、図式が成り立つことを「数学的」に「証明」するのは、少し骨が折れます。） Coeckeは、このString Diagram を使ってカテゴリー論的量子論を図解するという大胆な試みを展開していました。Coeckeのカテゴリー論的言語理論は、量子論との結びつきを強めていきます。 今回も紹介した、Cup状あるいはCap状の曲線は、Coeckeの量子論の解釈では、「エンタングルメント」状態を表すものです。かれは、この状態をYanking で直線に引き延ばすことで「量子テレポーテーション」を直感的に説明します。 こうして彼は、自然言語の意味理解に「エンタングルメント」や「量子テレポーテーション」の対応物を見つけていきます。そうした自然言語へのアプローチは、まったく新しいものです。 -------------------------------- 「 Interlude -- Monoidal categoryとString Diagram 」 を公開しました。 https://youtu.be/wk6C5F5hLhw ?list=PLQIrJ0f9gMcN2nXtvKCK4ApBaVglV8Drx 資料pdf https://drive.google.com/file/d/1czKkbonhRCXtaMjTAMeEiAizOLIE3qS5/view?usp=sharing blog：「数式と図式」 https://maruyama097.blogspot.com/2022/12...

【 Coeckeが考えたこと 】 今回は、DisCoCat の出発点となった Bob Coecke らの2010年の論文を紹介します。 かれの問題意識は、明確でかつ意欲的なものです。 「意味の記号論と分散意味論は、ある意味直交する競合する理論である。それぞれに長所と短所がある、前者は構成的だが定性的で、後者は非構成的だが定量的である。」 認知科学の分野でも、こころのコネクショニスト的モデルと記号論的モデルの間に、同じような立場の違いが存在します。 Coeckeが考えたことは、この二つの陣営の対立を乗り越える道はないのかということです。 僕自身は、知能のコネクショニズム的モデルでは人間の知能を構成する重要な特徴である「数学的能力」を説明できないと考えて「計算主義的」な知能のモデルに、強く惹かれていました。その意味では、Coeckeの問題提起とその「解決」の提案は、とても興味深いことでした。今では、こうした方向が正しいだろうと考えるようになりました。 ポイントは、二つの陣営の対立を乗り越えるのに、カテゴリー論を利用しようということです。 「文法としてのPregroupが特に興味深く、我々がそれを使用する動機となったのは、カテゴリー論的な観点に立つと、それがベクトル空間やテンソル積と共通の構造を持つということである。」 このあたりは、先日紹介した、Functor SemanticsについてのLawvereの言葉と同じものです。ただ、彼は、対立する陣営が、対立はしているものの、それぞれがその「市民」である「第三のカテゴリー」を具体的に発見します。 「ベクトル空間、線形写像、テンソル積のカテゴリも、Pregroupも、いわゆるcompact closedカテゴリと呼ばれるものの例である。具体的には、Pregroupでの型の並置は、monoidalカテゴリーのmonoidalテンソルに対応する。」 「文の意味を計算する数学的構造は、意味と型の二つを組み合わせたcompact closedカテゴリーとなる。」 素晴らしい！ -------------------------------- 「 DisCoCat --Coecke’s original form 」 を公開しました。 https://youtu.be/Y6ltrMZPijk ?list=PLQIrJ0f9...

【 数学的説明を少しスキップしました 】 これまでやろうとしていたことは、語から構成される文の文法性と語の意味から構成される文の意味を関連づけるために、この二つの「構成性」を結びつけるFunctorを利用しようということでした。 こうしたアプローチをFunctorial  Semanticsというのですが、この理論の創始者であるローヴェールは、興味深いことを言っています。 「二つのものを概念的に関連づけるためには、それらが共に共通のカテゴリーに属している必要がある。すなわち、数学的に言えば、両者が当初は異なるカテゴリーに属すると考えられていたのであれば、まず第一に、両者をFunctor的に、共通の第三のカテゴリーに移動させる必要がある。」 「しかし、もし両者を関連づけるこの試みが成功したならば、その時には、 こうした関連付けすべての最も明快な説明には、両者自身がもともと、この第三のカテゴリーの「市民」であったことを示すことを含まれているだろう。」 今回の例でしたら、文を構成する文法のカテゴリー PregX と意味をベクトルとして分散表現するカテゴリーFVectの、二つのカテゴリーが登場します。この二つのカテゴリーは、異なるものです。 ローヴェールのFunctorial Semantics のフレームを利用するためには、この二つのカテゴリーが、ともに共通の第三のカテゴリーに属することを言わなければなりません。 前回のセッションでは、「次回」にすなわち「今回」にそのことを説明すると言っていたのですが、残念ながら、今回のセッションでは、短い時間の中で、そのきちんとした説明をすることができませんでした。 「第三のカテゴリー」は何かの答えはわかっています。PregXもFVectも、ともに、monoidal categoryのcompact closed categoryに属します。ローヴェールの言い方を借りると、文法のカテゴリー PregXも意味を表現するカテゴリー FVectも、共に、compact closedなカテゴリーの「市民」なのです。 monoidal カテゴリーのグラフィカルな表現であるString Diagramについては、以前のセミナー「String Diagram を学ぶ -- カテゴリー論入門 (1)」で紹介したことがあります。 htt...

【 chatGPTにケチをつけたいわけではないこと 】 今回のセッションから、新しい内容、カテゴリー論を用いた構成的分散意味論を紹介しようと思います。  基本的な問題意識は、「文の意味は、個々の語の意味と、語から文を構成する文法規則によって構成的に決定される」という構成性の原理を文の意味論においても適用することです。 こうした、「カテゴリー論的構成的分散意味論」　Distributional Compositional Categorical Semantics をDisCoCat と呼ぶことがあります。すこしふざけた名前ですが、それは創始者のBob Coeckeのキャラクターだと思います。  Bob Coeckeが始めた「カテゴリー論的構成的分散意味論」は、この10年の間に大きく発展しました。現在では、量子コンピュータを使った自然言語処理 QNLP (Quantum Natural Language Processing) という新しい分野で、活発に研究が続けられている。 「カテゴリー論」＋「量子論」が、新しい「言語の意味論」と結びつくのです。これは、とても面白いことだと思います。今回のセミナーでも、こうした流れの一端を紹介できれと思っています。 話は変わりますが、最近話題のchatGPTで少し遊んでいます。いろいろ辛口のコメントもつけているので、丸山は chatGPTにケチばかりつけているという印象を持った人もいるかもしれません。ただ、そうではないんです。 chatGPT すばらしいです。でも、「なぜ」こんなことができるのでしょう？ chatGPT ときどきへましたり、ウソをついたりしますね。でも、「なぜ」こんなことが起きるのでしょう？ この二つの「なぜ」をかんがえるといろいろ面白いので、数年前につまんなくなって戦線離脱したAIの世界に、再び興味を持ち始めています。その意味では、chatGPTに感謝です。 -------------------------------- 「 カテゴリー論的構成的分散意味論 Overview 」 を公開しました。 https://youtu.be/xoSOTv3gYNw ?list=PLQIrJ0f9gMcN2nXtvKCK4ApBaVglV8Drx 資料pdf https://drive.goo...

【「呪文」と「魔法使い」 #3 へのコメント】 以前投稿した「「呪文」と「魔法使い」 #3」への「暗号技術については、嘘ばっかり。ほとんど全部、間違っている。」という僕のコメントが少し乱暴だったと思い、その理由をコメントとして付け加えました。 この投稿は、僕のblogでも公開しましたので、こちらからも参照できます。 https://maruyama097.blogspot.com/2022/12/3_0750247077.html ポスト量子暗号技術については、少し前のものになりますが、2019年6月のマルレク「暗号技術の現在 -- ポスト量子暗号への移行と量子暗号」を参照ください。 https://www.marulabo.net/docs/cipher/   > ポスト量子暗号とは何ですか？ ポスト量子暗号とは、量子コンピュータが現実的に実現されることを前提とした暗号システムのことを指します。ポスト量子暗号は、量子コンピュータが存在するときに使用される予定の暗号システムで、これらの暗号システムは、現在のクラシックな暗号システムが提供するセキュリティレベルを上回ることが期待されます。 ------------------（コメント始まり） そんなに間違ってはいない。 ------------------（コメント終わり） > ポスト量子暗号には、どのような暗号技術があるのでしょう？ ポスト量子暗号には、様々な暗号技術が存在します。一つの例として、量子キー配布に基づく暗号技術があります。これは、量子力学を利用して、通信相手間で安全な鍵を配布する技術です。これにより、通信者は、クラシックな暗号技術を使用して、安全に情報を伝送することができます。 また、別の例として、量子ハッキングを防ぐための暗号技術があります。これは、量子力学に基づいた技術で、量子コンピュータを用いて情報を暗号化することで、量子ハッキングから情報を守ることができます。 他にも、複数の量子暗号技術が提案されていますが、現在ではまだ実用化されているものはありません。技術の発展が進むにつれて、より多くの量子暗号技術が登場することが期待されます。 ------------------（コメント始まり） 「ポスト量子暗号」技術を、量子論を利用した「量子暗号」技術と同一視している。 「ポスト量...

【 Lambek vs. Lambek 】 Lambek には、彼が作り上げた二種類の文法があります。一つは、前回見た CCG( Combinatory Categorial Grammar)で、もう一つが、今回見る Pregroup Grammarです。 CCGの基本的な型は、文を表すsと名詞を表すnの二つだけでしたが、新しいPregroup 文法では、伝統的な英文法のカテゴリーに準拠して、次のように30数個の基本的な型が用意されています。 　π = subject, 　π1 = first person singular subject, 　π2 = second person singular and any plural personal subject, 　π3 = third person singular subject, 　πˆ3 = pseudo-subject, 　s = declarative sentence, a.k.a. statement, 　s1 = statement in present tense, 　s2 = statement in past tense, 　q = question, 　q = yes-or-no question, 　q1 = yes-or-no question in present tense, 　q2 = yes-or-no question in past tense, 　s = indirect statement, 　t = indirect question, 　σ = direct or indirect sentence, 　i = infinitive of intransitive verb, 　j = infinitive of complete verb phrase, 　j = complete infinitive with to, 　ϕ = quasi-sentence with infinitive, 　ψ = quasi-sentence with participle, 　o = direct object, 　o' = indirect object, 　oˆ = pseudo-object, 　n = name, 　n0 = mass noun, 　n1 ...

 【 呪文と魔法使い #4 】 OpenAIの野心的なプロジェクト、Theorem Proverについて質問してみた。 Theorem Prover を自然言語処理のシステムの一部と考えているようだ。 自然言語からの数学の問題の抽出はやさしい。それは、sentence to sentenceの一種だから。 難しいのは、抽出した問題を、数学的に証明すること。それは、言語処理の能力だけでは無理。数学的証明には、CoqやLeanの証明支援システムの助けがいる。実際、Theorem proverは、証明をLean等の言語での形式的証明の形で出力する。 OpenAIのTheorem Proverは、前処理に、GPR-fを利用している。 わからなくなると、英語で答えたり、同じ答えを繰り返す。 質問 9>, 10>に対する答えは、少しまともだが、問題の所在を理解しているか疑問。 詳しくは、丸山の次のセミナーを参照してほしい。「コンピュータ、数学の問題を解き始める」  https://www.marulabo.net/docs/math-proof/ 原論文の著者たちの態度は、真摯なものであり好感が持てた。 先の資料は長いので、次のビデオが簡潔に論文の結論部分について触れている。 「論文の結論にみるその「限界」の認識」 https://youtu.be/ICkF3ocX5JI?list=PLQIrJ0f9gMcPP8LOejaQQlYufAMEQbcdg 1 > OpenAI のGPT-f について教えてください。 GPT-fは、OpenAIが開発した自然言語処理モデルです。 GPT-f（Fine-tuned GPT）は、GPT（Generative Pretrained Transformer）モデルを微調整したもので、さらに高い精度を実現することを目的としています。 GPT-fは、大規模なトレーニングデータセットを用いてトレーニングされることで、高い自然言語理解能力を持っています。 GPT-fを用いることで、自然言語処理タスクをより効率的かつ正確に実行することができます。 2 > OpenAI の Theorem Prover には、GPT-f は利用されていますか？ GPT-fは、OpenAIのTheorem Proverに...

【「呪文」と「魔法使い」 #3 】 暗号技術については、嘘ばっかり。ほとんど全部、間違っている。  > ポスト量子暗号とは何ですか？ ポスト量子暗号とは、量子コンピュータが現実的に実現されることを前提とした暗号システムのことを指します。ポスト量子暗号は、量子コンピュータが存在するときに使用される予定の暗号システムで、これらの暗号システムは、現在のクラシックな暗号システムが提供するセキュリティレベルを上回ることが期待されます。 > ポスト量子暗号には、どのような暗号技術があるのでしょう？ ポスト量子暗号には、様々な暗号技術が存在します。一つの例として、量子キー配布に基づく暗号技術があります。これは、量子力学を利用して、通信相手間で安全な鍵を配布する技術です。これにより、通信者は、クラシックな暗号技術を使用して、安全に情報を伝送することができます。 また、別の例として、量子ハッキングを防ぐための暗号技術があります。これは、量子力学に基づいた技術で、量子コンピュータを用いて情報を暗号化することで、量子ハッキングから情報を守ることができます。 他にも、複数の量子暗号技術が提案されていますが、現在ではまだ実用化されているものはありません。技術の発展が進むにつれて、より多くの量子暗号技術が登場することが期待されます。 > ポスト量子暗号技術は、量子暗号技術と同じものですか？ ポスト量子暗号技術と量子暗号技術は、その概念においては似ていますが、異なる点もあります。 量子暗号技術とは、量子力学を利用した暗号技術のことを指します。これは、量子力学に基づいて、情報を暗号化することで、高いセキュリティレベルを実現する技術です。 一方で、ポスト量子暗号技術は、量子コンピュータが実現されることを前提とした暗号技術のことを指します。これは、量子コンピュータが現実的に実現されると想定されている未来の暗号技術です。ポスト量子暗号技術は、量子暗号技術を拡張したものであり、量子コンピュータの存在により、より高いセキュリティレベルを実現することが期待されます。 したがって、ポスト量子暗号技術は、量子暗号技術の発展系であり、量子コンピュータの存在により、より高いセキュリティレベルを実現することができる技術です。 > ポスト量子暗号の標準化の取り組みは存在しますか？ 現在、ポ...

 【 ランベックのカテゴリー文法 】 今回のセッションは、ランベックのカテゴリー文法の紹介です。 最初にお断りした方がいいと思うのですが、カテゴリー文法の「カテゴリー」は、数学のカテゴリー論の「カテゴリー」とは、直接の関係はありません。 カテゴリー文法の「カテゴリー」は、従来の文法の「品詞(Part of Speech)」概念の拡大です。その拡大された「品詞」をカテゴリーと呼んでいます。 このカテゴリーは、語の連接によって引き起こされる計算上の「型」を持ちます。 カテゴリー文法の型は、文を表す型 s と名詞を表す型 n の二つの基本的な型から、x/y とx\yという二つの演算でリカーシブに定義されます。 型の導出ルールは、基本的には、次の二つです。 　　(x/y)y -> x 　　y(y\x) -> x この二つのルールから、英文法の大きな部分をカバーできると言うのは、驚くべきことです。 ある文が文法的に正しい文であることの証明は、隣り合う語のカテゴリーの型の計算から、最終的に文のカテゴリー s を導出することができるかと言う問題に還元されます。 セッションのビデオとスライドに、いくつかの例を上げておきましたので、ぜひ、そちらを確認ください。 今回のセミナーでは、ことばの文法性と言う構成性を意味の構成性を結びつけようと思っているのですが、文法としてはランベックの文法を使います。ランベックの文法とローベールのFunctorial Semantics を組み合わせるのが、今回のセミナーのアプローチです。 ただ、文法と意味を結びつける方法は、他にもあります。 ランベックのカテゴリー文法は、語に型を割り当てるのですが、それは「型の理論」と深い結び付きを持っています。 「型の理論」としてのランベックの文法は、「型の理論」の Curry-Howard対応を用いて、文の型に、意味を付与することが可能です。これはこれで、文の意味について、とてもエレガントで強力なアプローチを提供します。 残念ながら、こうしたアプローチの紹介は、今回は、割愛しました。 -------------------------------- 「 Combinatory Categorial Grammar 」 を公開しました。 https://youtu.be/8TPBztzF...

【 長い時間の後に 】 言語学に革命をもたらした Chomskyの”Syntactic Structures”が出るのは1957年だ。翌年の1958年、Lambekは、文法の計算ルールは、たった二つの式で表されるという発見をする。 ただ、Lambekの理論は、言語学の学会では受け入れられなかった。1961年のアメリカ数学会でのLambekの発表は、言語学者からの敵意に取り囲まれたらしい。 「ただ、ノーム・チョムスキーとロバート・リースの二人だけが、私に研究を続けるようにと励ましてくれた。それでも私は、チョムスキーの生成-変形文法という新しい波が他のすべてを一掃するのを目の当たりにし（ Chomsky’s generative-transformational grammar sweeping everything else aside )、他のことに目を向けるようになった。」 彼は、言語学の世界は、Chomskyに任せることにして、数学の世界に進む。 1997年、Chomskyは “Minimalist Program” を発表して、それまでの理論を一新する。 1998年、LambekはCategirial Grammarの新しい定式化 Pregroup 文法を発表する。2008年には、Lambekは、それらをまとめた”From Word to Sentence” を発行し、言語学の世界に戻ってくる。 Lambekは言う。 「現在の言語理論に詳しい読者であれば、このモノグラフの根底にある多くの考え方が、過去半世紀にチョムスキーとその学派によって得られた深い洞察に影響を受けていることにお気づきだろう。」 「私はミニマリストのプログラムを完全に理解したとは言えないが、技術的な詳細はともかく、精神的にはpregroup文法はそのようなプログラムを実行する試みと見なすことができると考えている。」 40年以上の時を隔てて、両者は再会することになる。 -------------------------------- 「 ChomskyとLambek 」 を公開しました。 https://youtu.be/49ZgR7F-4P4 ?list=PLQIrJ0f9gMcN2nXtvKCK4ApBaVglV8Drx 資料pdf https://drive.google.com/file...

【 「呪文」と「魔法使い」#2 】 いろんなこと、知っているみたい。 最後は、ダウンした。 22/12/07 > GPT3は、数学の問題を解くことができますか？  GPT-3は言語データを元にトレーニングされており、人間が書いた文章や話した言葉を理解し、自然に会話をすることができるようになっています。したがって、GPT-3は数学の問題を解くことはできません。数学の問題を解くには、専門的な知識やアルゴリズムが必要ですが、GPT-3はそういった能力を持っていません。 > BQPについて知っていますか？ BQP（Bounded-Error Quantum Polynomial-Time）とは、量子計算における概念です。BQPは、量子計算において、ポリノミアル・タイム（多項式時間）内で解ける問題のことを指します。つまり、BQPは多項式時間内に解ける問題の集合を表します。また、BQPには誤差が存在することが前提とされており、その誤差は決まった上限値以下であることが保証されます。BQPの問題は、一般的にNP完全問題（困難な問題の集合）の一部であるとされています。 > 量子コンピュータを使って、NP完全問題を多項式時間で解くことはできますか？ 現時点では、量子コンピュータを使ってNP完全問題を多項式時間で解くことはできません。NP完全問題は、一般的にその解を求めるのに指数時間が必要であるとされています。量子コンピュータは、通常のコンピュータよりも高速に問題を解くことができる可能性がありますが、それでもNP完全問題を多項式時間で解くことは現時点では不可能です。ただし、将来的に量子コンピュータの性能が向上し、NP完全問題を多項式時間で解くことが可能になるかもしれません。 > 量子コンピュータが、普通のコンピュータと比べて、指数関数的な高速化が可能な問題には、何か特徴がありますか？ ひとつは、量子ステートが持つ相互作用や干渉を利用することです。量子ステートとは、量子系の状態を表すもので、複数の量子ビット（qubit）を持つことができます。これらの量子ビットは、相互作用や干渉を通じて、情報を共有することができます。これにより、量子コンピュータは、複数の問題を同時に解くことができ、普通のコンピュータよりも高速に問題を解くことができるようになります。...

【 「呪文」を覚えてズルして楽しようとしたのだが、「魔法使い」は正直者だった 】 ChatGPTがバズっているので、それを利用してセミナーの準備を楽にしようとしたのだが、失敗した。 いろいろ、セミナーをやっているのだが、関連する論文を探して、概要をまとめて、読んで中身を理解するのが、セミナー準備で必要なこと。それを助けてもらおうと思ったのだ。 研究室だと（僕には、そんな経験はないのだが）、教授が大学院生に下働きをさせてコキ使うのと同じこと。あわよくば、セミナーのスライドの下書きも作ってもらえると嬉しいな（そんなこともやらせてる、エライ先生はいるみたいだ）と、都合のいいこと考えていた。 以下そのログ。 -------------------------  > こんにちは こんにちは、私は Assistant と申します。どのようにお手伝いできますか？ 私は大型言語モデルであり、OpenAI によってトレーニングされています。私には最新の情報はありませんが、ご質問にお答えするのに役立つだろうと思います。 > chatGPTの chatGPT は OpenAI が開発した言語生成モデルです。chatGPT は GPT-3 の一部であり、文章を生成するためにトレーニングされました。そのため、chatGPT は会話シナリオや長文を生成することができます。また、人間が書いたような自然な文章を生成することもできます。chatGPT は、テキスト生成タスクや対話システムの構築など、さまざまな用途に使用されます。 > のchatGPTの基本的な論文を教えて下さい。 申し訳ありませんが、私には最新の情報を確認するためのブラウズ機能がありません。そのため、chatGPT に関する基本的な論文をお答えすることはできません。また、私は大型言語モデルであり、人工知能です。人工知能としてトレーニングされているため、私には論文を書く能力はありません。私は、お持ちの質問にお答えすることができるだけの情報しか持っていません。お手数をおかけして申し訳ありません。 ------------------------- 僕の目論見は、最初の最初で失敗したのだが、chatGPT、意外といいやつで正直者だ。 Deep Learning への関心をなくしてから大分経つのだが、今年...

【 ごめんなさい、チョムスキー様 】 今回のセッションでは、チョムスキーのMinimalist Program を紹介します。といっても、10分や15分で、チョムスキーの新しい言語理論を語ることは難しいのです。すごく雑な紹介になっています。すみません、チョムスキー様。 その上、今回のセミナーの「ことばと意味の構成性」を手がかりに、両者をFunctorial Semantics で結びつけるという枠組みには、文法理論としてのMinimalist Programは、使いにくいのです。文句を言ってごめんなさい、チョムスキー様。 では、なぜ、説明しにくい使えないものを、取り上げたのかと言えば、それは、僕がチョムスキーを好きだからです。 彼の言語理論は、昔から今も、とても魅力的です。Minimalist Programの重要な概念に「Merge」と言うのがあるのですが、Merageの獲得を、彼は、こう語ります。 「ある人の上に、その子孫にずっと伝えられる何かが起きた。あきらかに非常に短い間に、その遺伝子の変化はそのグループ内で優勢になった。それは、淘汰上の何らかの有利さがあったに違いない。ただ、それは非常に短い時間に、血縁上の小さなグループで起きた。さて、それは、なんだったのだろうか？  もっとも単純な想定は、それを疑う理由は何もないのだが、我々に起きたこととは、我々は Mergeを獲得したということだ。人は、すでに構成された心の中のオブジェクトをとって、それから、さらに大きな心の中のオブジェクトを構成することを可能にする操作を獲得したのだ。それがMergeだ。それを獲得するやいなや、人は、利用可能な表現や思考の階層的構造の無限の多様性をもつことになる。」 僕らはみな、言語能力という「超能力」を持つ、突然変異したミュータントの子孫なのです。 今年のノーベル賞を受賞したスバンテ・ペーボは、現行人類とネアンデルタール人の交雑が行われていたことを示したのですが、ネアンデルタール人は、人間のような言語能力を持ちませんでした。 きっと、ネアンデルタール人の旦那は、こう感じていたと思います。 「うちのかあちゃんは、頭の中で考えていることを、近くの仲間にテレパシーで伝えられる超能力を持っている」 もっとも、かれはそのことを、うまく表現する手段を持ちませんでした。 ----...

【 ローヴェールが考えたこと 】 このセッションでは、理論とモデルの関係を、カテゴリー論的にとらえなおしたLawvereのFunctorial Semantics を紹介します。 このFunctorial Semantics は、ことばとその意味に、数学的モデルを与えようとする今回のセミナーの基本的なツールとなります。 数学は、一般的には抽象的な議論を積み重ねていきます。カテゴリー論と呼ばれる数学の分野は、そのなかでももっとも抽象的なものかもしれません。 ある人は、カテゴリー論を"general abstract nonsense"な数学だと言いました。それは、一般化と抽象化を進めて、ついには、何の役にも立たないナンセンスなものになってしまった数学がカテゴリー論だということです。 ローヴェールは、現代のカテゴリー論の始祖の一人なのですが、最初から少し違ったことを考えていたと思います。彼は、抽象的な形式を取る数学にも、そうした数学を生み出す「背景」があると考えます。その「背景」は、数学者がある数学理論を、一般化・抽象化を通じてを完成させる、その以前から存在するものです。 そうした「背景」の一つが、集合論です。集合に対する直観は、決して抽象的なものではなく、具体的なものです。ほとんどの数学理論は、集合論の上で解釈されます。 ローヴェールは、カテゴリーCからカテゴリーDへの、構造を保存するようなFunctor Fは、Dの中でCのある「解釈」を与えることに気づきます。このとき、カテゴリーDは、カテゴリーCより、「具体的」だと考えることができます。 カテゴリーCが記号の結合方法を抽象的な”Syntax”として記述し、カテゴリーDは、その具体的な解釈を”Semantics”として与えるということです。 ルールの世界 vs, たとえの世界 理論 vs. モデル syntax vs. semantics こうした流れの上で、 grammar vs. meaning を考えていきたいと思います。 -------------------------------- 「 Functorial Semantics 」 を公開しました。 https://youtu.be/Gt4y5cmqwf8 ?list=PLQIrJ0f9gMcN2nXtvKCK4ApBaVglV8Drx...

【 君は「ゲーデルの完全性定理」を知っているか？ 】 「ゲーデルの完全性定理？」ミスタイプではありません。 「ゲーデルの不完全性定理」は有名なのですが、それは数学的証明の原理的限界を示したもので、何か新しいことを数学的に証明するには、ほとんど役に立たないのです。 ゲーデルには彼の名前がついた「完全性定理」という定理があるのです。ゲーデルの「完全性定理」は、後で述べる「モデル論」の基礎として、20世紀の数学に大きな影響を与えます。 前回、小学生の算数を例に、「ルールの世界」と「たとえの世界」があることを話しました。今回のセッションのテーマである「理論」と「モデル」は、この「ルールの世界」と「たとえの世界」を数学的に定式化したものです。 「理論」の世界では、ある命題φが成り立つのは、この理論の中で、命題φが証明される場合に限ります。「モデル」の世界では、ある命題φが妥当することが、何らかの形で（証明を介さずに）与えられています 理論とモデルの関係を、「すべてのモデルで真になる命題は、一階の述語論理で証明可能である」という形で初めて述べたのは、ゲーデルです。これをゲーデルの「完全性定理」といいます。ゲーデルの完全性定理は、次のようにも言い換えられます。「ある理論が無矛盾ならば、その理論はモデルを持つ。」 理論とモデルの関係を示す、このゲーデルの定理は、とても重要なものです。なぜなら、理論にモデルを与えるということは、理論を拘束する「証明可能性」の束縛をいったん離れて、理論に可能な解釈を与えることだからです。それは、理論の意味を、別の言葉で別の視点で考えることを可能にします。 「非ユークリッド的幾何学の発見」「非カントール的集合論の発見」という、19世紀、20世紀の数学史上の大発見は、それまでの理論の内部の演繹の結果としてではなく、理論に対してそのモデルを考えることで見出されていることに注目しましょう。 それは、理論のモデルを通じて、理論の意味するものを考えるということが、理論の大きな飛躍を生み出すということを示しています。それはまた、理論のモデルと目された実在的対象としての自然に対する認識の飛躍をもたらしました。 詳しいことは、スライドとビデオを参照ください。 ただ、それはまだ、数学や物理学の内部の出来事でした。理論とモデルの関係が、今回...

【 分数の割り算をお子さんにどう教えますか？】 「多様な「意味」の多様な「解釈」を、一つの枠組みで捉えることができるか？」 前回は、こう言う問いで終わったのですが、いくつかの準備なしでは、それにすぐに答えるのは難しいです。 このセミナーの目的の一つは、ことばの構成性と意味の構成性を理論的に結びつけることなのですが、今回のセッションでは、すこし、回り道をしようと思います。 まず、ある表現を、その表現とは異なる形で、その意味を解釈し理解しようとする我々の認識の働きに注目しようと思います。 それは、素朴なものですが、与えられた表現から、その表現が指し示す「意味」を取り出そうとするでプリミティブな試みとみなすことができるからです。 まだ、ことばの構成ルールを記述していないので、ここでは、その構成ルールも意味も、比較的明確な、小学生が習う算数 を例に考えてみようと思います。 2+3=5という計算を、「鉛筆二本と、定規三つで、全部で五つ」というように、具体的なものをあげて「たとえ」で説明することがあります。 前者の「2+3=5」という計算を「ルールの世界」、後者の「鉛筆二本と、定規三つで、全部で五つ」という説明を「たとえの世界」と呼ぶことにしましょう。 「たとえ」の世界は、具体的で現実的で、その世界は、我々の直観と「言葉」によって理解可能な「意味」の世界によって支えられています。 小学校の算数では、初めてであう計算の意味を、基本的には、たとえを通じて理解させます。そして、最終的には、たとえに訴えなくても計算ができるように、計算のルールを習得させることを目的としています。 本当は、ルールだけを覚えてしまえば、それでいいと言うわけではないのです。小学生の6年生になると、分数の掛け算、割り算を学びます。その「たとえ」= 説明自体なかなか難しいものです。 例えば、分数の掛け算だと、次のような例から、分母と分母を掛け、分子と分子をかければいいことが説明されます。 　「1dlで4/5㎡塗れるペンキがあります。2/3dlで何㎡塗れますか。」 絵を描いて、答えが、8/15㎡になることを示してみてください。 分数の割り算 1/2 ÷ 2/3 の説明だと、出てくる例はこんな具合です。 　「鉛筆が12本入ったケースと、3人で1組のグループがあります。この時、ケースの1/2をグループの2/3...

【 8/27 マルレク「暗号技術の現在」講演資料と講演ビデオ公開しました 】  MaruLaboでは、実施したセミナーの講演資料と講演ビデオを公開しています。 今回は、8月27日に行ったマルレク「暗号技術の現在」のセミナーの 講演資料と講演ビデオの公開です。ご利用ください。 講演資料： https://drive.google.com/file/d/172wp0DjNR1BehXyBejI4g_yXgxHT55fE/view?usp=sharing 講演ビデオ再生リスト： https://www.youtube.com/playlist?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz この「暗号技術の現在」の再生リストは、次の四つのビデオから構成されています。 　●  「暗号技術の現在」概説 https://youtu.be/LGkK28M1NPE?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第1部 「現代暗号技術の成立」 https://youtu.be/Rpl4a7Whd7A?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第2部 「ショアのアルゴリズムの発見」 https://youtu.be/itRvFSmIpgc?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz 　●  第3部 「ラティス暗号の時代の始まり」概説 https://youtu.be/K5-YWvcbfVw?list=PLQIrJ0f9gMcNJxKzZgnbw09zYBVrwoCNz このセミナー「暗号技術の現在」の参考資料・ショートムービーは、次のMaruLaboのサイト   https://www.marulabo.net/docs/cipher2/  からアクセスできます。 また、このセミナーは 内容的には、9月のマルゼミ「ラティス暗号入門」に続いています。こちらのページも参照ください。マルゼミ「ラティス暗号入門」： https://www.marulabo.net/docs/ciphe

 　「先生、肉牛と乳牛の違いわかりますか？」 昔、稚内に引っ越した頃、知り合いになった酪農家に聞かれたことがある。 　「食肉になる牛と、ミルクをだす牛の違いでしょ。（まんまだ）」 　「あ、乳牛はメスだけで、肉牛は、どっちもあり。（あたりまえだ）」 そんなことではなかった。 　「肉牛には名前がないけど、乳牛には名前があるんです。」 彼が言うには、肉牛は名前を持たず番号で管理されるが、乳牛は「メリー」とか「ベス」と名前をつけられて、酪農家に大事に育てられるのだという。 そうなんだ。知らなかった。 先日、近所のスーパーで「ホルスタイン」（これは乳牛）の肉が売っていた。珍しい。ローストビーフにして食べたが、新鮮で、ほとんどレアでもとても美味しかった。 宗谷では、人間より牛の数が多い。「宗谷黒牛」というブランドで肉牛も育てているが、それは宗谷岬一帯だけで、ほとんどは乳牛・ホルスタインだ。 大事に育てられていても、乳牛だって、僕ら人間と一緒で、いつか斃れる。ペットの葬式は普通にあるが、牛の葬式は見たことない。というかそんなこと、考えたこともなかったが。 美味しくいただいたお肉には、「個体識別番号」が明記されていた。乳牛にも番号あるじゃないか。 もしも、僕が誰かに食べられるなら、マイナンバーや戒名じゃなく、名前を使って欲しいな。

【 量子コンピュータであることを確認する方法 】 今回は、Mahadevの論文の紹介です。 2018年の論文全てではなく、彼女の仕事の一部である「Quantum Certification Protocol」の紹介です。これは、検証者が対話している相手のコンピュータが、本当に量子コンピュータであるのかをチェックするというプロトコルで、いわゆる「量子優越性」の実証に利用できるものです。 今回紹介するプロトコルとそのバリアントは、彼女のもっと大きな対話プロトコルの「1ラウンド」を形成することになります。「1ラウンド」というのは、今回見たプロトコルを一つのブロックとして、何度も何度も、何ラウンドも、対話を繰り返すのです。 今回見たプロトコルで、「標準基底で測定する」「Hadamard基底で測定する」という選択肢が含まれているのですが、それぞれの選択をSとHで表すと、SとHからなる長い並びで、大きな対話を特徴づけることができます。 彼女は、こうした対話を通じて、相手の量子デバイスを自分の忠実な「量子状態測定器」にかえます。こちらが本論なのですが、今回は、残念ながら触れることができませんでした。 また、いろいろ、説明が足りないところがあることに気づきました。 今日のセッションで、いきなりProver（証明者）とVerifier（検証者）という言葉が出てくるので、少し気になったのですが、Mahadevが対話型証明の手法を使ったということは触れていましたが、こうした数学的な「対話型証明」の設定と、彼女の「対話型証明」の設定には、違いがあります。 数学的な対話型証明の「証明者」は、能力に制限のない「全能者」でしたが、Mahadevの「証明者」は、そうではありません。能力に限界があります。Mahadevの「証明者」の能力は、量子複雑性の言葉で「BQP」と特徴づけられています。（ショアのアルゴリズムが属するクラスです）また、検証者の能力は「BPP」と定義されています。 それは、文脈上は明らかかもしれませんが、きちんと説明したほうがよかったと思っています。なぜなら、問題を明確に定義することが問題解決には不可欠ですから。 -------------------------------- 「 Quantum Certification Protocol 」 を公開しました...

【 LWE暗号の利用 】 Mahadevの論文を読む準備をしています。 Mahadevの量子計算の古典的検証では、古典コンピュータ上で実装可能で、しかし、量子コンピュータでも解読できない暗号、ポスト量子暗号のLWE暗号を利用します。今回のセッションでは、そのことを見ていきます。 基本的には、前回見た Trapdoor Claw-Free Functions (TCF) をLWEを使って定義します。こうして再定義された TCFを Noisy Trapdoor Claw-Free Functions (NTCF) といいます。それについては、セッションのスライドとビデオを参照ください。 ここでは、参考にした 2021年のMahadev達の論文の「はじめに」の部分が、よくまとまっていたので、それを紹介したいと思います。 「この論文では、純粋に古典的な検証者が、多項式時間に制限された一つの量子マシンと相互作用する新しいモデルを考察する。」 「量子デバイスの計算を多項式時間に制限することで、検証者は、ポスト量子暗号、すなわち、古典コンピュータ上で効率的に実装可能であるが、量子コンピュータでも解読できない暗号の基本技術を活用することができる。」 「このモデルでは、「信頼できない量子デバイスが “本当に ”量子的であることを効率的に検証する方法」と「信頼できない量子デバイスから検証可能な乱数文字列を生成する方法」という2つの基本的問題に対する解決策を提案する。」 「一つ目の課題は「量子優越性の証明問題」とも呼ばれ、既存のプロトコルでは、古典的スーパーコンピュータを用いて指数関数的な時間をかけて検証する必要がある。それに対し、本論文のqubit検証テストは、古典的検証者が多項式時間で検証可能な量子性の証明を提供する。」 「信頼できない量子デバイスを扱う難しさの中核には、デバイスの操作を通じて、量子デバイスの内部にあるqubitの構造を持たせることを強制することにある。すなわち、量子デバイスに実際にこの量子ビットを保持させ、また、検証者の要求に応えて、qubitの計測を実行することの難しさにある。」 この最後の部分をどう実現するかが、ポイントになります。 前回のセッションの最後の式、それは、今回のセッションの最後の式とも同じなのですが、claw (x0, x1) に対して、c...

【 clawとは何か 】 Mahadev の論文を読む上で必要な準備をしています。 今回は、Mahadevの暗号の利用で重要な役割を果たしている Trapdoor Claw-Free Functions の話をしようと思います。 Trapdoor というのは、現代の暗号の基本的な構成要素である「一方向関数」のことです。xからf(x)を求めるのは易しいのですが、逆に、f(x)からxを求めるのが難しい関数を、「一方向関数」といいます。 例えば、二つの素数p,qから、その積 N=pqを求めるのは簡単ですが、逆の、二つの素因数を持つ大きな数Nが与えられたとき、Nからその素因数p,qを求めるのは難しいです。そのギャップを利用しようと言うのが、RSA暗号の基本的なアイデアです。 「一方向関数」の上に見た説明に出てくる「易しい」とか「難しい」という言葉、感覚的にはわかると思うのですが、その定義を正確に述べるのは難しいことです。 「易しい」の定義は比較的簡単で、計算に要する時間が「多項式時間」であれば「易しい」と考えることができます。 ただ、「難しい」をその計算に要する時間が「多項式時間」ではなく「指数関数的時間」だとすればいいのでしょうか？ ある計算が、本当に「指数関数的時間」かかることを示すのは、難しいです。ある計算法では、「指数関数的時間」がかかるけど、素晴らしいアルゴリズムが発見されて、その計算が、「多項式時間」で終わる可能性があるからです。 （逆に、「多項式時間」で済む計算にも、「指数関数的時間」が必要な「おばかアルゴリズム」は存在します。おひまなら僕の「計算理論入門 -- 「やさしい計算」と「むずかしい計算」」をご覧ください。割り算を掛け算で計算できるのですが、とても手間がかかります。https://drive.google.com/file/d/1MNnGRkCJAsrR1GeKPyhVMk3VLYfnDhZH/view ） 「一方向関数」が存在すると言うことは、数学的にはキチンと証明されていません。 「易しい」とか「難しい」というけど、それは程度問題で、実際には、「一方向関数」といわれているものも、その逆関数も実は「多項式時間」で計算できる。ただ、そのやり方に気づいていないだけだ。と考えることもできるのですから。 実は、「一方向関数が存在する」という命題は、...