量子算法在连续吉布斯采样上首次实现理论优势，比经典算法快至少平方根倍。
Provable Quantum--Classical Separation for Continuous Gibbs Sampling
- 用量子奇异值阈值与温度渐进方法实现高效采样
- 经典算法需Ω(α)次查询，量子仅需~O(√α)次
- 低温度下优势指数级放大，适合高维系统模拟
我们首次证明了连续域上吉布斯采样问题的量子-经典分离。对于环面 $\mathbb{T}^d$ 上平滑（s-盖弗雷）势能的吉布斯态 $p\propto e^{-βE}$，其势垒幅度为 $α = e^{βΔ}$（$Δ = \max E - \min E$），任何经典算法——无论查询对数密度、梯度或任意高阶导数——在总变差距离恒定精度下均需 $Ω(α)$ 次查询；而基于量子奇异值阈值和温度渐进的量子算法仅需 $\tilde{O}(\sqrt{α})$ 次梯度查询即可完成采样。该优势在势垒幅度上呈二次方，低温时随维度指数级放大至 $e^{Ω(d)}$。经典下界为信息论性质，适用于所有具有势能及其任意阶导数查询访问的古典算法。
原文摘要 · Abstract (English)
We prove the first quantum--classical separation for a sampling problem over a continuous domain. For a class of Gibbs states $p\propto e^{-βE}$ on the torus $\mathbb{T}^d$ with smooth ($s$-Gevrey) potential and barrier amplitude $α=e^{βΔ}$, where $Δ= \max E-\min E$, every classical algorithm---querying the value, gradient, or any higher-order derivatives of the log-density---requires $Ω(α)$ queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with $\tilde{O}\left(\sqrtα\right)$ queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, $e^{Ω(d)}$, at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。