Algoritmo cuántico

Un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, como el modelo de circuito cuántico, como el que se ilustra en la figura.^[1]​ La teoría de la complejidad computacional le asigna la clase BQP a los algoritmos que pueden ser resueltos en un computador cuántico en tiempo polinómico con un margen de error promedio inferior a 1/4. En el análisis de los algoritmos cuánticos es habitual comparar la cota superior asintótica con el mejor algoritmo clásico conocido, o, si el problema está resuelto, con el mejor algoritmo clásico posible. Se usa la notación de Landau para definir la relación entre la talla de la entrada del problema y el número de pasos necesarios para resolverlo, o el número de posiciones de memoria que se utilizan durante su resolución.

Transformada cuántica de Fourier sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase.

Algoritmos de importancia histórica

Véanse también: Algoritmo de Deutsch-Jozsa, Algoritmo de Shor y Algoritmo de Grover.

El algoritmo de Deutsch-Jozsa fue propuesto por David Deutsch y Richard Jozsa en 1992^[2]​ y fue mejorado posteriormente por Richard Cleve, Artur Ekert, Chiara Macchiavello, y Michele Mosca en 1998.^[3]​ Su función es determinar si una función de tipo caja negra ${\displaystyle f:\{0,1\}^{n}\rightarrow \{0,1\}}$  es «constante» o «balanceada». Esto es, dada una función que para una entrada de n bits da un solo bit de salida, determinar si la salida es independiente de la entrada o si para la mitad de las entradas es 0 y para la otra mitad es 1. El planteamiento del problema excluye todas las otras posibles funciones. El algoritmo no tiene apenas utilidad práctica, pero es uno de los primeros ejemplos de un algoritmo cuántico que se ha demostrado que es exponencialmente más rápido que cualquier posible algoritmo clásico determinista.

El algoritmo de Shor, propuesto por Peter Shor en 1995 y relacionado con la aritmética modular, descompone en factores un número N en tiempo ${\displaystyle {\mathcal {O}}(\log N)^{3}}$  y espacio ${\displaystyle {\mathcal {O}}(\log N)}$ .^[4]​ Es responsable de buena parte de la atención que se le ha dedicado a la computación cuántica, por su relación con el problema RSA de importancia fundamental en criptografía.

El algoritmo de Grover, publicado por Lov Grover en 1996,^[5]​ demostró que un problema de utilidad práctica podía ser resuelto más rápidamente que el mejor algoritmo clásico posible. El algoritmo realiza una búsqueda en una base de datos desordenada con N entradas en un número de pasos de orden ${\displaystyle {\mathcal {O}}({\sqrt {N}})}$ , consumiendo un espacio de memoria de orden ${\displaystyle {\mathcal {O}}(\log N)}$ .

El desarrollo de la primera corrección de errores cuántica, propuesta también por Peter Shor en 1995,^[6]​ fue el primer paso hacia la computación cuántica a prueba de errores. Supuso un avance significativo porque por las leyes mecánica cuántica no es posible usar las estrategias habituales para la detección y corrección de errores de la computación clásica.

Referencias

1. Mosca, Michele (3 de agosto de 2008). «Quantum Algorithms». arxiv:0808.0369. Consultado el 18 de agosto de 2010. 
2. David Deutsch and Richard Jozsa (1992). «Rapid solutions of problems by quantum computation». Proceedings of the Royal Society of London A 439: 553. 
3. R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca (1998). «Quantum algorithms revisited» (PDF). Proceedings of the Royal Society of London A 454: 339-354. 
4. Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (en inglés)
5. Grover, L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
6. W.Shor, Peter (1995). «Scheme for reducing decoherence in quantum computer memory». Physical Reviews A. 

Enlaces externos

• El : Una lista completa de algoritmos cuánticos que son más rápidos que los algoritmos clásicos más rápidos conocidos.

Bibliografía adicional

• Michael Nielsen and Isaac Chuang (2000). Quantum Computation and Quantum Information. Cambridge: Cambridge University Press. ISBN 0-521-63503-9. OCLC 174527496. 
• J.Preskill, Lecture Note for Physics: Quantum Information and Computation el 6 de febrero de 2019 en Wayback Machine.

•   Datos: Q2623817