arXiv:2505.05301quant-phcs.LG2025-05被引 6

首个实现非凸采样量子加速的算法,突破经典方法瓶颈。

Operator-Level Quantum Acceleration of Non-Logconcave Sampling

  • 通过构造威滕拉普拉斯算子分解,将目标分布编码为量子态振幅。
  • 在非凸场景下实现高达四倍的量子加速,优于最优经典朗之万方法。
  • 适用于复杂能谷景观采样,适合量子计算与统计物理研究者。

从形如 $σ/propto e^{-βV}$ 的概率分布中采样是物理、化学、生物、计算机科学和统计学中的基础任务,其中 $V$ 为连续势能函数。当 $V$ 非凸时,分布变为非对数凹,经典方法如朗之万动力学常表现不佳。本文提出首个可证明加速一类连续时间采样动力学的量子算法。针对朗之万动力学,该方法将目标吉布斯测度编码为量子态的振幅,其对应于威滕拉普拉斯算子分解所得块矩阵的核。这一联系使得可通过奇异值阈值化实现吉布斯采样,在非对数凹情形下相较于最优经典朗之万方法实现高达四次方的量子加速。基于此框架,我们进一步开发了首个加速复制交换朗之万扩散的量子算法,该方法广泛用于复杂崎岖能谷景观的采样。

原文摘要 · Abstract (English)

Sampling from probability distributions of the form $σ\propto e^{-βV}$, where $V$ is a continuous potential, is a fundamental task across physics, chemistry, biology, computer science, and statistics. However, when $V$ is non-convex, the resulting distribution becomes non-logconcave, and classical methods such as Langevin dynamics often exhibit poor performance. We introduce the first quantum algorithm that provably accelerates a broad class of continuous-time sampling dynamics. For Langevin dynamics, our method encodes the target Gibbs measure into the amplitudes of a quantum state, identified as the kernel of a block matrix derived from a factorization of the Witten Laplacian operator. This connection enables Gibbs sampling via singular value thresholding and yields up to a quartic quantum speedup over best-known classical Langevin-based methods in the non-logconcave setting. Building on this framework, we further develop the first quantum algorithm that accelerates replica exchange Langevin diffusion, a widely used method for sampling from complex, rugged energy landscapes.

量子采样非凸优化朗之万动力学量子加速

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。