另一個角度看量子計算：與彈球碰撞的驚人關聯

選自acm.org

作者：Don Monroe

機器之心編譯

編輯：Panda

從看似無關的主題中發現某種共同特質是件挺有意思的事，而且說不定會帶來理解事物的新方式。本文探討了著名量子算法 Grover 搜索算法與完全彈性碰撞這一問題之間的關聯。

在科學和數學領域，許多看似無關的主題之間存在某些共同的特質。這樣的相似性有時能同時為這兩個領域帶來重大的進展，不過很多時候這樣的相似性只是單純地很有趣。

去年 12 月，谷歌一位物理學家 Adam Brown 發現：一種基本量子計算算法與一種用於計算無理數 π 的奇妙方法之間存在一種異常精確的關係。「目前來說這個發現只是單純很有意思，但我們希望找到思考事物的新方式，人們未來也許能使用這種方式尋找之前無法看到的聯繫。」Brown 說，「對於一個現象，多種思考角度是非常有用的。」

在網上發布的一篇預印本論文中（目前尚未完成同行評議），Brown 表明兩個看似無關的問題之間存在某種數學上的相關性。其中一個問題是為量子計算機提出的著名的 Grover 搜索算法，理論上它比任何經典搜索算法都更快。另一個問題則是一個出人意料的過程：通過統計理想彈性球的碰撞次數來得到任意精度的 π 值。

量子算法

量子計算要用到量子比特，每個量子比特可以同時表示兩個狀態，而它們通常用離子或超導迴路構建。從原理上看，一定數量的量子比特能表示和操作比經典比特多指數級數量的組合。之前，人們覺得利用這種概率性質來進行計算似乎是一場白日夢，但是研究者還是成功設計出了可從量子比特提取有用信息的算法。

第一個量子算法是彼得 · 秀爾（Peter Shor）1994 年提出的秀爾算法，當時他正在新澤西州的貝爾實驗室工作。秀爾算法能高效地將整數分解為質因數，也由此給現今的許多加密方案帶來了潛在的威脅。該算法的訣竅是將整數分解重構為一個新問題：確定一個序列的重複周期。這本質上是一種傅立葉變換，通過在量子比特的全集上使用全局運算就能找到這個序列。

第二個基本算法則是 Lov Grover 於 1996 年在貝爾實驗室獨立提出的 Grover 算法，它有著大不一樣的工作方式。「秀爾算法和 Grover 算法是兩種最典型的量子算法。」德克薩斯州大學奧斯汀分校的 Scott Aaronson 說，「即便在今天，我們所知的絕大部分量子算法都要麼受秀爾算法啟發，要麼受 Grover 算法啟發，要麼同時受兩者啟發。」

Grover 算法通常被描述為一個資料庫搜索過程，即檢查一個包含 N 項的列表，找到其中滿足所需性質的一項。如果該列表已按某種標籤進行了排序（比如按字母順序排列），那麼通過不斷連續減半地切分列表，就可以找到任意標籤；這個過程所需的查詢次數為 log₂N。但是，對於無序列表，檢查完每一項平均需要 N/2 步（有可能需要多達 N 步）。

和其它量子算法一樣，Grover 算法也會同時操作整個量子比特集，同時保留它們之間的關係（過早地查詢任意量子比特會使其狀態確定下來，從而將其轉換成一個普通比特，這會消除量子計算所帶來的優勢）。但是，Grover 的研究表明：通常僅需次全局操作就能找到所需的項。

這樣的提升沒有秀爾算法所帶來的提升多，因為秀爾算法帶來的是指數級的提升。但 Brown 強調說：Grover 算法可應用於更一般的、非結構化的問題。

Grover 算法的計算首先是對所有 N 個量子比特進行均等混合。然後，該算法會反覆讓所有量子比特進行兩種輪流交替的操作。第一個操作是嵌入該目標：它會反轉一個特定但未知的比特的狀態。該任務的目標是確定哪個比特被修改了，但方法不是觀測所有比特。第二個操作不需要有關該目標的任何信息。Grover 發現每次重複該序列時，該目標在混合結構中的權重都會增大（儘管這無法被觀測到）。重複了適當的次數之後，此時執行一次觀測，則有非常高的可能性能得到正確結果。

彈性球

這些複雜的量子操作似乎和彈性球沒有關係。但是，Brown 在研究與 Grover 算法相關的問題時看到了數學科普者 Grant Sanderson 做的一個動畫，讓他注意到了兩者之間的相似性。Brown 在自己的論文中表明這兩個問題之間存在一種精準的映射關係。

Sanderson 的動畫解釋了東伊利諾伊大學數學家 Gregory Galperin 在 2003 年描述的一個出人意料的觀察結果。在論文《Playing Pool with π》中，他想像有兩個能在水平面上無摩擦地運動的理想彈性球，它們能彼此以及與左側的牆發生完全彈性碰撞（即總動能守恆）。

如果右側的球向左撞向左側更輕的靜止球，則左側小球會向左運動，同時右側大球的速度並不會變慢多少。小球會在撞上牆後反彈，然後再次撞擊大球，這個過程會重複很多次。最後，這樣的碰撞會讓大球調轉方向，直到它最終以比小球更快的速度向右遠去。

在此之前，碰撞的次數會隨著大球與小球的質量比的增大而變多。如果兩個球的質量相等，碰撞會發生 3 次：第一次右側球會把所有運動轉移給左側球，左側球則在撞牆後反彈，然後又通過碰撞將動量完全返還給右側球。如果大球的質量是小球的 100 倍，則該過程會發生 31 次碰撞。如果這一質量比為 10000，則會有 314 次碰撞。根據計算（這個實驗無法實際進行），質量比每增加 99 倍，碰撞的次數除以質量比的平方根後就能讓 π 的數字表示多一位數：3.141592654...。

當 Brown 偶然看到 Sanderson 的動畫（動畫裡使用的方塊）時心裡正想著 Grover 算法，然後他發現兩者之間存在顯著的相似性。舉個例子，Grover 算法的兩個量子操作可以分別對應於球球碰撞和球牆碰撞。質量比對應於資料庫的大小。此外，最終的結果是：操作數（或碰撞數）正比於 π 以及資料庫規模（質量比）的平方根。（還有兩個 2 的因數只是反映了兩個問題的表記方法的差異）。

除了在這兩種如此不同的系統之間存在驚人的聯繫之外，π 在這兩種情況中究竟發揮了怎樣的作用？當然，π 這個無理數最出名的地方是它是圓的周長與其直徑的比，不過它也出現在橢圓以及球等更高維對象的對應比值中。定義球的方法之一是通過代數在橫縱坐標 x 和 y 給出限定條件：半徑為 r 的圓上的點滿足限定條件：x² + y² = r²。

事實證明，不管是上面的碰撞問題，還是 Grover 算法，都具有這種形式的限定條件。球的碰撞或操作量子系統對應於由這些限定條件定義的圓上的旋轉。

例如，對於兩個質量為 m（速度為 v_m）和 M（速度為 v_M）的彈性球，彈性碰撞會保留兩者的總動能。完全保留大球的動能需要在坐標 v_m 和 v_M 的平面中進行 180° 轉向，而 180° 就等於 π 弧度。

類似地，在量子系統中，觀察到某個特定結果的概率正比於對應該結果的「波函數」的平方。目標與其它所有結果的概率（振幅平方）之和必然為 1。

歷史上的其它關聯案例

也許有人要問：「這能針對世界的本質提供重要見解嗎？還是說只能滿足一點好奇心？」Brown 表示，「也許對 Grover 算法能為我們提供有關世界本質的重要知識，也許彈性球研究是為了滿足好奇心，或許將它們聯繫起來的原因更多的是第二個，而不是第一個。」

儘管如此，有時候這樣的聯繫還是能引出一些重大進展，在物理和數學歷史中已有為數不少的案例。舉個例子，物理學家已經投入了 20 多年時間探索強相互作用的多粒子量子系統與整合了高一個維度的彎曲時空的引力模型之間的驚人對應關係。甚至時空中的蟲洞有望解答與量子力學中遠距離粒子「糾纏」相關的悖論。

數學常常通過與不同領域之間的聯繫得到發展。例如，涉及一個簡單方程的整數解的費馬大定理直到幾個世紀之後才得到證明，而使用的方法來自「橢圓曲線」。再舉個例子，計算機科學家在一月份證明了一個與阿蘭 · 圖靈的可決定計算概念有關的定理，這又進一步給其它看似無關的領域帶來了衝擊。

在 Aaronson 看來，Grover 算法與彈性球之間的「這種對應關係儘管很精準，但可能也就是個有趣的類比（就是說我不知道如何使用這個關係來推導任何與 Grover 算法有關的未知性質）。但這樣已經很好了。」