Este sitio puede que no sea el lugar correcto para hacer esta pregunta porque es tanto una pregunta de física como de computación. En la computación cuántica, entiendo que los qubits tienen muchos más estados que ceros y unos. ¿Pero cómo es que esto realmente acelera la computación? Supongo que puede ser una forma de SIMD, es decir, instrucciones individuales actuando sobre múltiples datos. Con esto quiero decir que un solo qubit podría contener mil millones de números y lo mismo un segundo qubit. Al sumarlos, podrías efectivamente realizar la suma de todos los números en paralelo. ¿Es así como las computadoras cuánticas obtienen su alta velocidad, o es un mecanismo completamente diferente?
Respuesta
¿Demasiados anuncios?
Las computadoras cuánticas son un modelo fundamentalmente diferente de la computación clásica, incluso del paralelismo SIMD.
Los estados cuánticos tienen algunas propiedades especiales: (1) pueden existir en superposiciones de estados, como si varios valores diferentes de un bit o un registro estuvieran presentes al mismo tiempo, (2) puede haber entrelazamiento cuántico que fuerza correlaciones específicas entre diferentes bits cuánticos, y (3) al medir una salida obtendrás una respuesta elegida al azar de los estados cuánticos superpuestos basada en el tamaño de su "amplitud".
Esto hace que los algoritmos cuánticos sean muy diferentes de los algoritmos clásicos. Si tomo un registro cuántico de N qubits X y lo convierto en una superposición par de todos los valores posibles, ahora puedo calcular (digamos) el cuadrado del valor del registro y ponerlo en otro registro Y. Esto tarda tanto como calcular el cuadrado de un valor de forma clásica, a pesar de que la operación actúa en $2^N$ valores. Si mido Y obtendré un cuadrado aleatorio seleccionado de los $2^N$ cuadrados posibles, pero no puedo seleccionar cuál. Más intrigantemente, ahora X también contendrá instantáneamente la(s) raíz (tanto $\sqrt{Y}$ como $-\sqrt{Y}$), y si mido X ahora obtendré una de ellas.
El truco de los algoritmos cuánticos es realizar una computación de manera que cuando obtengas una respuesta aleatoria de la salida te diga algo que es difícil de calcular. Para el algoritmo de factorización de Shor, se convierte la factorización en encontrar un período de una función y luego se utiliza la computación cuántica para obtener un período aproximado: mediante la repetición se puede estar lo suficientemente seguro como para habilitar pruebas determinísticas. Esto es una aceleración exponencial, que es típica para los "buenos" algoritmos cuánticos. El algoritmo de búsqueda de Grover simplemente proporciona una aceleración cuadrática ($O(\sqrt{N})$ en lugar de $O(N)$), y bien podría haber muchos problemas que simplemente no se pueden acelerar con una computadora cuántica.
