Fast Quantum Subroutines for the Simplex Method

Giacomo Nannicini ()
Additional contact information
Giacomo Nannicini: IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, New York 10598

Operations Research, 2024, vol. 72, issue 2, 763-780

Abstract: 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.

Keywords: Optimization; linear programming; quantum algorithms; simplex method (search for similar items in EconPapers)
Date: 2024
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2341 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:72:y:2024:i:2:p:763-780

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().