韓文娟++黃敏

摘 要： 對(duì)海森堡模型位型[N，k] （N為海森堡鏈總格點(diǎn)數(shù)， k為格點(diǎn)中自旋向上的電子數(shù)）中尋找目標(biāo)數(shù)據(jù)的算法進(jìn)行討論分析。研究方法：將模型的能量矩陣對(duì)角化所得到的本征值構(gòu)成數(shù)據(jù)群，使用Fortran編程查找群中的目標(biāo)數(shù)據(jù)并進(jìn)行算法的分析討論。研究結(jié)論：參數(shù)相同時(shí)，對(duì)于位型[N，k]（k≤N/2） ，當(dāng)N（k）同，k（N）增大時(shí)，獲取模型同位置的目標(biāo)數(shù)據(jù)搜尋時(shí)間和所需要的輔助空間（字節(jié)數(shù)）均增加；同一位型[N，k]，獲取同位置的目標(biāo)數(shù)據(jù)搜尋時(shí)間和所需要的輔助空間（字節(jié)數(shù)）均不同。通過對(duì)海森堡模型搜尋目標(biāo)數(shù)據(jù)的算法討論可為研究者們?cè)谘芯抗ぷ髦凶魈岣哌\(yùn)算效率的借鑒。

關(guān)鍵詞：海森堡模型 本征值 目標(biāo)數(shù)據(jù) 算法 時(shí)間

中圖分類號(hào)：O431.2 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1003-9082（2016）04-0002-02

一、引言

海森堡模型是實(shí)現(xiàn)量子通信[1，2，3]和量子計(jì)算的物理體系之一， 一直吸引著很多的研究者對(duì)它并利用它作理論研究，在研究工作的普適計(jì)算中會(huì)涉及編程與數(shù)據(jù)運(yùn)算，因?yàn)閿?shù)據(jù)運(yùn)算是通過算法（Algorithm）描述的，一個(gè)程序如果對(duì)任何輸入都不會(huì)陷入無限循環(huán)，則它就是一個(gè)算法。在數(shù)據(jù)結(jié)構(gòu)課程內(nèi)容中，一個(gè)算法就是一種解題方法，算法是由若干條指令組成的有窮序列，一個(gè)算法中，有些指令可能是重復(fù)執(zhí)行的，因而指令的執(zhí)行次數(shù)可能遠(yuǎn)遠(yuǎn)大于算法中的指令條數(shù)，由有窮性（每一條指令的執(zhí)行次數(shù)必須是有限的）可知，對(duì)于任何輸入，算法在執(zhí)行了有限條指令后一定要終止，又由可行性（每條指令的時(shí)間是有限的）知道，一個(gè)算法必須在有限時(shí)間內(nèi)完成。算法有優(yōu)劣，求解同一個(gè)問題，可以有許多不同的算法，評(píng)價(jià)算法好壞的標(biāo)準(zhǔn)，除算法首先正確外，還考慮三點(diǎn)：（1）執(zhí)行算法所耗費(fèi)的時(shí)間；（2）執(zhí)行算法所耗費(fèi)的儲(chǔ)存空間，其中主要考慮輔助存儲(chǔ)空間；（3）算法易于理解、編碼和調(diào)試等。本文將海森堡模型位型[N，k] （N為海森堡鏈總格點(diǎn)數(shù)， k為格點(diǎn)中自旋向上的電子數(shù)，以下同）的本征值構(gòu)成數(shù)據(jù)群，使用2分 （即折半查找）法等進(jìn)行Fortran編程在不同數(shù)據(jù)群中查找目標(biāo)數(shù)據(jù)所需時(shí)間與耗費(fèi)的儲(chǔ)存空間情況進(jìn)行討論并結(jié)合算法進(jìn)行分析以讓讀者們對(duì)搜尋目標(biāo)數(shù)據(jù)有較好的了解，可為研究者們?cè)谘芯抗ぷ髦凶魈岣哌\(yùn)算效率的借鑒。

二、背景知識(shí)

1.一維XXZ海森堡開鏈模型的哈密頓量[4]

，式中N為格點(diǎn)數(shù)，Jx，Jy，Jz為相互作用參數(shù)，這里 ，令 ， ，

，則 ， 、

分別為XXX和 ZZ模型的能量矩陣，參數(shù)r取值為0到1。

2.海森堡模型本征值的獲得方法

使用置換群[5]方法形成一維XXZ海森堡開鏈模型位型[N，k]的能量矩陣， 將能量矩陣對(duì)角化得到 個(gè)本征值為數(shù)據(jù)群m作為查找目標(biāo)數(shù)據(jù)的具體環(huán)境。

3. 2分法[6]查找（Binary Search ）的基本思想

首先將待查的K值和有序表R[0]到R[n-1]的中間位置mid上的結(jié)點(diǎn)數(shù)進(jìn)行比較，若相等，則查找完成；否則，若R[mid]>K，則說明待查找的數(shù)只可能在做子表R[0]到R[mid -1]中，只要在左子表中繼續(xù)進(jìn)行二分查找，若R[mid ]

例如： 假設(shè)被查找的有序表中數(shù)序列為：

05，13，19，21，37，56，64，75，80，88，92

當(dāng)給定的K值分別為21和85時(shí)，進(jìn)行查找的過程如圖1，2所示，圖中用方括號(hào)表示當(dāng)前的查找區(qū)間，用↑表示中間位置指示器。

4.大圈縮小法

大圈中放整體數(shù)據(jù)，進(jìn)行一次操作后，數(shù)據(jù)圈縮小，再進(jìn)行一次操作，數(shù)據(jù)圈再次縮小……最終找到目標(biāo)數(shù)據(jù)。如搜尋目標(biāo)數(shù)據(jù)0.56789，將最后一位數(shù)是9的形成子塊1，在子塊1中倒數(shù)第二位數(shù)是8成子塊2，在子塊2中倒數(shù)第三位是7的成子塊3……最后得目標(biāo)數(shù)據(jù)如0.567890。

三、計(jì)算結(jié)果

目標(biāo)本征值的所需時(shí)間

目標(biāo)本征值的時(shí)間和空間（字節(jié)數(shù)）

四、討論與分析

1.算法相表1同，尋找相同位置的目標(biāo)數(shù)據(jù)所需時(shí)間與字節(jié)數(shù)（空間數(shù)）隨位型有變化

從表1、表2看出無論只用2分法（或大圈縮小法）搜尋不同數(shù)據(jù)群中相同位置的目標(biāo)數(shù)據(jù)時(shí)，搜尋時(shí)間和空間（字節(jié)數(shù)）會(huì)隨位型即N 同k增加或k同N增加（要始終滿足k≤N/2）而增加，這是因?yàn)殡S著格點(diǎn)數(shù)N（k）增加，本征值個(gè)數(shù)增加，搜尋要過濾的數(shù)據(jù)多些，所需的時(shí)間和空間（字節(jié)數(shù)）自然會(huì)長(zhǎng)些。

2.同位型而不同算法尋找相同位置的目標(biāo)數(shù)據(jù)所需時(shí)間與空間（字節(jié)數(shù)）不同

從表3看出同位型下，尋找相同位置的目標(biāo)數(shù)據(jù)，大圈縮小法由于搜尋時(shí)逐個(gè)過濾數(shù)據(jù)，所以不省時(shí)，花時(shí)長(zhǎng)，耗費(fèi)空間（字節(jié)數(shù)）較大，2分法則所需時(shí)間耗費(fèi)空間（字節(jié)數(shù)）均相對(duì)較小。

3.算法的時(shí)間與空間論述

3.1 算法的時(shí)間計(jì)量與時(shí)間復(fù)雜度

一個(gè)算法所耗費(fèi)的時(shí)間，是該算法中每條語句的執(zhí)行時(shí)間之和，每條語句的執(zhí)行時(shí)間是該語句的執(zhí)行次數(shù)（稱為頻度（Frequency Count））與該語句執(zhí)行一次所需時(shí)間的乘積，假設(shè)執(zhí)行每條語句所需的時(shí)間均是單位時(shí)間，一個(gè)算法的時(shí)間耗費(fèi)就是該算法中所有語句的頻度之和；當(dāng)一個(gè)算法的時(shí)間復(fù)雜度（Time Complexity）T（n）則是該算法的時(shí)間耗費(fèi)，是該算法所求解問題規(guī)模n的函數(shù)。 很多算法的時(shí)間復(fù)雜度不僅僅是問題規(guī)模n的函數(shù)，還與它處理的數(shù)據(jù)集的狀態(tài)有關(guān)。通常是根據(jù)數(shù)據(jù)集合中可能出現(xiàn)的最壞情況，估計(jì)出算法的最壞（Worst）時(shí)間復(fù)雜度。

3.2 目標(biāo)數(shù)據(jù)按序號(hào)查找與按值查找的平均時(shí)間復(fù)雜度相同

1）按序號(hào)查找 只能從頭個(gè)數(shù)據(jù)出發(fā)，逐個(gè)往下搜索，直至搜到該數(shù)為止，它和被尋找的位置有關(guān)，在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：

。2）按值查找 數(shù)據(jù)集中，查找是否有值等于給定值，若有的話，則返回首次找到給定值的儲(chǔ)存位置；否則返回NULL，查找過程從開始出發(fā)，逐個(gè)將數(shù)值與給定的數(shù)值作比較，平均時(shí)間復(fù)雜度也為 。

3.3 算法的空間論述

一個(gè)算法的空間復(fù)雜度（Space Complexity）S（n）定義為該算法所耗費(fèi)的存儲(chǔ)空間，它也是問題規(guī)模n的函數(shù)，算法不同，所耗費(fèi)的存儲(chǔ)空間也不同。

4.算法與程序的比較

算法的含義與程序相似，但二者有區(qū)別，一個(gè)程序不一定滿足有窮性，例如，系統(tǒng)程序中的操作系統(tǒng)，只要整個(gè)系統(tǒng)不遭破壞，它就永不會(huì)停止，即使沒有作業(yè)處理，它仍處于一個(gè)等待循環(huán)中，以待新作業(yè)的進(jìn)入，因此操作系統(tǒng)就不是一個(gè)算法。另外，程序中的指令必須是機(jī)器可執(zhí)行的，而算法中的指令則無此限制，但一個(gè)算法若用機(jī)器可執(zhí)行的語言書寫，則它就是一個(gè)程序。一個(gè)算法可用自然語言、數(shù)學(xué)語言或約定的符號(hào)語言來描述。

五、研究意義

本文將海森堡模型位型[N，k] 的本征值構(gòu)成數(shù)據(jù)群，進(jìn)行同位型不同算法和相同算法不同位型的目標(biāo)數(shù)據(jù)查詢所需時(shí)間與耗費(fèi)的儲(chǔ)存空間（字節(jié)數(shù)）情況進(jìn)行討論并結(jié)合算法進(jìn)行分析以讓讀者們對(duì)搜尋目標(biāo)數(shù)據(jù)有較好的了解，可為研究者們?cè)谘芯抗ぷ髦凶魈岣哌\(yùn)算效率的借鑒。

參考文獻(xiàn)

[1]席擁軍，方建興，朱士群，錢學(xué)旻.利用三對(duì)糾纏粒子作為通道實(shí)現(xiàn)任意三粒子量子態(tài)的概率傳送[J].量子電子學(xué)報(bào)，2006年第1期（第23卷）： 61.

[2]劉林曜，胡孟軍，呂洪君，解光軍.基于任意BELL態(tài)的量子密鑰分配[J]？. 量子電子學(xué)報(bào)， 2013年第4期（第30卷）： 439-444.

[3]蔣忠勝，呂洪君，解光軍.多維量子超密編碼可控信息傳輸[J].量子電子學(xué)報(bào)，2013年第4期（第30卷）： 450-454.

[4]韓文娟，周勛，張?zhí)珮s.海森堡模型中概率及相應(yīng)熵的計(jì)算分析[J]？量子電子學(xué)報(bào)，2012年第4期（第29卷）： 427-433.

[5]韓文娟，黃敏，劉海.海森堡鏈XY模型在一定位型下能譜[J].貴州大學(xué)學(xué)報(bào)（自然科學(xué)版） ， 2007年第3期（第24卷）： 244～246.

[6]唐策善.數(shù)據(jù)結(jié)構(gòu)[M].北京：高等教育出版社，1995.192.