Convex optimization using quantum oracles
Convex optimization using quantum oracles
复制标题
使用量子预言的凸优化
作者：
Joran van Apeldoorn;A. Gilyén;S. Gribling;R. D. Wolf
我们研究量子算法在多大程度上可以加速求解凸优化问题。遵循经典文献，我们假设通过各种预言机访问凸集，我们研究不同预言机之间的效率降低。特别地，我们展示了如何使用O~（1）量子查询来实现分离预言机的成员资格预言机，这是对经典所需的Ω（n）成员资格查询的指数量子加速。我们表明，量子计算机可以非常有效地计算凸Lipschitz函数的近似次梯度。将此与李、西德福和文帕拉最近的经典工作的简化相结合，给出了我们有效的分离预言。这反过来又意味着，通过一个已知的算法，O~（n）量子查询的成员资格预言机足以实现一个优化预言机（最著名的经典上限的成员资格查询的数量是二次的）。我们还证明了几个下界：如果算法知道凸集的内点，则需要Ω（n）量子分离（或成员资格）查询进行优化;如果算法不知道凸集的内点，则需要Ω（n）量子分离查询。
We study to what extent quantum algorithms can speed up solving convex optimization problems. Following the classical literature we assume access to a convex set via various oracles, and we examine the efficiency of reductions between the different oracles. In particular, we show how a separation oracle can be implemented using O~(1) quantum queries to a membership oracle, which is an exponential quantum speed-up over the Ω(n) membership queries that are needed classically. We show that a quantum computer can very efficiently compute an approximate subgradient of a convex Lipschitz function. Combining this with a simplification of recent classical work of Lee, Sidford, and Vempala gives our efficient separation oracle. This in turn implies, via a known algorithm, that O~(n) quantum queries to a membership oracle suffice to implement an optimization oracle (the best known classical upper bound on the number of membership queries is quadratic). We also prove several lower bounds: Ω(n) quantum separation (or membership) queries are needed for optimization if the algorithm knows an interior point of the convex set, and Ω(n) quantum separation queries are needed if it does not.
影响因子：
6.4
作者：
Chakrabarti, Shouvanik;Childs, Andrew M.;Li, Tongyang;Wu, Xiaodi
通讯作者：
Wu, Xiaodi