关于海森堡模型中寻找目标数据算法的讨论

韩文娟++黄敏

摘 要： 对海森堡模型位型[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.