@mastersthesis{10902/20118,
year = {2020},
month = {9},
url = {http://hdl.handle.net/10902/20118},
abstract = {ABSTRACT: Even if the quantum computing popularity has recently grown, the currently-available technology is not ready for a fundamental revolution of informatics. In this transition phase, hybrid quantum-classical algorithms can help in understanding the real power that this novel paradigm can reach in the future. In this work, we tested the capability of two such algorithms to solve combinatorial optimization problems: the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA). We used them to solve max-cut problems, consisting of separating the vertices of an undirected graph in two sub-groups so that the number of edges connecting vertices of different sub-groups is maximal. To do that, we mapped the problem into a quantum system, using the Ising formalism. In particular, we investigated the effect of changing the number of measurements of the quantum circuit associated with the system on the algorithms convergence. A large number of measurements (or shots) allows a better knowledge of the quantum state, but on the other hand, increases the convergence time, making the algorithms less competitive compared to classical techniques. The results showed that VQE needs a mínimum number of measurements to start converging towards the optimal problem solution. Once this threshold is overcome, the solution improves as 1/√shots. QAOA, on the other hand, does not seem to converge, independently of the number of shots.},
abstract = {RESUMEN: Aunque la popularidad de la computación cuántica haya crecido recientemente, la tecnología actualmente disponible no es todavía suficiente para revolucionar profundamente la informática. En esta fase de transición, los algoritmos híbridos cuánticos-clásicos pueden ayudar a comprender el real poder que esta nueva técnica puede alcanzar en el futuro. En este trabajo, estudiamos la capacidad de dos de estos algoritmos para resolver problemas de optimización combinatoria: el variational quantum eigensolver (VQE) y el quantum approximate optimization algorithm (QAOA). Los usamos para resolver problemas de tipo max-cut, que consisten en separar los vértices de un grafo no dirigido en dos subgrupos de modo que el número de conexiones entre vértices de diferentes subgrupos sea máximo. Para hacer eso, mapeamos el problema a un sistema cuántico, utilizando el formalismo de Ising. En particular, investigamos como cambiar el número de medidas del circuito cuántico asociado al sistema afecta la convergencia de los algoritmos. Un gran número de medidas (o shots) permite un mejor conocimiento del estado cuántico, pero por otro lado aumenta el tiempo necesario para converger, haciendo que los algoritmos sean menos competitivos en comparación con las técnicas clásicas. Los resultados mostraron que VQE necesita un número mínimo de medidas para comenzar a converger hacia la solución óptima del problema. Una vez que se supere este umbral, la solución mejora como 1/√shots. QAOA, por otro lado, no parece converger, independientemente del número de medidas.},
title = {Study of quantum computing techniques for the resolution of optimization problems},
author = {Trevisani, Nicolo},
}