El modelo de cómputo por consultas

Cuando modelamos cómputos en términos matemáticos, generalmente tenemos en mente el tipo de proceso representado en la siguiente figura, donde se proporciona información como entrada, se realiza un cómputo y se produce una salida.

Si bien es cierto que las computadoras que usamos hoy en día reciben entradas y producen salidas continuamente, interactuando esencialmente con nosotros y con otras computadoras de una manera que la figura no refleja, la intención no es representar el funcionamiento continuo de las computadoras. Más bien, se trata de crear una abstracción simple del cómputo, enfocándose en tareas computacionales aisladas. Por ejemplo, la entrada puede codificar un número, un vector, una matriz, un grafo, la descripción de una molécula o algo más complejo, mientras que la salida codifica la solución a la tarea computacional que tenemos en mente.

El punto clave es que la entrada se proporciona al cómputo, generalmente en forma de cadena binaria, sin que ninguna parte de ella esté oculta.

Descripción del modelo

En el modelo de consultas de cómputo, la entrada completa no se proporciona al cómputo como en el modelo más estándar sugerido anteriormente. En cambio, la entrada está disponible en forma de función, a la que el cómputo accede realizando consultas. Alternativamente, podemos ver los cómputos en el modelo de consultas como si tuvieran acceso aleatorio a bits (o segmentos de bits) de la entrada.

A menudo nos referimos a que la entrada es proporcionada por un oráculo o caja negra en el contexto del modelo de consultas. Ambos términos sugieren que la descripción completa de la entrada está oculta para el cómputo, y que la única manera de acceder a ella es haciendo preguntas. Es como si consultáramos al Oráculo de Delfos sobre la entrada: ella no nos dirá todo lo que sabe, solo responde preguntas específicas. El término caja negra tiene sentido especialmente cuando pensamos en la entrada como representada por una función; no podemos mirar dentro de la función y entender cómo funciona, solo podemos evaluarla en los argumentos que seleccionemos.

Vamos a trabajar exclusivamente con cadenas binarias en esta lección, en lugar de cadenas con diferentes símbolos, así que escribiremos $\Sigma = \{0,1\}$ de aquí en adelante para referirnos al alfabeto binario por conveniencia. Consideraremos distintos problemas computacionales —con algunos ejemplos sencillos descritos a continuación—, pero en todos ellos la entrada estará representada por una función de la forma

$$f:\Sigma^n \rightarrow \Sigma^m$$

para dos enteros positivos $n$ y $m.$ Naturalmente, podríamos elegir un nombre diferente en lugar de $f,$ pero nos quedaremos con $f$ a lo largo de la lección.

Decir que un cómputo realiza una consulta significa que se selecciona alguna cadena $x \in \Sigma^n,$ y luego la cadena $f(x)\in\Sigma^m$ queda disponible para el cómputo mediante el oráculo. La manera precisa en que esto funciona para los algoritmos cuánticos se discutirá en breve —necesitamos asegurarnos de que sea posible hacerlo con una operación cuántica unitaria que permita hacer consultas en superposición—, pero por ahora podemos pensarlo intuitivamente a alto nivel.

Finalmente, la forma en que mediremos la eficiencia de los algoritmos de consulta es sencilla: contaremos el número de consultas que requieren. Esto está relacionado con el tiempo necesario para realizar un cómputo, pero no es exactamente lo mismo porque ignoramos el tiempo de las operaciones que no son consultas, y también tratamos las consultas como si cada una tuviera costo unitario. Podemos tener en cuenta las operaciones distintas de las consultas si lo deseamos (y a veces se hace), pero restringir nuestra atención solo al número de consultas ayuda a mantener las cosas simples.

Ejemplos de problemas de consulta

Aquí hay algunos ejemplos sencillos de problemas de consulta.

• OR. La función de entrada tiene la forma $f:\Sigma^n \rightarrow \Sigma$ (es decir, $m=1$ para este problema). La tarea es dar como salida $1$ si existe una cadena $x\in\Sigma^n$ para la cual $f(x) = 1,$ y dar como salida $0$ si no existe tal cadena. Si pensamos en la función $f$ como una secuencia de $2^n$ bits a los que tenemos acceso aleatorio, el problema es calcular el OR de estos bits.

• Paridad. La función de entrada también tiene la forma $f:\Sigma^n \rightarrow \Sigma.$ La tarea es determinar si el número de cadenas $x\in\Sigma^n$ para las cuales $f(x) = 1$ es par o impar. Para ser precisos, la salida requerida es $0$ si el conjunto $\{x\in\Sigma^n : f(x) = 1\}$ tiene un número par de elementos, y $1$ si tiene un número impar. Si pensamos en la función $f$ como una secuencia de $2^n$ bits a los que tenemos acceso aleatorio, el problema es calcular la paridad (o el OR exclusivo) de estos bits.

• Mínimo. La función de entrada tiene la forma $f:\Sigma^n \rightarrow \Sigma^m$ para cualesquiera enteros positivos $n$ y $m.$ La salida requerida es la cadena $y \in \{f(x) : x\in\Sigma^n\}$ que aparece primero en el orden lexicográfico (es decir, de diccionario) de $\Sigma^m.$ Si pensamos en la función $f$ como una secuencia de $2^n$ enteros codificados como cadenas de longitud $m$ en notación binaria a los que tenemos acceso aleatorio, el problema es calcular el mínimo de estos enteros.

También consideramos problemas de consulta donde tenemos una promesa sobre la entrada. Lo que esto significa es que se nos da algún tipo de garantía sobre la entrada, y no somos responsables de lo que ocurra cuando esa garantía no se cumple. Otra forma de describir este tipo de problema es decir que algunas funciones de entrada (aquellas para las que no se satisface la promesa) se consideran entradas "sin importar". No se impone ningún requisito a los algoritmos cuando se les dan entradas "sin importar".

Aquí hay un ejemplo de un problema con promesa:

• Búsqueda única. La función de entrada tiene la forma $f:\Sigma^n \rightarrow \Sigma,$ y se nos promete que existe exactamente una cadena $z\in\Sigma^n$ para la cual $f(z) = 1,$ con $f(x) = 0$ para todas las cadenas $x\neq z.$ La tarea es encontrar esta cadena única $z.$

Los cuatro ejemplos que acabamos de describir son naturales, en el sentido de que son fáciles de describir y podemos imaginar una variedad de situaciones o contextos en los que podrían surgir.

En contraste, algunos problemas de consulta no son "naturales" en absoluto. De hecho, en el estudio del modelo de consultas, a veces se plantean problemas muy complejos y sumamente artificiales en los que es difícil imaginar que alguien quisiera resolverlos en la práctica. Sin embargo, ¡esto no significa que los problemas no sean interesantes! Las cosas que al principio pueden parecer artificiales o poco naturales pueden dar pistas inesperadas o inspirar nuevas ideas. El algoritmo cuántico de Shor para la factorización, inspirado en el algoritmo de Simon, es un gran ejemplo. También es una parte importante del estudio del modelo de consultas buscar extremos, que pueden arrojar luz tanto sobre las ventajas potenciales como sobre las limitaciones del cómputo cuántico.

Puertas de consulta

Cuando describimos cómputos con circuitos, las consultas se realizan mediante puertas especiales llamadas puertas de consulta.

La forma más sencilla de definir puertas de consulta para circuitos booleanos clásicos es simplemente permitirles calcular la función de entrada $f$ directamente, como sugiere la siguiente figura.

Cuando se crea un circuito booleano para un problema de consulta, la función de entrada $f$ se accede a través de estas puertas, y el número de consultas que realiza el circuito es simplemente el número de puertas de consulta que aparecen en el circuito. Los cables de entrada del propio circuito booleano se inicializan con valores fijos, que deben considerarse parte del algoritmo (en lugar de ser entradas al problema).

Por ejemplo, aquí hay un circuito booleano con puertas de consulta clásicas que resuelve el problema de paridad descrito anteriormente para una función de la forma $f:\Sigma\rightarrow\Sigma$:

Este algoritmo realiza dos consultas porque hay dos puertas de consulta. Su funcionamiento es el siguiente: la función $f$ se consulta sobre los dos posibles valores de entrada, $0$ y $1,$ y los resultados se introducen en un circuito booleano que calcula el XOR. (Este circuito en particular apareció como ejemplo de circuito booleano en la lección de Circuitos cuánticos del curso Conceptos básicos de información cuántica.)

Para circuitos cuánticos, esta definición de puertas de consulta no funciona, porque estas puertas serían no unitarias para algunas elecciones de la función $f.$ Entonces, lo que hacemos en su lugar es definir puertas de consulta unitarias que operan como sugiere esta figura sobre estados de la base estándar:

Aquí, nuestra suposición es que $x\in\Sigma^n$ e $y\in\Sigma^m$ son cadenas arbitrarias. La notación $y\oplus f(x)$ se refiere al OR exclusivo bit a bit de dos cadenas, que tienen longitud $m$ en este caso. Por ejemplo, $001 \oplus 101 = 100.$

Intuitivamente, lo que hace la puerta $U_f$ (para cualquier función $f$ elegida) es copiar la cadena de entrada superior $x$ y aplicar XOR del valor de la función $f(x)$ sobre la cadena de entrada inferior $y,$ lo cual es una operación unitaria para cualquier elección de la función $f.$ De hecho, es una operación determinista y es su propia inversa. Esto implica que, como matriz, $U_f$ es siempre una matriz de permutación, es decir, una matriz con un único $1$ en cada fila y en cada columna, y con todas las demás entradas siendo $0.$ Aplicar una matriz de permutación a un vector simplemente reordena las entradas del vector (de ahí el término matriz de permutación), y por tanto no cambia la norma euclidiana de ese vector —lo que revela que las matrices de permutación son siempre unitarias.

Cabe destacar que, cuando analizamos los algoritmos de consulta contando simplemente el número de consultas que realiza un algoritmo, ignoramos por completo la dificultad de construir físicamente las puertas de consulta —tanto en las versiones clásicas como en las cuánticas que acabamos de describir. Intuitivamente, la construcción de las puertas de consulta forma parte de la preparación de la entrada, no de encontrar una solución.

Puede parecer poco razonable, pero debemos tener en cuenta que no estamos intentando describir la computación práctica ni dar cuenta de todos los recursos necesarios. Más bien, estamos definiendo un modelo teórico que ayuda a arrojar luz sobre las ventajas potenciales del cómputo cuántico. Tendremos más que decir sobre este punto en la lección siguiente a esta, cuando centremos nuestra atención en un modelo de cómputo más estándar donde las entradas se proporcionan explícitamente a los circuitos como cadenas binarias.