Document type
Bachelor thesisPublication date
Publication license
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/201868
Comparison of the AQO and the QAOA for the vertex coloring problem
Journal Title
Authors
Director/Tutor
Journal ISSN
Volume Title
Related resource
Abstract
We benchmark the time resources needed to execute the adiabatic quantum optimization (AQO), and to run the Quantum Approximate Optimization Algorithm (QAOA), for the vertex coloring problem. This is done via a numerical simulation of 20 Erd˝os-R´eny random graphs for different cases ranging from 8 to 21 qubits. With this comparison, we explore two of the most important algorithms of the analog and gate-based quantum computing paradigms, respectively. We apply the canonical implementation for both algorithms, so their initial Hamiltonian is the same, the one with the typical sum of Pauli-X matrices. In this line, we consider linear scheduling time for the AQO. For final adiabatic time T = 100 ns, the AQO achieves an overlap with the degenerate solutions over 0.9 in all cases. Meanwhile, the QAOA using the Powell classical optimizer, 5 layers and thousands of iterations has an overlap around 0.5 for the 8 qubits case and below 0.25 for the other cases. So, our results for the given task and idealized conditions indicate that the AQO significantly outperforms
the QAOA in terms of time and success probability
Description
Treballs Finals de Grau de Física, Facultat de Física, Universitat de Barcelona, Curs: 2023, Tutors: Marta P. Estarellas, Jordi Riu, Lluís Garrido
Subject (English)
Citation
Collections
Citation
VIDAL MARCOS, Eric. Comparison of the AQO and the QAOA for the vertex coloring problem. [consulted: 16 of June of 2026]. Available at: https://hdl.handle.net/2445/201868