case-for-quantum.ipynb

Kernel: Python 3

El Caso de las Computadoras Cuánticas

1. La Complejidad de Sumar

El caso de las computadoras cuánticas, en pocas palabras, es que pueden resolver ciertos problemas que ninguna computadora clásica pudo. Para entender por qué sucede esto, primero debemos considerar cuánto esfuerzo computacional se requiere para resolver ciertos problemas.

Para comenzar, podemos revisar el algoritmo considerado en la primera sección: sumar dos números.

   9213
+  1854
=  ????

La suma de dos números de $n$ dígitos se puede hacer con un conjunto de operaciones simples, cada una de las cuales consiste en simplemente sumar dos números de un solo dígito. Para analizar la complejidad del procedimiento, podemos pensar en cuántas de estas sumas básicas se requieren y cómo este número depende de $n$. Nos referiremos a este número como $c(n)$.

En el caso más sencillo, donde no necesitamos acarrear un 1 en ningún momento, solo se requieren $n$ sumas básicas. En el peor de los casos, necesitaremos realizar $n$ operaciones de acarreo, cada una de las cuales requerirá una adición básica adicional. De estas consideraciones, podemos concluir que $n \leq c(n) \leq 2n$.

2. Notación O Grande

Podemos resumir este resultado diciendo que $c(n)$ crece linealmente con $n$. De manera más general, podemos decir que se puede encontrar una función lineal de $n$ que actúa como un límite superior para $c(n)$ cuando $n$ es grande. Dado que esta es una oración larga y verbosa, en realidad no querremos decir esto muy a menudo. En su lugar, podemos expresarlo de forma más compacta utilizando la 'notación O grande'.

Recordatorios

Notación O grande Para algunas funciones de ejemplo $f(x)$ y $g(x)$ y el parámetro $x$, la declaración $f(x) = O(g(x))$ significa que existen algunos números finitos $M>0$ y $x_0$ tales que $$f(x) \leq M g(x) \forall x>x_0.$$

La notación O grande es útil ya que nos permite comparar cómo los recursos/tiempo de ejecución requeridos por un algoritmo escalan con el tamaño de entrada, independientemente de la plataforma específica y la implementación del algoritmo bajo consideración. A continuación se muestran ejemplos de factores de escala comunes de un tiempo de ejecución $N$ en función del tamaño de entrada $n$; está claro que para un tamaño de problema lo suficientemente grande, el tiempo de ejecución de un algoritmo $O(a^n)$ superará al de un algoritmo $O(n^b)$, donde $a$ y $b$ son constantes.

Comparaciones de diferentes complejidades temporales. n es el número de bits de entrada y N es el número de operaciones requeridas. [5]

Con esta notación, la propiedad descrita anteriormente se expresa simplemente como $c(n) = O(n)$. Esto captura el comportamiento lineal sin necesidad de insistir en los detalles. Por lo tanto, independientemente de si $c(n) = n$, $c(n) = 2n$ u otra cosa, simplemente podemos decir que $c(n) = O(n)$.

Hay una suposición oculta en lo que hemos considerado hasta ahora. Al hablar del número de dígitos, hemos supuesto el uso de un sistema numérico específico. Sin embargo, la cantidad de dígitos dependerá del sistema numérico que estemos usando, ya sea decimal, binario u otro. Por ejemplo, el número de bits $n_2$ necesarios para expresar un número está relacionado con el número de dígitos decimales $n_{10}$ necesarios para expresar el mismo número por

$n_2 = \left\lceil \frac{\log 10}{ \log 2} , n_{10} \right\rceil \approx 3.3 , n_{10}.$

Dado que esta también es una relación lineal, no cambia la forma en que expresamos la complejidad usando la notación O grande. Igualmente podemos decir que $c(n_2) = O(n_2)$, $c(n_{10}) = O(n_{10})$, o incluso $c(n_{10}) = O(n_{ 2})$. Es por esta razón que a menudo podemos hablar simplemente del número de dígitos, $n$, sin necesidad de especificar qué sistema numérico es el que se utiliza.

3. Teoría de la Complejidad

La teoría de la complejidad es el estudio del esfuerzo computacional requerido para ejecutar cualquier algoritmo. Al considerar el mejor algoritmo posible para resolver un problema dado, también podemos estudiar el esfuerzo computacional inherente a la resolución de este problema. Para la suma ya conocemos el algoritmo óptimo, por lo que sabemos que es un problema de complejidad $O(n)$.

La multiplicación no es tan simple. Los algoritmos que aprendiste en la escuela para multiplicar dos números de $n$ dígitos habrán requerido operaciones básicas de $O(n^2)$, como sumas y multiplicaciones de un solo dígito. Aunque se han encontrado algoritmos con menor complejidad asintótica, se considera imposible realizar multiplicaciones con una complejidad $O(n)$.

Aun así, la multiplicación está lejos de ser el problema más complejo. Un ejemplo de un problema con una complejidad mucho mayor es la factorización: tomar un número de $n$ dígitos y encontrar sus factores primos. El algoritmo más conocido en este caso tiene una complejidad peor que $O\left(e^{n^{1/3}}\right)$. El exponencial aquí significa que la complejidad crece muy rápidamente y hace que la factorización sea un problema muy difícil de resolver.

Para demostrar este punto utilizando el tiempo de cálculo real, podemos tomar un ejemplo reciente.$^{1}$ Considera el siguiente número de 829 dígitos.

rsa_250 = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

Si intentas usar tu computadora para sumar o multiplicar números de este tamaño, encontrarás que puedes resolver tales problemas muy rápidamente. Si multiplicas la cantidad de procesadores que tiene tu computadora con la cantidad de segundos que tarda en obtener el número de segundos de núcleo, seguramente encontrarás que se requiere mucho menos de 1 segundo de núcleo.

Sin embargo, realizar la factorización de este número requiere una supercomputadora y alrededor de 2700 años de núcleo, lo que finalmente produce los siguientes dos factores.

p = 64135289477071580278790190170577389084825014742943447208116859632024532344630238623598752668347708737661925585694639798853367
q = 33372027594978156556226010605355114227940760344767554666784520987023841729210037080257448673296881877565718986258036932062711
p*q

2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

Para la factorización de números más grandes, llegamos fácilmente a un punto en el que una supercomputadora del tamaño de un planeta necesitaría funcionar por la edad del universo. Claramente, cualquier problema de este tipo es prácticamente imposible.

Hasta ahora hemos considerado solo operaciones matemáticas en números de $n$ dígitos, con la complejidad expresada como el número de operaciones simples de un solo dígito requeridas. Sin embargo, la teoría de la complejidad se puede usar para analizar cualquier método computacional para cualquier tipo de problema, ya sea buscando bases de datos, renderizando gráficos, simulando dinámicas o atravesando una mazmorra en Legend of Zelda. En cada caso, podemos encontrar un parámetro o conjunto de parámetros que sirvan como nuestro tamaño de entrada y expresar la complejidad en términos de este tamaño de entrada utilizando la notación O grande. Para buscar en una base de datos de $N$ entradas, por ejemplo, la complejidad es $O(N)$.

Formalmente, definir la complejidad de un algoritmo depende del modelo teórico exacto para el cálculo que estemos usando. Cada modelo tiene un conjunto de operaciones básicas, conocidas como operaciones primitivas, con las que se puede expresar cualquier algoritmo. Para los circuitos Booleanos, como consideramos en la primera sección, las operaciones primitivas son las compuertas lógicas. Para las máquinas de Turing, una forma hipotética de computadora propuesta por Alan Turing, imaginamos un dispositivo que avanza y manipula la información almacenada en una cinta. El modelo RAM tiene un conjunto más complejo de operaciones primitivas y actúa como una forma idealizada de las computadoras que usamos todos los días. Todos estos son modelos de computación digital, basados ​​en manipulaciones discretizadas de valores discretos. Por diferentes que parezcan entre sí, resulta que es muy fácil para cada uno de ellos simular a los demás. Esto significa que en la mayoría de los casos la complejidad computacional no depende significativamente de cuál de estos modelos se utilice. En lugar de establecer la complejidad específicamente para el modelo RAM o las máquinas de Turing, podemos simplemente hablar de la complejidad de las computadoras digitales.

4. Más allá de la Computación Digital

Aunque las computadoras digitales son dominantes ahora, no son la única forma de computación. Las computadoras analógicas también fueron ampliamente estudiadas y utilizadas en el pasado. A diferencia de los valores discretos de las computadoras digitales, estas se basan en manipulaciones precisas de parámetros que varían continuamente. A veces se ha afirmado que tales dispositivos podrían resolver rápidamente problemas que son intratables para las computadoras digitales. Sin embargo, tales afirmaciones nunca se han confirmado. Un obstáculo importante para las computadoras analógicas es la incapacidad de construir dispositivos con una precisión arbitrariamente alta. En las computadoras digitales, la discretización significa que los errores deben ser relativamente grandes para que se noten, y luego se pueden implementar métodos para detectar y corregir tales errores. En las computadoras analógicas, sin embargo, los errores pueden ser arbitrariamente pequeños e imposibles de detectar, pero aún así sus efectos pueden acumularse para arruinar un cálculo.

Si uno tuviera que proponer un modelo ideal de computación, podría tratar de combinar la robustez de una computadora digital con las manipulaciones sutiles de una computadora analógica. Para lograr esto podemos mirar a la mecánica cuántica. Ya hemos visto que los qubits son un sistema con salidas discretas 0 y 1 y, sin embargo, pueden existir en estados que solo pueden describirse mediante parámetros continuos. Este es un caso particular de la bien conocida noción de dualidad 'onda-partícula' que es típica de los sistemas cuánticos. No pueden describirse completamente como discretos o continuos, sino como una combinación de los dos. Como dijo Einstein,$^{2}$

'Parece como si debiéramos usar a veces una teoría y a veces la otra, mientras que a veces podemos usar cualquiera de las dos. Nos enfrentamos a un nuevo tipo de dificultad. Tenemos dos imágenes contradictorias de la realidad; por separado ninguna de ellas explica completamente los fenómenos... pero juntas lo hacen.'

Una computadora cuántica, cuyas operaciones primitivas son compuertas aplicadas a qubits, no es, por lo tanto, ni analógica ni digital, sino algo único. En capítulos posteriores exploraremos las consecuencias de esta naturaleza única. Veremos que las computadoras cuánticas pueden resolver problemas con una complejidad radicalmente diferente a las computadoras digitales. De hecho, la computación cuántica es la única tecnología conocida que puede ser exponencialmente más rápida que las computadoras clásicas para ciertas tareas, reduciendo potencialmente los tiempos de cálculo de años a minutos. También exploraremos cómo la corrección de errores cuánticos puede eliminar los efectos de cualquier imperfección.

5. Cuándo Usar una Computadora Cuántica

Con qubits y compuertas cuánticas, podemos diseñar algoritmos novedosos que son fundamentalmente diferentes de los clásicos digitales y analógicos. De esta manera, esperamos encontrar soluciones a problemas que son intratables para las computadoras clásicas.

Una forma en que esto se pueda hacer es cuando tenemos alguna función para la que queremos determinar una propiedad global. Por ejemplo, si queremos encontrar el valor de algún parámetro $x$ para el cual alguna función $f(x)$ es un mínimo, o el periodo de la función si $f(x)$ es periódica. Un algoritmo en una computadora digital podría usar un proceso en el que se calcula $f(x)$ para una variedad de entradas diferentes a fin de obtener suficiente información sobre la propiedad global. Sin embargo, con una computadora cuántica, el hecho de que podamos crear estados en superposición significa que la función se puede aplicar a muchas entradas posibles simultáneamente. Esto no significa que podamos acceder a todas las salidas posibles ya que la medición de tal estado simplemente nos da un único resultado. Sin embargo, podemos intentar inducir un efecto de interferencia cuántica, que revelará la propiedad global que necesitamos.

Esta descripción general ilustra el funcionamiento de muchos de los algoritmos cuánticos que ya se han descubierto. Un ejemplo destacado es el algoritmo de Grover, que reduce la complejidad de buscar a través de $N$ elementos de $O(N)$ a $O(N^{1/2})$. Esta aceleración cuadrática podría ser útil en muchas aplicaciones con tareas que se pueden expresar como una búsqueda no estructurada, como problemas de optimización y machine learning (aprendizaje automático).

# Este código es para crear la figura interactiva
from bokeh.layouts import column
from bokeh.models import ColumnDataSource, CustomJS, Slider
from bokeh.plotting import figure, show
from bokeh.embed import file_html
from bokeh.resources import CDN
import numpy as np
import IPython

x = np.arange(0,500)
y_linear = x
y_sqrt = 7.5*np.sqrt(x)

linear_source = ColumnDataSource(data=dict(x=x, y=y_linear))
sqrt_source = ColumnDataSource(data=dict(x=x, y=y_sqrt))

plot = figure(
              plot_height=400, 
              plot_width=800,
              sizing_mode="scale_width",
              tools="reset,save",
              x_range=[0, 500], y_range=[0, 500], 
              x_axis_label="Size of Problem",
              y_axis_label="Time Taken to Find Solution")
plot.line('x', 'y', source=linear_source, line_width=3, line_alpha=0.6, color="blue", legend_label="Classical Search O(N)")
plot.line('x', 'y', source=sqrt_source, line_width=3, line_alpha=0.6, color="red", legend_label="Quantum Search O(√N)")
plot.legend.location = "top_left"

callback = CustomJS(args=dict(source=sqrt_source), code="""
        var data = source.data;
        var f = (10-cb_obj.value)*2 + 3
        var x = data['x']
        var y = data['y']
        for (var i = 0; i < x.length; i++) {
            y[i] = f*Math.sqrt(x[i])
        }
        source.change.emit();
    """)

speed_slider = Slider(title="Relative Speed of Quantum Computer", value=7.5, start=1.0, end=10.0, step=0.1, show_value=False)
speed_slider.js_on_change('value', callback)

layout = column(plot, speed_slider)

caption = """
Es difícil comparar el rendimiento de los algoritmos en diferentes plataformas. Lo que podemos decir (a través de la notación O grande) es que,
a pesar de la diferencia de velocidades entre nuestras computadoras clásicas y cuánticas, para un problema lo suficientemente grande, el algoritmo de búsqueda cuántico
siempre superará al algoritmo de búsqueda clásico."""

html_repr = file_html(layout, CDN)
html_fig = "<figure>{0}<figcaption>{1}</figcaption></figure>".format(html_repr, caption)
IPython.display.HTML(html_fig)

Se obtiene una aceleración aún más impresionante con el algoritmo de Shor, que analiza funciones periódicas en el corazón del problema de factorización. Esto permite una solución cuántica para factorizar números de $n$ dígitos con complejidad $O(n^3)$. Esta es una aceleración superpolinomial en comparación con la complejidad de las computadoras digitales, que es peor que $O\left(e^{n^{1/3}}\right)$.

Otro enfoque hacia los algoritmos cuánticos es usar computadoras cuánticas para resolver problemas cuánticos. Como veremos en el próximo capítulo, expresar un estado cuántico requiere una cantidad de información que escala exponencialmente con el número de qubits. El solo hecho de escribir el estado de $n$ qubits se convierte en una tarea insuperable para las computadoras digitales a medida que aumenta $n$. Sin embargo, para una computadora cuántica solo necesitamos $n$ qubits para hacer el mismo trabajo. Esta capacidad natural para expresar y manipular estados cuánticos nos permite estudiar y comprender mejor los sistemas cuánticos de interés, como las moléculas y las partículas fundamentales.

Por lo tanto, la aplicación y adaptación de algoritmos cuánticos en diferentes industrias tiene la promesa de permitir casos de uso disruptivos en los negocios y la ciencia. Estos incluyen avances en el descubrimiento de fármacos, el machine learning (aprendizaje automático), el descubrimiento de materiales, la fijación de precios de opciones, el plegamiento de proteínas y la cadena de suministro.$^{3}$ Particularmente prometedores son aquellos problemas para los que los algoritmos clásicos enfrentan límites de escala inherentes y que no requieren que se cargue un gran conjunto de datos clásicos. Para obtener una ventaja cuántica, las respuestas de un problema dado deben depender en gran medida de muchos grados de libertad entrelazados exponencialmente con una estructura tal que la mecánica cuántica evolucione hacia una solución sin tener que pasar por todos los caminos. Ten en cuenta, sin embargo, que la relación precisa entre los problemas que son 'fáciles' para las computadoras cuánticas (que se pueden resolver en tiempo polinomial) y otras clases teóricas de complejidad sigue siendo una pregunta abierta.$^{4}$

Esto es solo una muestra de cómo los algoritmos cuánticos pueden realizar cálculos de una manera única. Se pueden encontrar más detalles sobre estos enfoques en capítulos posteriores. Pero primero debemos mirar más allá de un solo qubit e invertir algo de tiempo en comprender el conjunto completo de compuertas cuánticas que necesitaremos. Este es el enfoque del próximo capítulo.

6. Referencias

1. https://lists.gforge.inria.fr/pipermail/cado-nfs-discuss/2020-February/001166.html

2. Albert Einstein, Leopold Infeld (1938). The Evolution of Physics: The Growth of Ideas from Early Concepts to Relativity and Quanta. Cambridge University Press.

3. https://www.ibm.com/thought-leadership/institute-business-value/report/quantumstrategy

4. https://www.cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf

5. Image: Cmglee / CC BY-SA (https://creativecommons.org/licenses/by-sa/4.0)

import qiskit.tools.jupyter
%qiskit_version_table