量子游走相关算法研究进展

李萌 孙晓明,2

(1.中国科学院计算技术研究所 处理器芯片全国重点实验室，北京 100190；2.中国科学院大学，北京 100049)

0 引言

量子计算的发展趋势欣欣向荣，量子比特本身的存在就意味着相较于经典计算所具有的指数增加的运算空间和相应强大的并行性，有指数加速的潜力，未来能够被应用于密码破译、量子化学、工程计算、人工智能、材料模拟、金融经济等方面，甚至可以突破经典计算的瓶颈。虽然量子计算由于量子力学所特有的量子叠加和量子纠缠使得其在某些具体问题上的解决速度和效果大大提升，但如何发挥其并行优势，提高普遍计算力是当下最为关键的挑战之一。同时，真正通用的量子计算机还未建造成功，甚至一个在规模上有限制的通用物理设备仍有待设计和构建，量子计算优越性的充分体现更要依赖于量子算法的巧妙构思。

近年来量子算法的设计需要和应用需求不断增长。无论是有直接加速效果的，还是可以在带噪音中等规模量子设备(Noisy Intermediate-Scale Quantum Technology，NISQ)上运行展示优越性的量子算法，其研究从未中断。Shor算法在多项式时间内解决了大数因子分解问题[1]；Grover算法对于无结构数据库的搜索问题相较于经典算法可以达到平方加速的效果[2]。除了这些早期的著名量子算法，还有一类以量子游走为基础的量子算法在蓬勃发展，且在实验和应用方面展示出了巨大的活力和潜力。

经典的随机游走可以用作设计随机算法的计算框架，因此被广泛应用到包括计算机学科在内的许多学科中。量子游走刻画了微观世界中波函数的动力学演化过程，是经典随机游走在量子世界的对应和推广，但二者却很不一样。比如经典随机游走的概率分布是高斯型，而在量子情况下它具有多个峰值，不断震荡，扩散速度呈现平方式的增长。量子叠加和量子干涉特性使得量子游走有着显著区别于经典随机游走的优势。基于此可以利用量子游走开发高效量子算法，例如量子搜索算法、元素区分等，这些量子游走算法的性能表现相较于经典算法均会有加速效果。同时，随着研究的深入，量子游走陆续被证明是一种通用的量子计算模型。任何量子过程都可以理解为系统的动力学演化，进一步可以用量子游走来模拟。因此，量子游走为量子信息处理提供了一个直观的框架，是基础的量子算法设计工具之一，也是创新量子技术的核心之一[3-6]。

本文将首先介绍量子游走的基本概念和基本原理；然后介绍基于量子游走的几种搜索算法的发展，以及量子游走在其他相关应用中的关键进展；最后对量子游走未来的发展进行总结和展望。

1 量子游走简介

经典随机游走在数学上刻画了一系列随机步骤演变的过程。这一随机过程通常被描述为马尔可夫过程，游走者的下一个位置只取决于它当前的位置，不依赖于游走者之前时刻的任何信息。像花粉的布朗运动、波动的股票价格，以及高尔顿钉板和醉汉问题均属于经典随机游走。在经典的随机游走中，游走者本身占据一定的状态，状态间的随机跃迁导致了随机性的产生。这一概念最初由Pearson引入[7]，随后逐渐被用作计算机科学和各类算法发展的基本框架之一，且在计算机科学中有着广泛的应用，比如PageRank[8]、计算机视觉[9]和复杂社交网络分析[10]等。

Aharonov等人于1993年将量子物理与经典随机游走结合起来，首次提出量子游走模型[11]。量子状态的叠加和确定可逆的酉演化产生了随机性。与经典随机游走类似，量子游走可以分为离散时间量子游走和连续时间量子游走，二者在具体形式上有明显的差异。相比于连续时间量子游走，量子硬币为离散时间量子游走提供了额外的自由度，因此二者在性质上也有一定的差异和联系[12]。下面对二者做一些简单刻画[13]。

连续时间量子游走(Continuous Time Quantum Walk)依赖于图的拓扑结构。对于给定的图G=(V,E)，其邻接矩阵A和拉普拉斯矩阵L均是一|V|×|V|的矩阵，具体如下：

(1)

其中，deg(i)是顶点i的度。连续时间量子游走则发生于顶点对应的标准正交基态所张成的希尔伯特空间中，对于任意给定的初态|φ(0)〉，t步演化时间后的量子态为|φ(t)〉=e-iLt|φ(0)〉。

量子游走是基于量子力学的随机游走，其中游走者演化的初始状态和最终状态之间通过遍历图的边，在离散时间节点或通过基于图邻接矩阵的哈密顿量进行连续演化。此外，还有一些其他的量子游走模型。下面对Staggered量子游走(Staggered Quantum Walk)[14]和Szegedy’s量子游走(Szegedy’s Quantum Walk)[15]做一简单介绍。

(2)

由此定义两个反射算子：

(3)

一步量子游走演化算子即为：

U=RYRX

(4)

鉴于经典随机游走在数学、物理和计算机等学科领域的广泛应用，量子游走的应用研究也引发了极大的关注。受到量子干涉的影响，与经典随机游走相比，量子游走的扩散速度会明显变快，有平方级别的加速效果。因此，下面就基于量子游走的搜索算法和其他相关应用进行一一介绍。

2 基于量子游走的搜索算法

空间搜索问题是利用经典随机游走来解决的一类常见问题。在这类问题中，无向图G中有一个由标记顶点组成的顶点子集M，游走的方式由无向图G的边决定。空间搜索问题的目标是通过沿着图的边对图遍历以期用最短的时间来找到其中一个被标记的顶点。寻找标记顶点的一个简单策略是对图G进行随机游走，反复应用一些随机矩阵，直到达到其中一个标记顶点。相应地，量子游走也被用来解决空间搜索问题，并相较经典随机游走情形有一定的加速效果。这里将对两种关键框架(基于马尔可夫链的和基于不同图结构的)下量子游走搜索算法的由来、发展和现状做简要介绍。

然而，以上方法只能在非常有限的情况下找到被标记的顶点，要么对图结构有限制，要么对标记点的个数或分布有要求。基于此，Ambainis等人通过引入每步量子游走停留在标记点的概率p，利用插值的思想，基于量子游走并结合Quantum Fast-forwarding技术，在任意图上对于任意数量和排布方式的标记点，相比于经典搜索算法均可以实现平方加速的效果[25]。

除了以上基于马尔可夫链发展出的量子游走搜索算法以外，还有诸多工作是围绕不同的图展开的。基本的做法一般是初始化整个量子系统到均衡叠加态，连续作用量子游走搜索算子，对位置寄存器进行测量，检查被测量顶点是否为标记点。主要的技术手段就是基于空间结构和标记点的分布特点对空间中的点进行分类，以此得到量子游走搜索算子的归约不变子空间，从而达到降维的目的、简化计算，然后可直接进行谱分解对演化过程进行清晰刻画，同时可以结合增加自环、调整权重等手段提高搜索算法的成功概率。这一研究工作很大地依赖于图的对称性，目前业界对完全二分图[26-27]、Kroneckor图[28]、Johnson图[29]和强正则图[30]等均有研究。

3 量子游走相关应用

量子游走除了搜索，在其他方面也有诸多应用，如元素区分、测量、通用计算模型、完美状态传输和量子隐形传输等通信任务。

3.1 元素区分

元素区分问题是指对于给定的一列元素，判断这些元素是否均不同。即，对于给定的一个有限集X={x1,x2, … ,xn}，一个黑盒函数f:{1, 2,… ,n}→X，确定是否有两个不同的输入i≠j，有f(i)=f(j)，即xi=xj。

为了在经典计算机中解决这个问题，可查询有限集X中的所有元素，并对这些元素进行存储和排序，再遍历这个排序列表，来检查是否有重复的元素，因此需要Ω(n)次查询。

考虑这些元素两两组合构成的数对空间，即{(xi,xj):1≤i

Aaronson和Shi对区分一对一函数和两对一函数，证明了碰撞问题的Ω(n1/3)下界，由此进一步推出元素区分问题Ω(n2/3)的下界[32]。Ambainis等人主要借鉴了Grover算法和振幅放大等技巧，将该问题有效地转化为在图上搜索标记点的问题，利用量子游走搜索算法和在图上的量子游走得到问题的解，提出了具有加速效果的量子算法，其复杂度为O(n2/3)[33]。该算法从图中所有顶点的均匀叠加态开始；然后对非标记顶点执行一个转移规则，对标记顶点执行另一个转移规则；检查当前的顶点和移动到相邻的顶点都要花费一个时间步长；经过O(n2/3)步量子游走后，振幅聚集在标记顶点上，此时以常数概率测量得到标记状态。当然，这一算法也可以使用Staggered量子游走模型来实现[14]。

另外，该问题也可推广至判断在x1,x2,… ,xn中是否存在k个元素是相同的，对此基于量子游走的搜索算法的查询复杂度是O(nk/(k+1))[33]。类似地，量子游走算法也被用于解决找三角形问题[34]等。

3.2 通用计算

近年来量子游走陆续被证明是一种通用的计算模型。对于不同的量子游走模型，为证明其通用性，均是将量子计算编码到一个由量子线连接的图中，再基于此设计构成通用量子门集合的部件。由于量子计算到图的映射是等价的，从而可以证明这些量子游走模型均是通用计算模型。

Feynman为了给量子计算机这种计算设备提供一个物理上合理的描述，构造了一个哈密顿量来实现任意量子电路[35]。Childs扩展了Feynman的这一结果，首次证明了连续时间量子游走是一种通用的计算模型，即量子游走和量子电路本质上具有同样的能力，任意一个可以用通用量子计算机完成的任务也可以利用连续时间量子游走来完成[36]。事实上，对于一般的连续时间量子游走模型加以限制，即在稀疏图(低度的非加权图)上的量子游走对于量子计算均是通用的。Childs用虚拟量子线来表示计算基态，并通过散射理论讨论连接在导线上的小部件实现了3个量子门，即受控非门、π/8门和交换两个计算基的量子门。π/8门和交换两个计算基的量子门连续作用可以生成阿达玛门，而受控非门，阿达玛门和π/8门构成了一组通用量子门集合，故稀疏图上的连续时间量子游走可以有效地模拟任何量子电路，从而是一种通用的计算模型。

但是，用于对n个量子比特进行计算的图的规模关于n是指数级别的，而图中的各个顶点占据不同的空间位置，故量子游走不能有效地实现。鉴于此，Childs等人考虑了以上连续时间量子游走模型的推广，其中有许多相互作用的游走者；利用散射理论证明了多粒子量子游走能够实现通用的量子计算[37]，此时仅使用了多项式大小的图，故较之文献[36]更易于实验实现，并且可以作为构建一个可伸缩的量子计算机的架构，而不需要依赖时间的控制。

Lovett等人利用离散时间量子游走代替连续量子游走[36]，给出了一组同样的通用门集的等价构造，即受控非门、阿达玛门和π/8门，由此证明了离散时间量子游走和连续时间量子游走都是计算元件，具有通用性[38]。在连续时间量子游走的情况下[36]，图中任意顶点的最大度为3。而在离散时间的情况下，要用具有更高度的顶点来确保定向传播[38]。

一方面，量子游走是一种通用计算模型；另一方面，利用光学、离子阱、超导比特等在物理系统中实现量子游走的实验实现也有广泛的探索和深入的研究。因此，利用量子游走来实现量子门、量子电路，对于量子计算机的设计具有重要的潜力和较高的可行性，是未来研究的重要领域之一。

3.3 测量

量子测量在量子力学和量子信息处理中均起着基本的作用。半正定算子测量(Positive Operator Value Measure，POVM)相较于标准的冯诺伊曼投影测量会获得更多的信息。Kurzyński等人利用离散时间量子游走中游走者的概率振幅之间的干涉现象，证明了一维离散时间量子游走可以用来实现在单个量子比特上POVM的广义测量[40]。对于单个量子比特上任何秩1和秩2的POVM元素集{Ei}，都可以通过巧妙选取依赖于时间和位置空间的硬币算子以恰当工程化的量子游走来生成。在这种情况下，对游走者在位置x=i处的测量对应于在量子比特上的POVM元素Ei的测量。

随后在实验方面，Zhao等人使用光学设置，将量子比特编码在单个光子的偏振状态上，把量子游走的各个位置在光子路径上实现，给出了基于量子游走进行一个单量子比特上广义POVM测量的实验实现[41]。Bian等人也在光学系统中实现了基于量子游走的广义测量，关键是通过与位置相关的硬币旋转来控制硬币的内部动力学演化，进一步影响游走者的演化[42]。

Li等人进一步将理论结果从量子比特(Qubit)推广至Qudit，即基于量子游走实现了在Qudit上的广义测量，其中量子游走的步数是测量结果数目的两倍[43]。当然，除了POVM测量，利用量子游走也陆续实现了其他测量。在预先准备的相同的量子系统上的集体测量(Collective Measurement)就可以比局部测量(Local Measurement)提取更多的信息。Hou等人基于量子游走对两个相同的量子比特实现了确定性集体测量，并通过光量子游走实验实现了一个高保真度的集体测量，同时将其应用于量子态层析中[44]。

3.4 通信协议

量子游走是实现很多量子通信协议的有力工具之一，这里仅就量子游走在量子隐形传输和完美状态传输两方面的应用做简单介绍。

Wang等人基于两硬币量子游走提出了一种实现量子隐形传输的方法[45]。区别于传统的量子隐形传输协议，这一方案并不需要预先准备纠缠态，而是通过一步量子游走由条件移位算子就可以直接产生所需要的纠缠资源。此外，联合测量可以被两个投影测量替代，因此在实现上会更加简单。随后，Chatterjee等人在IBM量子平台上对这一协议提供了具体的实验展示[46]：主要利用IBM量子平台的五量子比特的机器和32比特的模拟器实现了k个量子比特的隐形传输，其中k=1, 2, 3，特别展示了Bell态、W态和GHZ态的隐形传输实验。同时，Li等人利用多游走者量子游走模型在直线、圈和带自环的两点完全图这3种图结构上实现了多比特量子态的隐形传输任务[47]。

除了以上利用量子游走在各个节点动态调控硬币操作来实现完美状态传输的方法以外，量子游走搜索算法也可以用来实现完美状态传输这一协议。考虑有两个标记顶点(发送点和接收点)的量子游走搜索算法，通过在标记顶点和非标记顶点处分别选取合适的硬币操作，可以较高概率地从发送顶点到达接收顶点。tefaňák等人讨论了星形图和带自环的完全图上的状态传输[52]。完全二部图[53-54]和完全多部图[55]上的完美状态传输也陆续得到分析。此外，在纠缠交换框架下，量子游走可以避开联合贝尔测量实现难这一瓶颈，在远距离几方之间实现纠缠的制备[56]。

4 结束语

量子游走作为一种有效的算法工具，本身具有强大的计算能力和应用潜力，在很多具体问题中的应用开发和算法设计都值得深入研究和探索。量子游走本身在实验方面的进展也令人欣喜，包括光子[57-59]、离子阱[60]、超导量子比特[61-62]和原子系统[63]等量子游走方案被先后提出。因此，基于量子游走的算法设计可行性高且效果前景好。

本文对量子游走做了简单介绍，列举了量子游走在搜索、元素区分、通用计算、通信协议和测量等方面的应用，希望可以启发研究人员将量子游走框架应用于量子信息处理和量子算法的设计之中，借助量子游走这一工具开发出更多能够体现量子优势的实用量子算法，实现相比于经典算法有多项式级别甚至指数级别的加速效果，实现量子游走在不同场景的应用，促进这一研究领域的不断向前发展。