量子算法为解决经典计算机上的困难问题带来了新的可能性,在实际问题上表现出了在时间复杂度上的优越性。目前量子算法对于少数的NP-hard问题可以实现指数加速（Shor大数质因子算法）,对于大多数问题可以实现二次加速。例如基于绝热演化的最大团算法和图同构算法都达到了二次加速;大多数基于搜索的经典算法可以通过Grover算法进行二次加速。如何创新性地推出更高效的量子算法,以及基于量子计算思维启发的高效经典算法是学术界关注与研究的基础问题。基于量子行走的量子算法目前被广泛应用于新算法的设计。量子行走是经典随机行走在量子系统的推广,由于量子行走是一种通用的量子算法模型,故可以通过量子行走构建其他新的量子算法。本文的研究主要涉及量子行走及其应用。由于量子行走传递特性和其行走的图或者网络的代数结构有着天然的关联性,特定代数结构的图上的量子行走有助于解决不同的问题。例如强正则图上的量子行走可以应用于空间搜索算法,循环图上的量子行走可以实现完美态传递等。然而图的复杂性也导致了图上量子行走的复杂性质,这使得获取量子行走的行走概率极其困难。针对这些问题,我们作了如下的研究工作:（1）量子行走概率计算方法的研究。驱动连续时间量子行走（Continous Time Quantum Walk,CTQW）的哈密顿量为图的拉普拉斯矩阵或者邻接矩阵,因此行走概率获取的传统方法为矩阵的特征值分解法。通常情况下,矩阵的特征值分解无法得到解析解,因此对于一般图只能通过数值计算的方法获取CTQW的行走概率。尽管特征分解的方法不适用于大部分图,但是对于一些特殊类型的图,通过特征分解可以解析地获得CTQW的传输概率,如完全图,超立方体等。对于强正则图和齐次树等图,邻接矩阵特征分解的方式不适用。对此,我们采用了一种基于图的通路数计数的方法,并成功地获得了这些图的行走概率。（2）Cycle图的完美态传递。Bose提出了链上的量子传输,并研究了利用自旋链实现量子计算和短距离量子通信的可能性。Christandl进一步研究了XY链（Chain or Path）以实现链上两端点之间的完美态传递。距离正则图,循环图上的完美态传递也由G.Coutinho,Milan等人做出了详尽的研究。链上的完美态传递可以通过研究雅可比矩阵和正交多项式获得,距离正则图和循环图上的完美态传递可以通过谱分解等方法获得。Cycle图是链的一个简单扩展,但是其上的完美态传递对应一个周期雅可比矩阵的逆问题,目前还没有针对这个问题的有效方法。我们发现,Cycle可以分解为两条端点带自环（Loop）的链,而对于链的研究则可归结为雅可比矩阵的逆问题,进而给出得到完美态传递Cycle的谱条件和雅可比矩阵逆问题的求解算法。（3）基于CTQW的多目标空间搜索。Grover搜索能对经典搜索算法提供二次加速,在Grover搜索中,任意的两个基态之间都有转移率。但是很多实际的物理网络受到空间限制,而物理硬件之间的访问或者传输只能在物理上相邻的介质之间才能发生。这种只有相邻顶点之间才具有转移率的量子搜索被称为空间搜索。很多图上空间搜索可以实现对于经典搜索的二次加速,这些网络包括强正则图,超立方体,完全图等。其中完全图上的空间搜索等价于Grover搜索。很多网络甚至能够实现多目标搜索的加速。利用概率幅度的通路计数计算方法,我们研究了强正则图上的双目标空间搜索,并给出了搜索达到二次加速的时间以及参数设置。（4）基于CTQW的最大团算法研究最大团问题是一个经典的NP-Complete问题（Non-deterministic Polynomial Complete Problem）。目前最大团问题的最优的精确算法的复杂度为2N4,N为问题规模。对于NP-complete问题的量子算法主要有基于Grover搜索的嵌套搜索算法,以及基于量子绝热演化的算法。这些算法的复杂度对于经典算法而言有二次的加速,因此其复杂度依然是指数级的。在CTQW中,不同点具有不同行走概率和概率幅度,这些概率幅和概率都是周期函数。概率幅度的频率分量上的强度在一定程度上反应了顶点是否属于最大团。本文设计了一种基于CTQW的最大团搜索算法。在大量的数值实验中,反例没有被发现。但是,由于随着图的增大,多项式的时间复杂度依然需要大量的时间。因此,对于更大的图还不能有效地验证。（5）基于量子线路的图同构算法研究已有的研究表明,基于CTQW的图同构算法无法区分非同构的强正则图,即非同构的同参数强正则图上的CTQW表现出相同的传输概率和概率幅度。如何利用通过量子算法来区分强正则图依然是一个开放问题。在论文的最后一个部分中,我们提出了一种基于图的重构猜想量子算法。我们首先提出了图的统计特征矢以及图册的统计特征矢概念;然后通过量子线路计算出图的统计特征矢量或者图册的统计特征矢量;最后根据统计特征失量是否相等来判定图是否同构。在强正则图上进行的数值实验,结果表明了该方法可区分所有顶点数小于等于64点的强正则图（没有多于64点同参数非同构的强正则图的数据）。