中山大学李绿周教授团队提出指数级加速“确定性”量子算法

　　量子算法的研究，一直是量子计算发展应用领域及进程极为关注的重点，昨日更新的量子算法动态研究显示，中山大学李绿周教授团队针对焊接树问题（Welded Tree Problem），在保证指数级加速的前提下，提出了即简单又具有确定性的量子算法。

　　相关研究以“Recover the original simplicity: concise and deterministic quantum algorithm for the welded tree problem”为题，以预印本形式提交到arXiv[1]，数值模拟表明，新算法的实际性能更好。

　　量子计算领域的一个主要目标是设计能够比经典算法更快地解决问题的量子算法。

　　量子游走（ Quantum Walks）是一种将经典游走推广到量子领域的方法，它在量子模拟、量子算法设计以及量子网络工程中扮演着重要的角色。

　　基于量子游走的一些搜索算法在解决经典问题时具有指数级别的加速，而有些则具有平方级别的加速。

　　当下，量子游走已发展成为算法设计的基本工具。

　　01.?指数级加速

　　量子游走分为离散时间量子游走（DTQW）和连续时间量子游走（CTQW）。

　　自Aharonov等科学家在三十年前首次创造“量子游走”一词以来，量子游走已成为理论和实验中的主要研究课题。

　　然而，到目前为止，基于DTQW框架的量子算法与最好的经典算法相比，最多只能提供二次加速。

　　对于基于DTQW框架的量子算法，是否能提供指数级加速，一直以来都并不清楚。

　　直到最近，研究提出了多维量子游走框架来解决焊接树问题，显示了基于DTQW框架的量子算法也可以实现对焊接树问题的指数加速。

　　02.?返璞归真，寻求根本

　　在该研究中，李绿周团队重新审视了焊接树问题的量子算法，并提出了一种纯粹基于最简单的量子游走相当简洁的算法，从而为焊接树问题提供了更简洁有效的解决方案。

　　与之前提出量子算法相比，它不仅保持指数速度加速，在理论上也是无误差的，使其成为少数几个体现无误差（精确）量子查询复杂性和随机查询复杂性之间指数分离的例子之一。

　　

　　图｜焊接树问题

　　

　　图｜实现广义 Grover 迭代的量子线路

　　

　　图｜数值模拟表明，新算法的实际性能更好

　　这项研究改变了在多维框架之前的DTQW框架最多只能实现二次速度提升的刻板印象。

　　量子算法一直是量子计算应用的关键，但是行业里的算法研究者们似乎过于拔高了问题的高度，难以下手，使得难以找到量子算法的突破之路。

　　正如李绿周教授所言：（量子）算法设计的本质在于返璞归真，即找到问题的根本性结构信息，并据此庖丁解牛。

　　引用：

　　[1]https://arxiv.org/abs/2304.08395