基于分立时间量子行走的量子搜索算法的研究

The universal quantum computer can be realized based on quantum walks(QWs) from both software and hardware. The coin and walker are in the quantum superposition state in discrete-time QWs and the quantum walker can spread faster than the classical random walks quadratically. The quantum search algorhthm can be devised based on the discrete-time QWs, and our goal is to find the target element as soon as possible with nearly 100％ success probability. The necessary evolution steps and the success probability depends on the different graphic structures and the coin operators. Compared to the Grover quantum search algorithm, the QWs algorithm can be implemented more easily and more robust to the noise. This work will further improve the realization of the quantum computer.

量子行走可以从软件和硬件两个方面帮助实现通用量子计算机。分立时间量子行走中，硬币和行走者处于量子相干叠加态，体现的是几率幅的叠加，这就导致了量子行走相比较经典随机行走的扩散速率更快并且呈现二次方的增长趋势。本项目利用量子行走特殊的性质，开发基于分立时间量子行走的量子搜索算法，目标是用尽量少的演化步数以接近100％的成功概率找到目标元素的位置。具体研究不同的图形结构、硬币操作对量子行走搜索算法成功概率以及所需运算步数的影响。量子行走搜索算法相比较Grover量子搜索算法，有更加易于物理实现以及更好的抵抗噪声等优势，将会进一步推进量子计算机的实现。

非均匀量子行走广泛用于设计更高效率和更好性能的算法、实现高维量子态的制备和测量、以及模拟复杂的量子现象等。行走中的高斯分布和等几率分布是算法中广泛使用的分布。保持相干性的等几率分布，即：所有可能的位置的等几率幅叠加，可以看成是W型最大纠缠态，是量子信息的重要资源，用于量子并行计算和多比特真随机数的产生。量子行走通过级联一系列硬币操作和行走操作实现。首先，我们完成了非均匀量子行走基本性质的探讨，其非均匀性通过随位置和演化时间改变的硬币操作实现，具体通过行走者的位置分布、扩散速率、以及硬币-行走者纠缠关联进行定量描述。提出非均匀量子行走制备行走者-硬币最大纠缠态，同时保持二次提速的理论方案。相比较之前的理论方法需要100步才能得到最大纠缠，以及相干相消导致行走者扩散速率降低，本方案在所有奇数步以及大于10的偶数步演化后都能得到最大纠缠，同时保持多路径相干相长模式，因此行走者呈现二次提速的扩散性质。此外，非均匀量子行走中可回复性与演化后分布是否对称无关，仅与非对称操作有关，这是量子行走除了二次提速外，区别于经典随机行走的另一个性质。其次，我们和南京大学量子光学组合作完成了非均匀量子行走的光学实验工作。采用光的水平和竖直偏振态表示两个不同的硬币态，将行走者的位置转化为光子到达探测器的时间，将光学半波片与电光位相调制器结合实现非均匀量子行走的多样性演化。采用时分复用技术测量硬币状态以及行走者的位置分布，由实验数据计算每一步演化后硬币的冯.诺依曼熵以及行走者的扩散速率。实验结果和理论分析基本符合。最后，我们通过改变随演化时间和位置变化的硬币操作，基于非均匀量子行走实现了高斯、等几率等任意分布。装置的环状结构严格保证了在整个演化过程中始终保留量子相干性，为实现多比特真随机、并行量子计算、量子算法演示、量子态调控等提供精确操控的平台。