Solving combinatorial optimization problems using quantum computing: a case study for the QAP

Abstract

Quantum computing is one of the most researched areas in computer science and withone of the greatest future prospects thanks to the new discoveries and methodologies thatcan provide approaches of a different kind to tackle problems and find solutions. One ofsuch methodologies is none other than quantum annealing, a metaheuristic focused on thequalities of quantum mechanics.

Combinatorial Optimization (CO) problems have always been a hassle to find solutionsin large scale problems owing to their complexity and resource consumption. However,these can be transformed into an equivalent Quadratic Unconstrained Binary Optimization(QUBO) model that is constraint-free and its variables are (binary) decision variables.What is best, QUBO models can be efficiently solve with quantum annealing in a quantumcomputer.

The objective of the project will be the study of all the particular functionalities andproperties of each aspect of all the transformation chain for the specific case study withthe QAP problem. The implementation of this problem, its transformation into a QUBOmodel and the solution obtained through quantum annealing are the key points that leadto harness the potential of quantum computing and set its current limits.