Fast Quantum Subroutines for the Simplex Method

• 成果类型: Article
• 署名作者: Nannicini, Giacomo
• 署名单位: International Business Machines (IBM); IBM USA
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2341
• 发表日期: 2024
• 关键词: algorithms

摘要

We propose quantum subroutines for the simplex method that avoid classical computation of the basis inverse. We show how to quantize all steps of the simplex algorithm, including checking optimality, unboundedness, and identifying a pivot (i.e., pricing the columns and performing the ratio test) according to Dantzig's rule or the steepest edge rule. The quantized subroutines obtain a polynomial speedup in the dimension of the problem but have worse dependence on other numerical parameters. For example, for a problem with m constraints, n variables, at most dc nonzero elements per column of the costraint matrix, at most d nonzero elements per column or row of the basis, basis condition number kappa, and optimality tolerance e, pricing can be performed in O similar to(e1 kappa d root == (dcn + dm)) time, n where the O similar to notation hides polylogarithmic factors; classically, pricing requires O(d0:7 c m1:9 + m2+o(1) + dcn) time in the worst case using the fastest known algorithm for sparse matrix multiplication. For well-conditioned sparse problems, the quantum subroutines scale better in m and n and may therefore have an advantage for very large problems. The running time of the quantum subroutines can be improved if the constraint matrix admits an efficient algorithmic description or if quantum RAM is available.