Understanding the Group Leaders Optimization Algorithm

Question

Context:

I have been trying to understand the genetic algorithm discussed in the paper Decomposition of unitary matrices for finding quantum circuits: Application to molecular Hamiltonians (Daskin & Kais, 2011) (PDF here) and Group Leaders Optimization Algorithm (Daskin & Kais, 2010). I'll try to summarize what I understood so far, and then state my queries.

Let's consider the example of the Toffoli gate in section III-A in the first paper. We know from other sources such as this, that around 5 two-qubit quantum gates are needed to simulate the Toffoli gate. So we arbitrarily choose a set of gates like $\{V, Z, S, V^{\dagger}\}$. We restrict ourselves to a maximum of $5$ gates and allow ourselves to only use the gates from the gate set $\{V, Z, S, V^{\dagger}\}$. Now we generate $25$ groups of $15$ random strings like:

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

In the above string of numbers, the first numbers in bold are the index number of the gates (i.e. $V = 1, Z = 2, S = 3, Z^{\dagger} = 4$), the last numbers are the values of the angles in $[0,2\pi]$ and the middle integers are the target qubit and the control qubits respectively. There would be $374$ such other randomly generated strings.

Our groups now look like this (in the image above) with $n=25$ and $p=15$. The fitness of each string is proportional the trace fidelity $\mathcal{F} = \frac{1}{N}|\operatorname{Tr}(U_aU_t^{\dagger})|$ where $U_a$ is the unitary matrix representation corresponding to any string we generate and $U_t$ is the unitary matrix representation of the 3-qubit Toffoli gate. The group leader in any group is the one having the maximum value of $\mathcal{F}$.

Once we have the groups we'll follow the algorithm:

The Eq. (4) mentioned in the image is basically:

$$\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]$$ (where $1 \leq i \leq 20$) s.t. $r_1+r_2+r_3 = 1$. The $[i]$ represents the $i$ th number in the string, for example in 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, the $6$-th element is 3. In this context, we take $r_1 = 0.8$ and $r_2,r_3 = 0.2$. That is, in each iteration, all the $375$ strings get mutated following the rule: for each string in each group, the individual elements (numbers) in the string gets modified following the Eq. (4).

Moreover,

In addition to the mutation, in each iteration for each group of the population one-way-crossover (also called the parameter transfer) is done between a chosen random member from the group and a random member from a different random group. This operation is mainly replacing some random part of a member with the equivalent part of a random member from a different group. The amount of the transfer operation for each group is defined by a parameter called transfer rate, here, which is defined as $$\frac{4\times \text{max}_{\text{gates}}}{2} - 1$$ where the numerator is the number of variables forming a numeric string in the optimization.

Questions:

1. When we are applying this algorithm to find the decomposition of a random gate, how do we know the number and type of elementary gates we need to take in our gate set? In the example above they took $\{V,Z,S,V^{\dagger}\}$. But I suspect that that choice was not completely arbitrary (?) Or could we have chosen something random like $\{X,Z,R_x,R_{zz},V\}$ too? Also, the fact that they used only $5$ gates in total, isn't arbitrary either (?) So, could someone explain the logical reasoning we need to follow when choosing the gates for our gate set and choosing the number of gates to use in total? (It is mentioned in the papers that the maximum possible value of the number of gates is restricted to $20$ in this algorithm)

2. After the part (in "Context") discussing the selection of the gate set and number of gates,is my explanation/understanding (paragraph 3 onwards) of the algorithm correct?

3. I didn't quite understand the meaning of "parameter transfer rate". They say that $4\times \text{max}_{\text{gates}} - 2$ is the number of variables forming a numeric string in the optimization. What is $\text{max}_{\text{gates}}$ in this context: $5$ or $20$? Also, what exactly do they mean by the portion I italicized (number of variables forming a numeric string in the optimization) ?

4. How do we know when to terminate the program? Do we terminate it when any one of the group leaders cross a desired value of trace fidelity (say $0.99$)?

Answer 1

I suggest looking at how a genetic algorithm works in a context of discrete variables to understand it. They provide a methodology but you can apply other mutation/crossover techniques.

---

Briefly, in a simple optimization problem where the variables are discrete, we can solve heuristically with genetic algorithms (which belongs to the class evolutionary algorithms). We generate a population of candidates (randomly) and we change the candidates at each iteration to try to find a good solution minimizing/maximizing an objective function (called fitness). You can represent the candidates by a string of values (called chromosomes in general). If you input this string of values to the objective function, you are evaluating the candidate or you assigning a fitness. Crossover/mutation operations are meant to change candidates and hope for achieving our objective in a way related to what happens in genetic.

The GLOA is just another genetic algorithms but with the difference of having different groups of population with a local optimum (leader as best candidate if you prefer) for each and of course a slightly different strategy for mutation/crossover. Usually, we have one group of candidates with one best candidate at each iteration.

Now for your questions:

1. You can choose whatever set of gates you want (like your example of a set). This is also true for the maximum number of gate operations you want to restrict your decomposition. Those are just parameters for the algorithm. I would say this is completely arbitrary (not so much logic necessarily just heuristic) but maybe what they chose was more adapted to their example or setup of work. In practice, you would have to try many parameters.

2. You are kinda retaking the original explanations and especially the diagram so I think you are summing up well.

3. I suggest looking at Figure 2 which shows the pseudo-code of this part to understand it. This is similar to one-way crossover in genetic algorithms. If you look at their original algorithm (GLOA, 2010), they choose a number $t$ between $1$ and half of the number of total parameters (variables) plus one. In this case, the number of parameters/variables is the length of a string which is $4 \times \text{max}_{\text{gates}}$. For the Toffoli gate, it was $5$. For other examples, it could have been more. But in general, they recommend $20$ as a good maximum (you can imagine how hard the optimization is with strings of more than $80$ variables on a simple computer).

For your visualization, look at the example string you give :

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

Here, a string represents a set of operations forming a circuit. We associate with it a fitness, which is related to the fidelity. It is like a candidate solution for our optimization problem. In that case, our $\text{max}_{\text{gates}}$ is $5$ because you see $5$ operations represented. Each operation is a gate of the set, the $2$ qubits it applies to and the angle if necessary, that is $4$ variables. In total, $5 \times 4 = 20$ variables for the problem.

1 3 2 0.0, in this case, means apply the $V$ gate on qubit $3$ controlled by qubit $2$ with an angle $0.0$ (note that with the $V$ gate there is no angle but say you were playing with like rotation gates, this becomes relevant).

4. This is also arbitrary depending on what you want. It can be a fixed number of iterations, or until you reach a threshold/convergence criteria.