前不久，史上最快的超大數(shù)相乘方法轟動(dòng)業(yè)界。近日，借由這個(gè)思路，谷歌一名軟件工程師提出了另一種優(yōu)化方式，使得量子版“遞歸”算法或?qū)⒊蔀榭赡埽?/p>

上個(gè)月，兩位研究人員發(fā)現(xiàn)的史上最快的超大數(shù)相乘方法，在業(yè)界掀起了不小的風(fēng)波，有望破解存在了近半個(gè)世紀(jì)的數(shù)學(xué)難題。

而就在前幾日，著名科普網(wǎng)站QuantaMagazine發(fā)表了一篇文章稱，另一種新乘法運(yùn)算方式為量子計(jì)算機(jī)打開了一扇新大門。

文章地址：

https://www.quantamagazine.org/a-new-approach-to-multiplication-opens-the-door-to-better-quantum-computers-20190424/

這篇論文作者是Google AI Quantum的軟件工程師Craig Gidney，于4月15日將文章《漸近有效的量子Karatsuba乘法》發(fā)表于arXiv。

論文地址：

https://arxiv.org/pdf/1904.07356.pdf

論文作者

在他的新論文中，Gidney描述了一種實(shí)現(xiàn)Karatsuba乘法的量子方法，這種方法不會(huì)產(chǎn)生巨大的內(nèi)存開銷。他沒(méi)有先生成中間值，再得到最終值，而是使用一種稱為“尾調(diào)用優(yōu)化”(tail call optimization)的方法來(lái)直接將輸入變?yōu)檩敵?。這使得算法可以避免創(chuàng)建量子計(jì)算機(jī)永遠(yuǎn)無(wú)法丟棄的中間信息。

Gidney希望他的方法能夠使許多經(jīng)典的遞歸算法適應(yīng)量子計(jì)算機(jī)。目前，量子計(jì)算機(jī)還很初級(jí)，幾乎不能進(jìn)行個(gè)位數(shù)乘法。但起碼有一個(gè)算法已經(jīng)準(zhǔn)備好了，只要它們的設(shè)計(jì)繼續(xù)改進(jìn)，它們將能夠做更多的事情。

數(shù)學(xué)處處充滿驚喜：大數(shù)乘法世紀(jì)難題或?qū)⑵平?，又有益于量子?jì)算

先來(lái)思考一下這么一個(gè)問(wèn)題：

我9歲的時(shí)候，我家有了一臺(tái)新電腦。這臺(tái)電腦在各方面都比我們的舊電腦好，除了一點(diǎn)：它不能運(yùn)行我最喜歡的賽車游戲。我記得我當(dāng)時(shí)就想，如果一臺(tái)漂亮的新電腦不能運(yùn)行我最喜歡的程序，那它還有什么意義呢?

同樣的問(wèn)題也適用于量子計(jì)算機(jī)。理論上，量子計(jì)算機(jī)可以做經(jīng)典計(jì)算機(jī)所能做的所有事情。然而，在實(shí)踐中，量子計(jì)算機(jī)的量子性質(zhì)使它基本上不可能有效地運(yùn)行一些最重要的經(jīng)典算法。

而這又是什么原因呢？

我們知道，一臺(tái)經(jīng)典計(jì)算機(jī)能做加法，它就能做乘法，而后可以處理許許多多更加復(fù)雜的信息。而量子計(jì)算機(jī)卻可能連非常基本的運(yùn)算也難以做到，其間原因就是——無(wú)法做到“選擇性遺忘”。

“選擇性遺忘”就好比：一個(gè)2G的內(nèi)存條實(shí)際上的容量或許只有1.95G。但對(duì)于量子計(jì)算機(jī)，它只能含淚說(shuō)道：“臣妾做不到哇！”

而在Gidney的論文中所討論的乘法算法利用了一項(xiàng)發(fā)現(xiàn)，這是數(shù)千年來(lái)乘法領(lǐng)域的首次進(jìn)步。傳統(tǒng)的小學(xué)乘法方法中，位數(shù)是n的兩個(gè)數(shù)字相乘需要n2步。幾千年來(lái)，數(shù)學(xué)家們一直認(rèn)為沒(méi)有更有效的方法了。

但是，正如我們最近在《極限速度！10 億位超級(jí)大整數(shù)相乘僅需 30 秒，半個(gè)世紀(jì)的猜測(cè)終被證明》一文中所報(bào)道的，1960年，一位名叫阿納托利·卡拉蘇巴(Anatoly Karatsuba)的數(shù)學(xué)家發(fā)現(xiàn)了一種更快乘法方法。

他的方法是把長(zhǎng)數(shù)字分成較短的數(shù)。例如，假如要將兩個(gè)8位的數(shù)字相乘，首先要將每個(gè)8位數(shù)字拆分為兩個(gè)4位的數(shù)，然后將每個(gè)4位數(shù)拆分為兩個(gè)兩位數(shù)。然后對(duì)所有兩位數(shù)進(jìn)行計(jì)算，最后將結(jié)果重組，就是最終的乘積。對(duì)于涉及大數(shù)的乘法， Karatsuba的方法比小學(xué)法的步驟要少得多。

如何快速地將兩個(gè)大數(shù)相乘(Lucy Reading-Ikkanda/Quanta Magazine)

數(shù)千年來(lái)，將兩個(gè)n位的數(shù)字相乘，需要n2個(gè)步驟。1960年，俄羅斯數(shù)學(xué)家Anatoly Karatsuba提出了一種更好的方法。

比如，在25×63這個(gè)算式中，使用小學(xué)乘法方法需要4個(gè)單位數(shù)乘法步驟，并將4步所得的積相加，才能得到最后的結(jié)果。

同樣的算式使用Karatsuba的方法，只需要做3次乘法，以及少量的加法操作和移位操作。

隨著數(shù)字位數(shù)的增加，Karatsuba方法可以重復(fù)使用，將大的數(shù)字分割成較小的數(shù)字，從而節(jié)省更多的單位數(shù)乘法操作。

類似“尾調(diào)用優(yōu)化”，量子版“遞歸算法”或?qū)?shí)現(xiàn)！

經(jīng)典計(jì)算機(jī)運(yùn)行Karatsuba方法時(shí)，它會(huì)隨著運(yùn)行進(jìn)行而刪除信息。例如，在將兩位數(shù)重組為四位數(shù)之后，它會(huì)忘記之前的兩位數(shù)，只關(guān)心四位數(shù)本身。經(jīng)典的Karatsuba方法就像登山者在上山的路上脫下裝備一樣——不需要一路攜帶所有東西時(shí)，你可以走得更快。

但量子計(jì)算機(jī)無(wú)法隨時(shí)“脫下”信息。

量子計(jì)算機(jī)通過(guò)操縱量子比特系統(tǒng)來(lái)執(zhí)行計(jì)算?！斑@些量子比特彼此交織或糾纏。這種糾纏使量子計(jì)算機(jī)擁有巨大的能量——量子計(jì)算機(jī)利用了所有量子比特之間存在的復(fù)雜關(guān)系，而不只是以單個(gè)比特存儲(chǔ)信息。因此，對(duì)于某些特定的問(wèn)題，量子計(jì)算機(jī)可以具有經(jīng)典計(jì)算機(jī)指數(shù)級(jí)倍數(shù)的處理能力。

量子糾纏，看似荒謬的超距感應(yīng)

但是使量子計(jì)算機(jī)強(qiáng)大的這種特性也使它們變得脆弱。因?yàn)榱孔颖忍丶m纏在一起，你不可能在不影響其他量子比特的情況下改變其中的一些量子比特。這使得不可能像經(jīng)典計(jì)算機(jī)那樣有選擇地刪除信息。扔掉某些量子比特就像剪斷蜘蛛網(wǎng)上的某幾股線——即使只“咔嚓”一下也可能導(dǎo)致整個(gè)蛛網(wǎng)分崩離析。

保留信息的這種要求使得難以創(chuàng)建“遞歸”算法的量子版本，因?yàn)椤斑f歸”意味著它們會(huì)反饋給自身。遞歸算法在計(jì)算機(jī)科學(xué)中有很廣泛的應(yīng)用，但為了達(dá)到最佳效果，它們要求計(jì)算機(jī)在每一步都要丟棄信息。沒(méi)有這種能力，計(jì)算很快就會(huì)變得不切實(shí)際。布里斯托爾大學(xué)(University of Bristol)量子信息科學(xué)家Ashley Montanaro說(shuō)，“如果每次進(jìn)行一項(xiàng)操作都會(huì)存儲(chǔ)信息，那么空間的大小就會(huì)隨著操作的數(shù)量而變化?！比魏螜C(jī)器都會(huì)很快耗盡內(nèi)存。

Gidney的工作在保持O(nlg3)門集程度(gate complexity)的同時(shí)，提高了量子計(jì)算機(jī)上從O1到O2的Karatsuba乘法的空間復(fù)雜度。他通過(guò)確保遞歸調(diào)用可以將其輸出直接添加到輸出寄存器的子部分來(lái)實(shí)現(xiàn)此目的。這避免了存儲(chǔ)和不計(jì)算中間結(jié)果的需求。

他使用Q#的跟蹤模擬器實(shí)現(xiàn)并測(cè)試了他的算法，并獲得具體的計(jì)數(shù)。

針對(duì)各種輸入尺寸的Karatsuba乘法和教科書乘法的Q＃implementation所使用的Toffoli gate和量子位數(shù)的雙對(duì)數(shù)坐標(biāo)圖

值得注意的是，在作者的實(shí)現(xiàn)中，Karatsuba乘法比教科書乘法更高效的交叉點(diǎn)(約10000位)比現(xiàn)代RSA密鑰的大小(2048到8192位)更大，這表明Shor算法在實(shí)踐中應(yīng)該更傾向于使用簡(jiǎn)單的乘法。

不過(guò)，這篇論文關(guān)注的是漸近參數(shù)，而不是試圖優(yōu)化常數(shù)因子。論文還忽略了一些重要的實(shí)際考慮，比如為了讓量子比特相互作用而將量子比特相互routing的成本。

此外，作者分析的情況(兩個(gè)量子整數(shù)的乘法)不同于Shor算法中的情況(一個(gè)量子整數(shù)與一個(gè)經(jīng)典整數(shù)的受控模乘法)。因此，對(duì)于Karatsuba乘法在Shor算法中的實(shí)際應(yīng)用，作者并沒(méi)有得出任何結(jié)論。

他表示，這種類似于經(jīng)典尾調(diào)用優(yōu)化的優(yōu)化應(yīng)該適用于各種遞歸量子算法。但在Gidney發(fā)表這篇論文之前，還不清楚是否有可能對(duì)這類算法進(jìn)行改造，讓量子計(jì)算機(jī)也能運(yùn)行。

Gidney希望他的新技術(shù)能讓量子計(jì)算機(jī)實(shí)現(xiàn)這類算法，而到目前為止，這類算法在量子計(jì)算機(jī)中使用似乎是緩慢而復(fù)雜的。