A través de este algoritmo podremos entender por qúe la computación cuántica puede ofrecer mejoras en el tiempo de ejecución de carácter exponencial frente a la computación clásica.
Su nombre se debe a David Deutsch, profesor de la Universidad de Oxford.
¿Y como vamos a conseguir eso objetivo?
Empecemos imaginando que tenemos una función básica,
, que tiene como dominio
y de igual manera tiene como imagen
. Es esta una función muy básica: puede dar siempre el mismo valor, ya sea 0 ó 1, a cualquier valor de entrada, o por el contrario puede ofrecer una valor diferente segun sea el valor de x. Llamaremos constantes al primer tipo de función, y balanceadas al segundo.
El problema al que nos enfrentamos se reduce a averiguar, dada una función
, de que tipo es.
Si disponemos de un ordenador clásico: ¿cuantas llamadas a la función hemos de hacer?. Es clara la respuesta : 2 veces.
Duetsch nos mostró que con un ordenador, o circuito, cuántico basta con hacer una sola llamada.
Veámoslo….
Leer más »