¿Cómo hace la superposición cuántica que el cálculo sea más rápido?

Las operaciones no son más rápidas , son más flexibles . De esa flexibilidad viene el poder.

Por ejemplo: en una computadora clásica no hay una operación de un solo bit que, cuando se aplica dos veces, cambie un bit. No hay función booleana$f$tal que$f(f(x)) = \overline{x}$. Pero las computadoras cuánticas tienen tal operación, representada por la matriz$M = \frac{1}{2} \begin{bmatrix} 1+i & 1-i \\ 1-i & 1+i \end{bmatrix}$. Tenga en cuenta que$M^2 = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}$es la forma matricial de una operación que cambia un poco.

Esta flexibilidad se extiende a sistemas de muchos qubits y crea caminos desde problemas hasta soluciones que no están disponibles para las computadoras clásicas. Por ejemplo, el algoritmo de búsqueda de Grover realiza una búsqueda no estructurada cuadráticamente más rápida al configurar básicamente una rotación gradual desde un estado inicial hasta el estado de la solución. Pero la rotación no corresponde a ninguna operación clásica, por lo que solo puedes hacerlo con una computadora cuántica.

El otro gran ejemplo de una operación solo cuántica es la transformada cuántica de Fourier . Imagine trazar las probabilidades de que la computadora esté en varios estados, uno tras otro, dispuestos en una línea y formando un gráfico irregular que salta hacia arriba y hacia abajo. Si interpreta ese gráfico como una onda de sonido, el QFT le dirá la frecuencia más fuerte que está presente. No es la frecuencia más fuerte en una lista de valores explícitamente almacenada, sino la frecuencia más fuerte en las probabilidades implícitas de que su computadora se encuentre en varios estados . (Advertencia: estoy simplificando demasiado aquí). ¡Eso es bastante extraño! Y, resulta, útil .

Es una consecuencia directa de la formalización matricial y la regla de Born. Consulte la puerta cuántica de Hadamard, que es el ejemplo central de su pregunta. Se necesita un estado superpuesto (que puede ser largo) para calcularse como entrada, lo contrae y genera un resultado.

Tenga en cuenta que el cálculo del estado superpuesto se realiza en un solo paso, sin importar cuán grande sea la superposición. Esta forma de computar se debe a la regla de Born.

Para obtener más información, consulte el libro Computación cuántica e información cuántica de Nielsen y Chuang. Es un libro de introducción muy bueno y fue muy utilizado cuando trabajaba en Perimeter Institute.