Quantum paths finding algorithm
Davide Integlia
Quantum paths finding algorithm.
Rel. Bartolomeo Montrucchio, Edoardo Giusto. Politecnico di Torino, Corso di laurea magistrale in Ingegneria Informatica (Computer Engineering), 2022
|
Preview |
PDF (Tesi_di_laurea)
- Tesi
Licenza: Creative Commons Attribution Non-commercial No Derivatives. Download (2MB) | Preview |
Abstract
The aim of this work is to design a hybrid quantum-classical algorithm to solve an optimization problem in the traffic flow domain. The basic idea is to spread vehicles on different paths in order to make the traffic as fluent as possible, while also minimizing the exposure to air pollution along the path. The problem is represented as Quadratic Unconstrained Binary Optimization (QUBO), that is a combinatorial optimization problem, frequently used for computer science applications. Such QUBO formulation can be mapped on a Quantum Annealer, a special machine that performs Adiabatic quantum computation. The problem is thus formulated: Given two distinct points in a city, a defined number of paths are selected among a set generated by Open Street Maps APIs.
These paths are selected using a classical greedy algorithm, that results in a compromise between computational time and quality of the solution
Relatori
Tipo di pubblicazione
URI
![]() |
Modifica (riservato agli operatori) |
