韓文娟++黃敏

摘 要： 對海森堡模型位型[N，k] （N為海森堡鏈總格點數(shù)， k為格點中自旋向上的電子數(shù)）中尋找目標數(shù)據(jù)的算法進行討論分析。研究方法：將模型的能量矩陣對角化所得到的本征值構(gòu)成數(shù)據(jù)群，使用Fortran編程查找群中的目標數(shù)據(jù)并進行算法的分析討論。研究結(jié)論：參數(shù)相同時，對于位型[N，k]（k≤N/2） ，當N（k）同，k（N）增大時，獲取模型同位置的目標數(shù)據(jù)搜尋時間和所需要的輔助空間（字節(jié)數(shù)）均增加；同一位型[N，k]，獲取同位置的目標數(shù)據(jù)搜尋時間和所需要的輔助空間（字節(jié)數(shù)）均不同。通過對海森堡模型搜尋目標數(shù)據(jù)的算法討論可為研究者們在研究工作中作提高運算效率的借鑒。

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

中圖分類號：O431.2 文獻標識碼：A 文章編號：1003-9082（2016）04-0002-02

一、引言

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

二、背景知識

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

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

，則 ， 、

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

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

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

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

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

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

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

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

4.大圈縮小法

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

三、計算結(jié)果

目標本征值的所需時間

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

四、討論與分析

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

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

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

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

3.算法的時間與空間論述

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

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

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

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

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

3.3 算法的空間論述

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

4.算法與程序的比較

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

五、研究意義

本文將海森堡模型位型[N，k] 的本征值構(gòu)成數(shù)據(jù)群，進行同位型不同算法和相同算法不同位型的目標數(shù)據(jù)查詢所需時間與耗費的儲存空間（字節(jié)數(shù)）情況進行討論并結(jié)合算法進行分析以讓讀者們對搜尋目標數(shù)據(jù)有較好的了解，可為研究者們在研究工作中作提高運算效率的借鑒。

參考文獻

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

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

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

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

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

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