劉齊禎，黃壽勝

（溫州大學(xué) 物理與電子信息工程學(xué)院，浙江 溫州 325035）

量子行走是經(jīng)典隨機行走的擴展［1］。因為很多問題都可以歸結(jié)為經(jīng)典隨機行走，所以量子行走以經(jīng)典隨機行走為類比，希望能把量子的并行性和經(jīng)典隨機行走的全能性結(jié)合起來。至今量子行走還是一個非常熱門的研究領(lǐng)域，基于量子行走的算法也不斷地出現(xiàn)［2－3］。值得一提的是Childs［4］等人的對稱樹算法，對于某些黑箱問題它能指數(shù)快于任何經(jīng)典算法。后來Childs［5］又指出量子行走能實現(xiàn)通用計算。

量子算法都是先產(chǎn)生盡可能多的疊加態(tài)，然后利用量子的并行性實現(xiàn)加速。如果要利用量子行走來設(shè)計或?qū)崿F(xiàn)量子算法，量子行走子必須行走一定步數(shù)來產(chǎn)生疊加態(tài)。然而在有限圖上的量子行走子，行走一定步數(shù)后，它在各點的概率趨于穩(wěn)定或震蕩，這時再行走下去已經(jīng)沒有意義。為了解決這個問題，本文在Douglas［6］的基礎(chǔ)上添加了相位因素，利用傅里葉變換模擬量子行走。

1 離散時間量子行走及其模擬

對于在N個點的圖上的量子行走，用經(jīng)典計算機模擬一步量子行走需要的時間為O（N6），優(yōu)化后為O（N4）［7］。Douglas［6］給 出 了 用 量 子 線 路 圖 來 模 擬 離 散 時 間 量 子 行 走 的 方 法，所 需 時 間 為O（ploy（log（N））），指數(shù)快于經(jīng)典計算機。

2 量子傅里葉變換的擴展

Shor［8］發(fā)現(xiàn)了量子傅里葉變換，并用量子傅里葉變換在很短的時間內(nèi)解決了大數(shù)因子分解問題。此后出現(xiàn)了很多基于量子傅里葉變換的算法，比如相位估計［9］，離散對數(shù)［8］，隱含子群問題等。本文對量子傅里葉變換進行擴展，然后利用這個擴展量子傅里葉變換模擬量子行走。

定理1：當正整數(shù)α和N互素，即α和N的最大公約數(shù)（α，N）＝1時，如果k取遍0到N－1的所有值，則α·k（modN）也取遍0到N－1的所有值。也就是說α·k（modN）是在集合｛0，1，…，N－1｝上的一個置換法則。符合條件0＜α＜N，且（α，N）＝1的α有φ（N）個，其中φ（N）為歐拉函數(shù)。

證明：把集合｛0，1，…，N－1｝看成模N的加法群G，其單位元是0，群的乘法法則就是數(shù)學(xué)上的加法模N。可以看出群G是一個循環(huán)群，其生成元是｛1｝。根據(jù)有限群倫，循環(huán)群群G有φ（N）個生成元，每個生成元都能獨立地生成群G。生成元的形式為gα，其中g(shù)為群G的任意一個生成元，α是與N互素且小于N的整數(shù)。令生成元g為1，則所有生成元的形式為1α＝α（用群的乘法），也就是說所有0＜α＜N，且（α，N）＝1的α都是群G的生成元，有φ（N）個。根據(jù)群G的乘法法則（加法模N）有αk＝α·k（modN），當k取遍0到N－1的所有值，則αk生成群G＝｛0，1，…，N－1｝，也就是說α·k（modN）也取遍0到N－1的所有值。如果考慮到順序，則α·k（modN）是在集合｛0，1，…，N－1｝上的一個置換法則，置換可以寫成

定理2：所有符合條件0＜α＜N，且（α，N）＝1的α構(gòu)成一個模N 的乘法群G，置換α·k（modN）構(gòu)成一個置換群H。群G和群H同構(gòu)。

證明：先證明所有符合上述條件的α所構(gòu)成的集合G，是一個模N乘法群，然后把公式（2）看成把群G同構(gòu)到群H 的映射法則。

（a）設(shè)α，β∈G，有α·β＝γ＋k·N，其中0＜γ＜N。α，β與N 互素，有α·β＝γ＋k·N與N 互素，所以γ與N互素。所以存在γ∈G使得α?β＝α·β（modN）＝γ，其中?是模N乘法群的乘法法則。

（b）設(shè)α，β，γ∈G ，有

可以看出公式（3）和（4）相等，所以有 （α?β）?γ＝α? （β?γ）。

（c）設(shè)α∈G。很顯然1∈G，有α?1＝1?α＝1·α＝α。所以存在單位元E＝1，對任意α∈G有α?E＝E?α＝α。

（d）設(shè)α∈G，因為α與N互素，則α有模N的乘法逆，即存在β使得α·β＝1（modN）?？梢钥闯靓乱才cN互素。所以對于任意α∈G都有它的逆β∈G。

由（a）－（d）可知G是一個模N乘法群。對于任意α∈G根據(jù)公式（2）得到一個置換h?？梢钥闯鏊械膆組成一個置換群H ，且群G和群H 同構(gòu)，同構(gòu)法則是公式（2）。

利用定理1和定理2就可以對量子傅里葉進行擴展。對于任意基矢｜j〉進行量子傅里葉變換，再對傅里葉變換的基矢｜k〉進行模N乘法操作，這樣就對量子傅里葉變換進行了擴展，過程如下

當α與N 互素時，公式（5）中基矢的相位e2πijk／N中的k和基矢本身｜k·α（modN）〉構(gòu)成一個置換。因為公式（5）中的疊加態(tài)與順序無關(guān)，把所有的疊加態(tài)按相位e2πijk／N中的k排列起來作為第一行，其對應(yīng)的基矢寫在第二行，就組成了一個置換h，如公式（2）所示。根據(jù)定理2中的（d），存在一個0＜β＜N與N 互素使得α·β＝1（modN），置換h可以表示為

公式（2）和（6）表示同一個置換，兩者可以通過列變換相互轉(zhuǎn)換。根據(jù)公式（6），公式（5）的最后結(jié)果可以表示為

公式（7）利用了相位的周期性。由公式（5）和（7）可知，只要在量子傅里葉變換后面加上模N乘法操作就可以得到如下變換

其中0＜β＜N與N 互素，可以叫這個變換為擴展量子傅里葉變換。公式（8）的相位中的β和j地位平等，可以相互調(diào)換，因為乘法的交換律。當0＜j＜N與N互素時，交換β和j的地位，進行公式（8）的逆變換就可以得到β，步驟如下

其中l(wèi)是j的模N 乘法逆。利用公式（9）和定理1和定理2就可以模擬量子行走。

3 用傅里葉變換模擬量子行走

圖1 一個有8個點的圖，點的編碼取奇數(shù)

設(shè)在圖1上的量子行走初態(tài)為

可以看出這時系統(tǒng)有最大疊加態(tài)，只有這樣量子算法才能發(fā)揮其威力［10］。但是以后的行走不會改變行走子在各點的概率分布，所以很難有實際應(yīng)用。本文利用擴展量子傅里葉變換解決這一矛盾。把公式（10）編碼成只有奇數(shù)的置換群的群元

為了簡單起見，這里用均衡投幣算符

以公式（10）為初態(tài)，用擴展傅里葉變換模擬量子行走，經(jīng)過三步行走后，各奇數(shù)基矢代表一個位置狀態(tài)，其對應(yīng)的相位代表硬幣狀態(tài)，最后利用公式（8）的逆變換得到結(jié)果。過程如下

可以看出量子行走子在各點的概率發(fā)生了變化，同時疊加態(tài)也是最大的，解決了前面所說的矛盾。

圖1是由公式（6）的置換h得到，取不同的α可以得到不同的圖形。把這些圖形進行組合疊加就可以得到復(fù)雜的圖形，這樣就可以對上面說的模擬方法進行擴展。

4 結(jié) 論

本文對量子傅里葉變換進行了擴展，利用擴展后的量子傅里葉變換對離散時間量子行走進行模擬。解決了在有限圖上的量子行走有較大的疊加態(tài)和量子行走在各點的概率發(fā)生變化，不能同時滿足的矛盾。本文提出的方法有助于基于量子行走的算法設(shè)計。最后把提出的方法推廣到更加復(fù)雜的圖形上。

［1］Aharonov Y，Davidovich L，Zagury N.Quantum random walks［J］.Physical Review A，1993，48（2）：1687－1690.

［2］Hillery M，Andersson E.Quantum tests for the linearity and permutation invariance of Boolean functions［J］.Physical Review A，2011，84（6）：0623291－0623297.

［3］Lee J，Lee H－W，Hillery M.Searches on star graphs and equivalent oracle problems［J］.Physical Review A，2011，83（2）：0223181－02231816.

［4］Childs A M，Cleve R，Deotto E，et al.Exponential algorithmic speedup by aquantum walk.15th annual ACM symposium on Theory of computing［C］.Boston：Assn for Computing Machinery，1983：59－68.

［5］Childs A M.Universal computation by quantum walk［J］.Physical Review Letters，2009，102（18）：1805011－1805014.

［6］Douglas B L，Wang J B.Efficient quantum circuit implementation of quantum walks［J］.Physical Review A，2009，79（5）：0523351－0523355.

［7］Douglas B L，Wang J B.A classical approach to the graph isomorphism problem using quantum walks［J］.Journal of Physics A：Mathematical and Theoretical，2008，41：0753031－0753039.

［8］Shor P W.Algorithms for quantum computation：discrete logarithms and factoring.35th Annual Symposium on Foundations of Computer Science［C］.Santa Fe：IEEE Computer Society Press，1994：124－134.

［9］Higgins B L，Berry D W，Bartlett S D，et al.Entanglement－free Heisenberg－limited phase estimation［J］.Nature，2007，450（7168）：393－396.

［10］Shenvi N，Kempe J，Whaley K B.Quantum random－walk search algorithm ［J］.Physical Review A，2003，67 （5）：0523071－05230714.