Los qubits son fundamentales para la computación cuántica y guardan cierta analogía con los bits en una computadora clásica. Los qubits pueden estar en un estado cuántico de 1 o 0, pero también pueden estar en una superposición de ambos estados. Sin embargo, cuando se miden los qubits, el resultado siempre es 0 o 1; las probabilidades de los dos resultados dependen del estado cuántico en que se encontraban.
A pesar del progreso experimental continuo desde finales de la década de 1990, la mayoría de los investigadores creen que “la computación cuántica tolerante a fallos todavía es un sueño bastante distante”. El 23 de octubre de 2019, Google AI, en colaboración con la NASA, publicó un artículo en el que afirmaba haber logrado la supremacía cuántica. Aunque algunos han cuestionado esta afirmación, sigue siendo un hito significativo en la historia de la computación cuántica.
La esfera de Bloch es una representación de un qubit, el bloque fundamental de construcción de las computadoras cuánticas.
El modelo predominante de computación cuántica describe la computación en términos de una red de puertas lógicas cuánticas. A continuación se presenta un tratamiento breve del tema basado en el capítulo 4 de Nielsen y Chuang.
Una memoria compuesta por bits de información tiene estados posibles. Un vector que represente todos los estados de memoria tiene por tanto entradas (una para cada estado). Este vector debe verse como un vector de probabilidad y representa el hecho de que la memoria se encuentra en un estado particular.
En la mecánica cuántica, los vectores de probabilidad se generalizan a operadores de densidad. Esta es la base matemática rigurosa para las puertas lógicas cuánticas, pero el formalismo del vector de estado intermedio suele introducirse primero porque es conceptualmente más sencillo. Este artículo se centra en el formalismo del vector de estado cuántico por simplicidad.
Comenzamos considerando una memoria simple compuesta por un solo bit. Esta memoria puede encontrarse en uno de dos estados: el estado cero o el estado uno. Podemos representar el estado de esta memoria utilizando la notación de Dirac.
Una memoria cuántica puede encontrarse en cualquier superposición cuántica de los dos estados clásicos:
En general, los coeficientes son números complejos. En este escenario, se dice que se ha codificado un qubit de información en la memoria cuántica. El estado no es en sí mismo un vector de probabilidad, pero puede conectarse con un vector de probabilidad mediante una operación de medición.
Si la memoria cuántica se mide para determinar si el estado es 0 o 1 (esto se conoce como medición en la base computacional), se observaría el estado cero con probabilidad |α|² y el estado uno con probabilidad |β|². Los números α y β se llaman amplitudes cuánticas.
El estado de esta memoria cuántica de un solo qubit puede manipularse aplicando puertas lógicas cuánticas, análogas a cómo se manipula la memoria clásica con puertas lógicas clásicas.
Una puerta importante para la computación clásica y cuántica es la puerta NOT, que puede representarse mediante una matriz:
$$\begin{bmatrix} 0 & 1 \ 1 & 0 \end{bmatrix}$$
Matemáticamente, la aplicación de dicha puerta lógica a un vector de estado cuántico se modela con multiplicación matricial.
Las matemáticas de las puertas de un solo qubit pueden extenderse para operar en memorias cuánticas de múltiples qubits de dos maneras importantes:
Los posibles estados de una memoria cuántica de dos qubits son:
La puerta CNOT puede representarse mediante la siguiente matriz:
$$\begin{bmatrix} 1 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix}$$
Como consecuencia matemática de esta definición:
En otras palabras, la puerta CNOT aplica una puerta NOT al segundo qubit si y solo si el primer qubit está en el estado |1>. Si el primer qubit está en el estado |0>, no se hace nada a ninguno de los dos qubits.
Cualquier computación cuántica puede representarse como una red de puertas lógicas cuánticas de una familia bastante pequeña de puertas. Una elección de familia de puertas que permite esta construcción se conoce como conjunto universal de puertas.
Un conjunto común incluye todas las puertas de un solo qubit, así como la puerta CNOT mencionada anteriormente. Esto significa que cualquier computación cuántica puede realizarse ejecutando una secuencia de puertas de un solo qubit junto con puertas CNOT. Aunque este conjunto de puertas es infinito, puede reemplazarse con un conjunto finito gracias al teorema de Solovay-Kitaev.
La factorización de enteros, que sustenta la seguridad de los sistemas criptográficos de clave pública, se considera computacionalmente inviable con una computadora ordinaria para enteros grandes si son el producto de pocos números primos (por ejemplo, productos de dos primos de 300 dígitos).
En contraste, una computadora cuántica podría resolver este problema de manera eficiente utilizando el algoritmo de Shor para encontrar sus factores. Esta capacidad permitiría a una computadora cuántica romper muchos de los sistemas criptográficos utilizados hoy en día, en el sentido de que existiría un algoritmo de tiempo polinómico (en el número de dígitos del entero) para resolver el problema.
En particular, la mayoría de los cifrados de clave pública populares se basan en la dificultad de factorizar enteros o el problema del logaritmo discreto, ambos resolubles mediante el algoritmo de Shor. En particular, los algoritmos RSA, Diffie-Hellman y Diffie-Hellman de curva elíptica podrían romperse. Estos se utilizan para proteger páginas web seguras, correo electrónico cifrado y muchos otros tipos de datos. Romper estos sistemas tendría repercusiones significativas para la privacidad y la seguridad electrónica.
Sin embargo, otros algoritmos criptográficos no parecen ser vulnerables a estos ataques. Algunos algoritmos de clave pública se basan en problemas distintos de la factorización de enteros y el logaritmo discreto a los que se aplica el algoritmo de Shor, como el sistema criptográfico de McEliece basado en un problema en teoría de códigos. Los sistemas criptográficos basados en retículos tampoco se conocen como vulnerables a las computadoras cuánticas, y encontrar un algoritmo de tiempo polinómico para resolver el problema del subgrupo oculto diédrico, que rompería muchos sistemas criptográficos basados en retículos, es un problema abierto bien estudiado.
Se ha demostrado que aplicar el algoritmo de Grover para romper un algoritmo simétrico (de clave secreta) mediante fuerza bruta requiere un tiempo igual a aproximadamente 2^(n/2) invocaciones del algoritmo criptográfico subyacente, comparado con aproximadamente 2^n en el caso clásico. Esto significa que las longitudes de clave simétricas se reducen efectivamente a la mitad: AES-256 tendría la misma seguridad contra un ataque que utiliza el algoritmo de Grover que AES-128 contra una búsqueda de fuerza bruta clásica (ver Tamaño de clave).
La criptografía cuántica podría potencialmente cumplir algunas de las funciones de la criptografía de clave pública. Los sistemas criptográficos basados en la mecánica cuántica podrían, por lo tanto, ser más seguros que los sistemas tradicionales frente a ataques cuánticos.
Además de la factorización y el logaritmo discreto, se han encontrado algoritmos cuánticos que ofrecen una aceleración superior al tiempo polinómico sobre los mejores algoritmos clásicos conocidos para varios problemas, incluyendo:
No se ha encontrado una prueba matemática que muestre que no pueda descubrirse un algoritmo clásico igualmente rápido, aunque esto se considera poco probable.
Sin embargo, las computadoras cuánticas ofrecen una aceleración polinómica para algunos problemas. El ejemplo más conocido es la búsqueda en una base de datos cuántica, que puede resolverse mediante el algoritmo de Grover utilizando cuadráticamente menos consultas a la base de datos que las requeridas por algoritmos clásicos. En este caso, la ventaja no solo es demostrable sino también óptima. Se ha demostrado que el algoritmo de Grover da la máxima probabilidad posible de encontrar el elemento deseado para cualquier número de consultas al oráculo.
Varios otros ejemplos de aceleraciones cuánticas demostrables para problemas de consulta se han descubierto posteriormente, como para encontrar colisiones en funciones de dos a uno y evaluar árboles NAND.
Para problemas con las siguientes propiedades:
El tiempo de ejecución del algoritmo de Grover en una computadora cuántica escalará como la raíz cuadrada del número de entradas (o elementos en la base de datos), en contraste con la escala lineal de los algoritmos clásicos.
Una clase general de problemas a los que puede aplicarse el algoritmo de Grover es el problema de satisfacibilidad booleana. En este caso, la base de datos a través de la cual itera el algoritmo es la de todas las posibles respuestas.
Un ejemplo (y posibilidad) de aplicación de esto es un rompecabezas de contraseñas que intenta adivinar la contraseña o clave secreta para un archivo o sistema cifrado. Los cifradores simétricos como Triple DES y AES son particularmente vulnerables a este tipo de ataque. Esta aplicación de la computación cuántica es de gran interés para agencias gubernamentales.
Dado que la química y la nanotecnología dependen de comprender sistemas cuánticos, y tales sistemas son imposibles de simular de manera eficiente clásicamente, muchos creen que la simulación cuántica será una de las aplicaciones más importantes de la computación cuántica.
La simulación cuántica también podría utilizarse para simular el comportamiento de átomos y partículas en condiciones inusuales, como las reacciones dentro de un colisionador.
El recocido cuántico o computación cuántica adiabática se basa en el teorema adiabático para realizar cálculos. Un sistema se coloca en el estado fundamental de un Hamiltoniano simple, que evoluciona lentamente hacia un Hamiltoniano más complejo cuyo estado fundamental representa la solución al problema en cuestión. El teorema adiabático establece que si la evolución es lo suficientemente lenta, el sistema permanecerá en su estado fundamental en todo momento durante el proceso.
Aunque las computadoras cuánticas pueden ser más rápidas que las clásicas para algunos tipos de problemas, estas no pueden resolver ningún problema que las computadoras clásicas no puedan resolver ya. Una máquina de Turing puede simular estas computadoras cuánticas, por lo que tal computadora cuántica nunca podría resolver un problema indecidible como el problema de la detención.
La existencia de computadoras cuánticas “estándar” no refuta la tesis de Church-Turing. Se ha especulado que teorías de la gravedad cuántica, como la teoría M o la gravedad cuántica de lazo, podrían permitir construir computadoras aún más rápidas. Actualmente, definir la computación en tales teorías es un problema abierto debido al problema del tiempo, es decir, actualmente no existe una forma obvia de describir lo que significa que un observador envíe una entrada a una computadora y reciba una salida más tarde.
^ ab The National Academies of Sciences, Engineering, and Medicine (2019). Grumbling, Emily; Horowitz, Mark (eds.). Quantum Computing : Progress and Prospects (2018). Washington, DC: National Academies Press. p. I-5. doi:10.17226/25196. ISBN 978-0-309-47969-1. OCLC 1081001288.
^ Benioff, Paul (1980). “The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines”. Journal of Statistical Physics. 22 (5): 563-591. Bibcode:1980JSP….22..563B. doi:10.1007/bf01011339.
^ Scott Aaronson (2005). “NP-complete Problems and Physical Reality”. ACM SIGACT News. 2005. arXiv:quant-ph/0502072. Bibcode:2005quant.ph..2072A. See section 7 “Quantum Gravity”: “[…] to anyone who wants a test or benchmark for a favorite quantum gravity theory, [author’s footnote: That is, one without all the bother of making numerical predictions and comparing them to observation] let me humbly propose the following: can you define Quantum Gravity Polynomial-Time? […] until we can say what it means for a ‘user’ to specify an ‘input’ and ‘later’ receive an ‘output’—there is no such thing as computation, not even theoretically.” (emphasis in original)
La revolución de la computación cuántica: Índice de Contenido: La revolución de la computación cuántica Los fundamentos de la mecánica cuántica Superposición y qubits Entrelazamiento cuántico Algoritmos cuánticos Supremacía cuántica...
Computación cuántica: Introducción: La computación cuántica, dentro del campo de la informática, aprovecha los principios de la física cuántica para realizar cálculos que superan las capacidades de las computadoras...
Los educadores de física están revolucionando la enseñanza de la física cuántica en las escuelas al alejarse de los métodos históricos tradicionales hacia un enfoque en aplicaciones prácticas. En...
La Amenaza de la Computación Cuántica: La llegada de la computación cuántica representa una amenaza significativa para la seguridad de nuestros sistemas criptográficos actuales. Las computadoras cuánticas, gracias a su capacidad para...
Introducción: Los dispositivos electrónicos, desde simples aparatos domésticos hasta sistemas computacionales avanzados, dependen de semiconductores como sus componentes fundamentales. Sin embargo, el papel de los...
¿Qué son los núcleos CUDA?: Un núcleo CUDA es una pequeña unidad de procesamiento dentro de muchas GPU NVIDIA diseñada para ejecutar tareas de computación en paralelo. Para simplificarlo, un núcleo CUDA es como un mini-CPU,...