En la computación cuántica, un algoritmo cuántico es un algoritmo que se ejecuta en un modelo realista de computación cuántica, siendo el modelo más comúnmente utilizado el modelo de computación del circuito cuántico. Un algoritmo clásico (o no cuántico) es una secuencia finita de instrucciones, o un procedimiento paso a paso para resolver un problema, donde cada paso o instrucción puede realizarse en una computadora clásica. Del mismo modo, un algoritmo cuántico es un procedimiento paso a paso, donde cada uno de los pasos se puede realizar en una computadora cuántica. Aunque todos los algoritmos clásicos también se pueden realizar en una computadora cuántica, el término algoritmo cuántico se usa generalmente para aquellos algoritmos que parecen intrínsecamente cuánticos o que utilizan alguna característica esencial de la computación cuántica, como la superposición cuántica o el enredo cuántico. Los problemas que son indecidibles usando computadoras clásicas siguen siendo indecidibles usando computadoras cuánticas. Lo que hace que los algoritmos cuánticos sean interesantes es que podrían ser capaces de resolver algunos problemas más rápido que los algoritmos clásicos. Los algoritmos más conocidos son el algoritmo de factorización de Shor y el algoritmo de Grover para buscar una base de datos no estructurada o una lista desordenada. Los algoritmos de Shor se ejecutan exponencialmente más rápido que el algoritmo clásico más conocido para factoraje, el tamiz de campo de número general. El algoritmo de Grover se ejecuta cuadráticamente más rápido que el mejor algoritmo clásico posible para la misma tarea. [Computación cuántica][Algoritmo][Circuito cuántico][Computadora] |