Este cómic de Scott Aaronson y Zach Weinersmith es una gran introducción breve sobre cómo funciona la computación cuántica:
En resumen, la razón por la que obtienes una aceleración es que la mecánica cuántica reemplaza las distribuciones de probabilidad clásicas con amplitudes y matrices de densidad. Esto significa que las probabilidades pueden agregarse de formas más sutiles que clásicamente, e incluso pueden cancelarse.
- ¿Cuál es el estado actual de desarrollo de las computadoras cuánticas?
- ¿Por qué los qubits pueden ser más útiles que los bits?
- ¿Podría usarse una computadora cuántica para escribir una prueba lógica de que una aplicación de software no tiene errores, equivalente a probar todas las combinaciones posibles de entrada y salida?
- ¿El experimento de la doble rendija en mecánica cuántica prueba la naturaleza no local de la mecánica cuántica y la existencia de la no localidad en la física?
- ¿Qué es el índice de pobreza multidimensional?
Entonces puede aprovechar esto para construir algoritmos probabilísticos muy eficientes. Normalmente, el enfoque adoptado es que inicialmente tiene una variable (es decir, un conjunto de qbits) inicializada en un estado donde todos los valores posibles tienen la misma probabilidad. Luego diseña un conjunto de operaciones de tal manera que las probabilidades de las respuestas incorrectas se cancelen mientras se suman las probabilidades de las respuestas correctas.
Esto le brinda una herramienta además de las que obtiene de los algoritmos clásicos, y le permite diseñar algoritmos probabilísticos con tasas de éxito mucho más altas de lo que es posible clásicamente.