一種求解哈密爾頓通路問題的新方法

(1.長春工程學(xué)院 電氣與信息學(xué)院， 長春 130012;

2.長春工業(yè)大學(xué) a.計算機科學(xué)與工程學(xué)院; 電氣與電子工程學(xué)院， 長春 130012)



摘 要：哈密爾頓通路問題屬于典型的NP完全問題。針對NP完全問題的特點提出了一種基于量子計算和混沌動力學(xué)的新方法。該方法首先把哈密爾頓問題變換成布爾表達(dá)式形式；然后構(gòu)建了一個新型的量子混沌計算機模型，該模型使用混沌放大器解決了量子狀態(tài)區(qū)分問題；最后得出結(jié)論，基于非線性迭代關(guān)系的新型量子混沌計算機可以在多項式時間內(nèi)解決哈密爾頓通路問題。

 關(guān)鍵詞：哈密爾頓通路； 量子計算； 混沌動力學(xué)； 放大器； 非線性迭代關(guān)系

 中圖分類號：TP301.6 文獻(xiàn)標(biāo)志碼： A

文章編號：10013695(2008)12356102



Novel method to solve Hamilton loop problem

MENG Xiangping1， MENG Jun2a， LV Lijuan2b



(1.School of Electrical Engineering， Changchun Institute of Technology， Changchun 130012， China;

2.a.School of Computer Science Engineering， b.School of Electrical Electronic Engineering， Changchun University of Technology， Changchun 130012， China)



Abstract:

Hamilton loop problem belongs to NPcomplete problems. This paper proposed an approach to it based on quantum computation and chaotic dynamics. Firstly， using a Boolean polynomial analyzed the Hamilton loop problem. Secondly， constructed a novel model based on quantum computation and chaotic dynamics which using a chaotic dynamics amplifier amplified the initial value in polynomial time. Considered the Hamilton loop problem and argued that the problem， in principle， it could be solved in polynomial time if the quantum computer was combined with the chaotic dynamics amplifier based on the logistic map.

 Key words：Hamilton loop; quantum computation; chaotic dynamics; amplifier; logistic map



0 引言

任何能夠在非確定型圖靈機上多項式時間內(nèi)解決的問題，就是NP完全問題^[1]，如背包、整數(shù)規(guī)劃、圖的著色、SAT、哈密爾頓通路和旅行商問題等。大部分計算機科學(xué)家認(rèn)為，只要有一個NP完全問題，有多項式時間的解法，其他的這一類問題難題也有多項式解法。針對NP完全問題許多學(xué)者提出了許多新的算法，如背包問題的動態(tài)規(guī)劃法和貪心算法^[2]，將背包問題和拍賣問題統(tǒng)一為拍賣背包問題，并以獲取最大化為目標(biāo)^[3]，利用遺傳算法求解旅行商問題^[4]等。

隨著近年來有關(guān)量子算法的研究及應(yīng)用的成功，尤其是Shor的大數(shù)質(zhì)因子分解的量子算法^[5]的應(yīng)用成功，使得國內(nèi)外許多學(xué)者的目光投向了這個領(lǐng)域。筆者所在實驗室已經(jīng)提出了基于量子計算的強化學(xué)習(xí)方法^[6]。混沌是非線性系統(tǒng)的本質(zhì)特性，具有隨機性、遍歷性及規(guī)律性等一系列特殊性質(zhì)。 混沌的發(fā)現(xiàn)，對科學(xué)發(fā)展具有深遠(yuǎn)的影響^[7] ，混沌已經(jīng)被作為在搜索過程中避免陷入局部極值的一種優(yōu)化機制而引入到進(jìn)化計算中，為進(jìn)化計算提供了新的研究領(lǐng)域和應(yīng)用方法^[8]。利用混沌的隨機性和遍歷性^[9，10]，本文提出了一種具有混沌效應(yīng)的放大器，讓它與傳統(tǒng)的量子計算機一起工作。結(jié)合這兩部分可以解決兩個量子塌縮后狀態(tài)難以區(qū)分的問題。

1 哈密爾頓通路問題

的概率為‖P|vf〉‖2=r/2n;r是式f(X)=1的根數(shù)目。如果r可以大得足夠探測到， 那么上面提出的哈密爾頓通路問題就可以在多項式時間內(nèi)解決。但是對于很小的r，確定它很難，這就意味著對f(X)=1的解的存在性所掌握的信息并不充分。鑒于此，下面進(jìn)行更深入的討論。。這樣做就把問題簡化為下面式子的1量子比特的問題:|〉= 1-q2 |0〉+q|1〉。后面將分析如何區(qū)分q=0和q>0（很小的正數(shù)）。

通常認(rèn)為用量子計算機解決NP完全問題只能得到二次方的加速，不能實現(xiàn)指數(shù)級的加速。止步定理表明，當(dāng)兩個量子態(tài)的點積塌縮為1時，分辨這兩種量子狀態(tài)幾乎是不可能的。有學(xué)者研究發(fā)現(xiàn)，即使使用放大器也不可能區(qū)分。

基于這點，運用傳統(tǒng)的方法難以奏效，筆者轉(zhuǎn)而尋找新的方法，該方法使用量子計算機的輸出I(xiàn)|〉作為另一個裝置的輸入，該裝置運用混沌動力學(xué)原理。傳統(tǒng)的基于酉演化的量子計算方法是難以解決放大問題的，所以本文提出一種新的方法，該方法把量子計算機與混沌放大器結(jié)合在一起。這種量子混沌計算機是一種新型的計算模型，并且證明了使用它在多項式時間內(nèi)解決放大問題是可能的。

3 混沌動力學(xué)放大器

關(guān)于經(jīng)典算法和量子混沌學(xué)的各個分支的研究已經(jīng)頗具成果^[12]，利用量子計算機開展量子混沌學(xué)的研究也已提出^[13~15]。下面討論混沌算法為什么在一般的計算問題中有很大的作用。混沌的一個重要特征是運動對初值的敏感性。鑒于此，本文利用混沌算法的這個特性來區(qū)別第2章提到的q=0和q>0兩種狀態(tài)。使用下面的非線性迭代關(guān)系：

非線性迭代關(guān)系的屬性取決于參數(shù)a，令a=371，那么李雅普諾夫指數(shù)是正的，運動軌跡對初值是很敏感的，具有混沌現(xiàn)象。所有的經(jīng)典算法都可以在量子計算機上執(zhí)行^[16]。本文提出了一種新的量子計算機，它由兩個部分組成：a）一般的量子計算機，通過輸出|〉= 1-q2 |0〉+q|1〉進(jìn)行計算；b）通過傳統(tǒng)的非線性迭代關(guān)系進(jìn)行計算，這兩個部分通過把態(tài)|〉轉(zhuǎn)換到密度矩陣進(jìn)行結(jié)合，如式（4）所示：

ρ =q2P1+(1-q2)P0(4) 

其中：P1和P0是態(tài)向量|1〉和|0〉的映射，實際上這個連接也可以認(rèn)為是量子混沌計算機的第三部分。在這里必須強調(diào)P1和P0將生成一個稱為阿貝爾代數(shù)群的經(jīng)典系統(tǒng)，在上面論述的第二個部分中的密度矩陣 ρ可以通過初始狀態(tài) ρ 0得到，如式（5）所示的使用非線性迭代關(guān)系：

ρ m=[I+fm( ρ 0)σ3]/2 (5) 

其中： I是密度矩陣；σ 3是 C2上的z分量的Pauli陣。為了找到 一個合適的m值，將在態(tài)ρm上測量 σ 3的值，Mm≡trρm σ 3。經(jīng)過簡單 的計算，得到

ρm=[ I +fm(q2) σ3]/2， Mm=fm(q2)(6) 

現(xiàn)在的問題是對于很小的但非零的q2，能否在多項式的時間內(nèi)，通過n步找到m值，使它滿足不等式Mm≥1/2。如果q=0那么，ρ0=P0，并且對于所有的m得到Mm=0；如果q≠0，小數(shù)量級的q將由于隨機的動態(tài)性進(jìn)行放大。下面討論這種放大的原理。由于由P0和P1產(chǎn)生的代數(shù)系統(tǒng)是阿貝爾的，那么由ρ0到ρm的轉(zhuǎn)換是非線性的。如何在最多2n步內(nèi)完成放大將取決于下面的命題。對于x0=q2的非線性迭代關(guān)系xm+1=f(xm)， fm(q2)就等價于xm。下面將在非線性迭代關(guān)系中使用xm進(jìn)行簡化。

命題1對于a∈[0，4]，x0∈[0，1]的非線性迭代關(guān)系xn+1=axn(1-xn)，假設(shè)x0為1/2n，集合J為{0，1，2，…，n，…，2n}。如果a=371，那么在集合J中存在整數(shù)m滿足不等式xm>1/2。

證明假設(shè)集合J中不存在m，那么對于集合J中的任意m都滿足不等式xm≤1/2，xm=371(1-xm-1)xm-1≥(371/2)xm-1，所以1/2≥xm≥(371/2)xm-1≥…≥(371/2)mx0=(371/2)m/2n。

由上式得到2n+m-1≥(371)m，即m≤(n-1)/(log2 371-1)。由于log2 371≈1891 2，m≤(n-1)/(log2 371-1)<5(n-1)/4，即m必定小于2n-1，這就與上面的假設(shè)矛盾，所以原命題成立。

命題2對于命題1，假設(shè)a=n，如果集合J中存在m0滿足xm0>1/2，那么m0>(n-1)/log2 371。

 證明對于0≤xm≤1，已知xm=371(1-xm-1)xm-1≤3.71xm-1，即xm≤(3.71)mx0。因為在集合J中m0滿足xm0>1/2，那么x0≥xm0/371m0>1/（2×371m0）。這符合條件x0=1/2n。

這樣很容易得到log22×371m0>n，即m0>(n-1)/log2 371。

通過上述兩個命題，對于較大的n，已經(jīng)有足夠的信息在至多2n步內(nèi)確定xm(Mm)的值，同樣對于q=k/2n中的某個整數(shù)k，可以類似地在至多2n步內(nèi)確定大于1/2的xm(Mm)。

4 仿真曲線

對式xn+1=axn(1-xn)，筆者在MATLAB上進(jìn)行了曲線仿真，如圖1所示。

仿真中令a=371，x0=0001。曲線表明可以很容易地在數(shù)步內(nèi)放大初始的x0，也即q2。

5 結(jié)束語

本文借助量子算法在解決問題所表現(xiàn)出的高并行性，分析了哈密爾頓通路問題，結(jié)合混沌動力學(xué)設(shè)計出一種新型的計算模型。該模型分為兩部分，即量子計算機和混沌放大器。前者的輸出作為后者的輸入。該模型解決了傳統(tǒng)量子計算機難以區(qū)分塌陷后量子狀態(tài)問題，并證明了放大過程的多項式解法。文末的仿真曲線表明了使用非線性迭代方程的高效性。 

參考文獻(xiàn)：

[1]GAREY M， JOHNSON D. Computers and Intractability: a guide to the theory of NPcompleteness[M]. New York: Freeman W H and Co，1979.

[2] 劉玉娟，王相海.01背包問題的兩種擴展形式及其解法[J].計算機應(yīng)用研究，2006， 23 (1):2830.

[3] 劉愛珍，王嘉禎，彭德云，等.一種高效的基于拍賣背包機制的移動agent調(diào)度策略[J].計算機應(yīng)用研究，2007， 24 (6):5254.

[4] 賀毅朝，劉坤起，張翠軍，等.求解背包問題的貪心遺傳算法及其應(yīng)用[J].計算機工程與設(shè)計，2007， 28 (11):26552658.

[5] SHOR P W. Algorithm for quantum computation: discrete logarithm and factoring algorithm[C]//Proc of the 35th Annual IEEE Symposium on Foundation of Computer Science. 1994:124134.

[6] MENG Xiangping， CHEN Yu， PI Yuzhen， et al. A novel multiagent reinforcement learning algorithm combination with quantum computation[C]//Proc of the 6th World Congress on Intelligent Control and Automation. Dalian:[s.n.]， 2006:2123.

[7] 呂金虎，魯君安，陳士華.混沌時間序列分析及其應(yīng)用[M].武漢:武漢大學(xué)出版社，2002.

[8] 陳國良，王煦法.遺傳算法及其應(yīng)用[M].北京:人民郵電出版社，2001.

[9] 劉麗，彭代淵，李曉舉.基于混沌序列的自適應(yīng)進(jìn)化規(guī)劃算法[J].計算機應(yīng)用研究，2007， 24 (5):4647，51.

[10] 張國勝，方宗德，李愛民，等.基于混沌技術(shù)的連續(xù)禁忌搜索算法研究[J].計算機應(yīng)用研究，2008， 25 (2):411413.

[11] 盧開澄.計算機算法導(dǎo)引[M].北京:清華大學(xué)出版社，2006.

[12] OHYA M. Complexities and their applications to characterization of chaos[J].Int Journ of Theoret Physics， 1998， 37 (11):495505.

[13] GARDINER S A， CIRAC J I， ZOLLER P. Quan tum chaos in an lon trap: the deltakicked harmonic oscillator[J].Physical Review Letters ， 1997， 79 (24):47904793.

[14] SCHACK R. Using a quantum Computer to investigate quantum chaos[J].Physical Review Letters ， 1998，A57 (3) :16341635.

[15] KIM I， MAHLER G. Quantum chaos in quantum turing machine[J].Physics Letters A ， 1999， 263 (6):268273.

[16] DEUTSCH D. Quantum theory， the ChurchTuring principle and the universal quantum computer[C]//Proc of Royal Society of London A. 1985:97117.