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

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.

Authors

• Adoni, Vijay
• University of Lethbridge. Faculty of Arts and Science

• quantum algorithms
• linear programming
• central path method
• linear program optimization

Identifier

hdl:10133/6501

OAI identifier oai:identifier

oai:opus.uleth.ca:10133/6501