Fast Quantum Subroutines for the Simplex Method.

What would Dantzig do with a quantum computer? It is unlikely we will ever find out the answer to this question. However, we can try to understand if the simplex method can be implemented on a quantum computer, and this might have piqued Dantzig's interest. The paper "Fast Quantum Subroutines for the Simplex Method" gives a quantum implementation of an iteration of the simplex method, in which the basis inverse is never explicitly computed: the quantum computer takes as input the current basis and certifies optimality or outputs the next basis. Because computing the basis inverse is expensive, this can lead to an asymptotically faster algorithm in terms of the problem size: in the best case, the quantum algorithm can identify pivots in essentially linear time! This, however, comes at the cost of worse dependence on some numerical parameters: all these tradeoffs are discussed in the full article. 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 d_c nonzero elements per column of the costraint matrix, at most d nonzero elements per column or row of the basis, basis condition number κ, and optimality tolerance ϵ, pricing can be performed in O ˜ (ϵ − 1 κ d n (d c n + d m)) time, where the O ˜ notation hides polylogarithmic factors; classically, pricing requires O (d c 0.7 m 1.9 + m 2 + o (1) + d c n) 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. Funding: This work was supported by the Army Research Office [Grant W911NF-20-1-0014] and the Air Force Research Laboratory [Grant FA8750-C-18-0098]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.2341. [ABSTRACT FROM AUTHOR]