Descripción:
El siguiente trabajo, surge de la creciente popularidad en el uso de la computación cuántica y sus mejoras prometedoras en tiempo de ejecución. Observando, que actualmente es una realidad tener acceso a una computadora cuántica, al menos si se tiene internet. Además, utiliza un lenguaje de programación de fácil manejo, como lo es Python. Por lo cual, ahora la pregunta ¿En qué tipo de computadora conviene ejecutar el código? es una pregunta que se debe tener la posibilidad de contestar. Sin embargo, derivado de esta surgen más preguntas, por ejemplo ¿Cómo medir la complejidad algorítmica cuántica? ¿Existen métricas que permitan esta comparación? ¿Cuál métrica permite evaluar un algoritmo cuántico, para decidir en qué computadora aplicar el algoritmo desarrollado? Entonces, es evidente que no se debe dar por sentado que la computadora cuántica es mejor que la computadora tradicional y solo replantear los "problemas difíciles'', para su aplicación en una computadora cuántica. Por lo tanto, se realiza esta investigación acerca de la complejidad algorítmica cuántica, en un modelo de computadora cuántica de Turing (Quantum Turing Machine). El cuál, permite trasladar algunas ideas sobre la complejidad algorítmica tradicional a esta nueva manera de computación. También, se revisa un modelo que se basa en la experimentación en física cuántica nombrado Quantum Algorithmic Measurement, permitiendo generar una propuesta de métrica para la complejidad en computación cuántica. Dicha métrica, es implementada sobre dos algoritmos cuánticos, el algoritmo de Grover y el algoritmo de Deutsch. Estos crean una generación de algoritmos fundamentales, no solo para la computación cuántica también en la computación tradicional, como lo son los algoritmos de búsqueda y consultas en bases de datos, entre otros. Concluyendo, que esta métrica puede ser útil como una forma de argumentación sobre si es factible, en términos de costo sobre el tiempo y el espacio cuántico, implementar un algoritmo desarrollado para la computación tradicional en el modelo de computación cuántica.