Un ordenador cuántico no es más que un ordenador que utiliza estados cuánticos en lugar de estados clásicos. Los estados cuánticos son simplemente combinaciones de los estados clásicos.
Digamos que un ordenador toma una determinada entrada $x_i$ a la salida $f(x_i)$ . Según la mecánica cuántica, puedes configurar tu ordenador de forma que su entrada sea un combinación de todas las entradas clásicas $x_i$ , a saber $\frac{1}{n} \sum_i^n x_i$ . Después de operar, su ordenador llevaría esta combinación de todas las entradas a la combinación de todas las salidas $\frac{1}{n} \sum_i^n f(x_i)$ .
Si esto fuera todo, podríamos calcular todo de las salidas de una función tan rápido como podamos calcular un . La advertencia cuántica es que cuando vas a mirar tu respuesta, no ves $\frac{1}{n} \sum_i^n f(x_i)$ , ya ves $f(x_i)$ para algunos $i$ , con probabilidad $\frac{1}{n}$ . Así que parece que sólo hemos calculado la función una vez, después de todo. Sin embargo, si somos inteligentes, podemos seguir sacando provecho de nuestro ordenador cuántico. Digamos que, en lugar de querer conocer todos los valores, $f(x_i)$ queremos conocer alguna función $g(f)$ que depende de todo de las respuestas $f(x_i)$ . Si somos lo suficientemente inteligentes, a veces podemos llegar a un algoritmo que toma $\frac{1}{n}\sum_i^n f(x_i)$ a $g(f)$ . El ordenador clásico podría haber necesitado computar cada $f(x_i)$ sólo para encontrar $g$ pero el ordenador cuántico sólo puede hacerlo "una vez".
Nota: esto no es exactamente como funciona en la mayoría de los casos, pero la mayoría de los casos requieren un poco de matemáticas para describir con precisión. Pero esta es la "idea general" de por qué los ordenadores cuánticos pueden superar a los clásicos.
