Novel Quantum Walk Algorithms: Phase Extensions and the Semiclassical Framework

Abstract

Quantum computing is an emerging paradigm that leverages the principles of quantum mechanics to process information, to provide a speedup with respect to classical computers. Among the different types of quantum algorithms that exist nowadays, quantum walks, which are quantized Markov chains, have shown good performance in a wide range of domains. In particular, a quantum walk introduced by Szegedy, which can be applied to arbitrary graphs, has been applied for tasks such as classification and optimization. The aim of this thesis is the development of novel quantum walk algorithms, from two differentiate research lines: phase extensions and the semiclassical framework. In the first results part of the thesis we extend the standard Szegedy quantum walk to incorporate complex phases, both at the level of edges with link phases, and at the level of nodes with arbitrary phase rotations (APR), giving rise to the graph-phased Szegedy walk. This phase-extended framework establishes a broader equivalence between coined and Szegedy walks, and provides new possibilities for quantum search algorithms on graphs without needing to modify the underlyingstructure..

La computación cuántica es un paradigma emergente que aprovecha los principios de la mecánica cuántica para procesar información, con el fin de proporcionar una aceleración en comparación con los ordenadores clásicos. Entre los diferentes tipos de algoritmos cuánticos que existen hoy en día, los caminos cuánticos, que son cadenas de Markov cuantizadas, han mostrado un buen rendimiento en una amplia variedad de dominios. En particular, un camino cuántico introducido por Szegedy, que puede aplicarse a grafos arbitrarios, ha sido utilizado para tareas como clasificación y optimización. El objetivo de esta tesis es el desarrollo de nuevos algoritmos de caminos cuánticos, desde dos líneas de investigación diferentes: extensiones de fases y el método semi clásico. En la primera parte de resultados de la tesis extendemos el camino cuántico de Szegedy estándar para incorporar fases complejas, tanto a nivel de aristas mediante fases de enlace, como a nivel de nodos mediante rotaciones de fase arbitrarias (APR en inglés), dando lugar al camino de Szegedy con fases de grafo...