CMP | 随机分层图上的指数级量子游走加速

量子计算领域的一个核心研究方向是对哪些问题可以实现量子加速，特别是可以实现超多项式乃至指数级的量子加速。此前，达到这个级别的量子算法多来自代数与数论，以 Shor 算法为代表^[1]，需要明显的群论结构。

在图论中，Childs 等人^[2]的工作研究了焊接树上的量子游走，是少数不依赖群结构却实现指数级量子加速的标志性结果：量子游走在多项式时间内以高成功概率到达图的出口顶点，而经典算法则需指数时间到达出口顶点。然而，该构造非常脆弱，对图结构的微扰（如短环）极为敏感，推广困难重重。

因此，量子游走是否可以对更广泛的图论问题达到超多项式乃至指数级的量子加速，是量子计算、理论计算机科学领域均十分关注的问题。

我们考虑连续时间量子游走：给定无向图的邻接矩阵  ，系统哈密顿量为  ，系统随时间演化，在  时刻为酉变换  。算法从起始顶点出发，演化一个（按合适分布抽取的）时间  后测量，目标是在有限时间内“击中”给定的出口顶点。

 我们考虑如下定义的随机分层图  ：

• 首先有一个“超图”  ：每个超顶点  对应一个顶点集  ，其大小为  ；

• 每条超边 生成 条在 与 之间的随机边（满足若干约束）。这里 ， 均为事先指定的参数；

• 把所有超顶点/超边展开，即得实际大图  。

这一设定允许我们以结构清晰的方式，将宏观几何（如一维链、二维/三维晶格）与微观随机连接耦合起来。一个具有一维链结构分层结构的随机图如下所示。

一维情形：超多项式加速的“常态化”

当超图  具有一维链结构且相邻超顶点规模的对数比值有界时，我们证明：

• 任一经典算法若要以非忽略概率从起始顶点到出口顶点，其时间至少为  ；

• 量子游走在时间  内到达且成功率为  ，其中  与  均由一个依赖边数序列（偶-奇位点之差的对数和）的指数项乘以  为上界；

• 在该结果中，“焊接树”这个特例可达到指数加速，而在更通用的一维随机模型中，超多项式加速更为典型。这为过去“指数级量子加速在图论中仅是孤例”的印象提供了直观。

更高维与更一般结构：从零模到指数加速

在高维情况下，我们将超图推广到 d 维晶格上（如 Lieb 晶格^[3]）。我们的分析借鉴了凝聚态理论中的零能模数量与结构理论，并以此分析量子游走的可达性与速度——当零模非局域化且相干传播有效时，量子游走击中时间可达到超多项式乃至指数级量子加速。

论文的主要结果可以总结为下面的表格。

（1）图稀疏化：一个可“造图”的普适方法

（2）技术关键：有效维数与 Krylov 子空间

（3）物理直觉：与 Anderson 局域化的联系

本工作将焊接树指数加速这一孤例推广到一系列可系统构造、可谱分析的具有分层结构的随机图上。分析上，这项工作采用了物理化的“零模（去）局域化—Krylov 子空间”的观点。作为总结，这项工作既提供了新的范式来证明量子计算超多项式乃至指数级的量子加速，也为量子计算与凝聚态物理的交叉研究打开了可操作的通道。

本工作引出了若干值得进一步探讨的开放问题：

1） 指数 vs. 超多项式的边界：在更高维、不同随机度量与连边规则下，指数级加速的充要条件是什么？能否给出“谱—几何结构”之间的统一判据？

2）稳健性与结构扰动：当分层图中引入局部结构（如短环）时，量子加速如何退化或保持？我们的工作已指出当图具有一定程度结构时有显著的量子加速，但是更完整的答案仍需系统性研究。

3）构造性与工程化：图稀疏化流程能否导出当前量子计算实验可实现的拓扑（如在光子/超导平台上可编程实现）？怎样把“谱去局域化”的要求转译为器件层面的可控参数？

[1] Peter W. Shor, "Algorithms for quantum computation: discrete logarithms and factoring." In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pp. 124-134. 1994.

[2] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman. "Exponential algorithmic speedup by a quantum walk." In Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 59-68. 2003.

[3] Elliott H. Lieb. "Two theorems on the Hubbard model." Physical Review Letters 62, no. 10 (1989): 1201.

[4] Philip W. Anderson. "Absence of diffusion in certain random lattices." Physical Review 109, no. 5 (1958): 1492.

图文 | 李彤阳

PKU QUARK Lab