量子科技中心_量科网

该团队研究的问题是在只能通过比较预言机（给定两个点，输出哪个函数值更大）访问目标函数的情况下，寻找非凸函数的驻点。针对一个二阶可微且具有Lipschitz梯度和Hessian矩阵的函数 \( f\colon\mathbb R^n\to\mathbb R \)，该团队开发了一种算法，能够使用 \(\widetilde O(n^2/ε^{1.5})\) 次查询访问一个 \(ε\)-驻点。该方法使用了一个子程序，该子程序可通过 \(\widetilde O(n^2\log(1/δ))\) 次查询以精度 \(δ\) 估计归一化Hessian矩阵。该团队进一步研究了在量子比较预言机模型下的这一问题（在该模型中，查询可以以叠加态进行），并开发了第一个寻找 \(ε\)-驻点的量子算法，该算法需要 \(\widetilde O(n/ε^{1.5})\) 次查询。