Comprender el algoritmo de optimización de líderes de grupo

Contexto:

He estado tratando de entender el algoritmo genético discutido en el documento Descomposición de matrices unitarias para encontrar circuitos cuánticos: Aplicación a Hamiltonianos moleculares (Daskin y Kais, 2011) (PDF aquí ) y Algoritmo de optimización de líderes de grupo (Daskin y Kais, 2010) . Trataré de resumir lo que entendí hasta ahora y luego formularé mis consultas.

Consideremos el ejemplo de la puerta de Toffoli en la sección III-A en el primer artículo. Sabemos por otras fuentes como esta , que se necesitan alrededor de 5 puertas cuánticas de dos qubits para simular la puerta Toffoli. Por lo tanto, elegimos arbitrariamente un conjunto de puertas como $\{V, Z, S, V^{\dagger}\}$ . Nos restringimos a un máximo de $5$ puertas y nos permitimos usar solo las puertas del conjunto de puertas $\{V, Z, S, V^{\dagger}\}$ . Ahora generamos $25$ grupos de $15$ cadenas aleatorias como:

1 3 2 0,0; 2 3 1 0,0; 3 2 1 0,0; 4 3 2 0,0; 2 1 3 0.0

En la cadena de números anterior, los primeros números en negrita son el número índice de las puertas (es decir, $V = 1, Z = 2, S = 3, Z^{\dagger} = 4$ ), los últimos números son los valores de los ángulos en $[0,2\pi]$ y los enteros medios son los qubits de destino y los qubits de control, respectivamente. Habría otras $374$ cadenas generadas aleatoriamente.

Nuestros grupos ahora se ven así (en la imagen de arriba) con $n=25$ y $p=15$ . La idoneidad de cada cadena es proporcional a la fidelidad de rastreo $\mathcal{F} = \frac{1}{N}|\operatorname{Tr}(U_aU_t^{\dagger})|$donde$U_a$es la representación de matriz unitaria correspondiente a cualquier cadena que generamos y$U_t$es la representación de matriz unitaria de la puerta Toffoli de 3 qubits. El líder del grupo en cualquier grupo es el que tiene el valor máximo de$\mathcal{F}$.

Una vez que tengamos los grupos, seguiremos el algoritmo:

La ecuación (4) mencionado en la imagen es básicamente:

$$\text{new string} [i] = r_1 \times \text{old string}[i] + r_2 \times \text{leader string}[i] + r_3 \times \text{random string}[i]$$ (donde$1 \leq i \leq 20$ ) st$r_1+r_2+r_3 = 1$ . El$[i]$ representa el$i$ ésimo número en la cadena, por ejemplo en1 3 2 0.0; 2 3 1 0.0; 3 2 1 0.0; 4 3 2 0.0; 2 1 3 0.0, el $6$ elemento es 3. En este contexto, tomamos $r_1 = 0.8$ y $r_2,r_3 = 0.2$ . Es decir, en cada iteración, todas las $375$ cadenas se mutan siguiendo la regla: para cada cadena en cada grupo, los elementos individuales (números) en la cadena se modifican siguiendo la ecuación. (4)

Además,

Además de la mutación, en cada iteración para cada grupo de la población, el cruce unidireccional (también denominado transferencia de parámetros) se realiza entre un miembro aleatorio elegido del grupo y un miembro aleatorio de un grupo aleatorio diferente. Esta operación reemplaza principalmente una parte aleatoria de un miembro con la parte equivalente de un miembro aleatorio de un grupo diferente. La cantidad de la operación de transferencia para cada grupo se define por un parámetro llamado velocidad de transferencia, aquí, que se define como

$$\frac{4\times \text{max}_{\text{gates}}}{2} - 1$$ donde el numerador es el número de variables que forman una cadena numérica en la optimización.

Preguntas:

1. $\{V,Z,S,V^{\dagger}\}$$\{X,Z,R_x,R_{zz},V\}$$5$$20$

2. Después de la parte (en "Contexto") que discute la selección del conjunto de puertas y el número de puertas, ¿es correcta mi explicación / comprensión (párrafo 3 en adelante) del algoritmo?

3. $4\times \text{max}_{\text{gates}} - 2$$\text{max}_{\text{gates}}$$5$$20$

4. $0.99$

Sugiero mirar cómo funciona un algoritmo genético en un contexto de variables discretas para entenderlo. Proporcionan una metodología, pero puede aplicar otras técnicas de mutación / cruce.

---

Brevemente, en un problema de optimización simple donde las variables son discretas, podemos resolver heurísticamente con algoritmos genéticos (que pertenecen a los algoritmos evolutivos de clase). Generamos una población de candidatos (aleatoriamente) y cambiamos los candidatos en cada iteración para tratar de encontrar una buena solución que minimice / maximice una función objetivo (llamada aptitud). Puede representar a los candidatos mediante una cadena de valores (llamados cromosomas en general). Si ingresa esta cadena de valores a la función objetivo, está evaluando al candidato o está asignando una aptitud. Las operaciones de cruce / mutación están destinadas a cambiar candidatos y esperan alcanzar nuestro objetivo de una manera relacionada con lo que sucede en genética.

El GLOA es solo otro algoritmo genético pero con la diferencia de tener diferentes grupos de población con un óptimo local (líder como el mejor candidato si lo prefiere) para cada uno y, por supuesto, una estrategia ligeramente diferente para la mutación / cruce. Por lo general, tenemos un grupo de candidatos con un mejor candidato en cada iteración.

Ahora para sus preguntas:

1. Puede elegir el conjunto de puertas que desee (como su ejemplo de conjunto). Esto también es cierto para el número máximo de operaciones de puerta que desea restringir su descomposición. Esos son solo parámetros para el algoritmo. Diría que esto es completamente arbitrario (no tanta lógica necesariamente solo heurística), pero tal vez lo que eligieron estaba más adaptado a su ejemplo o configuración de trabajo. En la práctica, deberías probar muchos parámetros.

2. Estás retomando las explicaciones originales y especialmente el diagrama, así que creo que estás resumiendo bien.

$t$$1$$4 \times \text{max}_{\text{gates}}$$5$$20$$80$

Para su visualización, mire la cadena de ejemplo que da:

1 3 2 0,0; 2 3 1 0,0; 3 2 1 0,0; 4 3 2 0,0; 2 1 3 0.0

$\text{max}_{\text{gates}}$$5$$5$$2$$4$$5 \times 4 = 20$

1 3 2 0.0$V$$3$$2$$0.0$$V$

4. Esto también es arbitrario dependiendo de lo que quieras. Puede ser un número fijo de iteraciones, o hasta que alcance un umbral / criterio de convergencia.