Classes of Quantum Complexity

Abstract

This work aims to ensure a digital functioning of the world of trading cards that we are already familiar with. For this purpose, a significant portion of the functions associated with trading cards has been transferred to the application, such as acquiring or exchanging them. The developed functions are comprehensive, starting with organized storage by collections. With this feature, users will be able to track which cars from a collection they possess and which ones they are missing. As a result, users can search for collections to subscribe to and begin collecting. The method for obtaining new cards is based on exchanges with other users or purchasing packs. These packs offer 3 cards from the selected collection and can be bought using coins that can be earned by answering questions correctly. Everything related to the cards and collections is created, modified, or deleted by the creators, who have their own panel to interact with their creations. The application is designed to be used in a web browser on our computer, developed using HTML/PHP, and with an SQL database.

Este trabajo de fin de grado trata sobre las clases de complejidad cuántica, que son el análogo cuántico de las clases de complejidad clásica. Empezamos en el primer capítulo introduciendo los conceptos matemáticos básicos que sustentan la computación cuántica, como la notación bra-ket, el espacio de estados y las puertas cuánticas. Después, en el segundo capítulo, estudiamos algo de teoría de complejidad clásica, como las clases de complejidad clásicas y el problema P vs NP. Después introducimos las clases de complejidad cuánticas, y estudiamos la relación entre ellas y las clases de complejidad clásicas, especialmente la relación entre BPP, BQP y PSPACE, viendo que una está contenida en la siguiente. En el tercer capítulo estudiamos algunos algoritmos cuánticos, como el algoritmo de Deutsch, el algoritmo de Simon y el algoritmo de Shor. Mostramos diferencias aparentes entre el mundo clásico y el mundo cuántico, como el hecho de que los ordenadores cuánticos pueden resolver el problema de factorización de un numero natural en tiempo polinomial, mientras que los ordenadores clásicos no se sabe que puedan hacerlo. Finalmente, en el cuarto capítulo, logramos implementar el algoritmo de Shor en varios simuladores cuánticos, y estudiamos cómo funciona en la práctica, comparando los diferentes backends. Además, implementamos la transformada cuántica de Fourier y la ejecutamos en varios ordenadores cuánticos reales.