Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
A quantum accelerated approach for the central path method in linear programming
Abstract
dc:description.abstractThe 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.
Degree
thesis:*- Level thesis:degree_level
- Masters
- Grantor dc:publisher
- Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
- Year dc:date.issued
- 2023
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Adoni, Vijay
- University of Lethbridge. Faculty of Arts and Science
- Advisor dc:contributor.supervisor
-
- Gaur, Daya
Subjects
dc:subject × 9Rights
- Language dc:language.iso
- en
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/10133/6501