¿Cómo es útil la salida del algoritmo de Grover si se requiere el resultado para usar el oráculo? Si ya conocemos el estado deseado, ¿cuál es el punto de usar el algoritmo?
Entonces, ¿puede darme un ejemplo concreto de una función de Oracle? Por ejemplo, si los elementos indexados en una búsqueda de Grover fueran, por ejemplo, patrones arbitrarios, ¿cómo sería la función de Oracle correspondiente? Hagamos el ejemplo más concreto. Cada patrón es la imagen de una cara y queremos ver si una cara desconocida se encuentra dentro del conjunto de patrones. Clásicamente, nuestro algoritmo de búsqueda es un algoritmo de correlación (por ejemplo, Kendall-tau, correlación de rango, etc.). ¿Cuál sería el análogo de esto para una búsqueda cuántica?
Hay una diferencia entre encontrar una solución y reconocer una solución. Oracle puede reconocer la solución o resolver una instancia particular del problema, pero no puede brindarle la solución para el problema completo. O, en otras palabras, Oracle le brinda una parte de la solución y es posible que deba consultar Oracle varias veces para obtener la solución completa. Oracle también se puede considerar como una función de biblioteca (como en los lenguajes de programación) que le brindará una solución para una instancia de un problema, y el costo real de la computación se mide por cuántas veces llama a la función y no por la complejidad inherente de la misma. función en sí misma que se toma como caja negra. Por ejemplo, digamos que tenemos un oráculo para una función , al presentar este oráculo con un par dirá si O no. En este caso, la complejidad del tiempo se toma como la cantidad de tiempo que necesita consultar el oráculo para obtener el resultado deseado.
Se puede tomar un ejemplo más concreto de Oracle para verificar si el número es primo. Digamos que queremos encontrar el primer número primo . El problema tiene distinta complejidad cuando se te da acceso al oráculo y cuando no se te da.
Ejemplo físico de un oráculo: digamos que nuestro problema es determinar el ángulo entre el piso y la pared que puede no ser necesariamente lo. Todo lo que puedes hacer es lanzar una pelota que chocará elásticamente contra la pared y regresará. Tienes el control del ángulo que lanzas y puedes anotar el ángulo con el que regresa. Cada lanzamiento de una pelota se puede comparar con la llamada de la función del oráculo y la restricción en el ángulo de la pelota que regresa (reflexión, que le da una pista sobre la orientación de la pared) se puede considerar un oráculo. La cantidad de veces que necesita repetir el lanzamiento de la pelota para obtener la orientación con la precisión deseada puede considerarse como la complejidad del problema en relación con el oráculo.
El oráculo no necesita conocer el estado deseado para verificar si un estado dado es el estado deseado.
El algoritmo de Grover se puede aplicar a problemas NP-completos . Este es el conjunto de problemas para los cuales no se conoce una forma de generar una solución en tiempo polinomial, pero una solución dada puede reconocerse en tiempo polinomial.