Fast quantum subroutines for the simplex method

DOI10.1007/978-3-030-73879-2_22MaRDI QIDQ2061891zbMATH OpenOpenAlexFDO

Authors Giacomo Nannicini

Publication date 21 December 2021

Full work available at URL https://arxiv.org/abs/1910.10649

zbMATH Keywords

quantum subroutines, asymptotic speedup

Mathematics Subject Classification ID

Extreme-point and pivoting methods (90C49) Abstract computational complexity for mathematical programming problems (90C60)

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 $kappa$, and optimality tolerance $epsilon$, pricing can be performed in $ildeO(frac1epsilonkappadsqrtn(d_{c}n+dm))$ time, where the $ildeO$ 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.

Recommendations

• scientific article; zbMATH DE number 1775388
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Asymptotically faster quantum algorithms to solve multivariate quadratic equations
• scientific article; zbMATH DE number 7559394
• Quantum fast Poisson solver: the algorithm and complete and modular circuit design
• Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving
• Fine-Grained Reductions and Quantum Speedups for Dynamic Programming.
• Quantum speedups for exponential-time dynamic programming algorithms
• Faster than classical quantum algorithm for dense formulas of exact satisfiability and occupation problems
• Quantum Speedups for Dynamic Programming on n-Dimensional Lattice Graphs

Cites work

• A friendly smoothed analysis of the simplex method
• A practical anti-cycling procedure for linearly constrained optimization
• A quantum interior-point predictor–corrector algorithm for linear programming
• A sublinear-time randomized approximation algorithm for matrix games
• An introduction to quantum computing, without the physics
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Fast sparse matrix multiplication
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 1256737 (Why is no real title available?)
• scientific article; zbMATH DE number 2103524 (Why is no real title available?)
• Improvements in quantum SDP-solving with applications
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Selected Topics in Column Generation
• Smoothed analysis of algorithms
• Steepest-edge simplex algorithms for linear programming
• The Average number of pivot steps required by the Simplex-Method is polynomial

Cited in

(9)

• Solving large-scale optimization problems related to Bell's theorem
• scientific article; zbMATH DE number 1775388 (Why is no real title available?)
• Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning
• Improvements in quantum SDP-solving with applications
• A quantum interior-point predictor–corrector algorithm for linear programming
• An introduction to variational quantum algorithms for combinatorial optimization problems
• Fast quantum subroutines for the simplex method
• Efficient use of quantum linear system algorithms in inexact infeasible IPMs for linear optimization
• An introduction to variational quantum algorithms for combinatorial optimization problems

This page was built for publication: Fast quantum subroutines for the simplex method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2061891)