Path: blob/main/translations/es/intro/why-quantum-computing.ipynb
4044 views
¿Por qué computación cuántica?
¿Qué es una computadora?
Dado que has logrado acceder a esta página web, ya deberías saber qué es una computadora. Hoy en día, las computadoras toman muchas formas: desde computadoras portátiles y teléfonos móviles hasta los sistemas que controlan los semáforos. ¡Parece que las computadoras pueden hacer cualquier cosa! Estos sistemas pueden ser muy complejos y especializados, pero todos tienen una cosa en común: una computadora lleva a cabo un conjunto de instrucciones sobre cierta información de entrada para darnos nueva información (de salida).
Las instrucciones que damos a las computadoras deben ser muy específicas e inequívocas. Llamamos a estos conjuntos de instrucciones algoritmos, y gran parte de la investigación en computadoras se centra en el comportamiento de diferentes algoritmos. En este curso, solo consideraremos las computadoras en su forma más simple; sin teclados, ratones o pantallas, solo información y algoritmos.
Clasificación de algoritmos de computadora
Para comprender el papel de las computadoras cuánticas entre las computadoras tradicionales modernas, primero debemos aprender cómo medimos el rendimiento de los diferentes algoritmos.
En ciencias de la computación, clasificamos los algoritmos según cómo crecen los recursos que utilizan con el tamaño de la entrada. A esto lo llamamos la complejidad del algoritmo. Por ejemplo, un algoritmo que decide si un número es par solo necesita mirar el último dígito de ese número. En este caso, la ‘entrada’ es un número y la salida es ‘par’ o ‘impar’. Llamamos a esto un algoritmo de tiempo constante, porque el tiempo que tarda el algoritmo en completarse no depende del tamaño del número de entrada. Es posible que a diferentes computadoras les tome diferentes cantidades de tiempo obtener este resultado, pero eso se debe a otros factores y no a la longitud de la entrada.
Veamos un ejemplo diferente. Esta vez, la entrada son dos números de igual longitud y el problema es sumarlos. En este caso, la salida será un nuevo número. Al sumar dos números de varios dígitos, un algoritmo común que probablemente aprendiste en la escuela comienza con el dígito más a la derecha de cada número y los suma. Luego se mueve un dígito a la izquierda (llevando un ‘1’ si el resultado fue mayor que 9) y repite el proceso. La computadora repite esto hasta que no hay más dígitos para agregar y el algoritmo finaliza.
¿Cómo de compleja es la suma?
El tiempo que tarda este algoritmo de suma en completarse...
...crece linealmente (proporcionalmente) con la longitud del número de entrada (tiempo lineal).
...no se ve afectado por la longitud del número de entrada (tiempo constante)
...crece con el cuadrado de la longitud del número de entrada (tiempo cuadrático)
Nuevamente, diferentes computadoras ejecutarán este algoritmo a diferentes velocidades; una laptop puede realizar sumas, millones de veces más rápido que un ser humano. Pero ya sea que pueda hacer un millón de operaciones por segundo o solo una, el ritmo de crecimiento será el mismo.
He aquí un último ejemplo que nos interesa especialmente. Digamos que tengo un número secreto (como un PIN), y el problema es adivinarlo. En este caso, el tamaño del problema es la longitud del número.
Digamos que la única forma en la que podemos verificar si nuestra respuesta es correcta es introduciéndola en un teclado. Dado que no tenemos información sobre cuál podría ser ese número, el mejor algoritmo para encontrar este número secreto utiliza un método de ‘fuerza bruta’, lo que significa que no hace nada inteligente y simplemente prueba todos los números posibles.
¿Cuánto tiempo llevaría esto? En teoría, podríamos tener suerte y adivinar la respuesta de una sola vez, pero esto es muy poco probable. En promedio, tendríamos que probar alrededor de la mitad de las entradas posibles, por lo que el tiempo de ejecución de nuestro algoritmo es proporcional al número de combinaciones posibles. La pregunta ahora es: ¿Cómo crece el número de combinaciones posibles con la longitud del número secreto?
Cada dígito que agregamos a nuestro número secreto multiplica el número de combinaciones posibles por 10. Por ejemplo, un número secreto con 1 dígito tiene 10 valores posibles (0, 1, 2, 3, 4, 5, 6, 7, 8 y 9), y un número secreto de 2 dígitos tiene 100 valores posibles. Suponiendo que el tiempo necesario para adivinar cada dígito es similar (independientemente de la longitud), podemos representar esto matemáticamente así:
ParseError: KaTeX parse error: Undefined control sequence: \cssId at position 1: \̲c̲s̲s̲I̲d̲{T}{T} \cssId{p…Notarás que el número de dígitos (d) es el exponente en esta ecuación y, como tal, decimos que este es un algoritmo de tiempo exponencial y que el tiempo de ejecución crece exponencialmente con la longitud de la entrada.
¿Por qué medimos algoritmos como este?
Diferentes computadoras tienen diferentes fortalezas; ciertas operaciones pueden ser más rápidas en una computadora que en otra. Al estudiar el crecimiento frente al tamaño de entrada, podemos ignorar los detalles específicos del dispositivo y, de hecho, medir el algoritmo, en lugar de la combinación específica de algoritmo y computadora. Es importante tener en cuenta que saber cómo escala un algoritmo con el tamaño de entrada también nos dice si el algoritmo crecerá de manera manejable o no.
Pensemos en el algoritmo de suma de tiempo lineal que vimos arriba. Si pudiéramos sumar dos números de 10 dígitos en un segundo, debido a la tasa de crecimiento lineal, deberíamos poder sumar dos números de 20 dígitos en dos segundos. Cada 10 dígitos adicionales deberían añadir aproximadamente un segundo más a nuestro tiempo de cálculo.
Por el contrario, imagina que puedes encontrar un PIN de 10 dígitos en 1 segundo utilizando el algoritmo de búsqueda de tiempo exponencial anterior. Esto significa que tu computadora es lo suficientemente rápida para intentar ~5,000,000,000 combinaciones por segundo. Esperaríamos que esta computadora que usa este algoritmo tarde aproximadamente 5,000,000,000 segundos (~150 años) para encontrar un PIN de 20 dígitos. Añadir otros 10 dígitos aumenta esto a alrededor de 150,000,000,000 años (~120 veces la edad del universo). Los algoritmos de tiempo exponencial con incluso una entrada de tamaño modesto (en este caso, ~30 dígitos) pueden volverse no solo difíciles, sino literalmente imposibles de llevar a cabo.
Si bien este problema de búsqueda de PIN es un ejemplo artificial que pretendemos que sea lo más simple posible, hay muchos problemas reales en informática para los que solo tenemos algoritmos ineficientes. A pesar de la impresionante velocidad de las computadoras actuales, estos problemas intratables pueden ser demasiado difíciles incluso para las supercomputadoras más potentes.
Pero si podemos encontrar algoritmos que crezcan de manera más eficiente, estos problemas intratables pueden volverse manejables de repente, incluso con computadoras relativamente lentas o poco fiables. Aquí es dónde la computación cuántica entra en juego.
¿Cómo puede ayudar la computación cuántica?
Hasta ahora, hemos pensado en los algoritmos de una manera muy abstracta, pero las computadoras que ejecutan estos algoritmos deben existir en el mundo real. Ya sean estas computadoras microchips de alta potencia o humanos con bolígrafos y papel, todas las computadoras se rigen en última instancia por las leyes de la física y las operaciones que pueden realizar limitan los algoritmos que podemos crear.
La física es un intento de desentrañar el conjunto de reglas que rigen en el universo. A principios del siglo XX, a través de delicados experimentos en laboratorios, los físicos vieron comportamientos extraños que la física no podía explicar en aquel momento. Esto significaba que las reglas no eran del todo precisas, por lo que desarrollaron de manera más completa la física ‘cuántica’, que describe muy bien este comportamiento.
Los físicos crearon la física cuántica para explicar un comportamiento que nunca antes habían visto, y los informáticos descubrieron que podían (en teoría) explotar este comportamiento recién descubierto para crear algoritmos más eficientes. Como resultado, hay ciertos problemas que creemos que son intratables para las computadoras convencionales, pero que son manejables para una computadora ‘cuántica’ que puede explotar este comportamiento. Uno de estos problemas es la factorización de enteros.
Supongamos que tenemos un número entero al que llamaremos ''. Un algoritmo de factorización encuentra los enteros y tales que . Esto a veces es fácil; puedes decir de un vistazo que , pero si es el producto de dos números primos grandes, este problema se vuelve muy difícil. Cuando hablamos de factorización de enteros, vamos a asumir el escenario más difícil (el peor de los casos). En la siguiente celda de código, estamos asignando un número de 250 dígitos a la variable x :
En 2020, los investigadores factorizaron este número utilizando una supercomputadora clásica y ~2700 años de núcleo de potencia de procesamiento. Este fue un gran esfuerzo y un récord en el momento de escribir este artículo. Podemos verificar sus resultados en la celda de código a continuación (¡afortunadamente, tenemos algoritmos eficientes para la multiplicación!):
El resultado que se muestra es el valor de la última línea de la celda. En este caso, podemos ver que p*q == x se evalúa como True . Aunque no está probado matemáticamente, estamos bastante seguros de que no existe un algoritmo eficiente para factorizar tales números en las computadoras tradicionales. De hecho, gran parte del cifrado de Internet se basa en la suposición de que este problema es intratable y que factorizar un número RSA de 617 dígitos es imposible. Por el contrario, conocemos algoritmos de factorización eficientes para computadoras cuánticas que, una vez que tengamos computadoras cuánticas lo suficientemente grandes, estimamos que podrían factorizar estos números en menos de un día.
¿Donde nos encontramos ahora?
Ahora sabemos que las computadoras cuánticas pueden llevar a cabo algoritmos más eficientes, pero las computadoras cuánticas que tenemos hoy en día son demasiado pequeñas e inestables para dar una ventaja sobre las computadoras tradicionales.
En un nivel muy simple, hay dos factores que limitan el tamaño de los problemas que pueden resolver nuestras computadoras cuánticas. El primero es la cantidad de datos que pueden almacenar y sobre los cuales trabajar, que solemos medir en qubits. Si no tenemos suficientes qubits, simplemente no podemos almacenar ni operar en problemas por encima de cierto tamaño. El segundo es la tasa de error de nuestra computadora cuántica; dado que solo vemos el comportamiento cuántico en experimentos de laboratorio delicados, crear computadoras cuánticas es un proceso delicado. Las computadoras cuánticas que tenemos ahora son ruidosas, lo que significa que a menudo se equivocan e introducen ‘ruido’ en nuestros resultados. ¡Demasiado ruido y nuestros resultados no tendrán sentido!
Por el momento, las computadoras cuánticas que tenemos son experimentales. Están limitadas por el número de qubits y las tasas de error, por lo que los problemas más grandes que pueden resolver actualmente aún son fácilmente manejables para las computadoras convencionales.
En algún momento en el futuro, esto cambiará. Llegaremos a la ‘ventaja cuántica’, en la que realmente tendrá sentido desde el punto de vista económico resolver un problema utilizando una computadora cuántica en lugar de una computadora convencional. ¿Cómo lo sabemos? ¡Porque medimos los algoritmos por su tasa de crecimiento! Sabemos que, mientras las computadoras cuánticas sigan desarrollándose de manera constante, eventualmente tomarán el relevo de las computadoras clásicas.
La estimación para factorizar un número RSA de 617 dígitos en menos de un día supuso ~20 millones de qubits ruidosos. En el momento de escribir este artículo, IBM tiene actualmente una computadora cuántica de 65 qubits y tiene como objetivo crear un sistema con más de 1000 qubits para 2023. Hay otros algoritmos que creemos que nos darán una ventaja cuántica mucho antes de este hito, pero parece que aún estamos muy lejos.
Deberíamos recordar de dónde vienen las computadoras convencionales. A continuación se muestra una imagen del primer transistor, creado en 1947. Los transistores son los componentes básicos de los procesadores de las computadoras modernas.
Crédito de la imagen: Empleado federal Enlace, Dominio Público .
70 años después, los chips de nuestras computadoras modernas pueden contener miles de millones de transistores.
En el resto de este curso, exploraremos los efectos cuánticos que nos permiten crear algoritmos más eficientes. Al final de este curso, podrás utilizar el paquete de software, Qiskit, para programar una computadora cuántica y ejecutar uno de estos algoritmos.
Test rápido
Las computadoras cuánticas finalmente...
...harán cálculos que son demasiado difíciles para las computadoras convencionales.
...reemplazarán a las computadoras convencionales.
...aumentarán la velocidad de las computadoras convencionales.