论文标题
通过强大的IPM框架，用于半决赛编程的更快的量子算法
A Faster Quantum Algorithm for Semidefinite Programming via Robust IPM Framework
论文作者
论文摘要
本文研究了凸优化中的一个基本问题，即以高精度来解决半决赛编程（SDP）。本文根据[Huang，Jiang，Song，Tao和Zhang，focs 2022]的现有基于SDP的内部方法分析进行了遵循。同时，以前的工作仅在经典环境中提供有效的实现。这项工作提供了一种新颖的量子实现。 我们在其输出的最佳性和可行性中给出了具有高准确性的量子二阶算法，并且其运行时间取决于条件良好的实例（1/ε）$。由于量子本身或一阶方法的限制，所有现有的量子SDP求解器在可行性中具有多项式误差依赖性或低临界性。
This paper studies a fundamental problem in convex optimization, which is to solve semidefinite programming (SDP) with high accuracy. This paper follows from the existing robust SDP-based interior point method analysis due to [Huang, Jiang, Song, Tao and Zhang, FOCS 2022]. While, the previous work only provides an efficient implementation in the classical setting. This work provides a novel quantum implementation. We give a quantum second-order algorithm with high-accuracy in both the optimality and the feasibility of its output, and its running time depending on $\log(1/ε)$ on well-conditioned instances. Due to the limitation of quantum itself or first-order method, all the existing quantum SDP solvers either have polynomial error dependence or low-accuracy in the feasibility.
