黎颖 韩泽尧 黎超健 吕劲 袁骁 吴步娇†

1) (北京大学物理学院,北京 100871)

2) (北京大学前沿计算研究中心,北京 100871)

3) (广东工业大学计算机科学与技术学院,广东 510006)

利用量子态的叠加性和纠缠,量子计算为显著地加速经典算法,例如大数分解、求解线性方程组、量子多体系统模拟等问题,提供了可能.随着量子计算机硬件的快速发展,探索量子计算超越经典计算极限方向的研究受到了越来越多的重视.针对一类特定的问题,现有的量子设备已经展现出超越经典计算机的能力.但由于一些量子算法(诸如大数分解等问题)需要依赖于一个通用的大规模的容错的量子计算机,考虑到现阶段的量子设备的量子比特数十分有限,且容易与环境发生退相干,近期的研究主要集中在探索基于含噪声的中等规模量子设备以及浅层量子线路的量子优越性.一些采样问题被作为演示量子优越性的候选项提出.本文介绍和总结了几个可以在现阶段的量子设备上实现的量子优越性问题,并就其中两个备受关注的量子优越性问题—随机量子线路模拟和玻色采样及其衍生的采样问题的理论和实验进展、经典模拟算法等展开讨论.随着上述两类量子优越性问题在超导和光学量子平台的实现,我们预期当前和近期的量子设备将解决更多问题,从而实现更一般的量子优势.

1 引言

一些重要的诸如Shor 算法的例子预示了量子计算机相较于经典计算机……