A quantum accelerated approach for the central path method in linear programming
No Thumbnail Available
Date
2023
Authors
Adoni, Vijay
University of Lethbridge. Faculty of Arts and Science
Journal Title
Journal ISSN
Volume Title
Publisher
Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
Abstract
The central path method is a crucial technique used in the optimization of linear programs. The method relies on classical computation which hits its limit for large instances, generally used in practice, in terms of efficiency. In this thesis, a proposal is made to explore the use of quantum algorithms to enhance the central path method’s performance when solving linear programs. We will go through the potential benefits and limitations of replacing the iterative equation-solving step with the HHL quantum algorithm, the Newton’s step for solving a set of nonlinear equations, and converting the nonlinear set of equations to bilinear equations with the help of McCormick relaxations. The aim of this thesis is to perform extensive experimentation on several types of efficient instances using each of the proposed algorithms and to evaluate their effectiveness through numerical simulations to find a promising approach for the central path method.
Description
Keywords
quantum algorithms , linear programming , central path method , linear program optimization