量子算法突破高维非线性优化瓶颈，实现对数级误差增长。
Quantum Non-Linear Bandit Optimization
- 结合量子蒙特卡洛与参数化函数逼近，设计新量子回归算子。
- 在高维场景下实现输入维度无关的对数级累积误差上界。
- 适合需要高效探索高维黑箱函数的科研与工业应用。
我们研究零阶黑箱函数优化问题，该问题在药物发现和材料设计等关键领域有广泛应用。已有工作表明，借助量子计算可突破经典方法 $Ω(√T)$ 的误差下界，实现 $O(\mathrm{poly}\log T)$ 的上界。但这些方法通常依赖于目标函数属于再生核希尔伯特空间的假设，且存在维度灾难问题。本文提出 Q-NLB-UCB 算法，首次实现输入维度无关的 $O(\mathrm{poly}\log T)$ 误差上界，适用于高维任务。算法核心包括量子蒙特卡洛均值估计、参数化函数逼近及新型量子非线性回归算子，这些组件对更广泛的量子机器学习问题亦具独立价值。实验验证了其在高维合成数据与真实世界任务中相较于其他量子算法的高效性。
原文摘要 · Abstract (English)
We study non-linear bandit optimization where the learner maximizes a black-box function with zeroth order function oracle, which has been successfully applied in many critical applications such as drug discovery and materials design. Existing works have showed that with the aid of quantum computing, it is possible to break the classical $Ω(\sqrt{T})$ regret lower bound and achieve the new $O(\mathrm{poly}\log T)$ upper bound. However, they usually assume that the objective function sits within the reproducing kernel Hilbert space and their algorithms suffer from the curse of dimensionality. In this paper, we propose the new Q-NLB-UCB algorithm which enjoys an \emph{input dimension-free} $O(\mathrm{poly}\log T)$ upper bound, making it applicable for high-dimensional tasks. At the heart of our algorithm design are quantum Monte Carlo mean estimator, parametric function approximation technique, and a new quantum non-linear regression oracle, which can be of independent interests in more quantum machine learning problems. Our algorithm is also validated for its efficiency compared with other quantum algorithms on both high-dimensional synthetic and real-world tasks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。