Un oráculo es un dispositivo utilizado para analizar algo llamado “complejidad de consulta”. Esto es esencialmente de lo que se trata el algoritmo de Grover.
La pregunta a responder es esta: dado un oráculo que acepta [math] n [/ math] número de entradas y devuelve [math] 1 [/ math] y [math] -1 [/ math] al ingresar una entrada aceptada o una entrada rechazada, respectivamente, ¿cuántas consultas al oráculo hay que hacer para poder encontrar una entrada aceptada? El algoritmo así diseñado debe ser independiente de la naturaleza del oráculo.
El oráculo aquí es un dispositivo que de hecho no se ha construido. Es simplemente un dispositivo de análisis, completamente hipotético. Resulta que han sido útiles de muchas maneras, que describiré más adelante. * *
- ¿Se utiliza la teoría de grupos en la IA?
- ¿Puedo ser un buen ingeniero informático si mi matemática es débil?
- Me dicen que si n = 25, tenemos Sn = 121392 donde Sn es el número de adiciones realizadas en la siguiente función para calcular el enésimo número de Fibonacci. ¿Alguien puede explicar cómo? Int F (int n) {if (n == 0) return (0); if (n == 1) return (1); retorno (F (n-1) + F (n-2));}
- ¿Cuál es la mejor manera de dibujar un gráfico de teoría de grafos rápidamente?
- Matemática discreta: ¿Cuál es la diferencia entre ser un elemento de un conjunto o ser un subconjunto de un conjunto?
De hecho, esta es una versión generalizada del problema de búsqueda, que es simplemente esto, en una lista de elementos [matemáticos] n [/ matemáticos], para averiguar la posición de un elemento específico.
En el paradigma actual, es fácil mostrar un algoritmo que encuentre la entrada aceptada en [math] O (n) [/ math] time y se puede demostrar que no se puede hacer mejor que [math] \ Omega (n) [/matemáticas].
En el paradigma cuántico, el algoritmo de Grover lo hace en [math] O (\ sqrt {n}) [/ math] y también se ha demostrado que no se puede hacer mejor que [math] \ Omega (\ sqrt {n}) [ /matemáticas].
Específico a la computación cuántica, existe una naturaleza de oráculos conocida como cambio de fase selectivo. Dado como entrada un estado con ciertas amplitudes en el estado aceptado y rechazado, invierte selectivamente el signo de la amplitud en el estado rechazado. Esta es una modificación crucial sobre la que depende el algoritmo de Grover.
######################################
Los oráculos en general también se usan para otros fines en la teoría de la complejidad.
Uno de esos usos es la relativización. Para casi cualquier clase de complejidad, podemos definir una versión de la misma que tenga acceso a algún oráculo aleatorio. Algunos resultados sobre las clases de complejidad también se mantienen en un mundo así. Tales resultados son inútiles para resolver P vs NP, uno de los problemas centrales, porque en un mundo relativizado, tanto P = NP como la conversación inversa.
Otro de estos usos es la creación de jerarquías. Dele un oráculo de una clase de complejidad a otra clase de complejidad y obtendrá una tercera clase de complejidad. Estos nuevamente pueden ser útiles para obtener una comprensión fundamental.
Hay mucho que decir sobre los oráculos, mucho más de lo que uno podría encajar en una respuesta, así que déjenme parar aquí.
