標籤：

有哪些用計算複雜性理論考慮自然界中的問題的例子?

01-04

曾經聽過王正漢老師在某次 Talk(http://zimp.zju.edu.cn/~xinwan/topo06/talks.html) 提及他們做 Topological Quantum Computing 的動機之一是, 當時有人用 Computer Science 的觀點考慮了 Jones Polynomial 的計算問題, 並歸到了某個複雜度類中. 結果很出人意料, 低階的情況下只有 n = 5的時候很難處理(可能有記憶錯誤). 之後他們設計了一個基於量子場論的計算模型來解決這一問題, 這就是後來的 Topological Quantum Computing.

我猜想這樣的例子應該還有. 譬如說可能存在量子模擬(比如計算化學)中的一些問題, 我們能夠證明在滿足一定約束條件下, 特定的一類問題能夠歸到某個能夠有效處理的計算複雜性類之中. 感覺應該有一些很有意思的結果.

自己答一發好了. 包括 Feynman 關於量子模擬的想法(嗯, 就是湊數的...), QMA和QMA-Complete, 以及 Quantum Hamiltonian Complexity.

Richard Feynman 最初關於量子模擬和量子計算機的想法, 其實就是個例子. 雖然我不知道 Feynman 想出這東西的時候, 自己是否知道計算複雜性相關的結果. 不過 Feynman 後來居然寫過一本計算理論教材:

甚至在最後還請人過來講當時還算新奇的 VLSI. 我猜要是 Feynman 在世的話, 肯定會寫本量子計算教材, 從兩邊理論講到實踐......

接著來. 上世紀末, Alexei Kitaev 在量子計算複雜性里最重要的工作之一, 提出 QMA (Quantum Merlin-Arthur 作為 NP 的量子對應). 以及找到第一個 QMA-Complete 問題, k-local Hamiltonian Problem.

非常巧合的是, k-local Hamiltonian Problem 對應的就是 MAX-SAT. 具體來說, 把 local Hamiltonian 對應於 SAT 問題裡面的 clause, 判斷 k-local Hamiltonian 的基態能量是否小於 a 或者大於 b 對應於判斷滿足條件 clause (比如3SAT 對於的是類似x_1 wedge eg x_2 wedge x_3的東西)的個數.

我想關於 QMA-Complete 可讀性最好的材料應該是 Dorit Aharonov 的這篇(quant-ph/0210077). 大概需要熟悉 Cook 定理的證明, 以及一點點量子力學背景.

上面的想法非常有趣, 能直接對應起來想必其中的聯繫也不僅僅這麼簡單, 畢竟它給出了量子計算複雜性和凝聚態物理之間的一些聯繫. 更進一步的 topic 是 Quantum Hamiltonian Complexity(berkeley.edu 的頁面), 以下照搬 Simons Institute 的介紹:

At one end of the spectrum, quantum Hamiltonian complexity expands the scope of computational complexity theory in new directions by asking three fundamental questions:

  • Can ground states of 「natural」 quantum systems be described succinctly?
  • Does the exponential complexity of general quantum systems persist at high temperature?
  • Is the scientific method sufficiently powerful to understand general quantum systems?

Each of these questions can be formulated as a precise computational question. The first question translates to a beautiful conjecture in condensed matter theory called the area law, which states that the ground state of any local Hamiltonian satisfies the property that the entanglement entropy across any cut is bounded by the edge expansion of the cut. The second question can be formalized as asking whether the quantum analog of the PCP theorem is true. And the third question can be formulated in terms of the power of an interactive proof system with a polynomial time quantum prover interacting with a polynomial time classical verifier.

很遺憾, topic 的複雜程度大大超過了我的能力範圍, 涉及到量子糾纏, area law, quantum game, quantum interactive proof system, quantum PCP conjecture etc.

不過我第一次看到這三個問題的驚訝程度, 真是一點都不亞於第一次看到 Scott Aaronson 的 Research Statement 裡面的三個問題. 很難想像, 幾乎都起源於上世紀三十年代的可計算性理論(以及上世紀七十年代的計算複雜性理論)和量子力學, 會在五十年後找到如此巧妙的聯繫.

有個挺相關的問題，有人試圖用computational complexity來解釋物理學中的black hole firewall paradox。具體可以看scott aaronson 的博客：Shtetl-Optimized

有人證明了尋找三維Ising model基態的問題是NP-co的，所以三維Ising model的解析解不太可能找得到。

http://www.brown.edu/Research/Istrail_Lab/papers/p87-istrail.pdf

推薦閱讀：

※什麼樣的人適合學計算化學（理論化學）？前景如何？
※你參與過/用過/看過的與計算化學相關的python項目？
※側重於材料/納米方向的理論計算化學課題組（美國）推薦？
※理論計算化學的方向的學生以後的出路有些什麼？
※為何知乎上活躍的化學工作者大多是計算化學，而不是其他化學領域？

TAG:物理學 | 計算化學 | 計算複雜性理論 |