2012-09-07

古典問題在量子設置中變成不可判定 (Updated)

Classical problem becomes undecidable in a quantum setting
http://phys.org/news/2012-07-classical-problem-undecidable-quantum.html

By Lisa Zyga, July 9, 2012

(Phys.org) -- 身為一種「事物在量子與古典體系中的運作有多麼不同」的證明(testament),物理學家已發現,有種問題在古典情境(context)中能輕易解決,卻無法在量子情境中完全被解決。物理學家認為,相同情況適用於許多其他類似的問題,那可能會影響量子運算應用以及描述微觀系統的量子多體模型(quantum many-body models)。

這些物理學家,來自德國柏林自由大學的 Jens Eisert 與 Christian Gogolin,以及來自加拿大安大略省滑鐵盧市,Perimeter Institute for Theoretical Physics (圓周理論物理研究所)的 Markus P. Muller,已將他們的研究發表在最近一期的 Physical Review Letters 上。

"我們提出一種存在於量子力學的新花招(novel twist),缺乏其古典相對物:我們能非常自然的證明,與量子力學有關的「合理問題」,有趣的是,是不可判定的(undecidable)," Eisert 表示。"同時,相應的古典問題是可判定的(decidable)。"

所問的問題涉及一種測量裝置,根據測量的結果,那產生多重輸出的任一種。此輸出狀態接著成為「輸入」,反饋到裝置中,導致新的輸出,如此週而復始。問題是,那裡是否存在任何「不曾存在的測量結果的有限序列(finite sequences of measurement outcomes that never occur)」。

"像這樣的問題很簡單 -- 只是問:是否有某些結果能出現在量子測量中,"  Eisert 說。

當使用某種古典測量裝置時,物理學家證明,他們總能找到一種演算法,能回答是否有任何「零機率(zero probability)」的輸出存在。故在古典環境中,此問題是可判定的。

然而,當使用某種量子測量裝置時,物理學家證明,不可能有一直都能提供正確答案的演算法,所以此問題變成不可判定的。科學家解釋,不可判定性來自於量子裝置中的干擾,那暗示(至少在此情境中)不可判定性顯然是一種真正的量子特性。

"在某種程度上,不管某些過程是否為量子力學所允許,某人能說,那是不可判定的;一種相當令人費解的情況," Eisert 說。

為了獲得這種結論,物理學家轉向一個眾所皆知的計算問題,稱為停機問題(halting problem),那在 1936 年由 Alan Turing(計算機之父)所引介。此問題是為了判定,某個程式在接受輸入後,是否最終能結束執行,即「halt」,或此程式是否將永遠執行下去。 Turing 證明,對於所有可能的輸入,並不存在能解決此問題的單一演算法,故此問題是不可判定的。在停機問題的「勢力範圍」內,它與數學中,Godel 著名的不完備定理相關。

在目前的研究中,物理學家已證明,若此量子測量問題對付的是「不可能的輸出」,且總能被某些演算法所解決,則必定存在某種演算法,能解決停機問題的每一個例子 -- 而 Turing 已證明那是不可能的事。

除了成為複雜量子世界的一個有趣例子之外,這些結果也能被擴展成「證明這些問題在其他領域中是不可判定的」。例如,有種類似的數學描述 -- 那適用於用在測量式(measurement-based)量子運算裝置中的量子導線 -- 指出,沒有演算法能確認「將不曾發生的測量結果」的順序。不可判定性也許常出現在多體問題中。在這些例子中,若知道某些問題是不可判定的,就能使這些物理學家對這些問題有新的觀點。

"我們在量子物理與電腦科學間建立一種新奇的連結:某些問題不僅在計算上難以判定(例如尋找 glassy quantum many-body models [光滑量子多體模型] 的基態,可以說是 QMA [量子梅林--亞瑟] 級的困難),身為一種原則問題(a matter of principle),以全世界所有可用的計算能力與執行時間,也絕對不可能去判定!" Eisert 說。 "一部嘗試要這麼做的電腦只會一直執行下去。這令人驚訝的事實也強調了量子力學先前不為人知的新奇面向。此外,那證明,不僅只有電腦科學中的 Turing 機學術問題可以是「不能判定的」,事實上,在自然界、物理學與直覺上也能夠如此。"

在未來,這些物理學家計畫要探索將「不可判定性」當成一種用於驗證構想之「驗證工具(proof tool)」的可能性。

"那完全是一種強大的新驗證工具," Eisert 說。"譬如,不管某種狀態是否可提取(distillable,譯註:量子力學術語),如果某人能發現不可判定的有趣結果,那麼某人將以一種非常不直接的方式,解決了「NPT bound entanglement 的存在(一個涉及量子資訊理論的問題)」這個存在已久的問題。"

"這裡有許多刺激的研究得完成。接下來,我們也許更能明白,對物理學理論而言,量子力學的真意(really says)是什麼,大自然對此的真意又是什麼。"

※ 把一些奇怪的譯文做了修改。相關報導:

* Quantum measurement occurrence is undecidable
http://link.aps.org/doi/10.1103/PhysRevLett.108.260501
J. Eisert, M. P. Muller, and C. Gogolin
Phys. Rev. Lett. 108, 260501 (2012) [5 pages]
doi: 10.1103/PhysRevLett.108.260501
※ 更新,關於 undecidability 的早期論文還包括下列二篇:

* Are problems in Quantum Information Theory (un)decidable?
http://arxiv.org/abs/1111.5425
Michael M. Wolf, Toby S. Cubitt, David Perez-Garcia
arXiv:1111.5425v1 [quant-ph]
* Decidable and undecidable problems about quantum automata
http://arxiv.org/abs/quant-ph/0304082
Vincent D. Blondel, Emmanuel Jeandel, Pascal Koiran,
Natacha Portier
arXiv:quant-ph/0304082v1
* 量子波函數代表現實嗎?
* 量子位元與膜共享令人驚訝的特點

沒有留言: