選自acm.org
作者：Don Monroe
機(jī)器之心編譯
編輯：Panda
從看似無關(guān)的主題中發(fā)現(xiàn)某種共同特質(zhì)是件挺有意思的事，而且說不定會帶來理解事物的新方式。本文探討了著名量子算法 Grover 搜索算法與完全彈性碰撞這一問題之間的關(guān)聯(lián)。
在科學(xué)和數(shù)學(xué)領(lǐng)域，許多看似無關(guān)的主題之間存在某些共同的特質(zhì)。這樣的相似性有時能同時為這兩個領(lǐng)域帶來重大的進(jìn)展，不過很多時候這樣的相似性只是單純地很有趣。
去年 12 月，谷歌一位物理學(xué)家 Adam Brown 發(fā)現(xiàn)：一種基本量子計(jì)算算法與一種用于計(jì)算無理數(shù) π 的奇妙方法之間存在一種異常精確的關(guān)系�！改壳皝碚f這個發(fā)現(xiàn)只是單純很有意思，但我們希望找到思考事物的新方式，人們未來也許能使用這種方式尋找之前無法看到的聯(lián)系�！笲rown 說，「對于一個現(xiàn)象，多種思考角度是非常有用的。」
在網(wǎng)上發(fā)布的一篇預(yù)印本論文中（目前尚未完成同行評議），Brown 表明兩個看似無關(guān)的問題之間存在某種數(shù)學(xué)上的相關(guān)性。其中一個問題是為量子計(jì)算機(jī)提出的著名的 Grover 搜索算法，理論上它比任何經(jīng)典搜索算法都更快。另一個問題則是一個出人意料的過程：通過統(tǒng)計(jì)理想彈性球的碰撞次數(shù)來得到任意精度的 π 值。
量子算法
量子計(jì)算要用到量子比特，每個量子比特可以同時表示兩個狀態(tài)，而它們通常用離子或超導(dǎo)回路構(gòu)建。從原理上看，一定數(shù)量的量子比特能表示和操作比經(jīng)典比特多指數(shù)級數(shù)量的組合。之前，人們覺得利用這種概率性質(zhì)來進(jìn)行計(jì)算似乎是一場白日夢，但是研究者還是成功設(shè)計(jì)出了可從量子比特提取有用信息的算法。
第一個量子算法是彼得 秀爾（Peter Shor）1994 年提出的秀爾算法，當(dāng)時他正在新澤西州的貝爾實(shí)驗(yàn)室工作。秀爾算法能高效地將整數(shù)分解為質(zhì)因數(shù)，也由此給現(xiàn)今的許多加密方案帶來了潛在的威脅。該算法的訣竅是將整數(shù)分解重構(gòu)為一個新問題：確定一個序列的重復(fù)周期。這本質(zhì)上是一種傅立葉變換，通過在量子比特的全集上使用全局運(yùn)算就能找到這個序列。
第二個基本算法則是 Lov Grover 于 1996 年在貝爾實(shí)驗(yàn)室獨(dú)立提出的 Grover 算法，它有著大不一樣的工作方式�！感銧査惴ê� Grover 算法是兩種最典型的量子算法�！沟驴怂_斯州大學(xué)奧斯汀分校的 Scott Aaronson 說，「即便在今天，我們所知的絕大部分量子算法都要么受秀爾算法啟發(fā)，要么受 Grover 算法啟發(fā)，要么同時受兩者啟發(fā)�！�
Grover 算法通常被描述為一個數(shù)據(jù)庫搜索過程，即檢查一個包含 N 項(xiàng)的列表，找到其中滿足所需性質(zhì)的一項(xiàng)。如果該列表已按某種標(biāo)簽進(jìn)行了排序（比如按字母順序排列），那么通過不斷連續(xù)減半地切分列表，就可以找到任意標(biāo)簽；這個過程所需的查詢次數(shù)為 log N。但是，對于無序列表，檢查完每一項(xiàng)平均需要 N/2 步（有可能需要多達(dá) N 步）。
和其它量子算法一樣，Grover 算法也會同時操作整個量子比特集，同時保留它們之間的關(guān)系（過早地查詢?nèi)我饬孔颖忍貢蛊錉顟B(tài)確定下來，從而將其轉(zhuǎn)換成一個普通比特，這會消除量子計(jì)算所帶來的優(yōu)勢）。但是，Grover 的研究表明：通常僅需次全局操作就能找到所需的項(xiàng)。
這樣的提升沒有秀爾算法所帶來的提升多，因?yàn)樾銧査惴◣淼氖侵笖?shù)級的提升。但 Brown 強(qiáng)調(diào)說：Grover 算法可應(yīng)用于更一般的、非結(jié)構(gòu)化的問題。
Grover 算法的計(jì)算首先是對所有 N 個量子比特進(jìn)行均等混合。然后，該算法會反復(fù)讓所有量子比特進(jìn)行兩種輪流交替的操作。第一個操作是嵌入該目標(biāo)：它會反轉(zhuǎn)一個特定但未知的比特的狀態(tài)。該任務(wù)的目標(biāo)是確定哪個比特被修改了，但方法不是觀測所有比特。第二個操作不需要有關(guān)該目標(biāo)的任何信息。Grover 發(fā)現(xiàn)每次重復(fù)該序列時，該目標(biāo)在混合結(jié)構(gòu)中的權(quán)重都會增大（盡管這無法被觀測到）。重復(fù)了適當(dāng)?shù)拇螖?shù)之后，此時執(zhí)行一次觀測，則有非常高的可能性能得到正確結(jié)果。
彈性球
這些復(fù)雜的量子操作似乎和彈性球沒有關(guān)系。但是，Brown 在研究與 Grover 算法相關(guān)的問題時看到了數(shù)學(xué)科普者 Grant Sanderson 做的一個動畫，讓他注意到了兩者之間的相似性。Brown 在自己的論文中表明這兩個問題之間存在一種精準(zhǔn)的映射關(guān)系。
Sanderson 的動畫解釋了東伊利諾伊大學(xué)數(shù)學(xué)家 Gregory Galperin 在 2003 年描述的一個出人意料的觀察結(jié)果。在論文《Playing Pool with π》中，他想象有兩個能在水平面上無摩擦地運(yùn)動的理想彈性球，它們能彼此以及與左側(cè)的墻發(fā)生完全彈性碰撞（即總動能守恒）。
如果右側(cè)的球向左撞向左側(cè)更輕的靜止球，則左側(cè)小球會向左運(yùn)動，同時右側(cè)大球的速度并不會變慢多少。小球會在撞上墻后反彈，然后再次撞擊大球，這個過程會重復(fù)很多次。最后，這樣的碰撞會讓大球調(diào)轉(zhuǎn)方向，直到它最終以比小球更快的速度向右遠(yuǎn)去。
在此之前，碰撞的次數(shù)會隨著大球與小球的質(zhì)量比的增大而變多。如果兩個球的質(zhì)量相等，碰撞會發(fā)生 3 次：第一次右側(cè)球會把所有運(yùn)動轉(zhuǎn)移給左側(cè)球，左側(cè)球則在撞墻后反彈，然后又通過碰撞將動量完全返還給右側(cè)球。如果大球的質(zhì)量是小球的 100 倍，則該過程會發(fā)生 31 次碰撞。如果這一質(zhì)量比為 10000，則會有 314 次碰撞。根據(jù)計(jì)算（這個實(shí)驗(yàn)無法實(shí)際進(jìn)行），質(zhì)量比每增加 99 倍，碰撞的次數(shù)除以質(zhì)量比的平方根后就能讓 π 的數(shù)字表示多一位數(shù)：3.141592654...。
當(dāng) Brown 偶然看到 Sanderson 的動畫（動畫里使用的方塊）時心里正想著 Grover 算法，然后他發(fā)現(xiàn)兩者之間存在顯著的相似性。舉個例子，Grover 算法的兩個量子操作可以分別對應(yīng)于球球碰撞和球墻碰撞。質(zhì)量比對應(yīng)于數(shù)據(jù)庫的大校此外，最終的結(jié)果是：操作數(shù)（或碰撞數(shù)）正比于 π 以及數(shù)據(jù)庫規(guī)模（質(zhì)量比）的平方根。（還有兩個 2 的因數(shù)只是反映了兩個問題的表記方法的差異）。
除了在這兩種如此不同的系統(tǒng)之間存在驚人的聯(lián)系之外，π 在這兩種情況中究竟發(fā)揮了怎樣的作用？當(dāng)然，π 這個無理數(shù)最出名的地方是它是圓的周長與其直徑的比，不過它也出現(xiàn)在橢圓以及球等更高維對象的對應(yīng)比值中。定義球的方法之一是通過代數(shù)在橫縱坐標(biāo) x 和 y 給出限定條件：半徑為 r 的圓上的點(diǎn)滿足限定條件：x + y = r 。
事實(shí)證明，不管是上面的碰撞問題，還是 Grover 算法，都具有這種形式的限定條件。球的碰撞或操作量子系統(tǒng)對應(yīng)于由這些限定條件定義的圓上的旋轉(zhuǎn)。
例如，對于兩個質(zhì)量為 m（速度為 v_m）和 M（速度為 v_M）的彈性球，彈性碰撞會保留兩者的總動能。完全保留大球的動能需要在坐標(biāo) v_m 和 v_M 的平面中進(jìn)行 180° 轉(zhuǎn)向，而 180° 就等于 π 弧度。
類似地，在量子系統(tǒng)中，觀察到某個特定結(jié)果的概率正比于對應(yīng)該結(jié)果的「波函數(shù)」的平方。目標(biāo)與其它所有結(jié)果的概率（振幅平方）之和必然為 1。
歷史上的其它關(guān)聯(lián)案例
也許有人要問：「這能針對世界的本質(zhì)提供重要見解嗎？還是說只能滿足一點(diǎn)好奇心？」Brown 表示，「也許對 Grover 算法能為我們提供有關(guān)世界本質(zhì)的重要知識，也許彈性球研究是為了滿足好奇心，或許將它們聯(lián)系起來的原因更多的是第二個，而不是第一個�！�
盡管如此，有時候這樣的聯(lián)系還是能引出一些重大進(jìn)展，在物理和數(shù)學(xué)歷史中已有為數(shù)不少的案例。舉個例子，物理學(xué)家已經(jīng)投入了 20 多年時間探索強(qiáng)相互作用的多粒子量子系統(tǒng)與整合了高一個維度的彎曲時空的引力模型之間的驚人對應(yīng)關(guān)系。甚至?xí)r空中的蟲洞有望解答與量子力學(xué)中遠(yuǎn)距離粒子「糾纏」相關(guān)的悖論。
數(shù)學(xué)常常通過與不同領(lǐng)域之間的聯(lián)系得到發(fā)展。例如，涉及一個簡單方程的整數(shù)解的費(fèi)馬大定理直到幾個世紀(jì)之后才得到證明，而使用的方法來自「橢圓曲線」。再舉個例子，計(jì)算機(jī)科學(xué)家在一月份證明了一個與阿蘭 圖靈的可決定計(jì)算概念有關(guān)的定理，這又進(jìn)一步給其它看似無關(guān)的領(lǐng)域帶來了沖擊。
在 Aaronson 看來，Grover 算法與彈性球之間的「這種對應(yīng)關(guān)系盡管很精準(zhǔn)，但可能也就是個有趣的類比（就是說我不知道如何使用這個關(guān)系來推導(dǎo)任何與 Grover 算法有關(guān)的未知性質(zhì)）。但這樣已經(jīng)很好了�！�
如何根據(jù)任務(wù)需求搭配恰當(dāng)類型的數(shù)據(jù)庫？
在AWS推出的白皮書《進(jìn)入專用數(shù)據(jù)庫時代》中，介紹了8種數(shù)據(jù)庫類型：關(guān)系、鍵值、文檔、內(nèi)存中、關(guān)系圖、時間序列、分類賬、領(lǐng)域?qū)捔校⒅鹨环治隽嗣糠N類型的優(yōu)勢、挑戰(zhàn)與主要使用案例。
