Cuando hablamos de computación cuántica es fácil caer en ejemplos demasiado artificiales. Podemos hablar de superposición, entrelazamiento, qubits e interferencia, pero queda una pregunta bastante más interesante: ¿Cómo se programa realmente un algoritmo cuántico?
Para verlo, vamos a resolver un problema muy sencillo de dos maneras:
Tenemos una colección de elementos y queremos encontrar uno que cumple una determinada condición.
Primero lo hacemos de la manera clásica, con C#. Después veremos cómo abordar el mismo problema con Q# utilizando el algoritmo de Grover.
Supongamos que tenemos:
int[] values = { 3, 8, 12, 17, 21, 42, 55, 61 };
y queremos encontrar el 42.
La solución más sencilla es una búsqueda lineal:
int Search(int[] values, int target)
{
for (int i = 0; i < values.Length; i++)
{
if (values[i] == target)
return i;
}
return -1;
}
No hay ningún misterio.
El algoritmo va recorriendo los elementos:
3 → no
8 → no
12 → no
17 → no
21 → no
42 → sí
En el peor caso tendremos que consultar todos los elementos.
Para una colección de N elementos, esto requiere:
O(N)
consultas.
Acá aparece una diferencia fundamental.
No podemos simplemente escribir:
for cada qubit
buscar()
y esperar que la computadora cuántica haga lo mismo más rápido.
La programación cuántica utiliza otro modelo.
Uno de los algoritmos más conocidos para búsquedas no estructuradas es Grover's algorithm.
Su idea fundamental es utilizar:
- superposición
- un oráculo cuántico
- interferencia
- amplificación de amplitud
- medición
para aumentar la probabilidad de obtener la respuesta que estamos buscando.
La cantidad de consultas necesarias pasa de: O(N)
a aproximadamente: O(√N)
Para utilizar Grover tenemos que formular la búsqueda de otra manera.
En lugar de preguntarnos: ¿Es este elemento igual a 42?
con cada elemento individualmente, definimos una función que identifica la solución.
Por ejemplo:
f(x) = 1 si x es la solución
f(x) = 0 en otro caso
Esta función se implementa como un oráculo cuántico.
Conceptualmente:
┌─────────────┐
x ─────►│ ORACLE │─────► marca x
└─────────────┘
El oráculo no nos devuelve directamente la solución.
Lo que hace es marcarla.
Y después Grover utiliza interferencia para aumentar su amplitud.
Primero necesitamos una superposición
Supongamos que tenemos 8 posibilidades:
000
001
010
011
100
101
110
111
Con tres qubits podemos representar esas ocho posibilidades.
Inicialmente tenemos un estado:
|000>
Aplicando una compuerta Hadamard a cada qubit obtenemos una superposición de todos ellos:
|000> + |001> + |010> + |011>
+ |100> + |101> + |110> + |111>
No significa que tengamos ocho computadoras ejecutándose independientemente.
Significa que nuestro estado cuántico es una combinación de esas posibilidades.
El oracle. Ahora necesitamos marcar nuestra solución.
Supongamos que queremos encontrar: 101
El oracle modifica la fase asociada a ese estado.
Conceptualmente:
000 +
001 +
010 +
011 +
100 +
101 -
110 +
111 +
La solución no apareció mágicamente.
Simplemente fue marcada mediante su fase.
Y esto es importante porque todavía no podemos medir y decir: ¡101!
Si medimos ahora, seguimos teniendo una probabilidad distribuida entre los estados.
Grover aplica una operación llamada difusión o inversión sobre la media.
Su objetivo es modificar las amplitudes de los estados.
Después de una iteración:
solución ↑↑↑
otros estados ↓
La amplitud de la solución aumenta mientras las amplitudes de los estados incorrectos disminuyen.
Repetimos este proceso aproximadamente: π/4 × √N veces.
Finalmente medimos.
La probabilidad de obtener la solución es mucho mayor.
¿Y dónde está Q#?
Ahora viene la parte que más nos interesa.
Q# no intenta esconder que estamos trabajando con un modelo diferente.
Un programa cuántico puede trabajar con Qubit: use qs = Qubit[3];
Tenemos tres qubits.
Podemos ponerlos en superposición:
ApplyToEach(H, qs);
H es la compuerta Hadamard.
Después podemos aplicar nuestro oracle y la operación de difusión.
Una versión conceptual de Grover puede verse así:
operation Grover(qs : Qubit[]) : Unit {
ApplyToEach(H, qs);
// Oracle
Oracle(qs);
// Difusión
Diffusion(qs);
}
En una implementación real necesitamos definir cuidadosamente el oracle y la difusión, pero la estructura fundamental ya está ahí:
superposición
↓
oracle
↓
difusión
↓
medir
Comparemos las dos soluciones.
En C# escribimos:
for (int i = 0; i < values.Length; i++)
{
if (values[i] == target)
return i;
}
El programa piensa en términos de:
elemento
elemento
elemento
elemento
...
Es una búsqueda secuencial.
En Q# pensamos en:
qubits
↓
superposición
↓
oracle
↓
interferencia
↓
medición
No estamos escribiendo una versión más complicada del mismo for.
Estamos utilizando un modelo computacional diferente.
Sería muy fácil concluir: Entonces una computadora cuántica puede buscar en una lista de un millón de elementos en √1.000.000 = 1.000 pasos.
No es tan sencillo.
Grover proporciona una ventaja en el número de consultas al oracle.
Eso no significa que toda la aplicación se ejecute en O(√N).
Tenemos que:
- preparar el estado cuántico;
- construir el oracle;
- ejecutar las operaciones cuánticas;
- repetir Grover el número adecuado de veces;
- realizar la medición.
Además, las computadoras cuánticas reales tienen limitaciones físicas y de hardware.
Por eso es más correcto decir: Grover reduce el número de consultas necesarias para una búsqueda no estructurada de O(N) a O(√N).
No significa que cualquier programa de búsqueda pueda reemplazarse automáticamente por Grover.
Lo interesante de Q# no es simplemente que tenga un tipo llamado Qubit.
Lo interesante es que el lenguaje permite expresar conceptos que no aparecen en un lenguaje clásico tradicional:
- Qubit
- Hadamard
- superposición
- medición
- operaciones unitarias
- oracle
Y eso cambia la forma en que pensamos el algoritmo.
En C# pensamos:
datos → operaciones → resultado
En Q# podemos pensar:
estado cuántico
↓
transformación
↓
interferencia
↓
medición
↓
resultado
No podemos decir simplemente eso.
Estamos comparando dos modelos de computación diferentes.
Para nuestra búsqueda:
Clásico: O(N)
frente a Grover: O(√N) consultas al oracle
Pero para aprovechar esa ventaja necesitamos una computadora cuántica y un problema que pueda expresarse adecuadamente mediante un oracle.
Además, si los datos están almacenados en una memoria clásica y tenemos que cargarlos en la computadora cuántica, esa carga también forma parte del problema.
Lo verdaderamente interesante
Quizás la parte más interesante de este ejemplo no sea que:
O(N) → O(√N)
sino por qué es posible hacerlo.
Una computadora clásica trabaja con bits:
0
1
Una computadora cuántica trabaja con qubits, que pueden encontrarse en superposición:
α|0> + β|1>
y las operaciones cuánticas pueden modificar las amplitudes de esos estados.
Grover aprovecha precisamente esto.
No estamos ejecutando un for` más rápido.
Estamos diseñando un algoritmo alrededor de las propiedades de la mecánica cuántica.
Y acá aparece una cuestión interesante para los lenguajes de programación.
En C# podemos abstraernos completamente del hardware:
int result = Search(values, 42);
En Q#, en cambio, muchas de las abstracciones del lenguaje están relacionadas directamente con el modelo cuántico:
use qs = Qubit[3];
ApplyToEach(H, qs);
Oracle(qs);
Diffusion(qs);
El programador tiene que pensar en:
¿Qué estado tengo?
¿Qué transformación estoy aplicando?
¿Qué amplitudes quiero aumentar?
¿Qué amplitudes quiero cancelar?
¿Cuándo puedo medir?
Es decir, el paradigma de programación cambia.
Grover es un buen ejemplo para entender que la computación cuántica no consiste simplemente en ejecutar programas clásicos más rápido.
Tenemos el mismo problema: encontrar un elemento que cumple una condición.
Pero utilizamos dos modelos diferentes.
En el modelo clásico:
buscar
↓
comparar
↓
buscar
↓
comparar
↓
...
En el modelo cuántico:
superposición
↓
oracle
↓
interferencia
↓
amplificación
↓
medición
Y ahí está, quizás, la diferencia más importante entre programar para una computadora clásica y programar para una computadora cuántica: No se trata solamente de aprender nuevas instrucciones. Hay que aprender a pensar en términos de estados cuánticos y transformaciones sobre esos estados.
.jpeg)
.jpeg)
