Arts and Science, Faculty of

Permanent URI for this collection

Now showing 1 - 1 of 1

A quantum accelerated approach for the central path method in linear programming
(Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, 2023) Adoni, Vijay; University of Lethbridge. Faculty of Arts and Science; Gaur, Daya
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.