导 读
论文地址：
Wong,W.C. Lau,R.W.M. Kwok,W.M. Lau,“Unusual kinematics-driven chemistry: cleaving C-H but not COO-H bonds with hyperthermal protons to synthesize tailor-made molecular films” Chem. Eur. J. 13,3187 (2007). 。
问题介绍
问题模型
给定一个凸函数 → R，且 f 是 L- smooth 和 μ-convex 的。我们定义条件数。我们希望从分布函数进行采样，这里 是正则化常数。给定 ε∈(0，1)。
对数凹采样：输出一个随机变量满足分布，使得；
归一化常数估计：输出一个随机变量 ，使得以至少 2/3 的概率满足。
主要贡献
我们设计了新的量子算法，对于采样对数凹分布和估计正则化常数两个问题，对比经典算法在复杂度上实现了多项式级加速。
定理 1（对数凸采样）给定一个对数凹分布 ρ，存在量子算法输出一个随机变量满足分布 ，使得：
这里 是 Wasserstein 2-范数，对于量子访问 oracle 的查询复杂度为 ；或
这里 是全变差距离（total-variation distance），对于量子梯度 oracle 的查询复杂度为 ；若初始分布满足热启动条件，则复杂度为 。
定理 2（归一化常数估计）存在量子算法输出一个随机变量 ，使得以至少 2/3 的概率满足 。
对于量子访问 oracle 的查询复杂度为 ；或
对于量子梯度 oracle 的查询复杂度为 ；若有一个热的初始概率分布（warm start），则复杂度为 。
另外，这个任务的量子查询复杂度的下界是 。
我们在表1和表2总结了我们的结果和先前经典算法复杂度的对比。
技术改进
我们开发了一种系统的方法来研究量子游走混合（quantum walk mixing）的复杂度，并揭示了对于任何可逆的经典马尔可夫链，只要初始分布满足热启动条件，我们就可以获得混合时间（mixing time）的平方加速。特别地，我们将量子行走和量子退火（quantum annealing）应用于朗之万动力学并实现多项式量子加速。下面简单介绍我们的技术贡献。
1. 量子模拟退火（quantum simulated annealing）。我们用于估计归一化常数的量子算法结合了量子模拟退火框架和量子平均值估计算法。对于每种类型，根据朗之万动力学（随机游走），我们构建了相应的量子游走。重要的是，随机游走的谱间隙在相应的量子游走的相位间隙中被“放大”为原先的平方。这让在给定足够好的初始状态的情形，我们使用类似 Grover 算法的过程来产生稳定分布状态。在退火框架中，这个初始状态就是前一个马尔可夫链的稳定分布状态。
3. 量子梯度估计（quantum gradient estimation）。我们将 Jordan 的量子梯度算法应用于我们的量子算法，并给出严格的证明来限制由于梯度估计误差引起的采样误差。
[1] Andrew M. Childs，Tongyang Li，Jin-Peng Liu，Chunhao Wang，and Ruizhe Zhang，&34; to appear in NeurIPS 2022.
[2] Rong Ge，Holden Lee，and Jianfeng Lu，&34; STOC 2020.
[5] Ruoqi Shen and Yin Tat Lee，&34; NeurIPS 2019.
[6] Keru Wu，Scott Schmidler，and Yuansi Chen，&34; 2021，arXiv:2109.13055.
图文 | 刘锦鹏、李彤阳
PKU QUARK Lab
![[美]JayBhattacharya《健康经济学（斯坦福卫生经济学教材）》作品简介与读书感悟](http://img.tianshugan.com/tsg/files/202212/1605556293278392322.jpg)
