论文标题
在内部点方法中有效利用量子线性系统算法进行线性优化
Efficient Use of Quantum Linear System Algorithms in Interior Point Methods for Linear Optimization
论文作者
论文摘要
量子计算引起了对优化社区的重大兴趣，因为它可能比传统的超级计算机更快地解决优化问题的类别。一些研究人员提出了量子计算方法，尤其是量子内点方法（QIPM），以解决凸优化问题，例如线性优化，半闪烁优化和二阶锥形优化问题。他们中的大多数都在每次迭代中应用了量子线性系统算法来计算牛顿步骤。但是，在QIPMS中使用量子线性求解器会带来许多挑战，例如有条件不良的系统和量子求解器的相当大误差。本文研究了如何在QIPM中有效使用量子线性求解器。因此，开发了一种不可过的量子内部方法来解决线性优化问题。我们还讨论了如何通过迭代完善而无需过多的量子求解器获得精确的解决方案。最后，分析了使用量子模拟器对我们的QIPM实现的计算结果。
Quantum computing has attracted significant interest in the optimization community because it potentially can solve classes of optimization problems faster than conventional supercomputers. Several researchers proposed quantum computing methods, especially Quantum Interior Point Methods (QIPMs), to solve convex optimization problems, such as Linear Optimization, Semidefinite Optimization, and Second-order Cone Optimization problems. Most of them have applied a Quantum Linear System Algorithm at each iteration to compute a Newton step. However, using quantum linear solvers in QIPMs comes with many challenges, such as having ill-conditioned systems and the considerable error of quantum solvers. This paper investigates how one can efficiently use quantum linear solvers in QIPMs. Accordingly, an Inexact Infeasible Quantum Interior Point Method is developed to solve linear optimization problems. We also discuss how can we get an exact solution by Iterative Refinement without excessive time of quantum solvers. Finally, computational results with QISKIT implementation of our QIPM using quantum simulators are analyzed.
