¿Hay una explicación laica de por qué funciona el algoritmo de Grover?

Esta publicación de blog de Scott Aaronson es una explicación muy útil y simple del algoritmo de Shor .

Me pregunto si existe tal explicación para el segundo algoritmo cuántico más famoso: el algoritmo de Grover para buscar una base de datos desordenada de tamaño en el tiempo .$O(n)$$O(\sqrt{n})$

En particular, me gustaría ver una intuición comprensible para el resultado inicialmente sorprendente del tiempo de ejecución.

Hay una buena explicación por Craig Gidney aquí (también tiene otra gran contenido, incluyendo un simulador de circuitos, en su blog ).

Esencialmente, el algoritmo de Grover se aplica cuando tiene una función que regresa Truepara una de sus posibles entradas y Falsepara todas las demás. El trabajo del algoritmo es encontrar el que regresa True.

Para hacer esto, expresamos las entradas como cadenas de bits y las codificamos utilizando los estados y de una cadena de qubits. Por lo tanto, la cadena de bits se codificaría en el estado de cuatro qubits , por ejemplo.$|0\rangle$$|1\rangle$0011$|0011\rangle$

También necesitamos poder implementar la función usando puertas cuánticas. Específicamente, necesitamos encontrar una secuencia de puertas que implementen una unitaria tal que$U$

$U | a \rangle = - | a \rangle, \,\,\,\,\,\,\,\,\,\,\,\,\, U | b \rangle = | b \rangle$

donde es la cadena de bits para los que la función devolvería y es ninguna de las que volvería .$a$True$b$False

Si comenzamos con una superposición de todas las cadenas de bits posibles, lo cual es bastante fácil de hacer simplemente Hadamarding todo, todas las entradas comienzan con la misma amplitud de (donde es la longitud de las cadenas de bits que estamos buscando y, por lo tanto, el número de qubits que estamos usando). Pero si luego aplicamos el oráculo , la amplitud del estado que estamos buscando cambiará a .$\frac{1}{\sqrt{2^n}}$$n$$U$$-\frac{1}{\sqrt{2^n}}$

Esta no es una diferencia fácilmente observable, por lo que debemos amplificarla. Para ello utilizamos el Grover Difusión del operador , . El efecto de este operador es esencialmente observar cómo cada amplitud es diferente de la amplitud media, y luego invertir esta diferencia. Entonces, si una cierta amplitud era una cierta cantidad mayor que la amplitud media, se convertirá en esa misma cantidad menor que la media, y viceversa.$D$

Específicamente, si tiene una superposición de cadenas de bits , el operador de difusión tiene el efecto$b_j$

$D: \,\,\,\, \sum_j \alpha_j \, | b_j \rangle \,\,\,\,\,\, \mapsto \,\,\,\,\,\, \sum_j (2\mu \, - \, \alpha_j) \, | b_j \rangle$

donde es la amplitud media. Entonces, cualquier amplitud se convierte en . Para ver por qué tiene este efecto y cómo implementarlo, vea estas notas de clase .$\mu = \sum_j \alpha_j$$\mu + \delta$$\mu - \delta$

La mayoría de las amplitudes serán un poco más grandes que la media (debido al efecto del single ), por lo que serán un poco menos que la media a través de esta operacion. No es un gran cambio.$-\frac{1}{\sqrt{2^n}}$

El estado que estamos buscando se verá afectado más fuertemente. Su amplitud es mucho menor que la media, por lo que será mucho mayor que la media después de aplicar el operador de difusión. El efecto final del operador de difusión es, por lo tanto, causar un efecto de interferencia en los estados que roza una amplitud de de todas las respuestas incorrectas y las agrega a la correcta. Al repetir este proceso, podemos llegar rápidamente al punto en que nuestra solución se destaca tanto de la multitud que podemos identificarla.$\frac{1}{\sqrt{2^n}}$

Por supuesto, todo esto demuestra que todo el trabajo lo realiza el operador de difusión. La búsqueda es solo una aplicación que podemos conectar a ella.

Consulte las respuestas a otras preguntas para obtener detalles sobre cómo se implementan las funciones y el operador de difusión .

Encuentro un enfoque gráfico bastante bueno para dar una idea sin ser demasiado técnico. Necesitamos algunas entradas:

• podemos producir un estado con superposición distinta de cero con el estado 'marcado' : .$|\psi\rangle$$|x\rangle$$\langle x|\psi\rangle\neq 0$
• podemos implementar una operación$U_1=-(\mathbb{I}-2|\psi\rangle\langle\psi|)$
• podemos implementar una operación.$U_2=\mathbb{I}-2|x\rangle\langle x|$

Esta última operación es la que puede marcar nuestro elemento marcado con una fase -1. También podemos definir un estado para que sea ortonormal a modo que forme una base ortonormal para el lapso de . Ambas operaciones que hemos definido preservan este espacio: comienzas con algún estado en el lapso de , y devuelven un estado dentro del lapso. Además, ambos son unitarios, por lo que se conserva la longitud del vector de entrada.$|\psi^\perp\rangle$$|x\rangle$$\{|x\rangle,|\psi^\perp\rangle\}$$\{|x\rangle,|\psi\rangle\}$$\{|x\rangle,|\psi^\perp\rangle\}$

Un vector de longitud fija dentro de un espacio bidimensional se puede visualizar como la circunferencia de un círculo. Entonces, configuremos un círculo con dos direcciones ortogonales correspondientes a y . $|\psi^\perp\rangle$$|x\rangle$

Nuestro estado inicial tendrá una pequeña superposición con y una superposición grande con . Si fuera al revés, la búsqueda sería fácil: simplemente prepararíamos , y probaríamos la salida usando la marca unitaria, repitiendo hasta que obtuviéramos el elemento marcado. No llevaría mucho tiempo. Llamemos el ángulo entre y the angle . $|\psi\rangle$$|x\rangle$$|\psi^\perp\rangle$$|\psi\rangle$$|\psi\rangle$$|\psi^\perp\rangle$$\theta$

Ahora tomemos un momento para pensar en lo que hacen nuestras dos acciones unitarias. Ambos tienen un valor propio -1, y todos los demás valores propios +1. En nuestro subespacio bidimensional, eso se reduce a un valor propio +1 y un valor propio -1. Tal operación es una reflexión en el eje definido por el vector propio +1. Entonces, es un reflejo en el eje , mientras que es un reflejo en el eje . $U_1$$|\psi\rangle$$U_2$$|\psi^\perp\rangle$

Ahora, tome un vector arbitrario en este espacio y aplique seguido de . El efecto neto es que el vector gira un ángulo hacia el eje . $U_2$$U_1$$2\theta$$|x\rangle$

Por lo tanto, si comienza desde , puede repetir esto muchas veces y llegar a un ángulo de . Por lo tanto, cuando medimos ese estado, obtenemos el valor con alta probabilidad.$|\psi\rangle$$\theta$$|x\rangle$$x$

Ahora necesitamos un poco de cuidado para encontrar la aceleración. Suponga que la probabilidad de encontrar en es . Entonces, clásicamente, necesitaríamos intentos para encontrarlo. En nuestro escenario cuántico, tenemos que (ya que es pequeño), y queremos una serie de ejecuciones tales que . Entonces, . Puedes ver la aceleración de la raíz cuadrada allí mismo.$|x\rangle$$|\psi\rangle$$p\ll 1$$O(1/p)$$\sqrt{p}=\sin\theta\approx\theta$$\theta$$r$$\sin((2r+1)\theta)\approx 1$$r\approx \frac{\pi}{2\theta}\approx \frac{\pi}{2\sqrt{p}}$

La explicación simple de cómo (y, por lo tanto, por qué) funciona el algoritmo de Grover es que una puerta cuántica solo puede reorganizar (o distribuir) amplitudes de probabilidad. Usando un estado inicial con amplitudes de probabilidad iguales para todos los estados de la base computacional, uno comienza con una amplitud de . Esto se puede "agregar" al estado (solución) deseado en cada iteración, de modo que después de las iteraciones se llegue a una amplitud de probabilidad de significa que se ha destilado el estado deseado.$1/\sqrt{N}$$\sqrt{N}$$1$