Este trabajo se desarrollará en la intensificación en Computación de los estudios del grado en Ingeniería Informática de la ESIIUCLM. Está enfocado desde la perspectiva de las asignaturas de "Diseño de Algoritmos" y "Teoría de Autómatas y Computación" fundamentalmente, aunque precisa un buen dominio de las asignaturas de matemáticas.
La computación cuántica es una forma radicalmente novedosa de procesar la información, completamente distinta de aquella a la que estamos acostumbrados, basados en la computación determinista del modelo Von Neumann, y que está posibilitada por propiedades exclusivas de la mecánica cuántica tales como la superposición de estados (que origina el denominado paralelismo cuántico) y la existencia de correlaciones sin análogo en la física clásica (entrelazamiento y correlaciones cuánticas).
A medida que evoluciona la tecnología, aumenta la escala de integración y caben más transistores en el mismo espacio, disponiendo de microchips de tamaño cada vez más reducido. Es bien conocido que cuanto más pequeño es, mayor velocidad de proceso alcanza el chip, sin embargo, y como es obvio, no podemos hacer los chips infinitamente pequeños, sino que existe un límite en el cual dejan de funcionar correctamente. Cuando se llega a la escala de nanómetros, los electrones se escapan de los canales por donde deben circular. A esto se le llama efecto túnel, que consiste en que una partícula clásica, si se encuentra con un obstáculo, no puede atravesarlo y rebota. Pero con los electrones, que son partículas cuánticas y se comportan como ondas, existe la posibilidad de que una parte de ellos pueda atravesar las paredes si son los suficientemente delgadas; de esta manera la señal puede pasar por canales donde no debería circular. Por ello, el chip deja de funcionar correctamente, y aquí es donde la computación cuántica entra en escena.
La idea de computación cuántica surge en 1981, cuando Paul Benioff expuso su teoría para aprovechar las leyes cuánticas en el entorno de la computación. En vez de trabajar a nivel de voltajes eléctricos, se trabaja a nivel de un cuanto. En la computación digital, un bit sólo puede tomar dos valores: 0 ó 1. En cambio, en la computación cuántica, intervienen las leyes de la mecánica cuántica, y la partícula puede estar en superposición coherente. Ahora la información se organizará en qbits (bit cuántico), cuyo valor puede ser 0, 1, pero también puede ser 0 y 1 a la vez (dos estados ortogonales de una partícula subatómica), es más puede estar en una composición arbitraria con diferente valores de pesos para el 0 y el 1. Eso permite que se puedan realizar varias operaciones a la vez, según el número de qubits.
Existen numerosas áreas donde la computación cuántica puede alcanzar resultados interesantes, que incluso podrían llegar a disminuir la complejidad de problemas intratables. El ámbito de la teoría de grafos es un ejemplo paradigmático de este tipo de áreas.
El principal objetivo de este trabajo será el de estudiar algunas técnicas de codificación de grafos en computación cuántica, mediante el uso de los qubits y puertas cuánticas, y mediante simulación, elaborar experimentos para grafos de tamaño reducido y comprobar las posibles mejoras alcanzadas.
En particular se estudiará el problema del isomorfismo de grafos, un problema para el que no existe algoritmo conocido que lo resuelva en tiempo polinomial, si bien no es un problema NP completo. Se usara la codificación propuesta por Mills et al, publicada en Physical Review, y se analizarán los resultados obtenidos en función del tamaño de los grafos.
La metodología que será utilizada se puede resumir en los siguientes puntos:
- Codificación de grafos mediante puertas cuánticas. Se seguirá el modelo de Mills et al.
- Implementación en el simulador QSimov. Para ello habrá que implementar macros de puertas y entrada de datos por fichero, que ahora no incorpora el simulador.
- Elaboración de tablas de resultados
Las principales competencias que el alumno trabajará son CM1, CM3, CM4 y CM7
[1] IBM - Q. Página web https://quantumexperience.ng.bluemix.net/qx/user-guide
[2] TFG Hernán Indibil de la Cruz Calvo. Simulador de programación cuántica
[3] Quirk Simulator. How to use. https://github.com/Strilanc/Quirk/wiki/How-to-use-Quirk
[4] Quantum invariants and the graph isomorphism problem. P. W. Mills, R. P. Rundle, J. H. Samson, Simon J. Devitt, Todd Tilma, V. M. Dwyer, and Mark J. Everitt. Physical Review A, 2019