高精度低复杂度的量子算法：轻松求解量子态问题

估算量子多体系统基态和激发态的性质是一个具有基础重要性的长期问题，在凝聚态物理、量子化学和材料科学中都有应用。尽管在理论复杂度和经验数值证据上都具有量子困难性，但寻找多体哈密顿量的本征态仍是核心目标，推动着从量子相位估计（QPE）到光谱滤波算法、基于耗散的算法等量子算法的不断探索。随着量子硬件和纠错技术的快速发展，考虑早期容错量子计算（FTQC）设备特性的量子算法设计受到越来越多的关注，其中最小化受控操作和电路深度至关重要，这一约束也适用于嘈杂中等规模量子（NISQ）设备。在此背景下，设计满足更少量子比特、低电路深度和受限量子比特连接性的量子算法是理想的目标，这些因素在将非局域受控门编译为局域门时往往相互关联。

考虑到上述硬件约束，基于光谱滤波的方法是有效寻找基态的良好候选，在初始重叠非零和能隙非零的假设下，可实现良好的渐近查询复杂度。然而，这些算法通常基于对实时演化算子e–iHt或哈密顿量H的块编码的完美高效查询，当编译为量子电路中的基本门时，其有利的扩展性不再存在。例如，通过 Trotter 化实现实时演化作为子程序会消除本征态性质估计中对数精度缩放的优势；而通过块编码实现则会失去良好的系统规模扩展性，且需要许多辅助量子比特和非局域受控门，违背了早期FTQC的精神。此外，现有工作中很少讨论算法的系统规模依赖性，因为它高度依赖于电路级实现以及量子设备的量子比特连接性，导致这些算法在量子电路层面变得次优。一个重要问题是，在NISQ和早期FTQC应用中考虑门复杂度和量子比特连接性时，如何设计高精度和低深度的算法。

本文提出了一种基于随机复合幺正线性组合（LCU）公式的全栈量子算法，用于本征态性质和本征能量的估算。单次电路的最大门复杂度与目标精度ε的倒数呈对数关系，优于基于QPE的方法，并与量子信号处理（QSP）的结果相当。对于具有守恒对称性的各种物理问题，该方法的电路深度较低。对于晶格哈密顿量，即使在最近邻（NN）量子比特连接性下，该方法也能实现近最优的系统规模门复杂度，其深度复杂度几乎与系统大小n无关（除了能隙的隐含依赖）。全栈算法在电路编译中具有低开销，因此与先进的本征态算法相比，对于晶格和分子问题，实际门数量（CNOT和非克利福德门）较少。

该算法在IBM量子设备上实现，使用多达2000个两量子比特门和20000个单量子比特门，对海森堡型哈密顿量实现了高精度本征能量估算，证明了其噪声鲁棒性。资源估算表明，对于20个格点的海森堡模型，CNOT门成本约为10⁴量级，T门成本约为10⁶量级，使其特别适用于NISQ和早期FTQC应用。该工作还为将最先进的量子算法编译为基本门提供了有用的工具箱。