關于海森堡模型中尋找目標數據算法的討論

韓文娟++黃敏

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

關鍵詞：海森堡模型 本征值 目標數據 算法 時間

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

一、引言

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

二、背景知識

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

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

，則 ， 、

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

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

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

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

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

例如： 假設被查找的有序表中數序列為：

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

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

4.大圈縮小法

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

三、計算結果

目標本征值的所需時間

目標本征值的時間和空間（字節數）

四、討論與分析

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

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

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

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

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

3.1 算法的時間計量與時間復雜度

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

3.2 目標數據按序號查找與按值查找的平均時間復雜度相同

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

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

3.3 算法的空間論述

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

4.算法與程序的比較

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

五、研究意義

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

參考文獻

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

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

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

[4]韓文娟，周勛，張太榮.海森堡模型中概率及相應熵的計算分析[J]？量子電子學報，2012年第4期（第29卷）： 427-433.

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

[6]唐策善.數據結構[M].北京：高等教育出版社，1995.192.