A quantum accelerated approach for the central path method in linear programming

Simple item page
dc.contributor.authorAdoni, Vijay
dc.contributor.authorUniversity of Lethbridge. Faculty of Arts and Science
dc.contributor.supervisorGaur, Daya
dc.date.accessioned2023-05-29T16:14:09Z
dc.date.available2023-05-29T16:14:09Z
dc.date.issued2023
dc.degree.levelMasters
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.
dc.identifier.urihttps://hdl.handle.net/10133/6501
dc.language.isoen
dc.proquest.subject0984
dc.proquestyesYes
dc.publisherLethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science
dc.publisher.departmentDepartment of Mathematics and Computer Science
dc.publisher.facultyArts and Science
dc.relation.ispartofseriesThesis (University of Lethbridge. Faculty of Arts and Science)
dc.subjectquantum algorithms
dc.subjectlinear programming
dc.subjectcentral path method
dc.subjectlinear program optimization
dc.subject.lcshLinear programming
dc.subject.lcshAlgorithms
dc.subject.lcshQuantum computing
dc.subject.lcshMathematical optimization
dc.subject.lcshInterior point methods
dc.subject.lcshDissertations, Academic
dc.titleA quantum accelerated approach for the central path method in linear programming
dc.typeThesis
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
ADONI_VIJAY_MSC_2023.pdf
Size:
1.72 MB
Format:
Adobe Portable Document Format
Description:
Download
License bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
license.txt
Size:
1.75 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
Arts and Science, Faculty of
University of Lethbridge Theses