- Algoritmo cuántico
-
Transformada de Fourier cuántica sobre tres qubits, basada en la aplicación reiterada de la puerta cuántica de Hadamard y de puertas de cambio de fase.
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.
Contenido
Algoritmos de importancia histórica
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
es «constante» o «balanceada». Esto es, dada una función que para una entrada de n bits da un sólo 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
y espacio 
.[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
, consumiendo un espacio de memoria de orden .Referencias
- ↑ Mosca, Michele (03-08-2008). «Quantum Algorithms». arxiv:0808.0369. http://arxiv.org/abs/0808.0369.
- ↑ David Deutsch and Richard Jozsa (1992). «Rapid solutions of problems by quantum computation». Proceedings of the Royal Society of London A 439: pp. 553.
- ↑ R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca (1998). «Quantum algorithms revisited» (PDF). Proceedings of the Royal Society of London A 454: pp. 339–354. http://arxiv.org/pdf/quant-ph/9708016.
- ↑ Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer (en inglés)
- ↑ 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
Enlaces externos
- El zoo de algoritmos cuánticos: 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
Categorías:- Informática cuántica
- Algoritmos cuánticos
Wikimedia foundation. 2010.
