No exponential search conjecture

最近看某個影片 有感而發 當作murmur

人類是很會想像的生物，會希望世界上如果有某些科技就好，像是時光機，永動機，煉金術，而人類發現這些東西做不出來是因為某些very deep的物理定律 限制了這些東西的存在性
像是時光機 因為被狹義相對論，永動機違反熱力學第二定律..之類
但這並沒有阻止人類有一天可能會征服宇宙 但什麼可能阻止人類征服宇宙 但一個可能的原因是computational complexity

TCS 一個deep conjecture 教做
Extended church turing thesis (ECT)
他的概念大概是說 現實當中 物理世界當中 能做出來的計算模型
都跟turing machine 等價 或是換個說法 人類世界能做出來的電腦 或是計算工具 最多最多 就只turing machine
能有效率解出來的問題 就是class P (polynomial time)。 但有另一個famous 意思是 有效率可以檢驗的問題 教做NP
famous question 就是 P vs NP。目前多數人conjecture NP當中最難的問題 np complete 沒有 polynomial time algorithm at least in worst case。許多科技上重要的問題都是NPC。

但再1970年代 feynman 提出 量子電腦這個可能 1995 shor's algorithm 發現 量子電腦可以factoring 大大衝擊了 ECT 於是就有了一個complexity class 教做BQP bounded error quantum polynomial time。BQP 被認為超過P 而且也有不少 tcs 理論的evidence like P vs NP 佐證這個猜想 這也就表示ECT maybe false
因為真實世界能造出的物理電腦 確實不僅限於P 而可以擴張到BQP

what about BQP vs NP ? 這問題當然也是未解 但多數的人認為BQP 沒辦法解NPC的問題 簡單說量子電腦不能幫助解np complete,
至少不能exponential speed up 但可以有quadratic 就是grover algorithm

但你可以問 why 不行? 2009 一個結果是 如果量子力學不是linear的 則量子電腦可以解NPC問題 in polynomial time 大致原因是因為量子計算 是 unitary evolution 所以你每次轉換 角度都要保持 但如果可以不linear 則可以放大角度 這樣就可以讓你把1/exp 小的角度 快速放大 你就可以解NPC 問題 in poly time, so sad

how about 其他科幻類型的電腦? 另一個常見的東西是封閉時間曲線
closed time like curve 可以想成是時光隧道 那會產生祖父悖論 殺了阿公自己就不會出生 但實際上可以這樣model 可以想像 宇宙會自動找出一個機率上的不動點 讓一切自洽 剛剛上述的example 就是 你殺掉祖父with 機率1/2 則你出生機率1/2 一切都是consistent
可是這個計算其實是很困難的 給一個很大的隨機矩陣 要找他的不動點 可以證明 如果存在這樣的機制 你可以encode 一個NPC 問題 變成找不動點 只要把這個NPC問題 丟進去時光隧道 就可以得到他的解 in poly time 可是時光機理論上是不存在的 so sad

另一個結果是 如果量子力學不是2-norm, 是4-norm, 6-norm...則BQP 會變超級強大 變成PP 也就是可以cover NP, 可是量子力學是2-norm, so sad

大家從上述例子都可以看到 這些有趣的東西 似乎都會implies 你可以解出NPC問題in poly time 反過來說 什麼東西governed這個世界?
如果我反過來說 世界有一條定律是 no matter what
這個物理世界不能讓你造出一個機制 可以解 NP complete 問題in poly time

這個principle 會告訴你 量子力學必須是線性unitary 且必須是2 norm
且 這個世界不可以有時光機 ....
你會得到許多物理上很deep的statement

如果世界是被創造的 有什麼東西是狠狠的鐵則被刻印在這個宇宙之內 或許有一條就是這樣 No exponential search conjecture
而這樣的東西 則阻止人類持續發展科技 而且也同時限制了諸多物理定律