基于离散时间量子行走的空间搜索算法研究

Since quantum walk provides the probability to speedup classical random walk, recent years quantum-walk based spatial search algorithm becomes an important research topic in quantum computation. One of the core problems is on what kind of graphs can spatial search algorithms achieve quantum speedup. In the oracle based iterative algorithm framework, the difficulty is to obtain the characteristic spectrum of the evolutionary operator in order to analyze the evolution process. Aiming at the unsolved problems in spatial search algorithm based on discrete-time quantum walk, this project plans to do the following work: (1) Study the evolutionary process of single target search on Johnson graph, present analytical result of time complexity and maximum success probability of the search algorithm. (2) Determine whether the search for multiple targets on strongly regular graphs gains quantum speedup by proving whether it is an instance of abstract search algorithm, reveal the effects of the number and position distribution of multiple targets on the performance of search algorithm. (3) Starting with the abstract search algorithm and basic pairing theory, propose a more general framework describing optimal quantum search algorithm to theoretically solve the spatial search problem.

量子行走提供了加速经典随机行走的可能性，近年来基于量子行走的空间搜索算法成为量子计算领域的重要研究课题。空间搜索算法研究的核心问题之一是在何种图上的搜索具有量子加速。在基于oracle的迭代算法框架下，求得演化算子的特征谱以确定算法的演化过程是算法分析的难点。针对离散时间量子行走空间搜索算法的未解问题，本项目拟完成：(1)采用算子扰动理论(基本配对定理)研究Johnson图上单目标搜索，确定算法的时间复杂度以及最大成功概率。(2)通过论证算法是否为抽象搜索算法的实例，确定强正则图上多目标搜索是否有量子加速，结合仿真实验揭示搜索目标的数量和分布对算法性能的影响。(3)从基本配对定理和抽象搜索算法入手，提出描述最优量子搜索算法的更一般化的框架，从理论上推动空间搜索问题的解决。

量子行走提供了加速经典随机行走的可能性，近年来基于量子行走的算法成为量子计算领域的重要研究课题。我们证明量子行走搜索算法在Johnson图和强正则图上分别搜索单个和多个目标时具有量子加速，讨论了四种离散时间量子行走（Discrete-time Quantum Walk, DTQW）搜索算法的性能，并通过完美状态转移（Perfect State Transfer, PST）问题探讨了量子计算模型的计算能力。.1）基于散射量子行走考虑Johnson图J(n,3)上的搜索问题。将搜索空间限定在与坍缩图相对应的低维子空间中，使用矩阵扰动理论证明J(n,3)上的离散时间量子行走算法具有量子加速。这一理论分析过程可用于任意确定k 的Johnson图J(n,k)。.基于连续时间量子行走(Continuous-time Quantum Walk, CTQW)考虑强正则图(N,k,λ,u)上的多目标搜索。使用路径计数的方法并将CTQW的跳转率设置为1/k的情况下，证明了两目标搜索的时间为O(√N)。.2) 基于DTQW的搜索算法可以看作是标准量子行走的变体。证明四种最常用的搜索算法可以归约为两种，记为U_I'和U_D'。二者在搜索单个或多个不相邻顶点时等价。对于多个相邻的目标顶点，数值仿真结果表明算法的性能依赖于图的密度，且U_D'比U_I'对此更敏感。设计量子搜索算法的三维可视化软件，探索难以给出理论分析的算法性能，给出算法运行过程及结果的直观展示。.3）研究二重Cayley树上两个根节点之间是否允许完美状态转移，借此探讨量子行走模型的计算能力。证明PST可以通过不重复的量子行走在根节点间距离的时间步内实现，而CTQW和传统的使用Grover硬币的行走均无法实现。上述结论为DTQW拥有比CTQW更强大的计算能力提供了支撑。