量子算法实现非线性蒙特卡洛问题的平方级加速，突破经典方法瓶颈。
Quantum speedup of non-linear Monte Carlo problems
- 设计新型量子嵌套蒙特卡洛算法，适配非线性期望估计
- 在广义非线性问题上实现平方加速，优于现有量子多层方法
- 适用于复杂随机优化与条件期望场景，算法逼近理论下限
随机变量的均值可视为概率分布空间上的线性泛函。已知量子计算在均值估计中相较经典蒙特卡洛方法实现二次加速。本文研究该加速是否适用于概率分布的非线性泛函估计。提出一种量子内嵌量子蒙特卡洛算法，对包括嵌套条件期望和随机优化在内的广泛非线性估计问题实现平方加速。该算法优于An等（2021）提出的量子多层蒙特卡洛方法，且其复杂度接近现有下界，仅差对数因子。关键创新在于为量子计算量身定制的一系列新型多层蒙特卡洛近似序列，构成算法性能提升的核心。
原文摘要 · Abstract (English)
The mean of a random variable can be understood as a linear functional on the space of probability distributions. Quantum computing is known to provide a quadratic speedup over classical Monte Carlo methods for mean estimation. In this paper, we investigate whether a similar quadratic speedup is achievable for estimating non-linear functionals of probability distributions. We propose a quantum-inside-quantum Monte Carlo algorithm that achieves such a speedup for a broad class of non-linear estimation problems, including nested conditional expectations and stochastic optimization. Our algorithm improves upon the direct application of the quantum multilevel Monte Carlo algorithm introduced by An et al. (2021). The existing lower bound indicates that our algorithm is optimal up polylogarithmic factors. A key innovation of our approach is a new sequence of multilevel Monte Carlo approximations specifically designed for quantum computing, which is central to the algorithm's improved performance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。