LUIS
Páginas: 6 (1364 palabras)
Publicado: 21 de abril de 2013
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 seutilizan durante su resolución.
Algoritmos de importancia histórica
El algoritmo de Deutsch-Jozsa fue propuesto por David Deutsch y Richard Jozsa en 19922 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 unaentrada 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ápidoque 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 deGrover, 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 . El desarrollo de la primera corrección de errores cuántica, propuestatambié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.
Algoritmo de Deutsch-Jozsa
En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico,propuesto por David Deutsch y Richard Jozsa en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos.
En el problema de Deutsch-Jozsa nos dan una función cuántica (que para nosotros es una caja negra) f(x1,x2,..., xn) que toma n bits de entrada x1, x2,..., xn y devuelve un valor binario f(x1, x2,..., xn). Sabemos que la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad); el problema es entonces determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando susalida.
Algoritmo de Deutsch
Esta es una versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos qubits auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.
El bloque H es una puerta Hadamard cuya operación es la siguiente:
El bloque Uf realiza la operación siguiente:
Además,
La entrada al circuito es: , que atraviesa dos...
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 seutilizan durante su resolución.
Algoritmos de importancia histórica
El algoritmo de Deutsch-Jozsa fue propuesto por David Deutsch y Richard Jozsa en 19922 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 unaentrada 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ápidoque 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 deGrover, 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 . El desarrollo de la primera corrección de errores cuántica, propuestatambié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.
Algoritmo de Deutsch-Jozsa
En computación cuántica, el algoritmo de Deutsch-Jozsa es un algoritmo cuántico,propuesto por David Deutsch y Richard Jozsa en 1992. Fue uno de los primeros algoritmos diseñados para ejecutar sobre un computador cuántico y que tiene el potencial de ser más eficiente que los algoritmos clásicos al aprovechar el paralelismo inherente de los estados de superposición cuánticos.
En el problema de Deutsch-Jozsa nos dan una función cuántica (que para nosotros es una caja negra) f(x1,x2,..., xn) que toma n bits de entrada x1, x2,..., xn y devuelve un valor binario f(x1, x2,..., xn). Sabemos que la función es constante (0 en todas las entradas o 1 en todas las entradas) o balanceada (devuelve 1 para la mitad de las entradas y 0 para la otra mitad); el problema es entonces determinar cómo es la función (constante o balanceada) aplicando entradas a la caja negra y observando susalida.
Algoritmo de Deutsch
Esta es una versión del algoritmo para una función f(x) de una sola entrada. Se utilizan dos qubits auxiliares en los cálculos. El algoritmo se ilustra en la figura de la derecha.
El bloque H es una puerta Hadamard cuya operación es la siguiente:
El bloque Uf realiza la operación siguiente:
Además,
La entrada al circuito es: , que atraviesa dos...
Leer documento completo
Regístrate para leer el documento completo.