量子行走搜索算法在计算科学中的应用研究

论文摘要

量子计算中一个很重要的研究热点是量子行走。连续时间量子行走和离散时间量子行走已经得到广泛研究。在计算机科学中,经典随机行走常被应用于工程和许多科学领域,是设计随机算法的一个非常强大的工具。因此量子行走作为经典随机行走算法的量子版本,我们有理由期望量子行走将在量子算法设计中有优越的表现。为了更好的理解量子行走,本文对量子行走做了更深入的研究,主要的工作有两方面:第一,我们讨论了如何实现有向图上的连续时间量子行走(CTQW)。有向图和无向图是图论中的两大分类,对于无向图,其邻接矩阵为厄米矩阵;对于有向图,其对应的邻接矩阵为非厄米矩阵。本文从这两类图的差异出发,研究应用量子行走的难点以及各自量子行走的性质。近年来,在具备对称性的无向图上的离散时间量子行走(DTQW)有许多的研究结果。如经典退火过程的量子行走模拟器、关联光子的纠缠性质等等。然而,有向图对应的邻接矩阵具备非厄米性,这将导致系统演化的概率不守恒,且当前量子计算机或量子模拟器缺乏实现非幺正时间演化量子行走的能力。本文中,我们证明了这两个障碍可以利用幺正膨化的方法解决。以三节点有向图为实例,探讨了重构后的演化算符在有向图上的演化行为。同时,注意到量子行走在图或网络中的潜在应用价值,研究了有向图上CTQW的特性以及CTQW与网络节点相对重要性的关联。第二,由于重构后的演化算符为幺正矩阵,为此设计了光学实验以验证有向图上量子行走的方案,并对实验结果与理论值进行了对比。基于量子行走的算法能否用于分析复杂网络(通常由非厄米邻接矩阵构成)并提供有效的排序策略具有重要的理论和实践意义。近年来,除之前广泛应用的离散系统量子模拟器,由耦合光波导晶格的制备和单光子源的技术发展,使得实验研究单光子和关联光子在离散晶格上的CTQW成为可能。本文利用线性光学器件,分别介绍了初态的制备过程、6维幺正矩阵的分解方法和光路实现步骤。最后为了说明有向图上的CTQW具备中心测度的特性,本论文以两个三节点有向图为例,制备初态在全局等权态上,进而实现幺正变换,并利用投影测量获得实验结果。经与理论值对比,实验结果保持了一致性,证明CTQW能够用以网络中心性测试和页面排序,给复杂网络分析提供有效的排序策略。

论文目录

文章来源

类型: 硕士论文

作者: 石雨豪

导师: 薛鹏

关键词: 量子行走,有向图,中心性测试,页面排序

来源: 东南大学

年度: 2019

分类: 基础科学,信息科技

专业: 物理学,计算机软件及计算机应用

单位: 东南大学

分类号: O413.1;TP301.6

DOI: 10.27014/d.cnki.gdnau.2019.000749

总页数: 83

文件大小: 5424K

下载量: 50

相关论文文献

• [1].一维分离时间量子行走的拓扑特性研究[J]. 山西大学学报(自然科学版) 2017(01)
• [2].基于连续时间量子游走的链路预测方法研究[J]. 计算机应用研究 2016(01)
• [3].逾渗分立时间量子行走的传输及纠缠特性[J]. 物理学报 2017(13)
• [4].一维单点位置缺陷分离时间量子行走的传输特性[J]. 山西大学学报(自然科学版) 2019(01)
• [5].一维非幺正分离时间量子行走的拓扑特性的检测[J]. 山西大学学报(自然科学版) 2019(03)
• [6].多维连续时间量子随机游动的It公式[J]. 数学物理学报 2016(04)
• [7].微观粒子的量子摄动理论[J]. 中国粉体技术 2012(04)
• [8].无序反射下分离时间量子行走的纠缠特性研究[J]. 山西大学学报(自然科学版) 2018(02)
• [9].连续时间量子行走在粘接树图上的散射特性研究[J]. 山西大学学报(自然科学版) 2014(04)
• [10].氢原子的量子力学表征[J]. 中国粉体技术 2009(05)
• [11].一维相位缺陷量子行走的共振传输[J]. 物理学报 2016(06)

标签：量子行走论文;  有向图论文;  中心性测试论文;  页面排序论文;