從看似無(wú)關(guān)的主題中發(fā)現(xiàn)某種共同特質(zhì)是件挺有意思的事，而且說(shuō)不定會(huì)帶來(lái)理解事物的新方式。本文探討了著名量子算法 Grover 搜索算法與完全彈性碰撞這一問(wèn)題之間的關(guān)聯(lián)。

在科學(xué)和數(shù)學(xué)領(lǐng)域，許多看似無(wú)關(guān)的主題之間存在某些共同的特質(zhì)。這樣的相似性有時(shí)能同時(shí)為這兩個(gè)領(lǐng)域帶來(lái)重大的進(jìn)展，不過(guò)很多時(shí)候這樣的相似性只是單純地很有趣。

去年 12 月，谷歌一位物理學(xué)家 Adam Brown 發(fā)現(xiàn)：一種基本量子計(jì)算算法與一種用于計(jì)算無(wú)理數(shù) π 的奇妙方法之間存在一種異常精確的關(guān)系?！改壳皝?lái)說(shuō)這個(gè)發(fā)現(xiàn)只是單純很有意思，但我們希望找到思考事物的新方式，人們未來(lái)也許能使用這種方式尋找之前無(wú)法看到的聯(lián)系?！笲rown 說(shuō)，「對(duì)于一個(gè)現(xiàn)象，多種思考角度是非常有用的?！?/p>

在網(wǎng)上發(fā)布的一篇預(yù)印本論文中（目前尚未完成同行評(píng)議），Brown 表明兩個(gè)看似無(wú)關(guān)的問(wèn)題之間存在某種數(shù)學(xué)上的相關(guān)性。其中一個(gè)問(wèn)題是為量子計(jì)算機(jī)提出的著名的 Grover 搜索算法，理論上它比任何經(jīng)典搜索算法都更快。另一個(gè)問(wèn)題則是一個(gè)出人意料的過(guò)程：通過(guò)統(tǒng)計(jì)理想彈性球的碰撞次數(shù)來(lái)得到任意精度的 π 值。

量子算法

量子計(jì)算要用到量子比特，每個(gè)量子比特可以同時(shí)表示兩個(gè)狀態(tài)，而它們通常用離子或超導(dǎo)回路構(gòu)建。從原理上看，一定數(shù)量的量子比特能表示和操作比經(jīng)典比特多指數(shù)級(jí)數(shù)量的組合。之前，人們覺(jué)得利用這種概率性質(zhì)來(lái)進(jìn)行計(jì)算似乎是一場(chǎng)白日夢(mèng)，但是研究者還是成功設(shè)計(jì)出了可從量子比特提取有用信息的算法。

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

第二個(gè)基本算法則是 Lov Grover 于 1996 年在貝爾實(shí)驗(yàn)室獨(dú)立提出的 Grover 算法，它有著大不一樣的工作方式?！感銧査惴ê?Grover 算法是兩種最典型的量子算法。」德克薩斯州大學(xué)奧斯汀分校的 Scott Aaronson 說(shuō)，「即便在今天，我們所知的絕大部分量子算法都要么受秀爾算法啟發(fā)，要么受 Grover 算法啟發(fā)，要么同時(shí)受兩者啟發(fā)?！?/p>

Grover 算法通常被描述為一個(gè)數(shù)據(jù)庫(kù)搜索過(guò)程，即檢查一個(gè)包含 N 項(xiàng)的列表，找到其中滿足所需性質(zhì)的一項(xiàng)。如果該列表已按某種標(biāo)簽進(jìn)行了排序（比如按字母順序排列），那么通過(guò)不斷連續(xù)減半地切分列表，就可以找到任意標(biāo)簽；這個(gè)過(guò)程所需的查詢次數(shù)為 log₂N。但是，對(duì)于無(wú)序列表，檢查完每一項(xiàng)平均需要 N/2 步（有可能需要多達(dá) N 步）。

和其它量子算法一樣，Grover 算法也會(huì)同時(shí)操作整個(gè)量子比特集，同時(shí)保留它們之間的關(guān)系（過(guò)早地查詢?nèi)我饬孔颖忍貢?huì)使其狀態(tài)確定下來(lái)，從而將其轉(zhuǎn)換成一個(gè)普通比特，這會(huì)消除量子計(jì)算所帶來(lái)的優(yōu)勢(shì)）。但是，Grover 的研究表明：通常僅需次全局操作就能找到所需的項(xiàng)。

這樣的提升沒(méi)有秀爾算法所帶來(lái)的提升多，因?yàn)樾銧査惴◣?lái)的是指數(shù)級(jí)的提升。但 Brown 強(qiáng)調(diào)說(shuō)：Grover 算法可應(yīng)用于更一般的、非結(jié)構(gòu)化的問(wèn)題。

Grover 算法的計(jì)算首先是對(duì)所有 N 個(gè)量子比特進(jìn)行均等混合。然后，該算法會(huì)反復(fù)讓所有量子比特進(jìn)行兩種輪流交替的操作。第一個(gè)操作是嵌入該目標(biāo)：它會(huì)反轉(zhuǎn)一個(gè)特定但未知的比特的狀態(tài)。該任務(wù)的目標(biāo)是確定哪個(gè)比特被修改了，但方法不是觀測(cè)所有比特。第二個(gè)操作不需要有關(guān)該目標(biāo)的任何信息。Grover 發(fā)現(xiàn)每次重復(fù)該序列時(shí)，該目標(biāo)在混合結(jié)構(gòu)中的權(quán)重都會(huì)增大（盡管這無(wú)法被觀測(cè)到）。重復(fù)了適當(dāng)?shù)拇螖?shù)之后，此時(shí)執(zhí)行一次觀測(cè)，則有非常高的可能性能得到正確結(jié)果。

彈性球

這些復(fù)雜的量子操作似乎和彈性球沒(méi)有關(guān)系。但是，Brown 在研究與 Grover 算法相關(guān)的問(wèn)題時(shí)看到了數(shù)學(xué)科普者 Grant Sanderson 做的一個(gè)動(dòng)畫，讓他注意到了兩者之間的相似性。Brown 在自己的論文中表明這兩個(gè)問(wèn)題之間存在一種精準(zhǔn)的映射關(guān)系。

Sanderson 的動(dòng)畫解釋了東伊利諾伊大學(xué)數(shù)學(xué)家 Gregory Galperin 在 2003 年描述的一個(gè)出人意料的觀察結(jié)果。在論文《Playing Pool with π》中，他想象有兩個(gè)能在水平面上無(wú)摩擦地運(yùn)動(dòng)的理想彈性球，它們能彼此以及與左側(cè)的墻發(fā)生完全彈性碰撞（即總動(dòng)能守恒）。

如果右側(cè)的球向左撞向左側(cè)更輕的靜止球，則左側(cè)小球會(huì)向左運(yùn)動(dòng)，同時(shí)右側(cè)大球的速度并不會(huì)變慢多少。小球會(huì)在撞上墻后反彈，然后再次撞擊大球，這個(gè)過(guò)程會(huì)重復(fù)很多次。最后，這樣的碰撞會(huì)讓大球調(diào)轉(zhuǎn)方向，直到它最終以比小球更快的速度向右遠(yuǎn)去。

在此之前，碰撞的次數(shù)會(huì)隨著大球與小球的質(zhì)量比的增大而變多。如果兩個(gè)球的質(zhì)量相等，碰撞會(huì)發(fā)生 3 次：第一次右側(cè)球會(huì)把所有運(yùn)動(dòng)轉(zhuǎn)移給左側(cè)球，左側(cè)球則在撞墻后反彈，然后又通過(guò)碰撞將動(dòng)量完全返還給右側(cè)球。如果大球的質(zhì)量是小球的 100 倍，則該過(guò)程會(huì)發(fā)生 31 次碰撞。如果這一質(zhì)量比為 10000，則會(huì)有 314 次碰撞。根據(jù)計(jì)算（這個(gè)實(shí)驗(yàn)無(wú)法實(shí)際進(jìn)行），質(zhì)量比每增加 99 倍，碰撞的次數(shù)除以質(zhì)量比的平方根后就能讓 π 的數(shù)字表示多一位數(shù)：3.141592654...。

當(dāng) Brown 偶然看到 Sanderson 的動(dòng)畫（動(dòng)畫里使用的方塊）時(shí)心里正想著 Grover 算法，然后他發(fā)現(xiàn)兩者之間存在顯著的相似性。舉個(gè)例子，Grover 算法的兩個(gè)量子操作可以分別對(duì)應(yīng)于球球碰撞和球墻碰撞。質(zhì)量比對(duì)應(yīng)于數(shù)據(jù)庫(kù)的大小。此外，最終的結(jié)果是：操作數(shù)（或碰撞數(shù)）正比于 π 以及數(shù)據(jù)庫(kù)規(guī)模（質(zhì)量比）的平方根。（還有兩個(gè) 2 的因數(shù)只是反映了兩個(gè)問(wèn)題的表記方法的差異）。

除了在這兩種如此不同的系統(tǒng)之間存在驚人的聯(lián)系之外，π 在這兩種情況中究竟發(fā)揮了怎樣的作用？當(dāng)然，π 這個(gè)無(wú)理數(shù)最出名的地方是它是圓的周長(zhǎng)與其直徑的比，不過(guò)它也出現(xiàn)在橢圓以及球等更高維對(duì)象的對(duì)應(yīng)比值中。定義球的方法之一是通過(guò)代數(shù)在橫縱坐標(biāo) x 和 y 給出限定條件：半徑為 r 的圓上的點(diǎn)滿足限定條件：x² + y² = r²。

事實(shí)證明，不管是上面的碰撞問(wèn)題，還是 Grover 算法，都具有這種形式的限定條件。球的碰撞或操作量子系統(tǒng)對(duì)應(yīng)于由這些限定條件定義的圓上的旋轉(zhuǎn)。

例如，對(duì)于兩個(gè)質(zhì)量為 m（速度為 v_m）和 M（速度為 v_M）的彈性球，彈性碰撞會(huì)保留兩者的總動(dòng)能。完全保留大球的動(dòng)能需要在坐標(biāo) v_m 和 v_M 的平面中進(jìn)行 180° 轉(zhuǎn)向，而 180° 就等于 π 弧度。

類似地，在量子系統(tǒng)中，觀察到某個(gè)特定結(jié)果的概率正比于對(duì)應(yīng)該結(jié)果的「波函數(shù)」的平方。目標(biāo)與其它所有結(jié)果的概率（振幅平方）之和必然為 1。

歷史上的其它關(guān)聯(lián)案例

也許有人要問(wèn)：「這能針對(duì)世界的本質(zhì)提供重要見(jiàn)解嗎？還是說(shuō)只能滿足一點(diǎn)好奇心？」Brown 表示，「也許對(duì) Grover 算法能為我們提供有關(guān)世界本質(zhì)的重要知識(shí)，也許彈性球研究是為了滿足好奇心，或許將它們聯(lián)系起來(lái)的原因更多的是第二個(gè)，而不是第一個(gè)。」

盡管如此，有時(shí)候這樣的聯(lián)系還是能引出一些重大進(jìn)展，在物理和數(shù)學(xué)歷史中已有為數(shù)不少的案例。舉個(gè)例子，物理學(xué)家已經(jīng)投入了 20 多年時(shí)間探索強(qiáng)相互作用的多粒子量子系統(tǒng)與整合了高一個(gè)維度的彎曲時(shí)空的引力模型之間的驚人對(duì)應(yīng)關(guān)系。甚至?xí)r空中的蟲洞有望解答與量子力學(xué)中遠(yuǎn)距離粒子「糾纏」相關(guān)的悖論。

數(shù)學(xué)常常通過(guò)與不同領(lǐng)域之間的聯(lián)系得到發(fā)展。例如，涉及一個(gè)簡(jiǎn)單方程的整數(shù)解的費(fèi)馬大定理直到幾個(gè)世紀(jì)之后才得到證明，而使用的方法來(lái)自「橢圓曲線」。再舉個(gè)例子，計(jì)算機(jī)科學(xué)家在一月份證明了一個(gè)與阿蘭 · 圖靈的可決定計(jì)算概念有關(guān)的定理，這又進(jìn)一步給其它看似無(wú)關(guān)的領(lǐng)域帶來(lái)了沖擊。

在 Aaronson 看來(lái)，Grover 算法與彈性球之間的「這種對(duì)應(yīng)關(guān)系盡管很精準(zhǔn)，但可能也就是個(gè)有趣的類比（就是說(shuō)我不知道如何使用這個(gè)關(guān)系來(lái)推導(dǎo)任何與 Grover 算法有關(guān)的未知性質(zhì)）。但這樣已經(jīng)很好了?！?/p>