Quantum approximate optimization algorithm: combinatorial problems and classical statistical models

Rava, Andrea Basilio (2021) Quantum approximate optimization algorithm: combinatorial problems and classical statistical models. [Laurea magistrale], Università di Bologna, Corso di Studio in Physics [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Non opere derivate 4.0 (CC BY-NC-ND 4.0)

Download (11MB)


The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm for solving combinatorial optimization problems. Since most of combinatorial optimization problems may be thought as particular instances of Ising Hamiltonians, the study of the QAOA is very relevant from the physical point of view for its potential applications in describing physical systems. In the QAOA a quantum state is prepared and, through 2p parameterized quantum evolutions, a final state which represents an extreme of cost function and encodes the approximate solution of the problem is obtained. The 2p parameters are determined through a classical parameter optimization process. In this work we apply QAOA to two different problems, the Max Cut and the random bond Ising Model (RBIM). For both problems we perform an analysis of the optimization efficiency, verifying that the quality of the approximation increases with p. For the Max Cut we perform a further analysis of the p=1 case for which we obtain an analytical expression for the cost function and make observations regarding the choice of the initial parameters in the optimization procedure. For the RBIM, for different disordered configurations we obtain the ground states energies and magnetizations for different lattice sizes and different level p of the optimisation. We observe that, even if the magnetisation is obtained for small lattice sizes, its behaviour suggests the presence of a transition separating a ferromagnetic from a paramagnetic phase.

Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Rava, Andrea Basilio
Relatore della tesi
Correlatore della tesi
Corso di studio
Ordinamento Cds
Parole chiave
optimization,QAOA,qubit,quantum algorithm,quantum computation,combinatorial problems,statistical methods,algorithm
Data di discussione della Tesi
26 Marzo 2021

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento