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?

Thanks for your attention!


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


1 Answer 1


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.

Also, when using a genetic algorithm, many strategies can be tried, and may generate better solutions than others. You can look at this question where a genetic algorithm is used for circuit decomposition.

  • $\begingroup$ Thanks. Is there any difference between using the unitary x final state superposition as a target? Or they are equivalent? (see my edit note) $\endgroup$
    – Fernando
    Mar 26, 2019 at 20:13
  • $\begingroup$ @Fernando They would be equivalent but the unitary takes into account all possible states one would apply the operation. So it is better to specify the unitary than trying all computational basis states. $\endgroup$
    – cnada
    Mar 27, 2019 at 7:18
  • $\begingroup$ I'm trying this and reading some papers, it's not converging to the exact solution for the Toffoli target. I'm wondering what I'm missing, because these papers seem to converge very fast. $\endgroup$
    – Fernando
    Apr 1, 2019 at 0:20
  • $\begingroup$ Are you using the same evolution strategy? $\endgroup$
    – cnada
    Apr 1, 2019 at 6:27
  • $\begingroup$ No, that's my next plan. I'm using a vanilla GA with elitism. I also tried various selection schemas and combinations of crossover/mutations, without success so far. It gets to 0.85 very fast, but then it stops improving. This is very weird, in the Daskin paper the conversion to the Toffoli unitary is very fast. $\endgroup$
    – Fernando
    Apr 1, 2019 at 7:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.