# Evolving a quantum circuit using a genetic algorithm

I've written a small quantum circuit simulator in python, so now I'm trying to evolve some circuits via genetic algorithms. My encoding is very simple, it's just a rectangular table of strings representing the gates. Here's a example of a random circuit:

+--------+--------+--------+-------+--------+-------+
| qubit  | col_0  | col_1  | col_2 | col_3  | col_4 |
+--------+--------+--------+-------+--------+-------+
| q0-->  |   I    | CNOT_2 |   S   |   Z    |   H   |
| q1-->  | CNOT_0 |   T    |   S   |   I    |   T   |
| q2-->  |   S    |   I    |   S   | CNOT_1 |   S   |
+--------+--------+--------+-------+--------+-------+


My first attempt is to generate the Toffoli gate, which input/output I encoded as follows:

inputs = [[0, 0, 0], [0, 1, 0], [1, 0, 0], [1, 1, 0]]
output_zero_probs = [[1, 1, 1], [1, 0, 1], [0, 1, 1], [0, 0, 0]]


So there are 4 input tests, and for each one there is the correspondent output. The variable output_zero_probs is the probability of measuring 0 for each wire for each input. Note that the last qubit holds the answer.

So for example, if the input is [1, 1, 0], the output should be [1, 1, 1], which correspondes to output_zero_probs of [0, 0, 0].

The fitness functions is just some measure of similarity between the circuit output and the expected output probabilities. The circuit dimension was fixed to 3 x 17, ie, 3 qubits x 17 columns. The mutation operator just changes a random cell, and the crossover operator exchanges an entire 'column' between 2 circuits.

So far it was not able to find the correct solution, it seems to evolve a bit, then it get stuck. Is this a feasible problem for a GA? If so, how can I improve on this? I mean, how can I 'push' the circuit to the right direction?

EDIT:

Now I think it's better to compare the final state of the system with the expected final state, instead of using probabilities, because these may change depending on the measures (I'm not sure if this reasoning is correct).

Follow up question: Genetic algorithm does not converge to exact solution

So in your example, you try to find the quantum circuit representing the Toffoli operation. I would then change my objective/fitness function and compare the unitary matrix representing the operation. You can use an minimization objective like : $$\mathcal{F} = 1-\frac{1}{2^n} |\operatorname{Tr}(U_aU_t^{\dagger})|$$
with $$U_a$$ is the unitary of the generated solution and $$U_t$$ the unitary you are trying to get. The trace part of this objective means try to get $$U_aU_t^{\dagger}$$ to the identity matrix on $$n$$ qubits.