A quantum genetic algorithm with quantum crossover and mutation operations

Abstract

In the context of evolutionary quantum computing in the literal meaning, a quantum crossover operation has not been introduced so far. Here, we introduce a novel quantum genetic algorithm that has a quantum crossover procedure performing crossovers among all chromosomes in parallel for each generation. A complexity analysis shows that a quadratic speedup is achieved over its classical counterpart in the dominant factor of the run time to handle each generation.

Appendix: An example of constructing the pseudo-randomizer \(R\)

In this appendix, we show an example to construct the pseudo-randomizer $R$ used in Algorithms 2, 3, and 4. It should map a $c$-bit string to a pseudo-random $n$-bit string except for $0_0\cdots 0_{c-1}$ that is mapped to $0_0\cdots 0_{n-1}$. Its internal circuit complexity should be $\mathrm{poly}(cn)$. As we use a quantum circuit to realize it in Algorithm 2, it is desirable to employ a circuit structure that is originally unitary.

Consider inputs $a\in \{0,1\}^c$. We design a circuit that maps $a_0\cdots a_{c-1}0_0\cdots 0_{n-1}$ to $a_0\cdots a_{c-1}\kappa _0\cdots \kappa _{n-1}$ with $\kappa =R(a)$, an $n$-bit pseudo-random number (here, $a_0\cdots a_{c-1}$ and $\kappa _0\cdots \kappa _{n-1}$ are the binary representations of $a$ and $\kappa$). By the definition of $R$, the circuit preserves $0_0\cdots 0_{c-1}0_0\cdots 0_{n-1}$. This circuit is generated by function gen_r_circ() described in Fig. 9. As is clear from the description, the circuit output from this function can be directly used as a quantum circuit. Using the circuit $C=$ gen_r_circ(), we have $|a\rangle |0\rangle \overset{C}{\mapsto }|a\rangle |R(a)\rangle$  $\forall a\in \{0,1\}^c$. The circuit complexity of $C$ is $O(cn)$ because, for each $i$, at most $n$ CNOT gates are used to decompose the gate output from step (2). In addition, gen_r_circ() spends $O(c\;\mathrm{poly}(n))$ time when a common random number generator [21, 31] is used in step (1).

Fig. 9

Description of function gen_r_circ()

Note that the function gen_r_circ() is called only once for each $t$, in the beginning of step 1 in Algorithms 2, 3, and 4. We have only to reuse the circuit $C$ for the use of the pseudo-randomizer until $t$ is incremented.

It is expected that outputs from the circuit $C$ possess good uniformity if we use a good random number generator in step (1) of gen_r_circ() for generating $C$. Let us write $\gamma$ as $\gamma (i)$ to emphasize its dependence on $i$. For a nonzero input $a_0\cdots a_{c-1}$, the $k$th bit of the output $R(a)$ is $\sum _{i=0}^{c-1}a_i\cdot \gamma _k(i)~~\mathrm{mod}~2$. This indicates that, for two different inputs $a$ and $a'$, the $k$th bits of $R(a)$ and $R(a')$ differ with probability $1/2$ in the ideal case where $\gamma (i)$’s are generated from a true random number generator. This is because $a$ and $a'$ differ by at least a single bit. It also indicates that two different bits, the $k$th and the $k'$th bits, of $R(a)$ for a nonzero input $a$ differ with the probability $1/2$ in the ideal case. This is because $\gamma _k(i)$ and $\gamma _{k'}(i)$ differ with the probability $1/2$.

Now we show the result of our numerical test of $C$. We tried statistical tests of randomness [21, 39] to test pseudo-random numbers output from $C$, using NIST’s Statistical Test Suite (STS) (version 2.1.1) [39]. We set $c=10$ and $n=32$. Mersenne Twister (MT) (version mt19937ar) [31] was used to generate $\gamma$ in step (1) of gen_r_circ(). We used the seed value 121,212 and did not reset MT during the circuit generation. The circuit $C$ output from gen_r_circ(), of course, consisted of $10$ outputs from step (2). For this $C$, we used the inputs $a\in \{0,1\}^c\backslash \{0_0\cdots 0_{c-1}\}$ from smaller to larger and obtained corresponding outputs $R(a)$ by numerical computation. We obtained $\hbox {1,023}\times 32$ bits in total in the outputs, since $2^{10}-1=1023$. We regarded them as a serial bit string from left to right and used STS in its default setting to test the string. In the execution of STS, we used $25$ binary sequences with length 1,200 as samples from the string. The following tests were tried with the default parameter values in STS: the Frequency Test, the Block Frequency Test, the Cumulative Sums Test, the Runs Test, the Longest-Run-of-Ones Test, the Binary Matrix Rank Test, the Spectral DFT Test, and the Serial Test. The string passed the tests except for the Binary Matrix Rank Test. It should be noted that the input length was too small for the binary matrix rank test [39]. In addition, randomness is not very strictly required for the use in evolutionary computing. Therefore, considering the tests that the string passed, we may claim that gen_r_circ() generates a usable pseudo-randomizer circuit for our algorithm.

We conducted another test: We generated ten circuits by calling gen_r_circ() ten times without resetting MT, using the seed value 676,767. For each circuit, we performed the same process as above to obtain the serial bit string. We obtained ten serial bit strings in total and tested the concatenated string using STS. As samples input to STS, we used $25$ binary sequences with length 12,000. The concatenated string passed the tests except for the Binary Matrix Rank Test and the Spectral DFT Test. It was unexpected that it did not pass the spectral DFT test. It requires a further investigation to reveal the reason of this phenomenon.

The results of the first and the second tests are summarized in Table 1. In summary for this appendix, we found that a pseudo-randomizer circuit whose outputs possess enough randomness for the use in evolutionary computing can be generated by the function gen_r_circ(). It is hoped that the function will be improved so as to achieve better randomness for the sake of general use.

Table 1 List of test results for the first and the second tests we performed (see the text for the details of the tests)