Un algoritmo cuántico no acelera todo
Un algoritmo cuántico es un programa pensado para un ordenador cuántico que usa la interferencia para llegar antes a una respuesta. Solo acelera algunos problemas concretos, y saber cuáles evita creer promesas que no son ciertas.
En esta lección harás un paso de búsqueda con amplitudes y sabrás qué problemas no mejoran.
Al final de esta lección
Nota
Puedo decir qué problemas aceleran los algoritmos cuánticos y qué problemas no.
Palabras clave
| Palabra | Qué significa |
|---|---|
| Algoritmo cuántico | un programa que usa amplitudes e interferencia |
| Amplificación | subir la amplitud de la respuesta buena |
| Aceleración | hacer el mismo trabajo en menos pasos |
| Ruido | los errores de un qubit real |
| Corrección de errores | usar muchos qubits para proteger uno |
| Simulador | un programa que sigue las reglas en un ordenador normal |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
La amplificación sube la respuesta buena
Imagina cuatro cajones y una llave en uno solo. Un programa normal los abre uno a uno. El estado cuántico los guarda todos con la misma amplitud, 0,5, y marca el bueno con un cambio de signo.
Un segundo paso refleja cada amplitud respecto a la media. Con cuatro objetos, un solo paso deja la respuesta buena con probabilidad 1.
Ejemplo resuelto: un paso con cuatro objetos
| Paso | Estado de los cuatro objetos | Media | Probabilidad del marcado |
|---|---|---|---|
| Inicio | [0,5 ; 0,5 ; 0,5 ; 0,5] | 0,5 | 0,25 |
| Cambiar el signo del marcado | [0,5 ; 0,5 ; 0,5 ; −0,5] | 0,25 | 0,25 |
| Reflejar respecto a la media (2 × media − amplitud) | [0 ; 0 ; 0 ; 1] | 0,25 | 1 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Un simulador no puede mostrar una aceleración
Nota
El laboratorio es un simulador: guarda todas las amplitudes en un ordenador normal, y cada qubit nuevo duplica el trabajo. No es un ordenador cuántico y no puede mostrar que uno sea más rápido. Lo que enseña son las reglas. Los scripts escriben en inglés: "chance of each" quiere decir "probabilidad de cada uno".
Un paso de amplificación
docker exec jupyter python3 steps/amplify.pySe muestra aquí y no se ejecuta. Crea una cuenta gratuita para pulsar Ejecutar y escribirlo en el terminal de tu propio laboratorio.
Qué escribe el script de la amplificación
El script usa cuatro objetos, numerados 00, 01, 10 y 11, con el 11 marcado. Al principio escribe 0.500 para cada uno, así que cada probabilidad es 0,25.
Tras cambiar el signo del marcado, las probabilidades siguen iguales. Tras un paso de amplificación escribe 1.000|11>: el objeto marcado es seguro.
La mejora de la búsqueda es cuadrática
Para buscar entre N objetos sin orden, un programa normal necesita del orden de N intentos. La amplificación necesita del orden de la raíz cuadrada de N pasos.
Es una mejora grande, pero cuadrática. No convierte un problema imposible en uno fácil, y solo se aprecia con una máquina real y muchos objetos.
Ejemplo resuelto: pasos según el número de objetos
| Objetos | Intentos de un programa normal | Pasos de amplificación |
|---|---|---|
| 4 | del orden de 4 | 1 |
| 100 | del orden de 100 | del orden de 10 |
| 1.000.000 | del orden de 1.000.000 | del orden de 1000 |
Las celdas que rellenan los estudiantes quedan en blanco en esta vista previa.
Qué no acelera un ordenador cuántico
Un ordenador cuántico no acelera abrir una página web, ordenar una hoja de cálculo ni ejecutar un programa corriente. Solo mejora problemas con una estructura que la interferencia pueda aprovechar.
El ejemplo más conocido es descomponer un número muy grande en factores. Un algoritmo cuántico lo haría mucho más rápido que los métodos conocidos, pero necesita una máquina enorme y sin errores.
Un error frecuente
Advertencia
Mucha gente cree que un ordenador cuántico prueba todas las respuestas a la vez y elige la buena. No es así. Al medir sale un solo resultado, por azar. El algoritmo debe preparar las amplitudes con interferencia para que la respuesta buena sea la más probable.
El ruido es el gran problema real
Un qubit real se estropea con el calor, las vibraciones y las lecturas. Esos errores se llaman ruido, y se acumulan con cada puerta.
La corrección de errores protege un qubit útil con muchos qubits físicos. Por eso es tan difícil construir máquinas que resuelvan problemas grandes. El simulador, en cambio, no tiene ruido: sus cuentas son exactas.