akon0.98bのよっぱらいの戯言

好客三年不変店 好店三年不変客

デモクリトスと量子計算

 

デモクリトスと量子計算

デモクリトスと量子計算

 

 

講義録

https://www.scottaaronson.com/blog/?p=3943

自著に当該書籍の書評を自作自演するイカしている著者

停止性問題を解決しコンヌ問題を否定

Anand Natarajan、John Wright、Zhengfeng Ji、Thomas Vidick、Henry Yuen

 

https://www.gizmodo.jp/2020/02/mip-re.html

 

 

量子計算複雑性理論における量子証明や量子アドバイス

 

 

 

第1章 原子と空間

デモクリトス古代ギリシアの哲学者。

デモクリトスは感覚的体験を原子の運動から説明するために、

知性と感性の対話で表現した。

知性→慣習として甘みがある。慣習として苦みがある。慣習として色がある。しかし、現実には原子と空間しかない。

感性→おろかな知性め!私たちをないがしろにしようというのか。おまえの根拠は私たちから得ているくせにる

 

 

第2章 集合

集合論


一階述語論理
トートロジーな命題
・モーダスポネンス
・同等性の原則
・変数名の変更
・量化記号の消去
・量化記号の追加
・量化記号の規則

非負整数に対するペアノの公理
・ゼロが存在する
・いずれの整数も、最大でも一つの前者しか持たない。

 

集合論の公理
空集合の公理
・外延性の公理
・対の公理
・和集合の公理
・無限公理
・べき集合の公理
・置換公理
・基礎の公理

 

 

第3章 ゲーデルチューリング、その仲間たち

カントールフレーゲゲーデルチューリングチャーチ、コーエン

 

第4章 心と機械

一定の機械的なプロセスが人の心も支配しているか

 

第5章 原始計算複雑性

 

第6章 P、NP、その仲間たち

PNP

 

第7章 ランダムネス

 

第8章 暗号

 シャノンの情報理論的安全性
安全な暗号法とは、平文サイズ≦鍵サイズ

 

第9章 量子

QWERTYアプローチ、つまり、歴史的な経緯で説明順が決まっている
量子学の教え方によって、複雑で難しいという評判が付いてしまった。
負符号を許すような確率法則の一般から教えたほうが良い。

 

 

第10章 量子計算

量子計算理論→量子力学計算複雑性理論の融合

 

BQP
・初期化
・変換
・測定
・一様性

可逆計算


デイヴィッド・ドイッチュのパラレルワールド
非自明な量子コンピュータを作れたらパラレルワールドの存在を示すことになる。

タイムパラドックスを回避する方法
https://wired.jp/2010/07/29/%E3%82%BF%E3%82%A4%E3%83%A0%E3%83%91%E3%83%A9%E3%83%89%E3%83%83%E3%82%AF%E3%82%B9%E3%82%92%E5%9B%9E%E9%81%BF%E3%81%99%E3%82%8B%E6%96%B9%E6%B3%95/

 

第11章 ペンローズ

脳は単なる量子コンピュータではなく、量子重力コンピュータであり、チューリング計算不能な問題を解くことができる。そして、これをゲーデル不完全性定理を使って示せるといっていることについての問題点を指摘する。

 

154

 

第12章 デコヒーレンスと隠れた変数

コヒーレンス熱力学第二法則による有効的な時間の矢

隠れた変数理論
量子力学に特徴的な確率的な性質を、実験者が観測できない変数を導入して説明する理論
・フロー理論
シュレーディンガーの理論
・ボーム解釈

隠れた変数理論に必要と思われる性質
・状態からの独立性
・時間スライスに関する不変性
・基底からの独立性
・相対論的因果律

隠れた変数を否定する(no-go)定理
ベルの定理
隠れた変数が存在するなら、ある種の実験で結果は必ずベルの不等式を満たすことを示した。一方、量子もつれが正しければベルの不等式は破られる。
・コッヘン=シュペッカーの定理

 

第13章 証明

確率的証明

ゼロ知識証明

PCP(確率的検査可能証明)

隠れた変数理論の計算複雑性

 

第14章 量子状態はどれほど大きいか

量子状態のサイズ

量子状態は指数関数的な量の古典情報を暗号化できるか

量子証明や量子アドバイス

 

第15章 量子計算に対する懐疑論

 

第16章 学習

ヒュームの帰納

計算論的学習理論、量子状態の学習可能性

 

第17章 対話型証明、回路下界、その他

古典的および量子的対話型証明系

IP=PSPACE定理、QIP=PSPACE定理

 

第18章 人間原理で遊ぶ

人間原理

終末論法

事後選択の量子計算

PostBQP=PP定理

 

第19章 自由意志

ニューカムパラドックス、自由意志

コンウェイとコッヘンの自由意志定理

アインシュタインが認めた乱数→ベルの不等式

 

第20章 タイムトラベル

時間的閉曲線を持つ古典的なコンピュータや量子コンピュータPSPACEの計算パワーを生む

 ・自分を極低温に冷やして凍らせ、後で温めて溶かす

・相対論的スピードで旅をする。

ブラックホールの事象の知平面に近づく

 

第21章 宇宙論と計算複雑性

宇宙論

ダークエネルギー

ベッケンシュタイン境界

ホログラフィック原理

 

第22章 質問タイム

量子力学の破綻

ブラックホールとファズボール(毛玉のようなふわふわした球状のもの)

神託はどこで登場するか。

→定義すればよい。

コンピュータ科学はなぜ物理学科の一分野ではないか。

→歴史的な経緯だから

 

目次

第1章 原子と空間

第2章 集合

第3章 ゲーデルチューリング、その仲間たち

第4章 心と機械

第5章 原始計算複雑性

第6章 P、NP、その仲間たち

第7章 ランダムネス

第8章 暗号

第9章 量子

第10章 量子計算

第11章 ペンローズ

第12章 デコヒーレンスと隠れた変数

第13章 証明

第14章 量子状態はどれほど大きいか

第15章 量子計算に対する懐疑論

第16章 学習

第17章 対話型証明、回路下界、その他

第18章 人間原理で遊ぶ

第19章 自由意志

第20章 タイムトラベル

第21章 宇宙論と計算複雑性

第22章 質問タイム