On the generalised phase kick-back and its applications

Resumo

La computación cuántica es una rama que ha adquirido creciente relevancia en los últimos tiempos, sobre todo tras el descubrimiento por parte de Peter Shor en los años 90 de un algoritmo para factorizar enteros de forma eficiente. Este resultado, que tiene importantes implicaciones en criptografía, sumado al avance que en los últimos años se ha producido a nivel técnico en el desarrollo de ordenadores cuánticos viables, hace necesario desarrollar nuevos criptosistemas resistentes a las técnicas de computación cuántica. Sin embargo, lo que se sabe sobre las limitaciones y posibilidades que ofrece este modelo de computación es todavía poco. En esta tesis, nos planteamos arrojar algo de luz a esta cuestión, estudiando la generalización de una de las técnicas más elementales y centrales en el desarrollo de algoritmos cuánticos: el phase kick-back. El algoritmo que construimos usando este denominado Generalised Phase Kick-Back, o GPK, permite resolver problemas como las versiones generalizadas de los problemas de Deutsch-Jozsa y Bernstein- Vazirani, pero eso no es todo. Gracias al estudio de su aplicación en la resolución de un nuevo problema que es a su vez una generalización de los dos mencionados anteriormente, el problema FBI, podemos estudiar la relación que esta técnica tiene con las transformadas de Fourier-Hadamard y Walsh, así como con el problema del balanceo. Además, se expone una resolución del problema de Simon que, empleando esta técnica, mejora la que ofrece el algoritmo de Simon, tanto en la versión habitual como en la generalizada.