凸函数

优化近似凸函数的量子加速及其在对数遗憾随机凸老虎机中的应用

贡献。在本文中，我们系统地研究了近似凸函数优化的量子算法，并将其应用于零阶随机凸老虎机。量子计算是一项快速发展的技术，量子计算机的能力正在急剧提升，最近谷歌 [ 6 ] 和中国科学技术大学 [ 42 ] 已经达到了“量子至上”。在优化理论中，半定规划 [ 3 ， 4 ， 11 ， 12 ]、一般凸优化 [ 5 ， 15 ]、优化中的脱离鞍点问题 [ 41 ] 等问题的量子优势已被证明。然而，据我们所知，近似凸优化和随机凸优化的量子算法是广泛开放的。在本文中，我们使用量子零阶评估预言机 OF 来考虑这些问题，这是先前量子计算文献中使用的标准模型 [ 5 ， 14 ， 15 ， 41 ]：