Medir el costo computacional

A continuación, analizaremos un marco matemático para medir el costo computacional, enfocado específicamente en las necesidades de este curso. El análisis de algoritmos y la complejidad computacional son disciplinas completas en sí mismas, y tienen mucho más que decir sobre estas nociones.

Como punto de partida, considera la siguiente figura de la lección anterior, que representa una abstracción de muy alto nivel de una computación.

La computación en sí podría modelarse o describirse de diversas maneras, como un programa escrito en Python, una máquina de Turing, un circuito booleano o un circuito cuántico. Nos centraremos en los circuitos (tanto booleanos como cuánticos).

Codificaciones y longitud de entrada

Empecemos con la entrada y la salida de un problema computacional, que supondremos son cadenas binarias. Podrían usarse otros símbolos, pero para simplificar esta discusión nos limitaremos a entradas y salidas de cadenas binarias. Mediante cadenas binarias podemos codificar una variedad de objetos interesantes que los problemas que queremos resolver podrían involucrar, como números, vectores, matrices y grafos, así como listas de estos y otros objetos.

Por ejemplo, para codificar enteros no negativos podemos usar la notación binaria. La siguiente tabla muestra la codificación binaria de los primeros nueve enteros no negativos, junto con la longitud (es decir, el número total de bits) de cada codificación.

Número	Codificación binaria	Longitud
0	0	1
1	1	1
2	10	2
3	11	2
4	100	3
5	101	3
6	110	3
7	111	3
8	1000	4

Podemos extender fácilmente esta codificación para manejar enteros tanto positivos como negativos añadiendo un bit de signo a las representaciones si así lo deseamos. A veces también es conveniente permitir que las representaciones binarias de enteros no negativos tengan ceros a la izquierda, los cuales no cambian el valor codificado pero permiten que las representaciones llenen una cadena o palabra de tamaño fijo.

Usar la notación binaria para representar enteros no negativos es tanto habitual como eficiente, pero si quisiéramos podríamos elegir una forma diferente de representar enteros no negativos mediante cadenas binarias, como las que se sugieren en la siguiente tabla. Los detalles de estas alternativas no son importantes para esta discusión — el punto es únicamente aclarar que tenemos opciones en cuanto a las codificaciones que utilizamos.

Número	Codificación unaria	Codificación lexicográfica
0	$\varepsilon$	$\varepsilon$
1	0	0
2	00	1
3	000	00
4	0000	01
5	00000	10
6	000000	11
7	0000000	000
8	00000000	001

(En esta tabla, el símbolo $\varepsilon$ representa la cadena vacía, que no tiene ningún símbolo y tiene longitud cero. Naturalmente, para evitar una fuente obvia de confusión, usamos un símbolo especial como $\varepsilon$ para representar la cadena vacía en lugar de escribir literalmente nada.)

Otros tipos de entradas, como vectores y matrices, u objetos más complejos como descripciones de moléculas, también pueden codificarse como cadenas binarias. Al igual que con los enteros no negativos, se pueden seleccionar o inventar diversos esquemas de codificación. Para cualquier esquema que elijamos para codificar las entradas de un problema dado, interpretamos la longitud de una cadena de entrada como la representación del tamaño de la instancia del problema que se está resolviendo.

Por ejemplo, el número de bits necesarios para expresar un entero no negativo $N$ en notación binaria, que a veces se denota $\operatorname{lg}(N),$ se calcula con la siguiente fórmula.

$$\operatorname{lg}(N) = \begin{cases} 1 & N = 0\\ 1 + \lfloor \log_2 (N) \rfloor & N \geq 1 \end{cases}$$

Suponiendo que usamos la notación binaria para codificar la entrada del problema de factorización entera, la longitud de la entrada para el número $N$ es $\operatorname{lg}(N).$ Nota, en particular, que la longitud (o tamaño) de la entrada $N$ no es $N$ en sí mismo; cuando $N$ es grande no necesitamos ni de lejos esa cantidad de bits para expresar $N$ en notación binaria.

Desde un punto de vista estrictamente formal, siempre que consideramos un problema o tarea computacional, debe entenderse que se ha seleccionado un esquema específico para codificar los objetos que se proporcionan como entrada o se producen como salida. Esto permite que las computaciones que resuelven problemas interesantes se vean abstractamente como transformaciones de entradas de cadenas binarias a salidas de cadenas binarias.

Los detalles de cómo se codifican los objetos como cadenas binarias deben ser inevitablemente importantes para estas computaciones en algún nivel. Sin embargo, generalmente no nos preocupamos demasiado por estos detalles al analizar el costo computacional, para evitar entrar en detalles de importancia secundaria. El razonamiento básico es que esperamos que el costo computacional de convertir entre esquemas de codificación "razonables" sea insignificante en comparación con el costo de resolver el problema real. En aquellas situaciones en que esto no sea el caso, los detalles pueden (y deben) aclararse.

Por ejemplo, una computación muy simple convierte entre la representación binaria de un entero no negativo y su codificación lexicográfica (que no hemos explicado en detalle, pero puede inferirse de la tabla anterior). Por esta razón, el costo computacional de la factorización entera no diferiría significativamente si decidiéramos cambiar de una de estas codificaciones a la otra para la entrada $N.$ Por otro lado, codificar enteros no negativos en notación unaria implica un crecimiento exponencial en el número total de símbolos requeridos, y no lo consideraríamos un esquema de codificación "razonable" por esta razón.

Operaciones elementales

Ahora consideremos la computación en sí, que está representada por el rectángulo azul en la figura anterior. La forma en que mediremos el costo computacional es contando el número de operaciones elementales que requiere cada computación. Intuitivamente, una operación elemental es aquella que involucra un número pequeño y fijo de bits o qubits, que puede realizarse de forma rápida y sencilla — como calcular el AND de dos bits. En contraste, ejecutar la función factorint no puede considerarse razonablemente una operación elemental.

Formalmente, existen distintas opciones sobre qué constituye una operación elemental dependiendo del modelo computacional utilizado. Nos centraremos en los modelos de circuitos, específicamente en circuitos cuánticos y booleanos.

Conjuntos universales de compuertas

En los modelos de computación basados en circuitos, es habitual considerar cada compuerta como una operación elemental. Esto plantea la pregunta de qué compuertas exactamente permitimos en nuestros circuitos. Centrándonos por el momento en los circuitos cuánticos, hemos visto varias compuertas hasta ahora en esta serie, incluyendo las compuertas $X,$ $Y,$ $Z,$ $H,$ $S$ y $T,$ compuertas swap, versiones controladas de compuertas (incluyendo NOT controlado, Toffoli y compuertas Fredkin), así como compuertas que representan mediciones en la base estándar. En el contexto del juego CHSH también vimos algunas compuertas de rotación adicionales.

También discutimos las compuertas de consulta en el contexto del modelo de consultas, y también vimos que cualquier operación unitaria $U,$ actuando sobre cualquier número de qubits, puede considerarse una compuerta si así lo decidimos — pero descartaremos ambas opciones para esta discusión. No trabajaremos en el modelo de consultas (aunque la implementación de compuertas de consulta mediante operaciones elementales se analiza más adelante en la lección), y considerar compuertas unitarias arbitrarias, potencialmente actuando sobre millones de qubits, como operaciones elementales no conduce a nociones significativas o realistas de costo computacional.

Limitándonos a compuertas cuánticas que operan sobre un número pequeño de qubits, un enfoque para decidir cuáles se consideran elementales es establecer un criterio preciso — pero este no es el enfoque estándar ni el que adoptaremos. En cambio, simplemente hacemos una elección.

Aquí hay una elección estándar, que adoptaremos como el conjunto de compuertas predeterminado para circuitos cuánticos:

• Compuertas unitarias de un solo qubit de esta lista: $X,$ $Y,$ $Z,$ $H,$ $S,$ $S^{\dagger},$ $T$ y $T^{\dagger}$
• Compuertas NOT controlado
• Mediciones de un solo qubit en la base estándar

Una alternativa común es considerar las compuertas Toffoli, Hadamard y $S$ como elementales, además de las mediciones en la base estándar. A veces todas las compuertas de un solo qubit se consideran elementales, aunque esto conduce a un modelo irrealistamente poderoso cuando no se tiene en cuenta correctamente la precisión con la que se realizan las compuertas.

Las compuertas unitarias de nuestra colección predeterminada forman lo que se llama un conjunto de compuertas universal. Esto significa que podemos aproximar cualquier operación unitaria sobre cualquier número de qubits con cualquier grado de precisión que deseemos, usando circuitos compuestos únicamente por estas compuertas. Para ser claros, la definición de universalidad no impone ningún requisito sobre el costo de tales aproximaciones, es decir, el número de compuertas de nuestro conjunto que necesitamos. De hecho, un argumento bastante simple basado en la noción matemática de medida revela que la mayoría de las operaciones unitarias deben tener un costo extremadamente alto. Demostrar la universalidad de conjuntos de compuertas cuánticas no es algo sencillo y no se cubrirá en este curso.

Para los circuitos booleanos, tomaremos las compuertas AND, OR, NOT y FANOUT como las que representan operaciones elementales. En realidad no necesitamos tanto compuertas AND como compuertas OR — podemos usar las leyes de De Morgan para convertir de una a la otra colocando compuertas NOT en los tres cables de entrada/salida — pero aun así es tanto habitual como conveniente permitir ambas. Las compuertas AND, OR, NOT y FANOUT forman un conjunto universal para computaciones deterministas, lo que significa que cualquier función desde cualquier número fijo de bits de entrada a cualquier número fijo de bits de salida puede implementarse con estas compuertas.

El principio de medición diferida

Las compuertas de medición en la base estándar pueden aparecer dentro de los circuitos cuánticos, pero a veces es conveniente retrasarlas hasta el final. Esto nos permite ver las computaciones cuánticas como consistentes en una parte unitaria (que representa la computación en sí), seguida de una fase simple de lectura donde los qubits se miden y los resultados se emiten. Esto siempre puede hacerse, siempre que estemos dispuestos a añadir un qubit adicional por cada medición en la base estándar. En la siguiente figura, el circuito de la derecha ilustra cómo puede hacerse esto para la compuerta de la izquierda.

Específicamente, el bit clásico en el circuito de la izquierda se reemplaza por un qubit en el de la derecha (inicializado al estado $\vert 0\rangle$), y la medición en la base estándar se reemplaza por una compuerta NOT controlado, seguida de una medición en la base estándar sobre el qubit inferior. El punto es que la medición en la base estándar en el circuito de la derecha puede desplazarse hasta el final del circuito. Si el bit clásico en el circuito de la izquierda se usa posteriormente como bit de control, podemos usar el qubit inferior en el circuito de la derecha como control en su lugar, y el efecto global será el mismo. (Estamos suponiendo que el bit clásico en el circuito de la izquierda no se sobreescribe después de que se realice la medición mediante otra medición — pero si eso ocurriera siempre podríamos usar un nuevo bit clásico en lugar de sobreescribir uno que se usó para una medición anterior.)

Tamaño y profundidad de circuito

Tamaño de circuito

El número total de compuertas en un circuito se denomina tamaño de ese circuito. Por lo tanto, suponiendo que las compuertas de nuestros circuitos representen operaciones elementales, el tamaño de un circuito representa el número de operaciones elementales que requiere — o, en otras palabras, su costo computacional. Escribimos $\operatorname{size}(C)$ para referirnos al tamaño de un circuito dado $C.$

Por ejemplo, considera el siguiente circuito booleano para calcular el XOR de dos bits.

El tamaño de este circuito es 7 porque hay 7 compuertas en total. (Las operaciones Fanout no siempre se cuentan como compuertas, pero a los efectos de esta lección las contaremos como compuertas.)

Tiempo, costo y profundidad de circuito

El tiempo es un recurso de importancia crítica, o una restricción limitante, para las computaciones. Los ejemplos anteriores, como la tarea de factorizar RSA1024, refuerzan este punto de vista. La función factorint no falla en factorizar RSA1024 como tal, simplemente no tenemos suficiente tiempo para dejarla terminar.

La noción de costo computacional, como el número de operaciones elementales necesarias para realizar una computación, está pensada como un proxy abstracto del tiempo requerido para implementar una computación. Cada operación elemental requiere cierta cantidad de tiempo para realizarse, y cuantas más operaciones necesite una computación, más tiempo tardará, al menos en general. En aras de la simplicidad, continuaremos estableciendo esta asociación entre el costo computacional y el tiempo requerido para ejecutar los algoritmos.

Pero nota que el tamaño de un circuito no necesariamente corresponde directamente a cuánto tiempo tarda en ejecutarse. En nuestro circuito booleano para calcular el XOR de dos bits, por ejemplo, las dos compuertas FANOUT podrían realizarse simultáneamente, al igual que las dos compuertas NOT, así como las dos compuertas AND. Una forma diferente de medir la eficiencia de los circuitos, que toma en cuenta esta posibilidad de paralelización, es mediante su profundidad. Esta es el número mínimo de capas de compuertas necesarias dentro del circuito, donde las compuertas dentro de cada capa operan en cables diferentes. De manera equivalente, la profundidad de un circuito es el número máximo de compuertas encontradas en cualquier camino desde un cable de entrada hasta un cable de salida. Para el circuito anterior, por ejemplo, la profundidad es 4.

La profundidad de circuito es una forma de formalizar el tiempo de ejecución de computaciones paralelas. Es un tema avanzado, y existen construcciones de circuitos muy sofisticadas conocidas para minimizar la profundidad requerida para ciertas computaciones. También hay algunas fascinantes preguntas sin respuesta sobre la profundidad de circuito. (Por ejemplo, aún se desconoce mucho sobre la profundidad de circuito necesaria para calcular el MCD.) No tendremos mucho más que decir sobre la profundidad de circuito en esta serie, más allá de incluir algunos datos interesantes al respecto a medida que avancemos, pero debe reconocerse claramente que la paralelización es una fuente potencial de ventajas computacionales.

Asignación de costos a diferentes compuertas

Una última observación sobre el tamaño de circuito y el costo computacional es que es posible asignar diferentes costos a las compuertas, en lugar de considerar que cada compuerta contribuye igualmente al costo total.

Por ejemplo, como ya se menciónó, las compuertas FANOUT a menudo se consideran gratuitas para los circuitos booleanos — es decir, podríamos elegir que las compuertas FANOUT tengan costo cero. Como otro ejemplo, cuando trabajamos en el modelo de consultas y contamos el número de consultas que un circuito realiza a una función de entrada (en forma de caja negra), estamos efectivamente asignando costo unitario a las compuertas de consulta y costo cero a otras compuertas, como las compuertas Hadamard. Un último ejemplo es que a veces asignamos diferentes costos a las compuertas según la dificultad de implementarlas, lo cual puede variar según el hardware considerado.

Aunque todas estas opciones son razonables en diferentes contextos, en esta lección mantendremos las cosas simples y nos quedaremos con el tamaño de circuito como representación del costo computacional.

Costo como función de la longitud de entrada

Nos interesa principalmente cómo escala el costo computacional a medida que las entradas se hacen cada vez más grandes. Esto nos lleva a representar los costos de los algoritmos como funciones de la longitud de la entrada.

Familias de circuitos

Las entradas a un problema computacional dado pueden variar en longitud, pudiendo hacerse arbitrariamente grandes. Cada circuito, por otro lado, tiene un número fijo de compuertas y cables. Por esta razón, cuando pensamos en algoritmos en términos de circuitos, generalmente necesitamos familias infinitamente grandes de circuitos para representarlos. Por familia de circuitos entendemos una secuencia de circuitos que crecen en tamaño, permitiendo acomodar entradas cada vez más grandes.

Por ejemplo, imagina que tenemos un algoritmo clásico para la factorización entera, como el usado por factorint. Como todos los algoritmos clásicos, este algoritmo puede implementarse con circuitos booleanos — pero para hacerlo necesitaremos un circuito separado para cada posible longitud de entrada. Si examináramos los circuitos resultantes para diferentes longitudes de entrada, veríamos que sus tamaños crecen naturalmente a medida que crece la longitud de entrada — lo que refleja el hecho de que factorizar enteros de 4 bits es mucho más fácil y requiere muchas menos operaciones elementales que factorizar enteros de 1024 bits, por ejemplo.

Esto nos lleva a representar el costo computacional de un algoritmo mediante una función $t,$ definida de forma que $t(n)$ sea el número de compuertas en el circuito que implementa el algoritmo para entradas de $n$ bits. En términos más formales, un algoritmo en el modelo de circuitos booleanos se describe mediante una secuencia de circuitos $\{C_1, C_2, C_3,\ldots\},$ donde $C_n$ resuelve el problema en cuestión para entradas de $n$ bits (o, de forma más general, para entradas cuyo tamaño está parametrizado de alguna manera por $n$), y la función $t$ que representa el costo de este algoritmo se define como

$$t(n) = \operatorname{size}(C_n).$$

Para los circuitos cuánticos la situación es similar, donde se necesitan circuitos cada vez más grandes para acomodar cadenas de entrada cada vez más largas.

Ejemplo: suma de enteros

Para explicar esto con más detalle, dediquemos un momento a considerar el problema de la suma de enteros, que es mucho más simple que la factorización entera o incluso el cálculo del MCD.

Suma de enteros

Entrada: enteros $N$ y $M$
Salida: $N+M$

¿Cómo podríamos diseñar circuitos booleanos para resolver este problema?

Para mantener las cosas simples, limitemos nuestra atención al caso en que $N$ y $M$ son enteros no negativos representados por cadenas de $n$ bits usando notación binaria. Permitiremos cualquier número de ceros a la izquierda en estas codificaciones, de modo que

$$0\leq N,M\leq 2^n - 1.$$

La salida será una cadena binaria de $(n+1)$ bits que representa la suma, que es el número máximo de bits necesarios para expresar el resultado.

Comenzamos con un algoritmo — el algoritmo estándar para la suma de representaciones binarias — que es el análogo en base $2$ de la forma en que se enseña la suma en las escuelas primarias de todo el mundo. Este algoritmo puede implementarse con circuitos booleanos de la siguiente manera.

Comenzando por los bits menos significativos, podemos calcular su XOR para determinar el bit menos significativo de la suma. Luego calculamos el bit de acarreo, que es el AND de los dos bits menos significativos de $N$ y $M.$ A veces estas dos operaciones juntas se conocen como un semisumador.

Usando el circuito XOR que hemos visto varias veces junto con una compuerta AND y dos compuertas FANOUT, podemos construir un semisumador con 10 compuertas. Si por alguna razón cambiáramos de opinión y decidiéramos incluir compuertas XOR en nuestro conjunto de operaciones elementales, necesitaríamos 1 compuerta AND, 1 compuerta XOR y 2 compuertas FANOUT para construir un semisumador.

Avanzando hacia los bits más significativos, podemos usar un procedimiento similar, pero esta vez incluyendo el bit de acarreo de cada posición anterior en nuestro cálculo. Encadenando dos semisumadores y tomando el OR de los bits de acarreo que producen, podemos crear lo que se conoce como un sumador completo.

Esto requiere 21 compuertas en total: 2 compuertas AND, 2 compuertas XOR (cada una requiriendo 7 compuertas para implementarse), una compuerta OR y 4 compuertas FANOUT.

Finalmente, encadenando los sumadores completos, obtenemos un circuito booleano para la suma de enteros no negativos. Por ejemplo, el siguiente circuito calcula la suma de dos enteros de 4 bits.

En general, esto requiere

$$21 (n-1) + 10 = 21 n - 11$$

compuertas. Si hubiéramos decidido incluir compuertas XOR en nuestro conjunto de operaciones elementales, necesitaríamos $2n-1$ compuertas AND, $2n-1$ compuertas XOR, $n-1$ compuertas OR y $4n-2$ compuertas FANOUT, para un total de $9n-5$ compuertas. Si además decidimos no contar las compuertas FANOUT, son $5n-3$ compuertas.

Notación asintótica

Por un lado, es bueno saber con precisión cuántas compuertas se necesitan para realizar diversas computaciones, como en el ejemplo de la suma de enteros anterior. Estos detalles son importantes para construir los circuitos.

Por otro lado, si realizamos análisis a este nivel de detalle para todas las computaciones que nos interesan, incluyendo aquellas para tareas mucho más complicadas que la suma, rápidamente nos veremos sepultados en detalles. Para mantener las cosas manejables y suprimir intencionalmente detalles de importancia secundaria, típicamente usamos la notación Big-O al analizar algoritmos. A través de esta notación podemos expresar el orden en que crecen las funciones.

Formalmente, si tenemos dos funciones $g(n)$ y $h(n),$ escribimos $g(n) = O(h(n))$ si existe un número real positivo $c > 0$ y un entero positivo $n_0$ tales que

$$g(n) \leq c\cdot h(n)$$

para todo $n \geq n_0.$ Típicamente $h(n)$ se elige como una expresión lo más simple posible, de modo que la notación pueda usarse para revelar el comportamiento límite de una función en términos simples. Por ejemplo, $17 n^3 - 257 n^2 + 65537 = O(n^3).$

Esta notación puede extenderse a funciones con múltiples argumentos de forma bastante directa. Por ejemplo, si tenemos dos funciones $g(n,m)$ y $h(n,m)$ definidas en enteros positivos $n$ y $m,$ escribimos $g(n,m) = O(h(n,m))$ si existe un número real positivo $c > 0$ y un entero positivo $k_0$ tales que

$$g(n,m) \leq c\cdot h(n,m)$$

siempre que $n+m \geq k_0.$

Conectando esta notación con el ejemplo de la suma de enteros no negativos, concluimos que existe una familia de circuitos booleanos $\{C_1, C_2,\ldots,\},$ donde $C_n$ suma dos enteros no negativos de $n$ bits, tal que $\operatorname{size}(C_n) = O(n).$ Esto revela la característica más esencial de cómo escala el costo de la suma con el tamaño de la entrada: escala linealmente.

Nota también que no depende del detalle específico de si consideramos que las compuertas XOR tienen costo unitario o costo $7.$ En general, el uso de la notación Big-O nos permite hacer afirmaciones sobre los costos computacionales que no son sensibles a tales detalles de bajo nivel.

Más ejemplos

Aquí hay algunos ejemplos más de problemas de la teoría computacional de números, comenzando con la multiplicación.

Multiplicación de enteros

Entrada: enteros $N$ y $M$
Salida: $NM$

Crear circuitos booleanos para este problema es más difícil que crear circuitos para la suma — pero pensando en el algoritmo de multiplicación estándar, podemos diseñar circuitos de tamaño $O(n^2)$ para este problema (suponiendo que $N$ y $M$ se representan con $n$ bits en binario). De forma más general, si $N$ tiene $n$ bits y $M$ tiene $m$ bits, existen circuitos booleanos de tamaño $O(nm)$ para multiplicar $N$ y $M.$

De hecho, existen otras formas de multiplicar que escalan mejor. Por ejemplo, el algoritmo de multiplicación de Schönhage-Strassen puede usarse para crear circuitos booleanos para multiplicar dos enteros de $n$ bits con costo $O(n \operatorname{lg}(n) \operatorname{lg}(\operatorname{lg}(n))).$ La complejidad de este método genera mucha sobrecarga, sin embargo, lo que lo hace práctico solo para números que tienen decenas de miles de bits.

Otro problema básico es la división, que interpretamos como calcular tanto el cociente como el resto dado un divisor y un dividendo enteros.

División entera

Entrada: enteros $N$ y $M\neq0$
Salida: enteros $q$ y $r$ que satisfacen $0\leq r < |M|$ y $N = q M + r$

El costo de la división entera es similar al de la multiplicación: si $N$ tiene $n$ bits y $M$ tiene $m$ bits, existen circuitos booleanos de tamaño $O(nm)$ para resolver este problema. Y al igual que con la multiplicación, se conocen métodos asintóticamente superiores.

Ahora podemos comparar los algoritmos conocidos para calcular el MCD con los de la suma y la multiplicación. El algoritmo de Euclides para calcular el MCD de un número $N$ de $n$ bits y un número $M$ de $m$ bits requiere circuitos booleanos de tamaño $O(nm),$ similar a los algoritmos estándar para la multiplicación y la división. También similar a la multiplicación y la división, existen algoritmos de MCD asintóticamente más rápidos — incluyendo algunos que requieren $O(n(\operatorname{lg}(n))^2 \operatorname{lg}(\operatorname{lg}(n)))$ operaciones elementales para calcular el MCD de dos números de $n$ bits.

Una computación algo más costosa que surge en la teoría de números es la exponenciación modular.

Exponenciación modular entera

Entrada: enteros $N,$ $K$ y $M$ con $K\geq 0$ y $M\geq 1$
Salida: $N^K \hspace{1mm} (\text{mod }M)$

Por $N^K\hspace{1mm} (\text{mod }M)$ entendemos el resto cuando $N^K$ se divide por $M,$ es decir, el único entero $r$ que satisface $0\leq r < M$ y $N^K = q M + r$ para algún entero $q.$

Si $N$ tiene $n$ bits, $M$ tiene $m$ bits y $K$ tiene $k$ bits, este problema puede resolverse con circuitos booleanos de tamaño $O(k m^2 + nm).$ Esto no es nada obvio. La solución no es calcular primero $N^K$ y luego tomar el resto, lo cual requeriría usar exponencialmente muchos bits solo para almacenar el número $N^K.$ En cambio, podemos usar el algoritmo de potenciación rápida (conocido alternativamente como el método binario y cuadrado repetido), que aprovecha la representación binaria de $K$ para realizar toda la computación módulo $M.$ Suponiendo que $N,$ $M$ y $K$ son todos números de $n$ bits, obtenemos un algoritmo $O(n^3)$ — o un algoritmo de tiempo cúbico. Y una vez más, se conocen algoritmos que son más complejos pero asintóticamente más rápidos.

Costo de la factorización entera

En contraste con los algoritmos recién discutidos, los algoritmos clásicos conocidos para la factorización entera son mucho más costosos — como podríamos esperar a partir de la discusión anterior en la lección.

Un enfoque simple para la factorización es la división por prueba, donde un algoritmo recorre la lista $2,\ldots,\sqrt{N}$ para encontrar un factor primo del número de entrada $N.$ Esto requiere $O(2^{n/2})$ iteraciones en el peor caso cuando $N$ es un número de $n$ bits. Cada iteración requiere una división de prueba, lo que significa $O(n^2)$ operaciones elementales por iteración (usando un algoritmo estándar para la división entera). Terminamos con circuitos de tamaño $O(n^2 2^{n/2}),$ que es exponencial en el tamaño de la entrada $n.$

Existen algoritmos para la factorización entera con mejor escalado. El cribado del cuerpo numérico mencionado anteriormente, por ejemplo, que es un algoritmo que usa aleatoriedad, se cree en general (aunque no se ha demostrado rigurosamente) que requiere

$$2^{O(n^{1/3} (\operatorname{lg}(n))^{2/3})}$$

operaciones elementales para factorizar enteros de $n$ bits con alta probabilidad. Si bien es bastante significativo que $n$ esté elevado a la potencia $1/3$ en el exponente de esta expresión, el hecho de que aparezca en el exponente sigue siendo un problema que causa un mal escalado — y explica en parte por qué RSA1024 permanece fuera de su dominio de aplicabilidad.

Costo polinomial versus exponencial

Los algoritmos clásicos para la suma, multiplicación, división entera y el cálculo del máximo común divisor nos permiten resolver estos problemas en un abrir y cerrar de ojos para entradas con miles de bits. La suma tiene costo lineal mientras que los otros tres problemas tienen costo cuadrático (o costo subcuadrático usando algoritmos asintóticamente rápidos). La exponenciación modular es más costosa pero aún puede realizarse de manera bastante eficiente, con costo cúbico (o costo subcúbico usando algoritmos asintóticamente rápidos).

Todos estos son ejemplos de algoritmos con costo polinomial, lo que significa que tienen costo $O(n^c)$ para alguna elección de una constante fija $c > 0.$ Como una aproximación de primer orden, los algoritmos con costo polinomial se consideran abstractamente como algoritmos eficientes.

En contraste, los algoritmos clásicos conocidos para la factorización entera tienen costo exponencial. A veces el costo del cribado del cuerpo numérico se describe como subexponencial porque $n$ está elevado a la potencia $1/3$ en el exponente, pero en la teoría de la complejidad es más habitual reservar este término para algoritmos cuyo costo es

$$O\bigl(2^{n^{\varepsilon}}\bigr)$$

para todo $\varepsilon > 0.$ Los llamados problemas NP-completos son una clase de problemas que no se sabe que tengan (y ampliamente se conjetura que no tienen) algoritmos de costo polinomial. Una formulación basada en circuitos de la hipótesis del tiempo exponencial postula algo aún más fuerte, que es que ningún problema NP-completo puede tener un algoritmo de costo subexponencial.

La asociación de los algoritmos de costo polinomial con los algoritmos eficientes debe entenderse como una abstracción flexible. Por supuesto, si el costo de un algoritmo escala como $n^{1000}$ o $n^{1000000}$ para entradas de tamaño $n,$ sería exagerado describir ese algoritmo como eficiente. Sin embargo, incluso un algoritmo cuyo costo escala como $n^{1000000}$ debe estar haciendo algo inteligente para evitar tener costo exponencial, que es generalmente lo que esperamos de los algoritmos basados de alguna manera en la "fuerza bruta" o la "búsqueda exhaustiva." Incluso los refinamientos sofisticados del cribado del cuerpo numérico, por ejemplo, no logran evitar este escalado exponencial en costo. Los algoritmos de costo polinomial, por otro lado, logran aprovechar la estructura del problema de alguna manera que evita un escalado exponencial.

En la práctica, la identificación de un algoritmo de costo polinomial para un problema es solo un primer paso hacia la eficiencia real. Mediante refinamientos algorítmicos, los algoritmos de costo polinomial con exponentes grandes pueden a veces mejorarse drásticamente, reduciendo el costo a un escalado polinomial más "razonable". A veces las cosas se vuelven más fáciles cuando se sabe que son posibles — así que la identificación de un algoritmo de costo polinomial para un problema también puede tener el efecto de inspirar algoritmos nuevos y aún más eficientes.

A medida que consideramos las ventajas de la computación cuántica sobre la clásica, nuestros ojos generalmente se dirigen primero hacia las ventajas exponenciales, o al menos las ventajas superpolinomiales — idealmente encontrando algoritmos cuánticos de costo polinomial para problemas que no se sabe que tengan algoritmos clásicos de costo polinomial. Las ventajas teóricas de este orden tienen las mayores posibilidades de conducir a ventajas prácticas reales — pero identificar tales ventajas es un desafío extremadamente difícil. Actualmente solo se conocen unos pocos ejemplos, pero la búsqueda continúa.

Las ventajas polinomiales (pero no superpolinomiales) en el costo computacional de cuántico sobre clásico también son interesantes y no deben descartarse — pero dado el actual desfase entre la tecnología de computación cuántica y clásica, parecen bastante menos convincentes en el momento presente. Sin embargo, algún día podrían volverse significativas. El algoritmo de Grover, por ejemplo, que se cubre en una lección posterior, ofrece una ventaja cuadrática de cuántico sobre clásico para la llamada búsqueda no estructurada, y tiene potencial para aplicaciones amplias.

Un costo oculto de la computación con circuitos

Hay un último problema que vale la pena mencionar, aunque no nos ocuparemos de él más en este curso. Existe un costo computacional "oculto" cuando trabajamos con circuitos, y se refiere a las especificaciones de los propios circuitos. A medida que las entradas se hacen más y más largas, se requieren circuitos cada vez más grandes — pero necesitamos obtener las descripciones de estos circuitos de alguna manera si vamos a implementarlos.

Para todos los ejemplos que hemos discutido, o que discutiremos en lecciones posteriores, existe un algoritmo subyacente del que se derivan los circuitos. Generalmente los circuitos de una familia siguen algún patrón básico que es fácil de extrapolar a entradas cada vez más grandes, como encadenar sumadores completos para crear circuitos booleanos para la suma o realizar capas de compuertas Hadamard y otras compuertas en algún patrón fácil de describir.

Pero ¿qué ocurre si hay costos computacionales prohibitivos asociados con los patrones en los propios circuitos? Por ejemplo, la descripción de cada miembro $C_n$ de una familia de circuitos podría, en principio, estar determinada por alguna función de $n$ extremadamente difícil de calcular.

La respuesta es que esto es de hecho un problema — y por ello debemos imponer restricciones adicionales a las familias de circuitos más allá de tener costo polinomial para que representen verdaderamente algoritmos eficientes. La propiedad de uniformidad para circuitos hace esto estipulando que, en diversas formulaciones precisas, debe ser computacionalmente fácil obtener la descripción de cada circuito de una familia. Todas las familias de circuitos que analizaremos sí tienen esta propiedad — pero este es sin embargo un problema importante a tener en cuenta en general cuando se estudian los modelos de circuitos de computación desde un punto de vista formal.