提出新型全量子随机游走，突破传统量子加速上限，实现六次多项式提速。
Practical advantage beyond the quadratic speedup limit with fully-quantum walks
- 用量子哈密顿模拟作提议，全环节量子化采样过程。
- 相比最优经典算法，实现六次多项式查询加速，远超二次极限。
- 在相同硬件下，实际运行时间优势提前至不足一天，适合未来容错量子机。
我们引入一类全新的全量子马尔可夫链采样方法——全量子梅特罗波利斯随机游走，其中提议与接受步骤均为量子原生机制。不同于通过量化经典高效马尔可夫链获得的标准量子游走，本方法以哈密顿模拟作为量子原生提议机制，拓展了量子游走的适用范围。目标为在总变差距离固定误差下，从经典密集伊辛模型的低温吉布斯分布中采样。该方法相较于此前量子游走实现约三次多项式渐近加速，相对于最优经典随机游走实现六次多项式查询加速。这表明在量子游走框架内，超越广泛假设的二次加速极限是可能的。我们对所有算法原语进行了完整的容错编译，并与CPU、GPU和FPGA上的最优经典马尔可夫链实现进行基准测试。在相同硬件假设下，实现实际加速的时间交叉点从传统量子游走的约10^3年降至不足一天。这些结果表明，全量子马尔可夫链是实现实用量子优势的有前景路径。
原文摘要 · Abstract (English)
We introduce a new class of fully-quantum Metropolis walks in which both the proposal and acceptance steps are intrinsically quantum. Unlike standard quantum walks obtained by quantizing classically efficient Markov chains, our algorithm employs Hamiltonian simulation as a quantum-native proposal mechanism, enlarging the class of quantum walks beyond classical counterparts. We target the problem of sampling from the low-temperature Gibbs distribution of classical dense Ising models, within a fixed error in total variation distance. This approach achieves about a cubic polynomial asymptotic advantage over previous quantum-walks, resulting in a total sixth-degree polynomial queries speedup compared to the best classical walk. This shows that speedups beyond the widely assumed quadratic limit are possible within the quantum walk formalism. We perform a complete fault-tolerant compilation of all algorithmic primitives and benchmark against CPU, GPU, and FPGA implementations of the best classical Markov chain. Under identical hardware assumptions, the resulting advantage runtime crossover is reduced from approximately $10^3$ years for conventional quantum walks to less than one day. These results identify fully-quantum Markov chains as a promising route toward practical quantum advantage.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。