Medición de la velocidad del algoritmo de Grover

La complejidad del tiempo de ejecución es, por supuesto, proporcional al número de operadores de difusión de Grover en el circuito cuántico.

Como probablemente sepa, los algoritmos cuánticos son probabilísticos. Usted es libre de elegir el número de operadores de Grover y, por lo tanto, el tiempo de ejecución del algoritmo. Cuantas más puertas coloque, más tardará en ejecutarse, pero aumentará la probabilidad de obtener la respuesta correcta.

Sin embargo, solo tiene sentido agregar nuevas puertas hasta algún punto en el que la probabilidad de obtener una respuesta correcta aumente tan levemente que este beneficio no cubra el costo de agregar una puerta +1 al tiempo de ejecución.

Esto sucede aproximadamente cuando el número de puertas es$\sim \sqrt{N}$dónde$N$es el tamaño del dominio de búsqueda del algoritmo. Es por eso que se dice que la complejidad asintótica del tiempo de ejecución del algoritmo de Grover es$O(\sqrt{N})$, que ofrece una aceleración cuántica cuadrática en comparación con el algoritmo clásico con complejidad de tiempo de ejecución$O(N)$.

Entonces, respondiendo a su pregunta: si quiere jugar con el algoritmo, debe probar diferentes números de puertas de difusión de Grover$k$en algún lugar de$k = 1$hasta$k = N$. El costo de tiempo de ejecución del algoritmo es proporcional a$k$, mientras que el simulador de IBM (o cualquier otro) calculará la probabilidad de obtener la respuesta correcta por usted. De esta manera puedes ver cuáles$k$es mejor. Como se mencionó anteriormente, se espera que esto crezca a medida que$k_{\text{best}} \sim \sqrt{N}$.