Pregunta original
¿Por qué el algoritmo de Grover está tan acelerado por los algoritmos cuánticos?
Grover no tenía algún tipo de algoritmo que modificara / mejorara para tener un algoritmo cuántico, si eso es lo que está preguntando. Lo que Grover propuso fue un algoritmo cuántico que es uno de los primeros en el campo que revolucionó, por así decirlo, la forma en que podemos obtener las soluciones al problema: el algoritmo de Grover [quant-ph / 9605043] Un algoritmo mecánico cuántico rápido para la base de datos buscar; dada una lista no estructurada de [math] N = 2 ^ n [/ math] ítems, ¿existe cierto ítem [math] l [/ math] en esta lista dada una función [math] f [/ math] que mapea la entrada a [matemáticas] 1: [/ matemáticas] si el elemento existe o [matemáticas] 0: [/ matemáticas] si el elemento no existe. En una computadora clásica, podría responderse en los pasos [matemática] O (N) [/ matemática] [el enfoque intuitivo de iterar sobre todos los elementos para encontrar [matemática] l [/ matemática]], pero usando el algoritmo de Grover, podría hacerse en [math] O (\ sqrt {N}) [/ math]. Genial, ¿eh?
- ¿Cuándo podrán los humanos comunicarse a través del enredo cuántico?
- ¿Cuánto han cambiado tu vida las computadoras?
- ¿La Física Cuántica necesita una nueva base de realidad funcional de onda?
- ¿El enredo cuántico algún día permitirá intercambiar información?
- ¿Cuál es su teorema, ley, propiedad o principio favorito (matemáticas, física (cuántica), química (cuántica), psicología ...)?
[si no tiene experiencia en mecánica cuántica, omita los siguientes pasos que describen el algoritmo]
- Registro de preparación. Prepare un registro cuántico de tamaño [math] n + 1 [/ math] de modo que los primeros [math] n [/ math] sean ceros y el qubit adicional sea [math] 1 | \ varphi_ {0} \ rangle = | 0 \ rangle ^ {\ otimes n} \ otimes | 1 \ rangle [/ math]
- Registro de inicialización . Aplique puertas Hadamard en el registro para crear una superposición perfecta de todos los estados posibles, es decir, [matemática] 2 ^ n [/ matemática] estados.
[matemáticas] | \ varphi_ {1} \ rangle = {\ frac {1} {\ sqrt {N}}} \ sum _ {i = \ big \ {0,1 \ big \} ^ n} ^ {} | i \ rangle \ otimes \ frac {| 0 \ rangle- | 1 \ rangle} {\ sqrt {2}} [/ math] - Marque la solución. Aplique la función booleana de recuadro negro de la superposición para marcar la solución del problema mediante un cambio de fase, es decir, [matemática] U_f | i \ rangle \ longrightarrow (-1) ^ {f (i)} | i \ rangle [ /mates].
[matemáticas] | \ varphi_ {2} \ rangle = \ frac {1} {\ sqrt {N}} \ lbrace \ sum_ {i = \ lbrace 0,1 \ rbrace ^ n} ^ {\ prime \ prime} | i> \ otimes \ frac {| 0> – | 1>} {\ sqrt {2}} – \ sum_ {i = \ lbrace 0,1 \ rbrace ^ n} ^ {\ prime} | i \ rangle \ otimes \ frac {| 0 \ rangle- | 1 \ rangle} {\ sqrt {2}} \ rbrace [/ math] donde [math] \ sum ^ \ prime [/ math] denota las soluciones deseadas que son soluciones [math] M [/ math] (suponiendo la lista puede tener M copias de [math] l [/ math]), y [math] \ sum ^ {\ prime \ prime} [/ math] denota las soluciones no deseadas de tamaño [math] NM. [/ math] - Aplicar operador Grover . La funcionalidad principal de este operador es amplificar la amplitud de las soluciones deseadas y des amplificar las amplitudes de las soluciones residuales.
- Iterar Realice los pasos 3 y 4 [matemática] \ pi / 4 \ sqrt {N / M} [/ matemática] veces, para obtener un buen resultado.
- Mide la salida. Se garantiza que los estados de solución aparecerán con mayor probabilidad en comparación con los estados sin solución.
El algoritmo de Grover, como muchos otros algoritmos cuánticos, utiliza fenómenos cuánticos como enredos y superposición para crear un paradigma que es más poderoso que los cálculos clásicos [que es un paralelismo masivo] para acelerar el proceso de búsqueda de un elemento en una lista no estructurada. Es como mirar todos los ítems [matemáticos] N [/ matemáticos] en esa lista al mismo tiempo, buscar el ítem [matemáticos] l [/ matemáticos], ¡que es genial!
