(Nota: supongo que la pregunta se relaciona con http://www.scottaaronson.com/pap… que muestra que las variables ocultas permiten una convergencia más rápida que Grover).
Gran pregunta! Gracias por A2A. Recorta el núcleo de lo que significa “optimización” y lo que no significa. ¡La imagen de abajo contiene la respuesta como veremos!
Con frecuencia, los científicos, como los abogados, adoran las renuncias. Desafortunadamente, nos gusta barrer nuestros descargos de responsabilidad bajo la alfombra. En otras palabras, a menudo dejamos de lado las renuncias y esperamos que la audiencia las “infiera”. Por qué ? ¿Quizás para no confundir a laicos y novatos? ¿Quizás para hacer que nuestro trabajo suene más definitivo de lo que realmente es? (¡NO sugiero que Scott haga esto en el documento anterior, creo que Scott es uno de los científicos más brillantes con vida, y siempre grita advertencias desde los tejados!)
- ¿Cómo la descripción cuántica de la realidad, como la superposición y el colapso de la función de onda, da lugar a la realidad que percibimos?
- ¿Cuáles crees que serán los cuellos de botella de las computadoras cuánticas?
- ¿Qué tipos de problemas resolvería una computadora cuántica de lógica difusa que el sistema actual basado en lógica binaria no lo hace?
- ¿De qué haremos qubits? ¿Ya tenemos?
- ¿Por qué los operadores hermitianos están asociados con cantidades físicas en la mecánica cuántica?
Entonces, antes de pasar a la cuántica, considere algoritmos “óptimos” para computadoras normales. Cuando un algoritmo es descifrado para ser óptimo, las advertencias son largas e incluyen:
- Óptimo solo porque el tamaño de los datos tiende al infinito
- Óptimo solo en términos de un cierto recuento de operaciones, como multiplicaciones o comparaciones
- A menudo óptimo solo en un sentido estadístico
- … e ignorando la estabilidad numérica que puede requerir precisión adicional
- … Ignorando el costo de la paginación de memoria, etc., que puede ser la sincronización de tiempo dominante.
- … pregúntele a Vladislav Zorov ¡Apuesto a que puede enumerar más!
Ahora en cuanto hay un par de supuestos adicionales:
- Los oráculos son gratuitos (busque quora para más detalles o vea más abajo)
- Las leyes de la física tal como las entendemos actualmente son correctas.
De vuelta a Grover:
Grover requiere que tengamos una unidad de memoria (oráculo) por la cual cada vez que accedemos a esta unidad de memoria accedemos a todos los registros de memoria en superposición. Esta es una hazaña que es difícil. Por ejemplo, un Gbyte Ram requeriría una computadora cuántica capaz de tener 8 mil millones de recuperaciones de memoria entrelazadas. En este momento podemos subir a unos 10 microsegundos, en lugar de 8 mil millones indefinidamente.
Volver a las variables ocultas y Grover:
El borrador cuántico de elección retrasada ha demostrado definitivamente que no existen variables ocultas. Si lo hicieran, podríamos hacerlo más rápido que Grover. ¡Pero parece que en ESTE UNIVERSO estamos atrapados con Grover!
Juego sobre aplausos!
